Why is Poly1305 popular given its 'sudden death' properties? ECDSA has the undesirable property that if a key pair reuses a nonce in a signing operation, the cryptosystem experiences catastrophic failure in the form of private key leakage. I've heard this referred to as "sudden death" cryptography. Of course the PS3 misuse of ECDSA is probably the most widely publicised incident.

One advantage of DJB-advocated cryptosystems like Ed25519 is that they lack this weakness. The Ed25519 website states that "hash function collisions do not break this system."

A perfect implementation of ECDSA will be problem free, but since implementation flaws are inevitable, it seems preferable to use cryptography without huge exposed sharp edges.

This being the case, I am puzzled by the DJB's and other's advocacy for an authentication function that exhibits "sudden death" in the event of inadvertent nonce reuse.

Is the use of Poly1305 really informed only by performance? If so, why is this so crucial? The widespread use of e.g. HMAC suggests that MAC computation costs are tenable as they are and without pressing issue. I don't understand why Poly1305 is receiving such preference when it seems so dangerous. Can someone explain this?

At least in the case of NaCl, Poly1305's "sudden death" properties aren't much worse than XSalsa20's. With any stream cipher, if you reuse the same stream with two messages, then the XOR of the ciphertexts gives you the XOR of the plaintexts. So your security is already ruined by nonce reuse, whether or not you rely on Poly1305.


WPA/WPA2 Handshake -- Why are Nonces not encrypted? During the WPA/WPA2 handshake, the client and AP compute a 256-bit Pre-shared Master Key (PMK) before exchanging Nonces that are used to compute the eventual key. Given that the hosts already have a shared key (the PMK); why dont they use it to encrypt the Nonces? The attacker exploits these nonces to do a dictionary attack -- it seems like the attack would be much more difficult if the nonces were encrypted.

Unfortunately, that wouldn't really achieve much. To see why, let's first recall the steps of the common dictionary attack on WPA/WPA2-PSK.

In WPA/WPA2-PSK, the key hierarchy goes like this:

password - this is the fundamental secret in the entire protocol, and all other keys are ultimately derived from this. Thus, the security of the protocol essentially boils down to the secrecy of this value.
PMK = PSK = PBKDF2(password, SSID, SSID-length, 4096, 256).
PTK = PRF(PMK, "pairwise key expansion", MAC1 || MAC2 || Nonce1 || Nonce2). The exact PRF that is used here is not important, but it is based on HMAC-SHA1.

Notice that as an attacker, if you know the password, then you have all the information you need to first derive the PMK (since everything else that goes into the PBKDF2 function is public), and then the PTK (since the MACs and the nonces are public). This, then, leads to the well-known dictionary attack: make a guess on the password, derive from this guess the PMK and PTK, then use the PTK on some of the captured data to verify your guess (e.g. by recomputing one of the message-authentication codes of the 4WHS). If the verification didn't check out, try another guess on the password.

Now, with your suggestion, the nonces wouldn't immediately be observable in the clear. However, this would only change the above attack slightly: again the attacker makes a guess on the password and derives the PMK as before. However, now it cannot immediately continue to derive the PTK, since it doesn't have the nonces. But this is not a problem, because the encryption of the nonces only depends on the PMK, which it now has a guess for. Thus, using this guessed PMK, it simply decrypts the encrypted nonces, and continues the attack as before, deriving the PTK and verifying the guess on the captured data. If the guess of the password was correct, then the attacker will obtain all the correct data and the final verification will check out. While if the guess was wrong, the final verification will most certainly fail.

Thus, the attack is more or less the same, just with one added step requiring the decryption of the nonces. Moreover, the only computationally intensive calculation being done here is the evaluation of the PBKDF2 function. The time needed for the extra decryption of the nonces dwarfs in comparison to this.


How are SHACAL-2 ciphers calculated? I am trying to learn about the underlying functionality of the different hash functions (currently SHA) and I'm pretty stuck even after watching a Stanford video about it.
One method of hashing is by using Merkel-Damgård construction with the David Meyers function and SHACAL-2 block ciphers.
As far as I understand MD is the message divided into a chain of 64-bit blocks containing the previous block value or IV (initial vector defined by the hash function or a custom salt key). The block value or IV along with the current block value and some x bit key is after going through the SHACAL-2 function then the new cipher.
Is this correct understood? If it is:
What happens inside the SHACAL function? What is math?
I found this but it doesn't really answer my question:
SHACAL in SHA-256

The MD construction uses a compression function $C$ ($F$ in the figures) such that it has two inputs.
$$h_i = C(h_{i-1},m_i)$$

and the first $h_{-1} = IV$ and the last $H = h_{2^k-1}$ is the hash  value.

The compression function can use a block cipher, where the message to the block cipher is the previous hash value and the key is the message. $h_i = E_{m}(h_{i-1})$
The first description of using a block cipher for compression function exists in Merkle's thesis on page 11. This construction is totally insecure since the existent block cipher directly chained and it can be shown that it has $\mathcal{O}(2^{n/2})$ second-preimage resistance instead of $\mathcal{O}(2^{n})$.
We don't want related key attacks as exist in some of the block-ciphers like AES and DES. This doesn't create a problem for encryption since the keys are chosen uniform randomly, however, the related keys can be used to attack the hash function. This is discussed extensively by Mannik and Preenel
We want large inputs due to the collision attacks on the compression functions [1] and therefore more rounds to process. So designers create a new block cipher for MD constructions instead of using existing ones. For SHA-1 it is called SHACAL and for SHA-2 it is called SHACAL-2.
The dividing value depends on the compression function, MD5, SHA-1, and SHA256 uses 512-bit message blocks, SHA512 is using 1024-bit message blocks. The messages are padded to be multiple of the block size with the message size is encoded at the end.
For example SHA-512 padding on NIST FIPS 180-4

Suppose that the length of the message, $M$, is $\ell$
bits.  Append the bit 1 to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation
$$\ell + 1 + k \equiv  896 \bmod 1024$$ Then append the 128-bit block that is equal to the number $\ell$ expressed using a binary representation

Formalize for arbitrary block size $b$ and $d$-bit encoded message size ( 64 for SHA-1 and SHA256, 128 for SHA512.
$$\ell + 1 + k \equiv  b-d \bmod b$$
So the design criteria are having a block cipher with many rounds, SHACAL has 80, SHA-256 has 64, and SHA512 has 80 rounds while keeping the round function simple.
And the block cipher is used as Davies–Meyer to create a one-way compression function.
For example, the math for SHA256 is

$\operatorname{Ch}(E,F,G) = (E \land F) \oplus (\neg E \land G)$
$\operatorname{Ma}(A,B,C) = (A \land B) \oplus (A \land C) \oplus (B \land C)$
$\Sigma_0(A) = (A\!\ggg\!2) \oplus (A\!\ggg\!13) \oplus (A\!\ggg\!22)$
$\Sigma_1(E) = (E\!\ggg\!6) \oplus (E\!\ggg\!11) \oplus (E\!\ggg\!25)$

The bitwise rotation uses different constants for SHA-512. The given numbers are for SHA-256.
The red $\boxplus$ mean $ c = a + b \mod 2^{32}$, i.e. modulo addition.
As we can see, simple operations that CPUs can handle, light round function, with a little degraded unbalanced Feistel structure.
And we learned from the Tiny Encryption algorithm that, even simple rounds can be secure after 32 rounds.


What is a block cipher? I have read about block ciphers, but I do not understand the topic completely.

Is a block cipher a way to send data or a way to encrypt data?

How is the data divided into multiply blocks before it is sent? Is the data partitioned before the encryption process or afterwards?

How long are the blocks? Can I choose any block size?

A block cipher is any cipher that works(encrypts, decrypts) on data in blocks (more than just one bit or one byte). A stream cipher is a cipher that works on the data one bit or byte at a time.

For example, DES is a block cipher because it works on the data in 64 bit chunks. This means that when you want to encrypt something with DES, you must first break it into 64 bit chunks, and encrypt each chunk with DES. Same with decryption.

An example of a stream cipher is RC4. If you want to encrypt using RC4, you need to encrypt each byte individually. There is no need to create chunks of that data, because RC4 works on the data one bit at a time.

You cannot choose a blocksize, because it's generally dictated by the algorithm you choose. How you send the data is not related to how you encrypt the data. That means a block cipher only says that you need to encrypt in a block, but says nothing about how you should transmit the data.


Is there a message size limit with elliptic-curve-based public-key encryption? There's a lot of discussion and answers regarding RSA's limits when it comes to the size of the plaintext, but I couldn't find anything similar when talking about ECC.

Is there a limit? If so, why and what is it?

Is there a limit?

Depends on what ECC encryption algorithm you're talking about.  ECC really means 'lets use elliptic curves to do cryptography', there are several ways to do that to do public key encryption.

If you use EC-ElGamal (which is just ElGamal translated to use Elliptic Curves), you're pretty much limited to the group size; you're encoding a EC point, and so you're limited to the number of EC points there are.

On the other hand, if you're using ECIES, there is no effective limit.  That's because you're not really encrypting the message with the curve itself; instead, you're using ECC to transport a one-use symmetric key, and then using that symmetric key to encrypt the message (and so the only size limitation would be the limit of whatever the symmetric algorithm you're using has).


How to check the integrity of a key received through mail using symmetric encryption? I would like to provide access to encrypted data through a cloud service provider, using a pay-as-you-go model. This means that we will sometimes need to revoke a user's access to the data. To restrict a revoked user's access, the CSP will re-encrypt the data and send the new key to valid users only through their mail.

Before using the new key they received by mail, however, the users will presumably need some way to verify its integrity and authenticity. If possible, I would like to implement this using only symmetric encryption (like AES) instead of asymmetric encryption like RSA. Is this possible, and if so, how?

Unfortunately, symmetric encryption do not provide integrity and digital signature functions. This is because symmetric encryption uses the same key for exncryption and decryption. This means that any who owns the decryption key can alter the data and no one will notice that the data is altered, because the same key was used for encryption.

This means that data integrity can be provided only by using asymmetric cryptography.


Does Identity-Based Encryption actually solve any problem? Identity-based encryption schemes[*] seem to have great potential in high-latency, delay-tolerant and mobile, ad-hoc networks since they apparently seem to avoid the need for key negotiation and exchanges. Used solely for key exchange, they allow any pair of members in the same group (however you choose to define it) to establish a unique pairwise secret that can be computed by each member up-front and as a function of their respective identities.
However, since each pairing based scheme - that I'm aware of - is predicated on a pre-distribution of some shared secret (e.g., the hashed ID of the agent raised to some secret integer), do any of these schemes offer any significant advantages over, let's say, a simple authenticated Diffie-Hellman (at least for purposes of symmetric key establishment)?
[*] Including pairing-based symmetric-key establishment schemes.

IBE is advantageous over standard asymmetric methods in one aspect, and that doesn't appear to apply in the case you're interested in.

In both cases, IBE and asymmetric methods require an enrollment process (whether to distribute secrets, or authentication data), so there's no real difference there.

However, when Alice wants to send a message to Bob, with standard asymmetric cryptography, Alice and Bob needs to exchange messages (whether to perform a DH exchange, or for Bob to send Alice his certificate).  In contrast, with IBE, Alice just encrypts the message with Bob's public id, and sends that message to Bob; Bob doesn't need to send a message to Alice.

So, that is the advantage of IBE; if you are sending unidirectional messages, you don't need a back channel to complete the exchange.  If this is important for you (for example, if you are sending encrypted emails; the store-and-forward email architecture doesn't allow a back channel), this is quite useful.  If you do have a convenient back channel (as in your case; you're going to exchange messages encrypted with a symmetric key anyways), it doesn't gain you anything.


zk-SNARKs vs. Zk-STARKs vs. Bulletproofs: definitions I have become quite familiar with Bulletproofs the last few months. Bulletproofs is the name given to a zero-knowledge proof system for arithmetic circuits, by Benedikt Bünz et al. It is a specific protocol with specific properties.

When Bulletproofs are discussed, they are often contrasted with zk-SNARKs and zk-STARKs. See, for instance, this question on the Ethereum StackExchange, where they discuss properties of Bulletproofs and compare them among zk-SNARKS and zk-STARKs.

A zk-SNARK is a zero-knowledge succinct non-interactive argument of knowledge. A zk-STARK is a "scalable transparent argument of knowledge", according to Eli Ben-Sasson's "Scalable, transparent, and post-quantum secure computational integrity".

To me, it sounds like the comparison ends there: the papers I consulted until now refer to SNARKs and STARKs as a list of properties that a proof system should have, not as a specific instantiation of a proof system. Considering the aforementioned Ethereum.SE question, it seems like both zk-SNARKs and zk-STARKs are actual instances of proof systems, since they list specific complexities and timings. Papers about specific SNARK and STARK construction, e.g. the Ben-Sasson paper, all seem to refer to "previous S[TN]ARK contructions", making me wonder whether the Eth.SE comparison can be fair.

So my question(s) is/are:

What is a zk-SNARK:

a specific proof system, and if so: which one?
a class of ZK proof systems, and if so: is this class specific enough to claim that proofs are "always 200 bytes"?

The same for zk-STARK, with most probably the same answer.
I feel that question 1. will come down to a class of proof systems, which makes me wonder why Bulletproofs wouldn't be a "zero-knowledge, succinct non-interactive argument of knowledge"; they are typically considered separate.

A class. Parameters according to which it is standard to compare them, are: prover time, verifier time, proof size, requirement of trusted setup, cryptographic assumptions. For "succinctness", the standard definition requires that verification time is sub-linear and proofs are "small".
STARK however, is a name of a specific zk-SNARKS protocol, see any Eli Ben Sasson talk on Youtube for the specific attributes.
I reckon it's because verification time is linear.


what is the impact of smaller bit size sbox There are multiple S-boxes type, as DES uses 4 bit S-box and AES uses 8 bit S-box. I want to know how this effect the security?? If we use 4 bit or 8 bit. apart from the DC attack. Both provides confusion then why 4 bit and 8 bit different size

the differential property , linear property , algebraic order is larger for 8 bit s-boxes compared to 4 bit s-boxes.

The optimal differential/linear  probability is 2^-6 for 8-bit s-box while it is 2^-2 for 4-bit s-boxes, therefore less number of active s-boxes needed (less rounds) to achieve minimum differential/linear security bound using 8-bit s-boxes.

However, 4-bit s-boxes are good for light implementation and threshold masking to resist side channel analysis.


Security of CCM in TLS, in comparison to GCM, SHA or SHA2 for the digest I've been looking into TLS cipher suites of OpenSSL and mbedTLS (previously called PolarSSL) and noticed that mbedTLS supports the CCM mode of operation (See list here), whereas OpenSSL does not. If I understand this correctly, this provides authenticated encryption and therefore covers the message hashing in TLS, like GCM.

Looking up CCM, I couldn't find much information on its security. How does it compare to GCM or SHA1/2?

Edit:

mbedTLS TLS cipher suites with CCM:

TLS-RSA-WITH-AES-128-CCM
TLS-RSA-WITH-AES-256-CCM
TLS-RSA-WITH-AES-128-CCM-8
TLS-RSA-WITH-AES-256-CCM-8
TLS-DHE-RSA-WITH-AES-128-CCM
TLS-DHE-RSA-WITH-AES-256-CCM
TLS-DHE-RSA-WITH-AES-128-CCM-8
TLS-DHE-RSA-WITH-AES-256-CCM-8
TLS-ECDHE-ECDSA-WITH-AES-128-CCM
TLS-ECDHE-ECDSA-WITH-AES-256-CCM
TLS-ECDHE-ECDSA-WITH-AES-128-CCM-8
TLS-ECDHE-ECDSA-WITH-AES-256-CCM-8
TLS-PSK-WITH-AES-128-CCM
TLS-PSK-WITH-AES-256-CCM
TLS-PSK-WITH-AES-128-CCM-8
TLS-PSK-WITH-AES-256-CCM-8
TLS-DHE-PSK-WITH-AES-128-CCM
TLS-DHE-PSK-WITH-AES-256-CCM
TLS-DHE-PSK-WITH-AES-128-CCM-8
TLS-DHE-PSK-WITH-AES-256-CCM-8

GCM and CCM are both basically fine as far as typical TLS use goes, although there is a litany of caveats for them:

Anything involving AES is likely to be vulnerable to timing side channel attacks, if you cannot guarantee that you are using hardware implementations of AES.  (Portable C code cannot.)
GCM is also likely to be vulnerable to different timing side channel attacks, if you cannot guarantee that you are using hardware Galois field arithmetic.  (Portable C code cannot.)
The length of the authentication tag directly affects security: the GCM and CCM suites use 128-bit tags, but the CCM-8 suites use 64-bit tags, so they cannot get better than a 64-bit security level against forgery.
For both GCM and CCM, the security contract requires that the key never be reused with a nonce.  If they were integrated into TLS sensibly, the protocol would mandate the use of sequential nonces, so that there is only one possible choice of nonce for each message and if a peer chooses any other nonce it will noisily fail to interoperate.  TLS 1.3 will do this, but when GCM was first introduced for TLS, it was foolishly designed to allow the peers to choose nonces however they like, to hilarious effect, and CCM in TLS parroted the mistake.

You can't fix any of these problems except by picking an entirely different cipher suite, but you can check whether these are problems for mbedTLS or your particular deployment of it—make sure mbedTLS uses sequential nonces, for example, and take a close look at how it computes AES and GHASH.

Or, if mbedTLS and your clients support it, just always use ChaCha20/Poly1305 cipher suites instead, which have none of these issues.


MAC tag size in AES CCM, when using CTR + CBC-MAC (not CBC MAC only) Assuming that AES CCM is used with respect of the NONCE unicity // the key life cycle, I wonder about the need of using the highest size for CBC-MAC authentication tag if CTR mode encrypts both payload AND authentication tag :

If no encryption is performed (e.g AES CBC MAC only), I understand the need of highest tag, i.e 128 bits , thus to prevent from brute force attack .

But : if the tag is ciphered using CTR mode as the payload is, I guess it guarantee that an adversary can not pickup any pair (Plain text / tag) and try to get another pair that matches ?

Any suggestions welcome, thanks !

There are different "brute force" attacks related to CBC-MAC:

Key search, which depends on key size and not the length of the authentication tag.
Tag guessing, where you just try a random tag for a modified message succeeds with probability $2^{-t}$ if the tag is $t$ bits long.

The first is not related to the tag length at all and even if you use AES-128 you are secure from it. (As long as it's a random key, anyway: e.g. a password derived key could still be guessed with a non-brute force attack.)

The second works the same whether you use plain CBC-MAC (with prefix free messages) or in CCM where the authentication tag is encrypted. By using a tag smaller than 128 bits you increase the probability of the attacker creating a correct tag at random. Whether the tag is encrypted or not, the probability is always $2^{-t}$.

Where the encryption may matter is security after the birthday bound. CCM may offer authenticity even after you have used the key too many times to offer full privacy (i.e. close to $2^{64}$ blocks). Even there the tag length gives an upper bound for security, so that fact does not justify using a shorter tag.

None of that means you must use a 128-bit tag, of course. Forging a 64-bit tag, for example, would be very unlikely. It comes down to how sure you want to be about authenticity.


Does the One-Time Hash-based Signature Scheme render Ring Signatures useless? On the Bitcoin community, to maintain privacy, they recommend using one-time spend addresses. CryptoNote, Monero et al. prefer Ring Signatures to maintain that privacy. There are some issues regarding double-spends in the Ring Signatures realm, so Linkable Ring Signatures + One-Time Key Images are used to avoid that. Both one-time spend addresses and CryptoNote's Ring Signatures approaches will be vulnerable to Quantum Computers in a near future, 'cause they rely on either Elliptic Curves or RSA, tho.

My point is, due the one-time nature of Hash-based Digital Signatures, we should use Merkle Trees to maintain an identity (although signing other public keys embedded in the message also works). But it's optional on that Signature Algorithm. Ring Signatures are used to maintain privacy for Signatures schemes which aren't One-Time, right? If so, are One-Time Signatures more "powerful" than other types of signature schemes?

Despite that question which I asking, One-Time Signatures are unsafe in the case of Network Splits / Hard-Forks. They freeze forever your funds on the other chain. This is a reason which I see Merkle Trees of Public Keys as needed, in the case of forks they're very helpful.

I'm writing a simple but not yet validated One-Time Hash-based Signatures library here (https://github.com/marcoonroad/hieroglyphs) - disclaimer: I'm not an information security and cryptography expert, but I try to do my best. I wonder if I need to implement the Ring Signatures algorithm to hide / protect identities, mostly due the possibility to navigate the chain/history of signatures in a network and track/guess identities by grouping discovered related public keys.

As a side note, there other approaches outside the Digital Signatures realm to implement Blockchains and sort of that. The Elixxir team (who David Chaum is a member and CEO) seems to plan to use Commitment Schemes instead of Digital Signatures, it's really interesting how hashes could be used for almost anything.

Thanks in advance!

I see several misunderstandings in your question. Let me provide some clarification:

One-time addresses don't provide privacy at satisfiable level. At first glance, it's impossible to associate some one-time address with some identity (person).
But analysis of the graph of transactions could reveal relations between one-time addresses. E.g., despite the fact you use one-time addresses to receive payments, then, to spend this money (buy a car) you would need to
aggregate all the addresses in a single transaction. This will reveal all you wanted to hide. Even if you try to make a confusing chain of transfers between one-time addresses, someone like Sherlock Holmes is able to unravel a tangle step-by-step.
One-time signatures (OTS) is not a feature, but a restriction.
You cannon say that OTS "more powerful than other types of signature schemes". Vice-versa, they are limited/hard to use.
Ring signatures, at least in original cryptographic meaning (https://en.wikipedia.org/wiki/Ring_signature), don't provide privacy by itself. They could be used just as a building block of a complex cryptosystem like Cryptonote/Monero. But if you use the term "ring signature" as the cryptosystem provided by Monero, you're right - its goal is a privacy, including unlinking senders and receivers of transaction and impossibility to associate relations between addresses.
There're several definitions of privacy in payments, several levels of privacy. And several solutions, the most noted are: 1) Cryptonote/Monero, 2) Bitcoin confidential transactions, ZkSNARKs based solutions of 3) Zcash and 4) Ethereum, 5)Bulletproof-based solutions for Bitcoin.
For example, Bitcoin Confidential Transactions provides only confidentiality of amounts of a transaction but doesn't hide senders and receivers. So, different systems achieve different aspects/levels of privacy. It's even so except bugs/attacks.

So, answering your question, OTS doesn't make Ring signatures useless in any sense, since:

one-time addresses doesn't provide privacy, while solutions based on ring-signatures (such as Monero) do;
OTS and one-time addresses are difficult/inconvenient to use, comparing to multi-time ones; e.g., in order to receive recurring payments, you constantly need to inform your payers with fresh addresses.


An unbreakable book cipher? In a recent press interview, a former terrorist of the 1970s described the cipher his group used to communicate. He claimed that method was unbreakable and I wonder if cryptographers today would agree. Here is how it functionned:

Take two identical books (same edition): one for the sender, one for the recipient.
Each sign - one could include spaces between words as signs - is encoded as follows:

  (page number) (line number) (number of character on the line) (random
  number)

additions, subtractions, multiplications or divisions of certain agreed value in a certain order are then applied. For example, 357 could mean:

  (page number*3) (line number -5) (character number +7)

This means that negative values can be created, especially if the
substraction value is in the double digits

A software script for such a cipher would be I think relatively easy to design. Also, the agreed values of the operations in step 2 can be changed anytime so the same base text can be reused.

Bottom line, it means for example a single 7-letter word would produce a string of 28 numbers, of various lenghts and some negative values or decimals or fractions perhaps - depending on what values are used for the operations.

what is your opinion on this method?

Book ciphers are well understood and this seems like a fairly minor variation. Following Kerchoff's Principle we separate the key being the book and the arithmetic operator and numbers and the rest. Picking a random number for fourth position makes no difference in this regard. But even if we let that be a secret to it makes little difference. Humans are lousy at picking random numbers and this will be apparent.

Multuplying by a constant is also a really bad idea. It will be very quickly apparent all numbers in a certain position are a multiple of constant and will be devided by it.

Subtracting or adding a number from row or character number will also be apparent after collecting sufficient data by observing the skewed range. such an addition will be slightly harder regarding page number due to higher cardinality of page numbers but won't necessarily be an issue see next.

Humans doing a poor job picking random numbers. Many people who use book ciphers flip forward a bit from where they are or start reading from the start of the page. This means rare letters will require on average more skipping forward leading to some leakage.

Also the book itself may be selected from a limited set of books can make the book itself guessable.  Given a large library of online books brute forcing such a cipher isn't all that difficult.

If you do not want to mark the book making it physically obvious it is a cipher key it is difficult to prevent repetitions when randomly selecting characters.

If the book is considered a secret not chosen from a limited selection available at your local book store for instance and the person using it picks a random starting point in the book for each letter and seeks the next matching one and marks off each used letter to prevent duplicates then it is a fairly secure cipher even without the additions described.

In reality most book ciphers have been and will be broken.


Affine Cipher: what to do if the number isnt invertible over mod n? I am currently solving a simple cryptanalysis problem where I need to decrypt a text file using frequency analysis. The text has been encrypted using an affine cipher over a 68 character alphabet which includes lower and upper case English letters, digits from 0 to 1, as well as those characters: ". , ; : _ \n" where _ denotes space.
Going over the frequency histogram of the text, the most frequent character is "," followed by "z". According to what I know, the most frequent character for the 68 character alphabet is space followed by "e".
Thus I end up with those two equations:
$$66a + b = 63 \bmod 68$$
$$4a + b = 25 \bmod 68$$
Which gives me:
$$62a = 38 \bmod 68$$
$a = 38 \cdot 62^{-1}  \bmod 68$
However, 62 isn't invertible mod 68. I am quite new to cryptography so I am quite unsure if there is some method to solve this issue.

If you divide the whole equation throughly 2 you get
$$31a\equiv 19\pmod {34}$$
which you can solve to get $a\equiv 5\pmod{34}$. This then gives two possibilities for $a\pmod {68}$: either 5 or 39. For these two possibilities you can then find the corresponding $b$ (it turns out to be 5 in both cases) and check which solution works.


Is a large random number cryptographically equivalent to the product of multiple smaller ones? Say I create a 256-bit key by taking a random number between $0$ and $2^{256}-1$.

Would it be cryptographically equivalent to generate $8$ numbers $r_1\dots r_8$ between $0$ and $31$, and combining them in the following way?

$$\mathit{rand} = 2^{r_1} \cdot 2^{r_2} \cdot 2^{r_3} \cdot 2^{r_4} \cdot 2^{r_5} \cdot 2^{r_6} \cdot 2^{r_7} \cdot 2^{r_8}$$

It would still add up to 256th power, but would it be secure of generating it this way? If not, then how to do it, how to generate big random number by combining smaller ones?

If you choose a number uniformly at random in the range $[0, 31]$, that's $32$ distinct values and thus $log_2(32) = 5$ bits of entropy.  If you choose $8$ such numbers, then you have $5 \times 8 = 40$ bits of entropy total, meaning that there are $2^{40}$ distinct combinations you could get.  It doesn't matter how you combine them, that's already far short of $2^{256}$.

And it gets worse, because you're multiplying numbers that you compute from your eight choices:

  $$\mathit{rand} = 2^{r_1}\cdot 2^{r_2}\cdot 2^{r_3}\cdot 2^{r_4}\cdot 2^{r_5}\cdot 2^{r_6}\cdot 2^{r_7}\cdot 2^{r_8} $$

Since multiplication is commutative ($a \times b = b \times a$) and associative ($a \times (b \times c) = (a \times b) \times c$), it means that many combinations among those $2^{40}$ distinct choices actually yield the same product after the multiplication.  E.g., if two sequences of random choices are permutations of each other their product is the same. In this case, it is even worse, since $\mathit{rand}=2^{r_1+\dots+r_8}$ is always a power of two: This means we are effectively sampling a $256$-bit number that has exactly one bit set, so there's only $256=2^8$ possible outcomes!

  If not, then how to do it, how to generate big random number by combining it from smaller ones?

Basically, by choosing digits at random in some base.  If you have $n$ randomly drawn digits $d_0, ..., d_{n-1}$ in base $b$, then $d_0b^0 + ... + d_{n-1}b^{n-1}$ is a uniform random number in the range $[0, b^n)$.  For example, to generate a 256-bit number at random, you could:

Choose 256 individual bits at random ($n = 256$, $b = 2$);
Choose 32 bytes at random ($n = 32$, $b = 8$);
Choose eight 32-bit machines words at random ($n = 8$, $b = 32$);
Choose four 64-bit machines words at random ($n = 4$, $b = 64$).

In practice, this is done by just concatenating randomly chosen bytes or machine words.


Does composing multiple substitution ciphers improve security? Will using two substitution ciphers one after the another be more secure than using single substitution cipher?

If the substitution ciphers belong to the same family, then their composition will also (typically, assuming that the family is closed under composition) belong to the same family.  Thus, breaking the combined cipher will be no harder than breaking an arbitrary cipher in the family.

For a simple example, combining two Caesar shift ciphers with shifts amounts $a$ and $b$ will just yield a Caesar shift cipher with shift $a+b$.

In particular, all simple substitution ciphers are vulnerable to frequency analysis, and also form a family that is closed under composition — the composition of any two simple substitution ciphers is itself a simple substitution cipher.

Thus, while the combination of, say, a keyword cipher with a Caesar shift might be slightly harder to break than either cipher alone (in the sense that it's not vulnerable to methods that only break either of the component ciphers alone), it's still no stronger than a generic simple substitution cipher.

(Similarly, say, combining two Vigenère ciphers yields another Vigènere cipher, although the effective key length of the combined cipher equals the least common multiple of the original key lengths, potentially complicating cryptanalysis.  Such a combined key does, however, have some repetitive structure that can make it considerably easier to break than a random key of equivalent length.)


RSA find public exponent Suppose I have an encryption oracle which can encrypt $m^e \mod n$ for any $m$. I know $n$ and I know $\varphi(n)$. However the public exponent $e$ is secret. Is it possible to figure out it's value when $e$ is not bruteforce-able?

Is it possible to figure out it's value when $e$ is not bruteforce-able?

It depends.
First note that knowing you can easily factor $n$ given that you also know $\varphi(n)$ (2-prime case).
Next note that $\mathbb Z_n^*\cong\mathbb Z_p^*\times \mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).

Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $x\mapsto x^e\bmod p$ and the same for $\bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.

Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.


what does output parameters of lwe estimator stands for? I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on  lwe estimator given bellow.

sage: load("estimator.py")
sage: n, alpha, q = Param.Regev(128)
sage: costs = estimate_lwe(n, alpha, q)

The output is

usvp: rop:  ≈2^57.2,  red:  ≈2^57.2,  δ_0: 1.009214,  β:  101,  d:  349,  m:      220
dec: rop:  ≈2^61.5,  m:      229,  red:  ≈2^61.5,  δ_0: 1.009595,  β:   93,  d:  357,  babai:  ≈2^46.8,  babai_op:  ≈2^61.9,  repeat:      293,  ε: 0.015625
dual: rop:  ≈2^81.4,  m:      376,  red:  ≈2^81.4,  δ_0: 1.008810,  β:  111,  d:  376,  |v|:  736.521,  repeat:  ≈2^19.0,  ε: 0.003906

What is rop, red, δ_0, β, d, m stands for in the output. I search many official documentation of lwe estimator like this (they give brief description of other parameters like bop in section 7) and this. But they provide information about input parameters and algorithms used and not about the output parameters. Any help is appreciated.

δ_0: the root Hermite factor required
β: the BKZ block size
d: the dimension of the lattice being reduced
m: the number of LWE samples used


Is it possible to derive an Ed25519-public-key from an Ed25519-signature? If you have an Ed25519-signature and the signed message, can you derive the corresponding public-key or is the signature anonymous (except if you already know the public-key of course)?

From Wikipedia, an EdDSA signature is a pair $(R, s)$ of a point $R \in E(k)$ and scalar $s \in \mathbb Z$ satisfying the verification equation $$[2^c s] B = [2^c] R + [2^c H(R, A, M)] A,$$ where $E/k$ is the underlying curve over a field $k$, $B \in E(k)$ is the standard $k$-rational base point of large prime order and cofactor $2^c$, and $A \in E(k)$ is the public key.

It is tempting to say that if you had $h = H(R, A, M)$, then you could simply compute an inverse $k$ of $h$ modulo $\ell$ and compute $A = [k] ([s] B - R)$, and hope that complications with the the covfefe $2^c$ won't eat your lunch.  But, by design, the only way to compute $h$ is in fact to know $A$ a priori to feed it into $H$.  And unless you break the preimage resistance of $H(R, A, M)$, which is SHA-512 in the case of Ed25519, you won't get very far doing this.

However, that only answers the question you asked literally: Can I derive $A$ from an Ed25519 signature?  You also mentioned anonymity, which is a slightly different kettle of fish.  The question for anonymity should be the key privacy property: Given two signatures $(R, s)$ and $(R', s')$, can I tell with nonnegligible probability whether they were made by the same key pair or not?

In the case of most RSA-based signature schemes, the answer is yes (to both questions), thanks to a problem of counting German tanks well-known in the anglophone empirical inference literature—that is, most RSA-based signature schemes do not provide key-privacy.  What about Ed25519?

The answer may be a little trickier, because we don't demand recovery of the public key as the standard approach to breaking RSA-based key privacy works.  The literature does not seem to be rife with references about key privacy for signature schemes, but there is a simpler sufficient criterion for key privacy of encryption schemes which could likely be adapted to signature schemes.

I leave it as an exercise for the reader to adapt this into a sufficient criterion for key privacy of signature schemes, demonstrate that Ed25519 satisfies the criterion, and publish it all to fame and glory in the cryptology literature.


SHA-1 collisions - what about practical attacks? I understand the theoretical problem with hash collision but when it comes to practice, I get very confused.

Suppose a attacker would like to forge a certificate (or any kind of structured piece of file) using hash collisions, I wonder how it is possible to find a collision (already unlikely) and moreover, this collision is "found" from relevant structured input bytes (dates, common name, dns attacker).

It sounds very strange for me, I can't understand how one can found a hash collision which helps as an attack, I can only think about a random raw bytes which could generate a same hash, but it would not be parsed (ex: x509 certificate hash collision find by an attacker, but the x509 malicious content is random bytes not understandable by browser).

The question asks how a collision in a hash such as SHA-1 could become a practical concern, with focus on the case of a public-key certificate à la X.509.

I'll first give an example involving executable code signing. I'll assume an attacker in a position to write bootstrap code (like, the supplier of a development toolchain, or someone who compromised that toolchain), and enough resources to perform one single attack finding two distinct 128-byte colliding messages on SHA-1 with a small change: the value of the (arbitrary) 160-bit initialization value. The later is possible

by brute force with expected effort less than $2^{81}$ hashes (about the effort devoted to bitcoin mining in a year according to that source) using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website);
or with less effort using complex specialized methods exploiting weaknesses in SHA-1's compression function, with an estimated effort comparable to

$2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
$2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
$2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).

Suppose an executable file format consisting of

: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8
: 4-byte length of section 5, allowing to locate the signature
: (anything)
: PKCS#1v2 RSA-4096 signature of the SHA-1 hash of 1-2-3-4-5.

The attacker writes or adapts bootstrap code 3 so that the executable is

: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8

: code that gets the value of $k$ from section 3.4, then jumps to section 3.6 or 3.5 according to if $k^\text{th}$ bit of section 3.3 is 0 or 1
: filler data so that 3.3 is aligned to a 64-byte boundary
: 128-byte data block
: 4-byte $k<1024$ such that the two values of section 3.3 differ in the $k^\text{th}$ bit
: code performing whatever the attacker wants to perform
: code performing whatever the bootstrap is supposed to perform

: 4-byte length of section 5, allowing to locate the signature
: (anything)
: PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3 / 4 / 5.

The adversary needs to

know 1 / 2 / 3.1 / 3.2 when starting the attack
apply enough rounds of SHA-1 to deduce the 160-bit SHA-1 state after hashing 1 / 2 / 3.1 / 3.2, giving the 160-bit initialization value of the SHA-1 variant attacked
perform one of the costly attack at the beginning of this section
having found two 128-byte colliding data blocks, determine a bit index $k$ where they differ, and label the colliding blocks A and B according to if $k^\text{th}$ bit of the block is 0 or 1
construct two version 3A and 3B of the bootstrap code 3, differing only by containing block A or B in section 3.3; notice that 3.5 and 3.6 can be changed without performing the costly attack again;
plant version 3A of the boostrap, which does as it is supposed to perform
let an unsuspecting developer create an application with bootstrap 3A, and getting it signed;
obtain that signed original;
create a forgery by changing section 3.3 to block B, so that version 3B of the bootstrap is in place;
arrange for the forgery to be used on target machines, using the reputation of the application developer.

The forgery pass signature verification because the SHA-1 hash of 1 / 2 / 3 / 4 / 5 is unchanged, but when launched executes the code of section 3.5 performing whatever the attacker wants to perform, when the signed original did not.

Further, it is possible to encipher the code of section 3.5 using the block of section 3.4 as key, making it impossible to analyze the exact behavior of bootstrap 3B from the knowledge of bootstrap 3A. And code of section 3.1 can be of the form decipher-then-execute, so that the intention is less apparent.

Similar tricks can be pulled with some "data" format that are executables in disguise; e.g. that trick has been pulled with postcript and MD5.

Back to certificates in X.509-like format: consider a simplified certificate format with

: identity of the certificate holder, in ASCII on 44 bytes right padded with spaces
: public modulus $N$ of a 2048-bit RSA key, on 256 bytes (big-endian)
: (other certificate data, including public exponent, attributes..)
: PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3

and one of two relevant attack models

An attacker legitimately purchases from an honest certification authority a certificate with her identity Alice and a public modulus $N_a$, modify it into a certificate with the identity of Bob and public modulus $N_b$, and holds the private keys $d_a$ and $d_b$ corresponding to $N_a$ and $N_b$ ($d_a$ is necessary to obtain the certificate; $d_b$ allows Alice to impersonate Bob);
A rogue certification authority knowingly supplies to Alice a certificate with the identity of Bob and a public modulus $N$ with factorization known to Alice (and perhaps having relatively easily found prime factors, making it more plausible that the above attack occurred), allowing Alice to impersonate Bob; and if word ever leaks that Alice impersonated Bob using a certificate issued by this authority, pretends that it has fallen to the above attack.

Note: something close to one of the above things has actually occurred with MD5-based X.509 certificates, per the evidence given here. This had been publicly described circa 2009.

In order to actually perform the attack, Alice

searches one SHA-1 collision between two 64-byte data blocks $M_a=I_a\|J_a$ and $M_b=I_b\|J_b$ with the first 44 bytes $I_a$ and $I_b$ corresponding to Alice's and Bob's identity; and 20 other bytes $J_a$ and $J_b$ arbitrary except for having the first bit set

the brute force Parallel Collision Search referenced earlier allows that with expected effort less than $2^{82}$ hashes: the function iterated can map a 160-bit value to a 64-byte block with either Alice's or Bob's identity in $I$ according to one bit; and map the other 159 bits to the unconstrained bits of $J$; when a collision is found, there is a 50% chance that it will be between a 64-byte block with different identities, thus usable;
it is conceivable to adapt some specialized methods exploiting weaknesses in SHA-1's compression function (in particular Marc Steven's publication referenced earlier describes a chosen-prefix collision attacks with expected effort about $2^{77.1}$ hashes);

finds a 236-byte value $K$ so that $N_a=J_a\|K$ and $N_b=J_b\|K$ (big-endian) are 2048-bit integers with known factorization, squarefree, and odd (and if necessary, with $N_a$ passing whatever other test the certification authority may perform, and $N_b$ passing whatever other test the entity to which Alice wants to represent herself as Bob may perform); given our message format, it is even feasible (though not required) to ensure that both $N_a$ and $N_b$ have exactly two large primes factors: we can choose $p_a$ and $p_b$ arbitrary primes about 900 bits, then systematically construct and explore $K$ such that $p_a$ divides $N_a$ and $p_b$ divides $N_b$, until both $N_a/p_a$ and $N_b/p_b$ are primes.
finds a public exponent $e$ acceptable for both $N_a$ and $N_b$ (there's a fair chance that the common $e=2^{16}+1$ will do) and compute private exponents per RSA as defined in PKCS#1, as $d_a=e^{-1}\bmod\lambda(N_a)$ and $d_b=e^{-1}\bmod\lambda(N_b)$, which is easy knowing the factorization of $N_a$ and $N_b$;
legitimately obtain the certificate with identity $I_a$, public modulus $N_a$, public exponent $e$ (which typically requires signing the certification request using $d_a$);
change $I_a$ to $I_b$ and $N_a$ to $N_b$ in the certificate (this will not change the SHA-1 hash, thus the forgery is a certificate that pass the verification procedure);
impersonate Bob using the forged certificate and $d_b$.

A countermeasure would be that certification services enforce the insertion of some unpredictable data in the beginning of certified data.


Does adding more characters to the Enigma rotors improve crypto strength? This seems like an obvious question but I haven't been able to find it, so here goes:

Enigma is based on an alphabet of A-Z (26 characters); obviously this directly affects message content (e.g. numbers would be specified using their names one, four, two, etc) and it also has a direct bearing on the number of possible permutations (crypto strength).

Would increasing the alphabet of the rotors (e.g. to A-Z, 0-9, and a selection of special characters) increase crypto strength? I know it would increase the number of possible permutations but I'm not sure if that would introduce some kind of weakness.

Update (additional context)

I'm building a "for fun" software implementation of Enigma, in C# - currently as a UWP application that will run on any Windows 10 device (including phones).  It will include implementations of a few of the real-world historical Enigmas (I, M3, M4) as well as the ability to take "extended" Enigmas where you can create your own rotor sets with any number of rotors, including new wiring's and character sets (i.e. beyond A-Z).

Based on feedback provided adding additional characters could be dangerous.
I was thinking that for an 'extended' implementation you might want to include 0-9 and some special characters commonly used these days (such as : /).  I guess one motivation for this was convenience.  Of course given the flexibility of modern computing I guess I'd be better off allowing the user to input "convenience-plain-text" such as "HTTP : //WWW" transform it to "standard enigma A-Z plain-text" "HTTPCOLONBACKSLASHBACKSLASHWWW" then encipher it, and possibly perform the reverse at the other end.  Maybe that's the basis of further questions another time.

Update - 28-July-2017

Based on this Q&A I can now actually measure the increase in key-size for enigma like systems; whilst expanding the supported character set does increase the key size, adding additional rotors increases it by significantly more (notwithstanding the other issues that affect the overall crypto-strength of enigma).

Does adding more characters to the (Enigma) rotors improve crypto strength?

Not really… since the weaknesses of Enigma go well beyond the count of chars per wheel!

Of course you could – theoretically – think of using very big (read: huge) wheels with an insane char range. But, when looking at the “time” and “resources” you would need to invest each time you’ld merely wanted to encrypt and decrypt things with such a beast, it simply wouldn’t make much sense. Modern ciphers already blow Enigma out of the water in terms of speed, cryptographic-strength, etc.

Differently stated: the gain you would achieve by adding chars won’t be big enough to level-up good old Enigma into the realms of more recent and better preforming algos (like aes, chacha, et al).

Also, as CodesInChaos already hinted in his comment, it would put you on a very slippery road with a good chance that you’ll end up introducing additional attack vectors. In a worst case, you could break one of the stronger parts of Enigma while ignoring the real cryptographic weaknesses that already come with Enigma; which would result in something like a (let’s just call it) cryptographic nightmare.

Yet, don’t get me wrong: for something like a non-public “student project” with the goal to have a truckload of chances to shape your cryptanalytic abilities… this could be fun to fiddle with and maybe worth thinking about for a minute. But if you do, you better be prepared to notice you’ll need to fix a whole truckload of nasty little issues related to Enigma. Simply increasing the char count will not do it.


would parallel crypto mining work Hi everyone I was wondering would it be possible to mine a cryptocurrency like bitcoin in parallel. I have read a little about mining pools https://en.wikipedia.org/wiki/Mining_pool , But that's not quite what I'm looking for . the idea i had was to create a customized mining software that would Comprise of a master node with multiple Slave nodes like this .

The master node would join the most profitable bitcoin mining pool
so let's say i had the slave software running on 20,000 computer.
The mining pool would see is one miner from me is this practical.

What you describe is called proxy mining, and it exists. You basically start your "own" pool, and let your master divide the work.

It's mostly done to have less load on the pool though, it has no computational advantage over having all slaves join the pool.


Which of these 3 AES 128 symmetric encrypt/decrypt routines is most secure? I am developing a symmetric en-/decryption routine written in c# for a database containing user-specific, sensitive information.

I have narrowed down the implementation to 3 different approaches, but simply cannot determine which is the "best". So, which of these is the most secure?

AES in GCM mode. Using either BouncyCastle or CLR Security implementation.
For those who don't know, GCM mode utilizes CTR mode with a provided counter (not sure of the exact implementation) and an additional message authentication process (definitely not HMAC)
AES in CTR mode. Using Bouncy or CLR security again. In this instance I would use the .net HMAC and utilize a 16 byte IV randomly generated (securely) as the unique nonce.
AES in CBC mode. Using the .NET implementation. Again the HMAC from .net and rand IV.

The simpler the better cause I'll probably mess it up

Thanks a bunch

GCM mode is best, as it can not be attacked using padding oracle attacks, which are much more common than commonly thought. It is also the only one providing integrity protection, something that is certainly much overlooked.

Make really sure your NONCE is random though, or use one that is uniquely defined (even in time) within the database.

SquareRootOfTwentyThree makes a valid objection to say that the comparision should have been between GCM mode and symmetric ciphers + HMAC. There are several reasons why I would favor GCM mode over HMAC:

two separate/unrelated keys are needed for encryption and HMAC
you need to match the security of the hash in the HMAC with that for encryption
there is more room for error when using HMAC (provide a MAC over the wrong data)
you need to communicate two different algorithms to the other party
you need to check if HMAC is actually performed

This is opinionated as all can be made secure.

The last point about the HMAC check sounds obvious, but see what happened to XML encryption in WS-security where in most implementations the signature validation could be switched off, leading to padding oracle attacks. Creating a protocol that simply performs GCM mode has fewer points of failure.

Note that the drawback regarding the NONCE mentioned by CodesInChaos is a valid one. Unfortunately any of these algorithms is affected if the IV or NONCE is not used correctly.

GCM is started to be used by updates of several protocols (TLS, XML encryption) and has been approved by NIST.


Implement deniable encryption with AES/RSA I'm on a crypto app using OpenSSL (I'm more an implementer/cryptographer than a cryptologist), mainly as a hobby, for now.

My app will be able to encrypt a file (not a container) with symmetric or asymmetric or both encryption (sym then asym), and I want to implement "deniable encryption" (I'm in France, you should have heard about the law which has just been voted: our NSA now has all rights on internet).

My first issue is RSA: for example, when decrypting with a wrong key, it fails to leave a correct padding. So, a file won't be decrypted to a random looking badly deciphered text. I hope a symmetric algorithm will allow me to do that, but first I'm using RSA. Do any of you have an idea on how to "force" RSA to decrypt a file to a valid message (but not the cleartext), allowing a user to claim it was the right key? I assume that the protocol will be known.

If possible I would also be interested in suggestions of other methods with this "behaviour", or implementations of this.

EDIT: Precision: The cryptosystem*will be able to encrypt a cleartext with public-key (which implies symmetric encryption) OR symmetric encryption OR (minor probability) both one after the other (for i.e.: Let's say you have an already symmetric ciphered file you need to relay, you can apply a public-key encryption, which will make the file encrypted twice with probably 2 different algorithms and 2 different keys).

PS: Redirected to chat, too many comments.

We need clear goals. The question asks for "plausible deniability" or "deniable encryption", and these terms needs a precise definition in a public-key context (implied by RSA). I assume that in addition to the IND-CPA and IND-CCA1 properties of a cipher, including hybrid (as implied by AES), it is desired that:

One without the private key can't distinguish ciphertext from random data of the same length (with the exception of data too small to be correct ciphertext considering the key size).
One trying to decipher ciphertext with the wrong private key get random-like output and no error message (with the exception of ciphertext too small to be correct ciphertext considering the key size).
Even one with the private key can not distinguish from random the ciphertext obtained by encryption with the corresponding public key of unknown random data.

I think these goals are orthogonal. (1) is most natural; (2) helps leaving interceptors clueless; (3) is useful in a context of layered encryption. The whole gives some useful level of deniability in societies where possessing random files and encryption programs designed for deniability is not objectionable.

I propose a simple scheme that I claim meet the above goals. It is close to the simplest possible form of hybrid RSA/AES encryption: use a random key to AES-encipher the bulk of the data, and use RSA to encipher that key. The only difficulty is making sure we do not leave a bias here or there. In particular, usual RSA primitives have their ciphertext with some bits biased, sometime constant, failing (1); and with the right private key, they often reveal more structure, failing (3).

The key setup is that of RSA. Users have private keys $(N,d)$, and all the corresponding public keys $(N,e)$ are made public. $n$ is the bit size of $N$, so that $2^{n-1}\le N<2^n$. I restrict to plaintext, ciphertext, and more generally data or files that are a contiguous collection of octets. Ciphertext always is exactly $\lceil(n-1)/8\rceil$ octets longer than the plaintext. Big-endian binary is used in all conversions between octets and integer.

Symmetric encryption is done using AES-128 for $128<n\le2049$, AES-192 for $2049<n\le4097$, AES-256 for $n>4097$.

The encryption procedure accepts a public key $(N,e)$ and plaintext:

repeat the following steps..

generate $M$ uniformly random in $\{0\dots N-1\}$;
compute $C=M^e\mod N$, which is textbook RSA encryption;

..until $C<2^{n-1}$ [notes: here $C$ is uniformly random in $\{0\dots2^{n-1}\}$; in the context, the end condition means that $C$ fits in $n-1$ bits; it will take on average less than two iterations to get there];
generate $a$ uniformly random in $\{0\dots2^{7-((n-2)\bmod8)}-1\}$ [note: in other words, generate $a$ of 7-((n-2)%8) random bits];
let $A=a\cdot 2^{n-1}+C$ [note: that concatenates $a$ and $C$ for a total of $8\cdot\lceil(n-1)/8\rceil$ bits, when considering $a$ and $C$ as bitstrings of fixed sizes $7-((n-2)\bmod8)$ and $n-1$ bits];
output $A$ as $\lceil(n-1)/8\rceil$ octets;
let the low-order bits of $M$ be the AES key of the size determined by $n$;
encipher the plaintext (if any) in AES-CTR mode with implicit zero IV, and output it.

The decryption procedure accepts a private key $(N,d)$ (possibly in another form) and data that is a putative ciphertext:

read the first $\lceil(n-1)/8\rceil$ octets of data, forming an integer $A$ of (at most) $8\cdot\lceil(n-1)/8\rceil$ bits; if there is not enough data, terminate with error or hang;
compute $C=A\bmod(2^{n-1})$ [note: that forms $C$ by ignoring the high-order $7-((n-2)\bmod8)$ bits of $A$, considered as a bitsring of $8\cdot\lceil(n-1)/8\rceil$ bits];
compute $M=C^d\mod N$, which is textbook RSA decryption;
let the low-order bits of $M$ be the AES key of the size determined by $n$;
decipher the rest of the data (if any) using AES-CTR mode with implicit zero IV, and output it.

I do not support encryption to multiple users (a common feature of hybrid encryption), or checking that the plaintext or ciphertext is unaltered, which are antagonist with the combination of the goals.

I make no attempt to hide the length of the original data (adding some level of this is simple: for example, before encryption, append 0 to 255 random octets, and a final octet coding the random number of random octets added, which will allow removing the appropriate number of octets on decryption; goals need minor refinements).

UPDATE: I have made IND-CPA and IND-CCA1 explicit goals. IND-CCA2 is not met. Worst problem is that the cipher is extremely malleable, including to one not knowing which public key was used, and that's a weakness: an adversary guessing the plaintext (e.g. from context and ciphertext length) can replace it with another ciphertext that will decipher to any plaintext of her choice that is not longer than the original, without knowing which key is used (with knowledge of the public key, anything can be enciphered, of course). Another weakness is that the size overhead depends on the key size, and is higher than strictly necessary. It seems all this can be fixed, but with two passes for decryption and added complexity.


Non interactive threshold signature without bilinear pairing (is it possible)? All threshold signature schemes that I have seen need bilinear pairings to avoid parameter exchange between parties. These are normally commitment schemes for a certain secret.

I believe a 2-round non-interactive scheme is possible, without using bilinear pairings, but I'm not entirely sure if it is secure.

Setup

Assume a set of parties with a pair of private/public keys $s_{i} \times G \mapsto P_{i}$, and a Shamir's secret shares $y_{i}$ of $y$ in a $(t,n)$-threshold where $t+1$ are required to recover the secret.

Assume there is a client interested in the signature result and that it can participate in the signature protocol. It can also try to break the protocol to get useful information (such as trying to get $y$), but gains nothing in receiving an invalid signature.

The Lagrange interpolation is defined as $\mathcal{L}^{i}$ such that $\mathcal{L}^{i} y_{i} \mapsto y$ and $\mathcal{L}^{i} y_{i} \times G \mapsto Y$. Also, $y \times G \mapsto Y$. I know this is already possible from this thread.

ThrGenSig(B) $\mapsto$ (c, p)

Produces a Schnorr signature for the $B$ data block from a 2-round multiparty computation.

Round 1) The client sends $B$ to more than $t+1$ parties. Each party computes an hash value $H(s_{i}||B) \mapsto m_{i}$ and replies with $m_{i} \times G \mapsto M_{i}$.

Round 2) The client selects the first $t+1$ to reply and computes $\mathcal{L}^{i} M_{i} \mapsto M$. The tuple $(B, M)$ is sent to the selected parties. Each party derives $m_{i}$ again and $c = H(Y||M||B)$, equal to all parties. Each party replies with $(m_{i} - c \cdot y_{i}) = p_{i}$. The signature result is computed in the client from $\mathcal{L}^{i} p_{i} \mapsto p$, and $c$ is already known.

VerSig(B, c, p) $\mapsto$ {0,1}

Verification is done as any Schnorr signature.

$p \times G + c \times Y = M$
Is c = H(Y||M||B)

Correctness:
Note that, since the same $t+1$ parties are used to produce $M$ and $p$, the Lagrange interpolation works. The degree of the polynomial for $m_{i}$ is the same as for $y_{i}$, and we can sum shares of the same degree due to the homomorphic properties. The scheme only needs $t+1$ active parties during the 2-rounds.

Rushing adversary: A commitment scheme is not needed between parties since there is no interactivity. The client and a colluding party may try to perform $M_{0}^{'} + \sum_{i=1}^{t} M_{i} = M^{'}$ forcing the result where $m^{'} \times G \mapsto M^{'}$ is known. However, since $m_{0}^{'}$ cannot be known due to DLP, the party cannot participate to produce a valid signature for $M^{'}$. $m_{i}$ values are not exposed in any other way.

Distinct $m$ values: $m$ and $m_{i}$ values are the same for the same parties and $B$. No problem here. Even $t$ colluding parties cannot force the same $m$ for a different $B$. The $m_{i}$ share of the honest party will force a distinct $m$ with high probability. The adversary can try via the rushing adversary for a known $M$ via $M_{0} + \sum_{i=1}^{t} M_{i}^{'} = M$, but needs to derive a $m^{'} \times G \mapsto \sum_{i=1}^{t} M_{i}^{'}$ for the colluding parties. $m^{'}$ cannot be derived due to DLP.

Did I miss something. Is this safe?

The scheme as written is insecure if an attacker can get the same message signed twice.

The honest parties will compute their $m_i$ deterministically, but the attacker doesn't have to.

The attacker will get $(m_i - c \cdot y_i) = p_i$ and $(m_i - c' \cdot y_i)= p_i'$ for each participant.

These equations can be solved to get $y_i = \frac{p_i - p_i'}{c' - c}$. Since the attacker knows all the values on the right-hand side, the attacker can get $t+1$ shares and recover $y$.

One possible solution to avoid this is to ensure that the same message is never signed twice.


Reconstruction vector in Linear secret sharing schemes Suppose we have a policy $A \wedge ( D \vee (B \wedge C))$ with attributes ${\{A,B,C,D}\}$. The set of subsets of attributes which satisfy this policy is ${\{{\{A,D}\},{\{A,B,C}\},{\{A,B,D}\},{\{A,C,D}\}}\}$ of which ${\{{\{A,D}\},{\{A,B,C}\}}\}$ is the set of minimal subsets.

We convert the above boolean formula into a LSSS matrix $L = {\{{\{1,1,0}\},{\{0,-1,1}\},{\{0,0,-1}\},{\{0,-1,0}\}}\}$ according to this(Pg. No 30).

We usually find a vector $g$ such that $g^T \cdot L = (1,0,0)$ for all such authorized subsets such that $\forall i \in [4], (g_i = 0) \vee (g \in Attr)$.

If I understand it correctly, suppose a user has attributes $Attr ={\{A,D}\}$. That means his input vector in this case will be $V = (1,0,0,1)$. Since he does not have $B,C$ those $g_i$s (false attributes) will be assigned $0$ and then we solve the equation of unknowns $g = (x_1,0,0,x_2)$ to get $x_1 = 1$ and $x_2 = 1$.
So in this case, it turns out that $g = V$. Is this the right way to calculate $g$?

Assuming above way of calculating $g$ is correct, if he has $Attr ={\{A,B,D}\}$, then if we proceed with the same procedure as above ( the equation of unknowns will be $(x_1,x_2,0,x_3)$), how do we proceed to calculate $g$ as we then have two cases?. I know that ${\{A,B,D}\} \supset {\{A,D}\}$ as is the case for monotone policies.

Another way is that each subset of the rows of this matrix includes $\mathcal{e} = (1,0,0)$ in its span if and only if the corresponding attributes satisfy the formula. We take the rows corresponding to ${\{A,D}\}$ and find the coefficients $(1,1)$ so that $e$ is in the span. Then why do $\{A,B,D\}$ and $\{A,C,D\}$ have the same coefficients i.e (1,0,1)? I have a vague intuition but not sure.

What is the correct way to calculate $g$?

Notation in this answer is as in the answer to a question on the same LSSS construction.

Is this the right way to calculate g?

You are correct that you solve for $g$ by setting attributes $B$ and $C$ to zero.  What you are actually doing is computing a solution vector, which I will denote by $\mathbf{g}_{\{A,D\}} \in \mathbb{F}^2$, to $\mathbf{g}_{\{A,D\}} \cdot M_{\{A,D\}} = (1,0,0)$ where

$M_{\{A,D\}} =
\begin{pmatrix}
  1 & 1 & 0 \\
  0 & -1 & 0
\end{pmatrix},
$

and then lifting to a solution by padding with $0$s to get a full vector $\mathbf{g}$.  So here you find that $\mathbf{g}_{\{A,D\}}=(1,1)$ (and happens to be unique in this case), and then we pad with $0$s in the corresponding components of the vector $V$ to get $(1,0,0,1)$.  This final solution (after padding) is called a recombination vector for this set.

The vector $V$ is just a way of saying which rows it is permissible to combine in order to try to obtain the target vector $(1,0,0)$.  If you like you can think of finding $\mathbf{g}$ as finding a solution to the equation

$
\mathbf{g} \cdot
\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}
\cdot M = (1,0,0)
$

where the middle matrix is a square zero-matrix replacing the leading diagonal with the entries of $V$.  It is essentially irrelevant that $V=\mathbf{g}$ in this case: the point is that the support (here meaning the indexing set of non-zero components) of the vector $\mathbf{g}$, denoted by $supp(\mathbf{g})=\{1,4\}$, is contained in $supp(V)=\{1,4\}$.

How do we proceed to calculate g as we then have two cases?

If a vector $\mathbf{g}$ works for the smaller set $\{A,D\}$, then it will also work for the larger set $\{A,B,D\}$, since the target vector already lies in the linear span of rows indexed by attributes $\{A,D\}$.  In other words, the same solution works because $supp(\mathbf{g}) = \{1,4\} \subseteq supp((1,0,0,1)) = \{1,4\} \subseteq supp((1,1,0,1)) = \{1,2,4\}$.

Indeed, it is easy to check that your solution $\mathbf{g}=(1,0,0,1)$ also solves

$\mathbf{g} \cdot
\begin{pmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 1 \\
\end{pmatrix}
\cdot M = (1,0,0).$

Thus in general it suffices to compute recombination vectors $\mathbf{g}$ for only the minimally authorised sets: then for any authorised set $A$ we can take any $\mathbf{g}$ for any minimally authorised set which contains the set $A$ and it will also work for $A$.

Then why do {A,B,D} and {A,C,D} have the same coefficients i.e (1,0,1)?

In this example there is only one vector, namely $\mathbf{g}=(1,0,0,1)$ for all three sets $\{A,D\}$ $\{A,B,D\}$ and $\{A,C,D\}$, which means you get $\mathbf{g}_{\{A,B,D\}} = \mathbf{g}_{\{A,C,D\}} = (1,0,1)$.  This is because to combine the vectors $\{ (1,1,0), (0,-1,1), (0,-1,0)\}$ owned by $\{A,B,D\}$, we must have zero contribution from $(0,-1,1)$; similarly, to combine the vectors $\{ (1,1,0), (0,0,-1), (0,-1,0)\}$ owned by $\{A,B,D\}$, we must have zero contribution from $(0,0,-1)$, otherwise the third component will not be $0$ as it must be for constructing the target vector $(1,0,0)$.


Distinguishing attack on CBC-MAC I want to ask about distinguishing attack on CBC MAC, as in the paper published by Ketting Jia, Xiaoyun Wang, Zheng Yuan, and Guangwu Xu: Distinguishing Attack and Second-Preimage Attack on the CBC-like MACs.

In that paper it is said that "if there is a collision in the structure, the MAC function is random function. Otherwise it is a CBC MAC."

What is the meaning of that statement?

As I know, random function does not have collision, but in that statement it is said that if there is a collision, it is random function.

The quoted sentences means: if there is a collision among the MACs of the $2^{(n+1)/2}$ messages submitted, the attacker playing the distinguishing game announces that the oracle is a random function; else announces that the oracle is CBC-MAC.

This works because the messages submitted differ only in their first block, thus will never collide under CBC-MAC, when they collide with odds $0.632\dots$ (by the birthday "paradox") for a random function. The attacker employing the strategy outlined in a game where the objective is distinguishing between an oracle implementing a random function, and an (equally likely) oracle implementing CBC-MAC with a fixed random key, will have an advantage compared to announcing a result at random.

Update: to prove that there are never collisions with CBC-MAC, assume that there is such collision between two messages identical in all but the first block; use that a block cipher with a fixed key is a permutation over the set $\{0,1\}^n$; and conclude that the first block must be identical in the two messages.

So far, this is purely a distinguisher, without much practical applications. However the paper goes on to explain another attack, which I'll illustrate in a simplified version below.

Assume CBC-MAC using messages of three blocks, a block cipher of $n$ bits, and $n$-bit output. The attacker obtains the MAC of $2^{(n+1)/2}$ messages $M_j=j||j||0$ where the first two blocks are $j$ and the third block all-zero. Odds that a collision on the MAC occurs is about $0.632\dots$ (both for a random function and CBC-MAC). If that happens for messages $M_a$ and $M_b$, the adversary submits $M'_a=a||a||1$ and $M'_b=b||b||1$. If the MAC is CBC-MAC, there will with certainty be a MAC collision between $M'_a$ and $M'_b$, whereas odds of such a collision would be $2^{-n}$ if the MAC was a random function.

This allows computing a second preimage of a message with any desired third block, after little more than $2^{n/2}$ queries.

This attack is known as a birthday forgery. It is briefly discussed in ISO/IEC 9797-1, which standardizes CBC-MAC, as early as in the 1999 edition, with attribution to Bart Preneel and Paul C. van Oorschot: MDx-MAC and Building Fast MACs from Hash Functions, published in the proceedings of Crypto 1995.

For in-depth coverage of similar attacks on CBC-MAC, see the work of Antoine Joux, Guillaume Poupard, and Jacques Stern: New attacks against standardized MACs, published in the proceedings of FSE 2003; or/and Karl Brincat and Chris J. Mitchell: New CBC-MAC forgery attacks (preliminary zipped version here), published in the proceedings of ACISP 2001.


Use of ElGamal encryption for signature generation If RSA (textbook RSA that is) generates a digital signature by using the sender's private key, couldn't any cryptosystem (the only two that come to mind are RSA and ElGamal) capable of asymmetric encryption do the same?

For example, I've read that ElGamal is encryption only. Why can't ElGamal encryption (not DSA) do the same that RSA does?

Because the function used for RSA encryption and decryption is commutative. This means that given secret key $sk$ and public key $pk$ for all messages $m$ you have that $$D(E(m,pk),sk)=E(D(m,sk),pk)=m.$$ This means that first encrypting a message with the public key and then decrypting the so obtained ciphertext with the corresponding secret key yields the same as first decrypting a message with the secret key and then encrypting the result with the corresponding public key.

Since the RSA function enjoys this property, one can obtain a public key encryption scheme and a signature scheme using the same function (I ignore padding and stuff like hashing and speak only of textbook RSA). Due to this property, people often wrongly say that in general signing a message is identical to decrypting (often also encrypting) with the secret key.

However, this property does not hold for ElGamal, where the public key encryption scheme and the signature scheme are very different.


Deriving AES key and HMAC key from shorter master key I am working in .NET and as far as I can tell the only choice for key derivation is PBKDF2-HMAC-SHA1.  SHA1's output size is only 160 bits.  But I am implementing authenticated encryption and thus need 512 bits of key material (a 256-bit AES key and a 256-bit HMAC key).  My original idea was to input the password, salt, and a high numberOfIterations into PBKDF2 to derive both the AES key and the HMAC key.

Several people pointed out that I was making an attacker's job easier.  Getting 512 bits of key material from PBKDF2-HMAC-SHA1 would require ceil(512/160) = 4 calls * numberOfIterations.  However, an attacker would only need the AES key to decrypt the message, so he/she would only need to perform ceil(256/160) = 2 calls * numberOfIterations.

I've read two suggestions on how to fix this:

Use PBKDF2-HMAC-SHA512. It would provide enough output for both keys.  Unfortunatley, .NET doesn't seem to support this.
Use PBKDF2-HMAC-SHA1 with the password, salt, and a high numberOfIterations to output a 160-bit master key.  Then use HKDF-Expand to expand the master key into two 256-bit keys.  Unfortunately .NET doesn't provide HKDF-Expand as far as I can tell.

I have read in other stack exchange posts such as this post and this post that one could derive two keys from a master key (MK) by doing the following:

Create 160-bit MK through PBKDF2-HMAC-SHA1 using a user-supplied password, a 160-bit salt, and a high numberOfIterations.
Calculate HMAC-SHA256(MK,"e") -> aesKey
Calculate HMAC-SHA256(MK,"a") -> hmacKey

Would these steps result in a suitable pair of keys for AES-encrypt-then-HMAC-authenticate?

Note 1: I realize that the 256-bit aesKey and 256-bit hmacKey would each only have 160 bits of entropy, but that doesn't seem concerning, as the likely attack path would be on the password, not the keys.
Note 2: Even though .NET does offer HMAC-SHA256, HMAC-SHA512, etc., it does not offer a choice for PBKDF2-HMAC other than PBKDF2-HMAC-SHA1.

Would these steps result in a suitable pair of keys for AES-encrypt-then-HMAC-authenticate?

Yes. That would be fine. It almost is HKDF-Expand, in fact.

However, as you note, by deriving the two 256-bit keys from a 160-bit key your effective security will "only" be 160 bits, since an attacker could brute force the intermediate key. That is not at all a problem realistically, but if you had strict requirements from e.g. some regulations you would want to fix that.

One way would be to derive 320 bits using PBKDF2 (requiring twice the iterations you pass it) and then deriving the two 256-bit keys from that.

The idea of using every other byte of 512-bit PBKDF2 output that poncho mentioned in comments would also work, but there is a slight weakness in key separation. If one of the final keys – the AES or MAC key (or just a byte of either) – leaks somehow, an attacker can look for the other in less time than expected by only calculating one of the PBKDF2 calls for each password.

Again, that is probably not a real problem, because you will want to keep both keys secret and it is only a factor of four in attack time. It does seem a bit untidy, though, and using HMAC/HKDF for key derivation instead is an easy solution.


One-time pad mistake in the transmission? I have a question which arised by analyzing the one-time pad cipher. I encrypt a binary sequence $a_1,a_2,..,a_N$ using a one-time pad with key sequence $k_1,k_2,k_3,...$, so I send $a_1+k_1, a_2+k_2,\dotsc,a_n+k_N$.

Now I make mistake and instead of sending the above sequence I transmit $a_1+k_2,...,a_N+k_{N+1}$. Assuming now that you know that I made this error and that my message makes sense, can you find the message?

Remark: Using a one-time pad means I encipher a message as $b_1b_2\dots b_N$ where $b_j\equiv a_j+k_j \pmod q$ where $q$ is the size of the alphabet, in our case $q=2$.

Assuming that you have not used the one-time pad bits $k_2, ..., k_{N+1}$ to encrypt another message, then the answer is no, the attacker cannot determine the message.

This can be seen by using the normal proof of One Time Pad's security; the bits $k_2, ..., k_{N+1}$ are random and uncorrelated to any other bits the attacker has access to; hence the attacker gets no information on the values of $a_1, ..., a_N$ from the sequence $a_1+k_2, ..., a_N+k_{N+1}$.  That those random uncorrelated bits are not the precise ones that you intended to use is irrelevant.

On the other hand, if the sender realized his mistake, and then sent $a_1+k_1, a_2+k_2, ..., a_N+k_N$, at that point, the attacker could deduce information about the message.  This violates the restriction that "bits from the one time pad are used only once", and this actually allow the attacker to deduce the original message (or its complement).


If Blum Blum Shub is modified to use a prime modulus, is it still secure? The definition of the Blum Blum Shub cryptographically secure pseudorandom number generator is $x=x^2 \mod N$ where $N=p \times q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, the security comes from an attacker not knowing the factors of $N$, but why can't I simply use a single prime number?

I suggest you read the paper about the generator, because that question is answered there:
A Simple Unpredictable Pseudo-random Number Generator, Blum, Blum, Shoup, 1986

They don't have any formal expression of what is called "state compromise extension" there, but they already state in the section 6. The $1/p$ generator is predictable on page 6 exactly the case of using a prime modulus.

Their main point is: Yeah, it might look nice and have nice properties, but you can "calculate forward and backwards in the sequence with about $2|p|$ digits of information."

For more details I suggest reading the paper.


What is a "rewinding argument"? I've been reading a bit about cryptographic protocols and I keep seeing the phrase "rewinding argument". I've been unable to find a good source that would explain what is meant by this. It seems like proofs that use this technique cause trouble against active adversaries? I would appreciate if someone would explain what a rewinding argument is and why this is the case.

Rewinding is used in all sorts of interactive protocols, but it's perhaps easiest to understand it for a zero-knowledge property.

In proving zero-knowledge, we consider a cheating verifier interacting with an honest prover. The prover knows something that the verifier doesn't (say, the factorization of an RSA modulus), and we worry that by cheating, the verifier could gain some information.

The zero-knowledge property means that "whatever the verifier outputs from this interaction, he could have generated without interacting at all". If that's true, then the interaction must not have conveyed any meaningful "knowledge" to the verifier.

So how do we prove the statement in quotes? We say: first suppose you have a cheating verifier $V$. When $V$ talks to an honest prover, it outputs (a distribution of) some transcript $t$. We have to show how to sample the same (or very close) distribution of $t$, without talking to any honest prover. It's not likely that we can analyze the code of $V$ to "figure out what it's doing." Instead, we have to treat $V$ as a kind of black-box. Recall that $V$ is designed to operate in an interactive fashion, so we have to feed protocol messages into $V$, pretending to be the honest prover.

We might feed into $V$ a simulated "message 1" from the prover, and then later a simulated "message 2". Then, after seeing how $V$ responded, we might go back to a previous internal state of $V$ and feed in a different simulated "message 2" -- that's rewinding. We can rewind and invoke $V$ many different times, as long as we are careful to spend only polynomial time overall (assuming $V$ itself is polynomial-time).

BTW, there are some security frameworks (e.g., Universal Composability) which do not allow rewinding.


Why can't you just clone encrypted data and use it? Let's take a contactless card for example (one for public transport lets say (i.e. MiCard)), the data is encrypted on the card and encrypted on the reader as far as I know.

So how come somebody who could read those cards couldn't just clone the card, copying all the encrypted data onto another card and go around using that? It's all encrypted on the card anyway, isn't it?

If this is the case, why don't people do it and wouldn't contactless credit/debit cards and many other pieces of encrypted data be the same?

** Not sure if this was the right area to ask, apologies if it's not.

Long story short, @GuutBoy is correct. Contactless cards are (in theory, at least), difficult to clone.

Cards with a magnetic stripe are effectively "cloned" by the simple act of reading the magnetic stripe. All of the data on the magnetic stripe is read, verbatim, by a reader. And that magnetic data could be replayed to any third party.

Chip-based cards are not the same; when you read from them, you do not get any of the data on the card. To simplify greatly, you ask the card to authorize you for a charge of a certain monetary value. The card generates a token that authorizes you to charge that amount and hands it to you. You pass this to the card processor. The token cannot be used to perform further charges against the card.

In order to clone the card, it's likely you would have to either take the card for a significant period of time or destroy the card in the process. In either of those cases, at that point you might as well simply steal the card.


Cryptographic enforcement schemes using Diffie-Hellman If one wants to set up a decentralized cryptographic enforcement scheme in which the level of 'confidentiality' of information is marked by its position in a poset, why not use Diffie-Hellman to derive the key of a node from its immediate parents?

This is as opposed to the tree-based scheme described in this paper.

In more detail:

You have a poset $X$ from which you want to build a CES. You have a public one-way function $f$. The poset has a top element $r$ and a randomly generated key $k(r)$. Here is how you derive $k(x)$ for all $x \in X$: Let $u \in X$. We can assume one of only two possibilities (we can easily generalize to more than these):

$u$ has one parent $x$. Then $k(u) = f(k(x))$.
$u$ has two parents $x_1$ and $x_2$. Then choose a random DDH-hard
cyclic group $G$ and a generator $g \in G$ and publish $(G, g,
   g^{k(x_1)}, g^{k(x_2)})$. $k(u) = g^{k(x_1)k(x_2)}$.

[edit]

When sending a message, a chain can be used to communicate its position in the poset. Let's say that if a node $u$ has one parent, its 'name' will be denoted $u$ (which will be random). Let's say if it has 2 parents, its name will be the $(G, g, g^{k(x_1)}, g^{k(x_2)})$. Then you publish the chain.

1) The meaning of a poset is that there may also be members $x,y \in X$, where neither $x \leqslant y$ nor $x \geqslant y$. Now consider such incomparable $x$ and $y$ with $parent(x)=parent(y)=w \in X$ and furthermore $u \in X, y=parent(u), x \nleqslant u, x \ngeqslant u$

Now $k(x)=f(k(w))=k(y)$. Then also $k(u)=f(f(k(w))=f(k(x))$, even though $x$ is not a predecessor of $u$. This is clearly a security violation in almost any information-flow control policy.

2) you would need an additional hash function to return the result of the DH exponentiation back to the key-domain.

3) It is not a good idea to change identities while changing keys

4) You will need information on the DAG structure to define the actual function used, which is considered inefficient in HKAS

5) In general, it is not a good idea to have node keys computed from parent keys, instead other secret values are used, to enable efficient key-updates

6) It is more efficient in change management and initial deployment to have anything depend only on one predecessor rather on multiple ones. Remember, the nodes are security levels, not users or computers.


Does simulation extractability require that the protocol have a backdoor in it? As I understand it, one of the properties required to prove UC-security is simulation extractability. One example is the paper by Kosba et al adapting NIZKs to the UC model, but in their construction the witness is encrypted and the ciphertext appended to the proof, and whoever holds the private key can extract the (confidential) witness. (There's also a separate trapdoor that can forge proofs, but for the forged proofs the extractor is not required to work.)

Is this property required for simulation extractability? Would any UC-secure NIZK system also have a backdoor in it? Or am I misinterpreting what simulation extractability means?

Link to the Kosba et al preprint: http://eprint.iacr.org/2015/1093

Extractability inherently requires that the party who holds the extraction trapdoor can extract the witness. Therefore, it is important that the common reference string (CRS) is set up by a trusted party in the real protocol. However, this requirement for setting up the CRS in a trusted way is not only specific to extractability but also required by other notions such as soundness or zero-knowledge (see, e.g., [1] where the fact that the CRS is not set up by a trusted party is used to attack a protocol). Ultimately, you may observe that this trusted setup requirement is not only specific to zero-knowledge protocols, but applies to every protocol which relies on a CRS.

Regarding the UC-secure NIZK part of the question: Roughly speaking, realising a UC compatible zero-knowledge protocol requires to achieve simulation extractability. Therefore, one also has to take care that the CRS is set up by a trusted party in real instances of the protocol.

References

[1] http://stevengoldfeder.com/papers/ZKCSP.pdf


Find a LFSR given 2n (or more) non-consecutive keystream bits How can I calculate the polynomial and state of a LFSR given 2n (or more) non-consecutive keystream bits? It is known to be n bit. If they were consecutive, I could use the Berlekamp–Massey algorithm.

Simple example: n is 7 and I know the keystream is
0...0...1...0...1...0...1...1...1...0...1...0...1...0
where the . is an unknown bit

Any explanation or reference to paper or text book with algorithm will be greatly appreciated.

We are given the sequence $b_i$ for $i$ multiple of $m>1$ with $0\le i<2n\,m$.

If all the given $b_i$ are identical, we can't compute any missing $b_i$ (beyond a wild guess they are all $b_0$), stop.
Build the sequence of $2n$ known bits $c_j=b_{(j\,m)}$ with $0\le j<2n$.
Use Berlekamp–Massey to find a LFSR (polynomial $P$ of degree $k$ and $k$-bit initial state) matching $c_j$.
Find some period $p$ of the $c_j$. For small degree $k$, we can simulate operation of the LFSR until the state repeats (OK to say $k\le40$ on a PC) or we can use baby-step/giant-step (OK to say $k\le75$ on a PC, see final section of this former revision). But more generally, if $P$ factors into a product of irreducible polynomials of degrees $k_r$ (thus with $k=\sum k_r$), then a period is $p=\prod(2^{k_r}-1)$.
Note: For large polynomial, we can still efficiently compute $c_j$ for large arbitrary $j$ (see this), once we have $P$ and starting state.
If $\gcd(m,p)=1$, then $b_i$ also has period $p$, thus $\forall j\in\Bbb N,\ c_j=b_{(j\,m\bmod p)}$ ; it follows that $\forall i\in\Bbb N, b_i=c_{(i\,m^{-1}\bmod p)}$
Note: $m^{-1}\bmod p$ needs to be computed only once, e.g. with the half extended Euclidean algorithm.
Note: with $p=\prod(2^{k_r}-1)$ and $m$ a power of two as in the question, $\gcd(m,p)=1$ always holds. If $\gcd(m,p)\ne1$, it might be possible to find a smaller period, by factoring $p$ and iteratively removing those factors that leave what remains a period, until finding the smallest period $p_\text{min}$ (which depends on the irreducible factors of $P$ being primitive or not, and on the starting point). $\gcd(m,p_\text{min})=1$ allows to conclude without guesswork.

Once $2k$ consecutive $b_j$ are found, an easy option to find the LFSR yielding them is to use Berlekamp–Massey again. The initial state of the LFSR for the $b_j$ (in Fibonacci form) is of course the first $k$ bits $b_i$.

Not covered (yet?): polynomial arithmetic would allow to directly derive the LFSR for the $b_j$ from the one for the $c_j$; and conclude when $\gcd(m,p_\text{min})\ne1$ and partial information on the $b_j$ is available.


What will be appropriate AES padding characters? I am completely noob in terms of cryptography and security.
So I decided AES Cipher for encrypting my data.

I pad my input data String with blank white spaces to fit it in multiples of my cipher blocksize.
So "Hello world" becomes "Helo world                   "

But is it the right way ?
Can some body crack my key, by sending empty Strings ?

But is it the right way?

There are various padding styles for this. The padding must be removed correctly and uniquely. For example, the all-zero padding may remove your actual information. Some of the padding schemes;

append 1 then all zeros
ciphertext stealing padding.
PKCS#7 padding defined in rfc 2898

  For such algorithms, the method shall be to pad the input at the trailing end with k - (l mod k) octets all having value k - (l mod k), where l is the length of the input.

for example;

  ......01
  ....0202
  ..030303

The right way, indeed using a mode like CTR so that you will not need padding. The paddings have security issues like padding oracle attacks in CBC mode.

  Can somebody crack my key, by sending empty Strings?

What is an empty string, all-zero? Why do you need to send all-zero? What is the Mode of operation? There are lots of questions about this. That really depends on your application. For example, it may reveal that you send it again if you are using ECB mode - don't use it. If you use a semantically secure mode you can be fine, however, keep in mind that each mode has its own problems. For example; in CBC mode the nonce must be unpredictable, In GCM, CTR the IV must be unique.

Use modern encryption modes like Authenticated Encryption (AE). AE will provide you Confidentiality, Integrity, and Authentication. AE examples are AES-GCM and ChaCha20-Poly1305 which are in TLS 1.3. AES-GCM internally uses CTR mode that no need a padding scheme.


Small generator for classical Schnorr signatures? I'm implementing classical Schnorr signatures for real-world use. By "classical," I mean that the operations occur in a finite group, with no elliptic curves.
I'm following Schnorr signature and Schnorr group at Wikipedia, and some academic papers.
After choosing $p=qr+1$ with $p$ and $q$ prime I need to calculate a suitable "generator" $g$.
As explained on the Wikipedia page, I set $h=2$ and try to see if $h^r \textrm{mod } p$ is different from 1 (it always has been so far) and that value becomes $g$.
The trouble is, $g$ is (logarithmically) about as large a number as $p$ when chosen this way.
Is there a way to choose a smaller $g$ so that less parameter data needs to be passed around?
If I understand correctly, any $g$ s.t. $g^q=1 \textrm{ mod }p$ ought to work (provided, of course, $g \ne 1$). It's easy to see why $2^r$ works; it's because $(2^r)^q=2^{rq}=2^{p-1}$ which is 1 by Fermat's little theorem.
But can a smaller $g$ be derived somehow?

FIPS 186-4 appendix A.2 gives an algorithm to generate $g$. They are not talking about Schnor signatures but apparently DSA uses just the same kind of finite cyclic groups.

The algorithm really just tries random $1 < h < p-1$ until it finds an $h$ that fulfills $h^r \not\equiv 1 \pmod{p}$. Apparently the probability to find such an $h$ is not too small.

Fermat's little theorem states that $a^{p-1} \equiv 1 \pmod{p}$ for any prime $p$ and $a \in \mathbb{Z}^+$ with $p \nmid a$.

Thus, with $h<p$ you automatically get $p \nmid h$ and therefore $g^q \equiv h^{rq} \equiv h^{p-1} \equiv 1 \pmod{p}$.

I guess the goal cannot be to find a $g$ with a small bit width to save data. As you calculate $g = h^r \text{ mod } p$ with $r$ being random (uniformly distributed), the possible values for $g$ should be uniformly distributed as well.


Akamai's Legacy SSL/TLS Cipher Profiles I'm conducting a research regarding CDN security, and have noticed that in the following document https://community.akamai.com/docs/DOC-5175
A cipher suite named "ak-akamai-pfs-supported" includes the following:

ECDHE-ECDSA-AES256-GCM-SHA384
ECDHE-ECDSA-AES128-GCM-SHA256
ECDHE-RSA-AES256-GCM-SHA384
ECDHE-RSA-AES128-GCM-SHA256
ECDHE-ECDSA-AES256-SHA384
ECDHE-ECDSA-AES128-SHA256
ECDHE-RSA-AES256-SHA384
ECDHE-RSA-AES256-SHA
ECDHE-RSA-AES128-SHA256
ECDHE-RSA-AES128-SHA
AES256-GCM-SHA384
AES128-GCM-SHA256
AES256-SHA256
AES128-SHA256
AES128-SHA
DES-CBC3-SHA

My questions is, do the following ciphers from the mentioned above list do support Perfect Forward Secrecy?

AES256-GCM-SHA384
AES128-GCM-SHA256
AES256-SHA256
AES128-SHA256
AES128-SHA
DES-CBC3-SHA

The few cipher suites you mention don't have PFS since they all use RSA as key exchange. Only the ECDHE ciphers from the list have PFS since they use ECDH as key exchange.