Key Prefix KDF with Counter I don't want to discuss the security problem with MD-based hashfunctions when using them as KDF. Since the existence of SHA3 or Skein hashfunction it is possible to use them as key prefix KDF.

What I mean with key prefix KDF is the following:
In https://eprint.iacr.org/2010/264.pdf you can find it or in short:

KDF(x) = H(x||1)||H(x||2)||...||H(x||n)

H is a Hashfunction, x the seed, the numbers are a counter.
While it is not specified what the counter is exactly is, I have a question.
The Counter starts with 1 and goes to N. How many Bytes is that Counter? Is it a single Byte?

I think you're encountering the difference between an academic paper and an implementable standard like an RFC or NIST Special Publication.

In an academic setting, details like encodings rarely matter. Using a uint8, uint16, or plain old int results in the same security in this case. So the counter can be encoded however you wish.

However, unless you foresee a true need to generate enormous outputs, I would use a single byte and ensure that you return an error if the requested output is larger than 255*(hash length). This prevents the user from mis-using your KDF in an application for which it was not designed.


How to convert random bytes into blocks of numbers without weakening entropy? Let's say you have a, or several random byte(s) 0-255 and would like to derive numbers 0-9 for a One Time Pad (OTP) of them.
What would be a non-naïve approach to represent 256 possible values onto 10 possible values without weakening the underlying security? I am not sure that I simply can discard 6 states of the 256 values to achieve division by 10 without a fraction as result and not weaken security at the same time.
Is there a simple, yet convincing mathematical approach that I could port myself to a programming language to map bytes into blocks of numbers ranging from 0-9 safely?

Yes, it is called the simple discard method or rejection sampling. Basically you generate a byte of randomness, then check if the value is equal to or higher than 250 (the highest multiple of 10). If so, you discard the value and regenerate the byte. If you have a value in the range [0, 250) then you simply use modulo 10 (the remainder after the division). And there you are, a well distributed and secure value.
Of course, this method is not very efficient when it comes to a one-time-pad. Generally the one-time-pad is used over bits. But if you have it over digits then it is easier to use 10 to the power of digits you need, then use the simple discard method to generate the larger value, and then perform the (optional) modular reduction. If you take just enough bits, the modular reduction is not needed. After generating the binary value you can perform base conversion to convert the binary value into digits.
If you think the second method is still not efficient enough, then you can use the optimized simple discard method of which I'm the author.

Note that many libraries have both a method to create a large random number in a range as well as methods to get a decimal string, so in that case you can retrieve all required random digits in just two calls (although you may have to convert the character string into values within an integer representing each digit).


Using simulation proofs I am formulating a simulation based proof, but I'm not sure how much power I can give the simulator. For example if a simulator needs to simulate the output of a symmetric key encryption algorithm then it can just pick a random string of the same length and use that to simulate the output. Would it be possible though to give the simulator a random symmetric key encryption (SKE) algorithm with the same sized output and use that to simulate the value too? Surely these outputs would be indistinguishable too? So the simulator essentially sets up a different SKE scheme and uses that to simulate the original SKE scheme. Is this permitted in simulation based proofs?

Anything is permitted as long as it works. The question you have to ask is what role a symmetric encryption plays in the protocol. If it is decrypted at some stage in the protocol potentially to a corrupted party, then you need to be able to simulate that and have it decrypt to the correct value. If it is never decrypted, then why is it ever used in the protocol?

Sorry for the self-citation, but you can read more about this at: https://eprint.iacr.org/2016/046.pdf.


Constant time multiplicative inverse within a word I was playing with an algorithm which at one step, calculated $f(x) = x^{-1} \mod p$ for $0 < x < p = 2^{64}-59$ (note $p$ is a prime). I used Knuth's Vol 2 Algorithm X algorithm for calculating inverse modulo a prime, using the Extended GCD, but I was wondering if there was a way for making it run in constant time, within a word?

The trick I found online for producing constant time inverses used Montgomery Multiplication, and therefore wouldn't fit within a 64-bit word.

My objective is to write a 64-bit cipher which (is probably insecure, definitely slow, and) uses inversion for confusion and diffusion.

Edit: Specified $p = 2^{64}-59$, a prime.

Edit2: Specified the algorithm attributed to Knuth with link to page which has attribution.

You can compute $f(x) = x^{\phi(p)-1} \bmod p$ in constant time, using $O(\log p)$ constant time modular multiplies.  If $p$ is prime, this reduces to $f(x) = x^{p-2} \bmod p$

BTW: calling it 'Knuth's' algorithm is, in general, not very helpful; Knuth gives hundreds of different algorithms in 'The Art of Computer Programming'.  I assume you mean the Extended Euclidean algorithm?


How to apply IV and tag to protect messages encrypted using AES-GCM? I'm applying the Arduino Crypto Library for the code fragments.

In the above library, example of encryption and decryption using GCM given as follows:

For encryption:

GCM<AES256> gcm;
gcm.setKey(key, sizeof(key));
gcm.setIV(iv, sizeof(iv));
gcm.addAuthData(adata, sizeof(adata));
gcm.encrypt(ciphertext, plaintext, sizeof(plaintext));
gcm.computeTag(tag, sizeof(tag));

For decryption:

GCM<AES256> gcm;
gcm.setKey(key, sizeof(key));
gcm.setIV(iv, sizeof(iv));
gcm.addAuthData(adata, sizeof(adata));
gcm.decrypt(ciphertext, plaintext, sizeof(plaintext));
if (!gcm.checkTag(tag, sizeof(tag))) {
    // The data was invalid - do not use it.
    ...
}

These are my questions:

Should the IV be unique for each 128 bit text or for each message? How should the next IV be generated? Should we increment the IV by one for each message or for each block of 128 bit?
Does adding the IV in authentication data makes it less secure?
Does sending the computed tag by prepending / appending to the ciphertext, create any vulnerability?
What is the standard way to share the IV & computed tag?

1.The IV should be unique for each 128 bit text or for each massage?

Per message.  Using an IV of 0 for the first message, 1 for the second, etc is just fine (no matter how long each message is), and is actually fairly common.

  2.Is adding the IV in auth data makes it less secure?

No, it doesn't.  It also doesn't make it any more secure; however if it makes you feel better, feel free.

  3.Is sending the computed tag by pepending/appending to the ciphertext, creates any vulnerability?

No, it doesn't create any problems; as long as the decryptor can unambigiously derive the computed tag, IV and raw ciphertext, any method of transport is fine.  In fact:

  4.What is the standard way to share the IV & computed Tag?

The most common way is the prepend the IV, and append the computed tag to the ciphertext, and send that as a unit; as above, we don't mind revealing the IV and the tag to an evesdropper; and we'll detect any modification to the IV and the computed tag by an active attacker (except for the possibility that he rolls back the entire message to a previously sent one; GCM can't detect that).

The most common variation I've seen to that is not to send the entire IV, but only a portion (64 bits), and have the other 32 bits shared between the sender and the receiver; this reduces the bandwidth used a tad, and we still can send $2^{64}$ messages per key, which is plenty.  Of course, this is an implementation trade-off, with no security implications; you don't need to follow this example.

Also, unrelated to your question, but the Arduino API is not very well thought out.  For one, in the decryption phase, the application is supposed to ask for a decryption, and then separately ask for the tag validation.  That means that it's up to the application to maintain cryptographic safety; if the application forgets to ask for the validation, then everyone looks like it's working, but you're not actually secure.  This is the sort of 'rake-in-the-grass' behavior that we like to stay away from; if they got this wrong, one can only wonder what other things the crypto library authors messed up on...


The Boneh-DeMillo-Lipton fault attack (RSA CRT) I am trying to understand the Boneh-DeMillo-Lipton fault attack on RSA CRT signature.

Suppose that we sign a message $m$ with RSA-CRT :

$d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$

$s_p = h(m)^{d_p} \bmod p$ and $s_q \not= h(m)^{d_q} \bmod q$ where $h$ is a hash function

By CRT we get $s$ the signature modulo $n=pq$

I don't understand the following assertion :

As $s^e \equiv h(m) \pmod p$ but $s^e \not \equiv h(m) \pmod q$ we can factorize $n$ by $p=GCD(s^e - h(m), n)$.

Can somebody explain to me why $p$ is the greatest common divisor between $s^e - h(m)$ and $n$?

$q$ does not divide $s^e-h(m)$, but $p$ does, so since the gcd must divide both $s^e-h(m)$ and $n$ it's $p$. To be even more explicit, we know that $p$ divides both $s^e-h(m)$ and $n$. The only larger divisor of $n$ that is also divisible by $p$ is $n$ itself, but if $n$ would divide $s^e-h(m)$, then $q$ would also divide $s^e-h(m)$, which we already assumed does not hold.


Why is the El Gamal commitment scheme information theoretically binding? I am a bit stuck on the following claim:

  The ElGamal commitment scheme is information theoretically binding

As far as I understand, an adversary $A$ would win the binding game if it is able to find an $x\prime\neq x$ such that $C(x)=C(x\prime)$.

$C(x)=C(x\prime)$ implies:

$$ (g^r,h^rx)=(g^{r\prime},h^{r\prime}x\prime)$$

How is this impossible to be found? Since generators are cyclic, it should be possible to find an $r\neq r\prime$ that with $g^r=g^{r\prime}$, or am I overseeing something?

How is this impossible to be found? Since generators are cyclic, it should be possible to find an $r\neq r'$ that with $g^r = g^{r'}$, or am I overseeing something?

Yes, you're probably thinking the wrong way, possibly like this: there are values $a,b$ with $a\neq b$ and $a^2 = b^2$. But if you look closely, in this case the base is the same and the exponent differs.

The main arguement here is: If the group order is $t$, and we have $r \neq r' \mod t$, then $g^{r} \neq g^{r'}$. Alternatively: set $x = r' - r \mod t$, which is non-zero modulo $t$. Then $g^{r'} = g^{r + x} = g^r \cdot g^x$. This can't be equal to $g^r$ if $x$ is not zero or a multiple of the group order.

With a fixed generator, the first element in the tuple fixes $r$ - even if you don't know what $r$ actually is. And that in return fixes $h^r$. And for a given ElGamal ciphertext this fixes $m$.


A question about verifier in zero knowledge proof I found an article about zero knowlegde authentication and I have question
ethesis.nitrkl.ac.in/5755/1/110CS0371-2.pdf

It said
"In Cryptography, the Zero Knowledge confirmation/convention is a sort of convention in which one entity (claimant) demonstrates an alternate entity (verifier) that a certain information is genuine separated from the way that it doesn't pass on that the data given is genuine or false."

Does this mean that the verifier does not (and will not) know whether the data from the claimant is true or false? Because using the cave analogy, the verifier will know about the genuineness of the data, since the verifier will see where the claimant will come out from (either from the wrong / right path).

From that paper, what I got is: The verifier doesn't know what the data is, and it also doesn't (and won't) know whether the data is genuine or not

Edit: English is not my first language, so maybe I got the wrong conclusion / translation from that bolded part...

The meaning of this has two aspects:

After running the protocol successfully, the verifier is convinced (with overwhelming probability) that the information is genuine.
The verifier can by no means extract the information from the protocol. It is simply impossible (not unlikely, actually impossible).

Very simplified a zero knowledge protocol goes like this:

First, the prover sends some information to the verifier
Then the verifier generates a random value (often just a single bit) and sends that to the prover
The prover answers based on that random value, and the verifier can check that answer combined with the first value and his random value.

The protocol is set up such a way, that only if the prover truly knows the secret information, he can send the correct answer in the last step with certainty. Otherwise he has to rely on luck. So if the verifier used random values in the second step and the prover didn't know them in the first step, there is a certain chance (often probability $0.5$) that the verification in the end does not work out.

And lastly, the above steps are done multiple times and only if the prover passed all of them the verifier is convinced. With probability $1/2$ per round, the remaining uncertainty after $k$ rounds is $\frac{1}{2^k}$.


Does unbalancing a feistel cipher always improve security? Does it improve security at all? So according to Wikipedia unbalanced feistel ciphers provide greater provable security. Specifically, they state:

  The Thorp shuffle is an extreme case of an unbalanced Feistel cipher in which one side is a single bit. This has better provable security than a balanced Feistel cipher but requires more rounds.

Which is a summary of the paper "How to Encipher Messages on a Small Domain — Deterministic Encryption and the Thorp Shuffle".

Forgive the simplicity of the question I'm about to ask, but as an amateur, to me this  seems counter intuitive. If for each plaintext block we have:

$$L_{i+1} = R_i $$

and

$$R_{i+1} = L_i \oplus F(R_i, K_i)$$

Where F is the round function, then doesn't constraining either $L_i$ or $R_i$ to a single, or fewer bits (given whichever side is smaller, they will swap in the next round) mean that each xor is easier to reverse since only single bits are being altered at a time (and we know this reliably since algorithms aren't secret...)? Does that not make the cipher more susceptible to side channel attacks, essentially becoming more of a stream-like operation?

So, is this actually the case and if so why? Is there any particular implementation of an unbalanced feistel cipher one should avoid - for example, are there optimum sizes for the data size bigger than a single bit?

Actually the article you link to does not say that a balanced Feistel cipher is less secure than an unbalanced one; it says that the security of an unbalanced Feistel cipher is more easily proven, given enough rounds.

Luby and Rackoff have shown in 1988 that a balanced Feistel scheme with only 4 rounds is "perfectly" secure as long as the round functions are "random enough". This deserves clarification: Luby and Rackoff use n-bit blocks, and their results holds up to, at least, $2^{n/4}$ queries (the attacker is allowed to submit up to that number of blocks to encrypt or decrypt to a black box which knows the key, and yet he still cannot predict the encryption or decryption of another value with non-negligible probability). Maurer and Pietrzak, and then Patarin, later showed that with more rounds, one can get as close as wanted to the $2^{n/2}$ limit (6 rounds suffice, as Patarin demonstrated). (Of course, "random enough" round functions are ideal objects whose existence is not clear; existing Feistel-based ciphers use faster functions which are certainly not "random enough", and compensate by adding more rounds.)

By making n big enough, $2^{n/2}$ is large enough to achieve sufficient security (e.g. use $n = 256$).

Morris, Rogaway and Stegers study the problem of encrypting very small blocks; thus, they cannot make $n$ "large enough". They must cope with a small $n$. The maximum theoretical security of a Feistel scheme (balanced or not) is $2^n-3$ queries (there are $2^n$ possible block values; if the attacker knows the encryption of all save two, then he can guess the remaining two with 100% accuracy, because Feistel schemes are always even permutations; this is the only known structural weakness of Feistel ciphers). The authors say quite clearly (end of page 4) that there is no known practical attack on a Feistel cipher with enough rounds, even with small blocks, so the $2^n-3$ security limit is in practice achieved. But they want more than practical security, they want proven security. A security proof works by assuming that the round functions are information-theoretically secure, and sees how the whole cipher stands up under that assumption. The trouble with a balanced Feistel cipher is that such proofs cannot go beyond $2^{n/2}$.

On the other hand, with an unbalanced cipher and many rounds (much more than 6; figures in the article go to about 64 rounds), it is possible to get a security proof close to $2^n$. This does not mean that unbalanced Feistel ciphers are "more secure", only that information-theoretic tools are more easily applied for proving security of an unbalanced Feistel cipher. And a single unbalanced round is certainly not more secure than a single balanced round; quite the opposite: security-wise, a single unbalanced round sucks. But if you accumulate enough such rounds, then you can boost the security proof to higher levels.


Is storing the hash of a key together with ciphertext encrypted with that key secure? Is it secure to store the hash of a symmetric cipher key along with data encrypted with that key? Are there any circumstances or algorithms in which this combination could lead to potential weaknesses -- or is it always a bad idea? Assume the cipher is AES-128 or -192 and the hash is SHA-256, and also assume that the key was derived from a pass phrase.

I think this is generally not a good idea, for two reasons.

First, do not generate a key as a hash of a passphrase.  Where possible, you should try to avoid deriving cryptographic keys from passphrases, as passphrases rarely have enough entropy to make a secure crypto key.  If you must derive the crypto key from a passphrase, then be sure to use PBKDF2 (or similar key derivation function), which is specifically designed to mitigate (but not eliminate) some of these risks, by making key derivation a slow process.

Second, if the key is derived from a passphrase, I do not recommend storing a hash of the key.  This may make it easier to mount exhaustive passphrase-search attacks, including facilitating construction of rainbow tables that map from the hashed-key to the original passphrase.  Instead, simply use authenticated encryption.

If you use authenticated encryption, there's no need to store a hash of the key.  You can tell whether a key is correct by trying to decrypt and seeing whether the decryption is authentic.  If it is authentic, you're good; if it isn't authentic, you've got the wrong key.

And you probably want authentication anyway, so this kills two birds with one stone.


GCM Create M tables and R I am trying to optimize GCM multiplication. This PDF explains GCM:
The  Galois/Counter  Mode  of  Operation  (GCM)
The algorithms are in section 4.1

In algorithm 3 I have to multiply table M [128] with the element P that represents the
polynomial α.
Formulas (3) and (4) appear on page 9. From what I can understand, this would be:

**if V127 =0 then V ← rightshift(V )

else
V ← rightshift(V ) ⊕ R**
The polynomial f would be 0xe1, no?
But in algorithm 3 I do not understand this: M[i] ← M[2i] · P. What would be the value of the element P if it corresponds to the polynomial α?
Hopefully, someone knows some code of the implementation of the tables that I can read. I have not found any code that can help me understand all of this.

The polynomial f would be 0xe1, no?

it is $e1 \mathbin \|0^{120}$ i.e. 0xe1000000000000000000000000000000

What would be the value of the element P, if it corresponds to the polynomial α?

it is 2 reversed i.e. 0x40000000000000000000000000000000


Keys required for cryptography I am reading an article on cryptography at following location:
http://www.entrust.com/resources/pdf/cryptointro.pdf

Historically, encryption systems used what is known as symmetric cryptography. Symmetric cryptography uses the same key for both encryption and decryption. Using symmetric cryptography, it is safe to send encrypted messages without fear of interception (because an interceptor is unlikely to be able to decipher the message); however, there always remains the difficult problem of how to securely transfer the key to the recipients of a message so that they can decrypt the message.
With symmetric cryptography, as the number of users increases on a network, the number of keys required to provide secure communications among those users increases rapidly. For example, a network of 100 users would require almost 5000 keys if it used only symmetric cryptography. Doubling such a network to 200 users increases the number of keys to almost
20,000. Thus, when only using symmetric cryptography, key management quickly becomes unwieldy even for relatively small-scale networks.

How did the author conclude 5000 keys for 100 users and 20,000 keys for 200 users?

The system can be viewed as a complete graph, in which each vertex is a user and each edge represents a different symmetric key.

Thus for 100 users (vertices), you need (100*99)/2 keys (edges). This is roughly 5,000.

To help visualise, consider the image below from Wikipedia. It demonstrates a complete graph with seven users. Hence 21 seperate keys would be required.


What happened to Poly1305AES? Is it obsolete? I've been told that Poly1305AES is a great choice of MAC for constrained (embedded) environments. I'd checked out DJB's writing on it briefly, and have to say that I found its simplicity likeable, performance convincing & security proofs rigorous enough.

But also, libsodium author has told me today that his library won't support this construction.
Because... "it's not used anywhere". I'm baffled by this scarce an explanation.

I'm also confused, since libsodium does support XChaCha20-Poly1305, and AES sure thing — so it has all the primitive pieces; but won't give the combined construction.

Frank Denis also said:

  There is nothing wrong with [poly1305aes], but it's not used anywhere, and it wouldn't have any benefits over existing constructions.

What are those existing constructions? Do I guess correctly, HMAC-SHA2?..

Please shed some light onto the algo; I'm pretty far from advanced cryptography, and this interaction (+ my followup research) only makes me feel "I know that I don't know much".

Poly1305 is a universal hash function. The output of that function cannot be used safely without being encrypted.

In order to encrypt it, any cipher can be used. AES was used as an example in the paper, but the very same paper mentioned:

  Users can switch from Poly1305-AES to Poly1305-AnotherFunction, with an identical security guarantee. All the efforts invested in the non-AES part of Poly1305-AES can be reused; the non-AES part of Poly1305-AES cannot be broken.

In fact, even Bernstein didn’t use this function with AES. The first real-world instantiation of Poly1305 was with Salsa20.

Poly1305 is widely used today, mainly with ChaCha20, a Salsa20 variant.

With AES, it never saw much real-world deployment, and Poly1305-AES has never been part of any standards.

GMAC is very similar to Poly1305, but can benefit from hardware acceleration on many platforms that also provide AES acceleration. This is probably the most commonly used construction today.

On constrained systems, constructions such as AES-CCM are better candidates as the AES core function can be used both for encryption and authentication instead of having to implement two completely different functions.

To recap, Poly1305-AES was just an example. That particular example was not used in practice, as standardized and widely deployed constructions with AES already existed. These were either more compact, or eventually got very efficient due to hardware support.

But Poly1305 is good, especially on hardware that lacks what is required to implement GMAC efficiently (carry less multiplication). So, it is used with ciphers that are also efficient without hardware support, not with AES.


Fully Homomorphic Encryption: Going from an integer to bits I was answering this question Computing Logarithm using homomorphic encryption and I came up with a solution if you had encryptions of the bits of the number that you wanted to take the log of.  But in that situation all they have is a fully homomorphic encryption of the number itself.

I was curious if there was a way to compute encryptions of the bits from an encryption of the number.  i.e. is there some $f$ such that $f(E(x)) = (E(x_1),E(x_2),...,E(x_n))$ where $x_i$ is the $i$th bit of x?

One possible solution for you is to use a Bit Extraction Circuit. The references are framed in terms of MPC but they should be applicable. If you want something more specific/efficient to homomorphic encryption, it will depend on the scheme.

O. Catrina and S. Hoogh, “Improved primitives for secure multiparty
integer computation,” in Security and Cryptography for Networks
(SCN’10), ser. LNCS, vol. 6280. Springer, 2010, pp. 182–199.
O. Catrina and A. Saxena, “Secure computation with fixed-point
numbers,” in Financial Cryptography and Data Security (FC’10), ser.
LNCS, vol. 6052. Springer, 2010, pp. 35–50.
I. Damgard, M. Fitzi, E. Kiltz, J. B. Nielsen, and T. Toft, “Unconditionally secure constant-rounds multi-party computation for equality,
comparison, bits and exponentiation,” in TCC’06, ser. LNCS, vol. 3876.
Springer, 2006, pp. 285–304.


Relation between factors and their sum on RSA In RSA and other crypto based on prime factors. If I would know the sum of $p+q$, would it reveal any more information than just knowing $p\cdot q$?
Edit: I do not know either $p$ or $q$. The question relates to the fact that if I know the sum and the multiplication, can I find the factors $p$ and $q$ faster compared to when I don't know the sum?

Let $n = p \cdot q $ be product of distinct primes $p$ and $q$, of arbitrary size as in the RSA setup.
The RSA public key $(n,e)$ contains both the modulus and the public exponent, so we assume both are known.
Let $b = p +q$. If $b$ is also known, then we can form a quadratic equation as
$$ f(x) = x^2 - b x + n \label{1}\tag{1}$$ by using the following identity:
$$(x-p)(x-q) = x^2 - (p+q) x + (p\cdot q).$$
The solution of the quadratic equation (\ref{1}) is that $p$ and $q$ and can be found by the second-degree formulas using this equation:
$$p,q =  \frac{ b \pm \Delta}{2}$$ where the discriminant $\Delta = \sqrt{b^2 - 4n}.$
It is also possible to directly find the private exponent too! Observe that:
$$\varphi(n) = (p-1)(q-1) = pq - p -q +1 = pq - (p +q) +1 = n - b + 1.$$
Since $e \cdot d \equiv 1 \bmod \varphi(n)$, you can solve for $d$ without computing $p$ and $q$, though those are also cheap to compute if you would still like to use them.

Example:
Let $m = 35$ and $b = 12$. We thus need to solve $x^2 - 12x + 35$, which gives us:
$$\Delta = \sqrt{12^2 - 4 \cdot 35} = \sqrt{144 - 140} = \sqrt{4} =2. $$
As a result:
$$p = \frac{12 + 2}{2} = 7 \text { and }  q = \frac{12 - 2}{2} = 5.$$


Correctness of signle-point Oblivious PRF In the paper Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF, Chase et al. shows that a PSI scheme can be achieved by using an oblivious PRF (OPRF). They summarized a single point OPRF protocol between a sender $S$ and a receiver $R$ that can be used to check if an element $y_R\in Y_R$ has an equivalent in the set $X_S$ as follows:

Let $F(\cdot)$ pseudo-random code that produce a pseudorandom string, and $H$ be a Hash function
Let $a\cdot b$ denotes the bitwise AND operation between $a$ and $b$, and $a \oplus b$ denotes the bitwise XOR operation

Sender $S$
Receiver $R$

 Sample $s \xleftarrow{$} \{0,1\}^\lambda$
Select and input $y_R\in Y_R$  Sample $r_0 \xleftarrow{$} \{0,1\}^\lambda$ and compute $r_1 = F(y_R)\oplus r_0$

$S$ and $R$ engage in $\lambda$-times OT protocol in which $S$ is the receiver and $R$ is the sender. At each step $i\in \{1,\dots,\lambda\}$, $S$ sends the choice bit $s[i]$ to the OT, and $R$ sends $r_0[i], r_1[i]$ as inputs to the OT. The OT returns $r_{s[i]}[i]$ to $S$.

Once the $\lambda$-time OT is terminated, $S$ sets $q$ as the ordered concatenation of $r_{s[i]}[i]$ received, i.e., $q=r_{s[1]}[1]\mid\mid \dots \mid\mid r_{s[\lambda]}[\lambda]$.

$S$ sets $k=(q,s)$ and define the OPRF as: $$OPRF_k(x)=H(q\oplus[F(x).s])$$

In the video presentation of this paper, the authors said that, after the OT exchange, $q$ is in fact equal to: $q=r_0 \oplus[s\cdot F(y_R)]$. So if the input $x$ given to the $OPRF$ function is equal to $y_R$, we have: $$OPRF_k(y_R)=H(q\oplus[F(y_R).s]) = H(r_0\oplus[s\cdot F(y_R)] \oplus [F(y_R).s]) = H(r_0)$$

My question is the following: why after the OT protocol, $q=r_0 \oplus[s\cdot F(y_R)]$?

My question is the following: why after the OT protocol, $q=r_0 \oplus[s\cdot F(y_R)]$?

Let's start with a case-distinction on the first bit of the OTs:

$s[0]=0$: In this case the sender gets $r_0[0]$ back. Written differently we actually get $r_0[0] \oplus 0\cdot F(y_R)[0]$ (because a XOR with a zero doesn't change anything). However we're in the case of $s[0]=0$ so we might as well write $r_0[0] \oplus s[0]\cdot F(y_R)[0]$.
$s[0]=1$: In this case the sender gets $r_0[0]\oplus F(y_R)[0]$ back. Also written differently we get $r_0\oplus 1\cdot F(y_R)[0]$. However we're in the case of $s[0]=1$ so we might as well write $r_0[0] \oplus s[0]\cdot F(y_R)[0]$.

As you can see in both cases we end up with $r_0[0] \oplus s[0]\cdot F(y_R)[0]$ on S's end. All that is left is to apply the exact same logic to the remaining bits of the OTs.


Is there any SRP-like key exchange only using "standard" cryptographic primitives? I am looking into PAKEs (password-authenticated key exchanges), and it seems like SRP (Secure Remote Password) is essentially the de-facto standard.

However, implementing SRP actually requires doing modular arithmetic, and is similar to, say, implementing Diffie-Hellman. That is, you'd have to have constant-time exponentiation algorithms, a fast bignum library, and getting one of any of these subtly wrong and you might have a terrible side-channel attack.

And unlike algorithms like AES or Curve25519, there aren't many crypto libraries that contain a primitive for SRP, so "rolling your own" is often unavoidable anyway.

Are there any PAKEs that instead of using "custom" mathematics like SRP, simply is implemented in terms of more standard primitives, such as "any secure cryptographic hash", "any secure Diffie-Hellman-like exchange", "any secure signature scheme"? It would be a lot more obvious that it's secure - SRP isn't obviously secure at first glance unless you actually follow the reduction to the discrete log problem - and a lot easier to securely implement providing you have secure implementations of the primitives.

For example, I could think of a weak PAKE, where you simply do a Diffie-Hellman key exchange, but both parties attach a MAC to the ephemeral public keys derived from the password. This is obviously secure if the password is strong, but unlike SRP an attacker gains enough information for an offline brute-force attack, and the server has to store the password in plaintext.

I'm looking for whether there are PAKEs similar to SRP in strength that are as easy as the above weak scheme to intuitively understand and implement in terms of other primitives.

The first protocol for password authenticated key exchange that appeared in the crypto community was the Bellovin-Merritt scheme (see also this survey page 4). This protocol is very simple, and might actually suit your need: is is exactly a Diffie-Hellman key exchange, in which the flows are encrypted with a block cipher (using the common password as the key of the cipher), and where the secret key the players agree on is derived by hashing the Diffie-Hellman tuple. The security of this protocol was analyzed several times, in various models (ideal cipher model or random oracle model, in indistinguishability-based framework or simulation-based framework...). Although it does not enjoy a proof of security in the plain model, you might be satisfied with a protocol proven secure in the random oracle model.

In this case, this scheme seems to exactly fit your requirements: you need "any Diffie-Hellman key exchanged", together with "any (good) hash function" and "any block cipher" that allows you to encrypt the flow with the password. Variations of the Bellovin-Merritt scheme that might make it even simpler are presented in this article (they essentially replace the block cipher by a simple one-time pad, and have two variants, one non-concurrently secure and one concurrently secure).

EDIT: so, after discussing with Ricky Demer, this does not quite work yet. A necessary condition for this to work is that the messages generated by the DHKE - which are group elements - should be indistinguishable from random bit-strings. For DHKE over $\mathbb{Z}^*_p$ for some large prime $p,$ group elements can be naturally mapped to a distribution statistically indistinguishable from bit-strings, and existing implementations might already encode these messages as random-looking bit strings (but this would have to be checked). For more sparse groups such as elliptic curves, I believe such a mapping can be done, but it would be more cumbersome from an implementation point of view. I thank Ricky Demer for pointing this out.

The variants presented in this article do not use a block cipher, which gives rise to dictionary attacks when the encoded element does not look random, but using a kind of multiplicative one-time pad: Alice masks her flow $g^x$ by multiplying it with $M^{\mathsf{pw}}$, where $M$ is a group element and $\mathsf{pw}$ is the password (and Bob plays similarly). Here, you do not have to care about how group elements are represented; however, you must perform an exponentiation (with a small exponent) and a multiplication, hence it does not makes a black-box use of the DHKE key exchange.

EDIT:

So, I discussed today with my PhD advisor, who happens to be the author of quite a number of papers in the PAKE area (in particular this paper which I had mentioned). It confirmed what I had started to think: it does not seem feasible to build a PAKE with a black box access to a DH key exchange and symmetric primitives. Somehow, you have to be at least able to multiply two group elements (hence you must know their structure). I cannot prove that it is infeasible, of course, but that is currently unknown in the scientific community, and not believed to be feasible.


What kind of analysis can I perform on my implementation of Salsa20 and Rabbit ciphers? I've implemented both the Salsa20 and Rabbit ciphers in C#. My implementation is for academic purposes and I've tested both of them against the test vectors. I implemented a system that encrypts a file twice, once with each form of encryption. I want to find out what kind of analysis I can perform to test their various aspects such as speed, security, performance etc.

While I understand that some of you might think this is not a good idea, I am doing it purely for academic purposes and this will never be used in a real world system.

I would like to perform some tests where I compare the plaintext and ciphertext and note any observations. I have no experience or idea regarding where to start or what to do. Though I do not need to go into depth on this topic as my professor doesn't require it.

Thanks

ChaCha20 and Salsa20 are both considered secure ciphers and so looking at the keystream will get you nowhere.  What you can do is analyze your implementation:

It should run in exactly constant time regardless of inputs.
There should be no data-dependent branches or array lookups


Is the role of public key/private key determined arbitrarily or mathematically? I have read about conflicting information about the roles of public/private keys.

In one article(Asymmetrical-key algorithms), it says:

  Simply put each party, say Alice, picks a private random value, inputs
  this into a key generation program, and receives two keys. It is
  arbitrary which of these is made public and which is kept private, but
  the privacy of the private key is paramount.

While in many other articles, they suggest that private keys is always for decryption and public keys encryption. Or private keys are for the party being authenticated while public keys are authenticating ones.

So my question is, are private keys called 'private' only because you keep them private, or because they have some mathematical merits that fundamentally differentiate them from their public counterpart?

The web article states

  ..a key generation program (produces) two keys. It is arbitrary which of these is made public and which is kept private.

This second sentence is wrong, especially since it appears in a general discussion about "Asymmetrical-key algorithms" (sic: the closer usual adjective in the cryptographic literature is asymmetric, and the concept is better known as public-key).

In most common forms of public-key cryptography, the public and private keys are very different beasts, and we can't exchange them. Examples:

Public-key cryptography based on the Discrete Logarithm Problem (DSA, ECDSA, EdDSA, Schnorr signature, ElGamal encryption, ECIES..), where there is a direct method to find the public key from the private key: $\text{Pub}=g^\text{Priv}$ (or $\text{Pub}=\text{Priv}\times G$ depending on notation), when that's not possible in the other direction (security relies on that).
Hash-based public key cryptography, for a similar reason.
RSA encryption and signature as practiced, where the public key is $(N,e)$ and the private key is $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ (see RSAPrivateKey in PKCS#1 v2.2). And even if we reduce the later to $(N,d)$ so that the two keys become substitutable, doing such substitution would ordinarily ruin security, because ordinarily $e$ is small, thus guessable. Better methods allow to recover $e$ from $(N,d)$ for size of $e$ up to $29.2\%$ the size of $N$ (see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999), which covers all values of $e<2^{256}$, often considered as a practical upper limit.

In fact, I can only see that the quoted statement applies to a particular cryptosystem: a form of RSA where $e$ in the public key $(N,e)$ is random and large, and the private key is stored as $(N,d)$. That is barely used because it makes the use of either key several times more costly than in regular RSA with small $e$ (in the hundreds for the public key, like 3 to 4 times for the private key), and almost double the storage requirement of the public key.

  Are private keys called 'private' only because you keep them private, or (do) they have some mathematical merits that fundamentally differentiate them from their public counterpart?

The later!

  Is public key always for encryption, and private (for) decryption?

No, because there are other uses of public/private keys than encryption and decryption.

When doing encryption and decryption, the public key is always the one used for for encryption, and the private key is always the one used for encryption.

When signing (or demonstrating one's identity), the private key is always the one used. When verifying a signature (or someone's identity), the public key is always the one used.

In the context of an RSA cryptosystem, the expression "encrypt with private key" is sometime used where there should be "sign" or "apply the private-key transformation $x\to x^d\bmod N$". Same for "decipher with public key" where there should be "verify" or "apply the public-key transformation $x\to x^e\bmod N$". The web article does that without emphasis on the impropriety, and worse for an unspecified asymmetric cryptosystem. That's a sign of lack of rigor in the material, and sadly is very common. It seems some authors believe that all signatures are based on a trapdoor permutation, like RSA signatures are. I've recently seen that in a standard for train tickets under review, where a drawing explains that the prescribed DSA signature verification compares the hash of the message to be authenticated against the result of decryption with the public key (which is plain wrong). That same misconception is there (which mentions DSA two paragraphs after the drawing).


Is SHA-256 secure as a CTR block cipher? Generate a 256-bit random nonce. XOR it with a 256-bit reusable symmetric key. This is x.

We represent numbers in simple binary instead of a counting function. 0 in dec = [256 zeros] in binary, 1 = [255 zeros]1, 23092348 = [241 zeros]1011000000101110001111100, etc.

For each nth block needed for the length of the plaintext, XOR x with n and hash it with SHA-256 to form b[n].

Let p[n] be the nth 256-bit block in the plaintext and c[n] be the nth block in the ciphertext. Then c[n] := b[n] XOR p[n].

Send the unencrypted nonce along with the ciphertext.

To decrypt c[n], XOR it with b[n] to retrieve p[n].

Is this secure? If so, then why do we need AES-256?

If this is not secure, then is there any mode of operation for which SHA-256 is secure as a block cipher? Specifically, it would need to be used in cipher feedback, output feedback, or any other mode that only uses the cipher in the encryption direction.

Well, as far as we know, the mode you suggest should be secure.  Now, to be honest, AES256 versus your mode isn't quite a fair comparison; your mode gives somewhat less theoretical security; if you encrypt a known $2^n$ block message, the key can be recovered with $2^{256-n}$ effort; however, this observation doesn't really affect the practical security.

However, as for why AES might be preferable:

AES is faster.  Performance, of course, varies wildly between platforms and implementations; but taking as an example the CryptoC++ benchmarks, we see AES256 listed as 18.2 cycles per output, while SHA256 takes about 31 cycles per output.  Note: SHA256 is listed as 15.8 cycles per byte; however, that is bytes of input; a single SHA256 compression evaluation takes 64 bytes of input, and hence takes 1011 cycles; in your use, you use a single SHA256 compression evaluation to generate 32 bytes of keystream; hence 1011/32 = 31.6 cycles per byte of output.
AES can be used on contexts other than counter mode.  That is, AES is invertable (if you know the key); that sometimes comes in handy.
However, the most important point is: AES has been far more extensively analyzed in this context.  SHA256 has been analyzed fairly heavily for collision resistance; however, I don't know if anyone has really looked at the question "if we have a large number of hashes of related but unknown images, can we gdeduce what the image is?".  With AES, we known that people have been attacking it with this question in mind.


AES-128 as compression function in Merkle-Damgard construction Using a compression function $f : A × A → A$. A basic version
given by:

$W_0 = IV$
$W_1 = f(W_0, m_1)$
$W_2 = f(W_1, m_2)$
...
$W_n = f(W_{n-1}, m_n)$

$W_n$ is the output of the hash function, $m_1,m_2 . . . m_n$ is the message and $IV$ is a constant.

What would be the simplest way to implement AES-128 as the compression function? And would it be one way?

Excuse my ignorance, I am very new to the topic. My very wild stab in the dark is that AES-128 can be used in a way that feeds its own produced ciphertext blocks back into itself as the key.

This short thesis describes some of the basic ways in which to use the Merkle-Damgård construction based on block ciphers. The construction that is commonly used in MD5 and related constructions is in fact an instance of the Davies-Meyer construction. This could be directly applied to your construction (you have to add length padding and a length field to get a secure hash function of course) as follows: let $E_k(m)$ be a block cipher (like AES) with key $k$ and message block $m$, then we take $f(W_i) = E_{m_i}(W_{i-1}) \oplus W_{i-1}$ for $i=1,\ldots n$. This way we get a secure hash function, provided $E$ is a secure block cipher in the appropriate sense (essentially indistinguishable from a random permutation).


AES256-CBC vs AES256-CTR in SSH I used AES256-CBC to SSH to a remote server. Recently, it stopped working with the following message:

no matching cipher found: client aes256-cbc server
aes128-ctr,aes256-ctr,arcfour256,arcfour,3des-cbc

When I used AES256-CTR as a cipher to SSH to the server, it worked as expected.

I read this article which outlines the following:

  CBC (Cipher-block chaining)
   Encryption parallelizable: No
   Decryption parallelizable: Yes

  CTR (Counter)
   Encryption parallelizable: Yes
   Decryption parallelizable: Yes

Is “Encryption parallelization” necessary in SSH?

Any other advantages of AES256-CTR over AES256-CBC used in SSH except being more robust against padding oracle attacks?

Other advantages of CTR are:

easier to decrypt from a certain offset within the ciphertext
no randomness requirements for the nonce

nonce can be calculated, e.g. be a simple counter
nonce can be a message identifier

$E = D$: encryption is the same as decryption, which means

only encryption or decryption required from the block cipher
less logic required

no padding overhead or mechanism required
key stream can be pre-calculated (latency advantages)

Draws:

sequential speed the same (about the same number of ciphertext blocks)
cryptographic security (when used properly)

Disadvantages:

nonce reuse is catastrophic, confidentiality is completely lost
leaks somewhat more information about the size of the plaintext
multiple, slightly different schemes with regards to IV creation and the method that the nonce is used
still less common in libraries or known by (starting) developers

Another questionable disadvantage is that CTR has no error propagation, but that should probably be considered an advantage by now; if you want integrity, use an authentication tag (MAC or signature).

You can attack CBC and CTR using different methods, with different consequences. If CBC mode has problems in a certain protocol, then switching to another mode has its advantages of course. See the answer of Thor for good reason to switch to CTR for OpenSSH specifically.

That's probably a better reason to disable CBC than the reasons given above. If you want to know for sure, you should ask the OpenSSH developers though (or the person that disabled CBC-mode, anyway).


Simulation based proofs: Simple examples I am aware that,(in theory) in order to proof that a scheme is secure using simulation based proof we replace an adversary in real world with a simulator in ideal world. Then we try to show that their view are (computationally) indistinguishable (if the scheme is secure).

What I need is some simple examples (in zero knowledge or secure multi party computation) that use this idea to proof. So how the simulator is constructed, why sometime we use an adversary to interact with the simulator are not clear to me.
Any reference to a paper or explanations would be much appreciated.

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.


RSA: Private key given public key, plain text, and cipher text with no padding? Are there attacks which will return the RSA private key when the attacker knows the public key, plain text, and cipher text when no padding is used in the RSA algorithm?  If yes, what are the known attacks, under what conditions have they been successfully implemented, and what other cryptographically-secure asymmetrical encryption algorithms will produce identical cipher texts from the same plain text without the attacker being able to determine the private key through knowledge of the public key, the plain text, and the cipher text?

It is not important that the attacker knows the plain text or the cipher text because they will have access to that information along with the public key.  What is important is that the private key can not be obtained and that the public-key encryption results of identical plain texts are the same.

For reference, the asymmetrical encryption usage is a subset of an algorithm which requires the characteristics specified above.

While there is a related question, there was no accepted answer and other responses to that question and similar questions caveat their answers with "when properly used", i.e., when RSA is implemented with padding:  Finding Private key in RSA with public key, cipher text and plain text

No there is not.

First of all the key size needs to be bigger then the message otherwise RSA will not work

Remember one thing, if you have a public key you can have as many clear texts and cipher texts as you want. This is because everyone can use your public key to cipher a message. So if there was a method were by knowing the public key, clear text and cipher text you could discover the private key RSA would not be used. The question of whether the Padding is used or not is irrelevant. Knowing the public key you can cipher the messages using padding or no padding it is your choice. I am sure that in java you will have providers that implement RSA with no padding so you right now can get millions of clear texts and cipher texts from any public key.

Now why this can't happen:

$C^b = M\ mod\ N$

Being C the ciphertext, b the private key and M the clear text. Then you get

$b = \log_c M\ mod\ N$

And this is the problem. This is discrete log which is in NP. So you can't solve this in polynomial time even if you have infinite number of ciphertexts and clear texts


Cryptanalysis Affine Cipher: Brute-Force Search Vs. Meet-in-the-middle Affine Cipher:

$Enc(x) = (ax + b) \mod m$

$Dec(x) = a^{-1}(x-b) \mod m$

For a brute-force key search, we need to do $a \cdot b$ encryptions in the worst case.

For a meet-in-the-middle attack, how many encryptions/decryptions do we need to do in the worse case?

Meet-in-the-middle attack definition:  Affine cipher can be broken up into two separate encryptions and decryptions.

$Enc(x) = (ax)\mod m = c_1$

$Enc(c_1) = (c_1 + b) \mod m = c_2$

$Dec(c_2) = (x-b) \mod m = c_1$

$Dec(c_1) = a^{-1}(c_1) \mod m = x$

Now you can start by encryption x over all possible values of $a$ and decrypt $c_2$ over all possible values of $b$ then compare the two tables and find a match over $c_1$

Which now I realize has answered my question that it uses $a + b$ encryptions.

Side question:  How is $a^{-1}$ calculated?  $m - a = a^{-1}$ or maybe $m - a \mod m = a^{-1}$

I don't know what you mean by a 'meet-in-the-middle' attack.  The obvious way to attack this cipher is a known plaintext attack, that is, encrypt any two distinct plaintexts $x_1, x_2$ (and hence two encryptions), getting their encryptions $y_1, y_2$ :

$y_1 = (a x_1 + b) \mod m$

$y_2 = (a x_2 + b) \mod m$

and solve for $a, b$ as:

$a = (y_1 - y_2) (x_1 - x_2) ^ {-1} \mod m$

$b = (x_1y_2 - x_2y_1) (x_1 - x_2) ^ {-1} \mod m$

Now, as for your side question of what $a^{-1}$ means, well, that is the modular inverse of $a$; if we claim that $c = a^{-1}$, this is equivalent to claiming that $a \cdot c = 1 \mod m$

The modular inverse of $a$ can be found efficiently (given a, m) by the Extended Euclidean Method


Different padding rules for Merkle–Damgård and Keccak/sponge function We learned that length padding was used in Merkle–Damgård  where after padding with zeros another block is added that contains the initial length of the input. This is supposed to prevent same hash values for the different inputs $x \ne x0..0$.

Then again for Keccak we learned it is possible to use simple padding (e.g. add $10..0$). Why is that possible for sponge functions? Isn't it still possible to find two different inputs that will be padded to the same value and then deliver the same hash?

Please be quick with your answers - I'm preparing for my exam tomorrow. (And this is a question that could be asked and that I cannot answer...)

Actually, the Merkle–Damgård construction also specifies a padding bit after the message. The length is there the ensure that a padded message cannot be the suffix of a different longer message. A collision at the prefix leads to a collision in both messages.
With a padding bit, a singe byte message 0x30 vs a 2 byte message 0x30 0x00 are padded to 0x30 0x80 and 0x30 0x00 0x80, ensuring the compression function input is not the same for that block, even without the message length at the end of the padding.
The sponge construction does not require the same message suffix protection because of the way it mixes the input into the state. The size of the state as well as how much data is mixed/squeezed (block size) determine the chance of both a state collision as well as an output collision.
Example collision over multiple blocks
Here we have a toy hash function with a 48-bit block size and 48-bit internal state size. It has no length padding, but does use a single bit padding after the message. The hash is not secure, and suffers from a collision between "THIS IS NOT " and "ENACT ", which are unpadded 2 block and 1 block inputs to the compression function:
Message 1 "THIS IS NOT A TEST!", length 19 bytes (152 bits):
initial value     Block 1 "THIS I"  Block 2 "S NOT "
0x67452301AB89    0x544849532049    0x53204E4F5420

** state collision here **

Block 3 "A TEST"  Block 4 "!" and padding bit
0x412054455354    0x218000000000

Hash Output
0xFE25B6A1C8C0

Message 2 "ENACT A TEST!", length 13 bytes (104 bits):
initial value     Block 1 "ENACT "
0x67452301AB89    0x544849532049

** state collision here **

Block 2 "A TEST"  Block 3 "!" and padding bit
0x412054455354    0x218000000000

Hash Output
0xFE25B6A1C8C0

Because the last 2 input blocks are the same and (since the padding is the same), the state collision at the unpadded prefixes causes a collision in the outputs.
We modify the hash function to add the length; we save the final 2 bytes of space for the length, for a 65535 bit message length limit:
Message 1 "THIS IS NOT A TEST", length 19 bytes (152 bits):
initial value     Block 1 "THIS I"  Block 2 "S NOT "
0x67452301AB89    0x544849532049    0x53204E4F5420

** state collision here **

Block 3 "A TEST"  Block 4 "!" and padding bit and length
0x412054455354    0x218000000098

Hash Output
0x7F266204EDAF

Message 2 "ENACT A TEST", length 13 bytes (104 bits):
initial value     Block 1 "ENACT "
0x67452301AB89    0x544849532049

** state collision here **

Block 2 "A TEST"  Block 3 "!" and padding bit and length
0x412054455354    0x218000000068

Hash Output
0xE7D693B5011B

Once the length is added to the padding, it prevents this from happening in the output, even though there is a state collision. As above, the padding bit 1 prevents near identical messages with different lengths of trailing 0 bits from being processed the same way in the compression function, which will cause a collision at the block level.
Keccak uses a much larger state and block size, say 1600-bits and 1088-bits (for a 256-bit hash). The chance of an internal state collision is much less than the security provided by the hash size, so a length is not required. Not having a length padding also simplifies implementations, since you do not need to keep track of the data you are processing. The padding bit 1 is still required for the same reason as an MD hash. The final padding bit (in 10*1) is required to prevent identical messages from causing a collision when the sponge rate is different, this would not be required if the rate was fixed.
For most MD hashes, the state and output are the same, with a larger block size, this means the chance of a state collision is most likely higher than the specified security level of the hash, hence the strengthening by adding the length.


What is the computational cost of a public key certificate signature verification? What is the computational cost of a certificate signature verification in terms of exponentiation, multiplication and other computation operations?

It very much depends on the asymmetric cryptosystem used, and its parameters.

With RSA using small public exponent (which is typical), the cost of verifying a certificate (knowing the signer's public key) is dominated by a few (typically $17$ or $2$) modular multiplications (for $e=2^{16}+1$ or $e=3$) with arguments of the size of the public modulus. With the Rabin cryptosystem, that goes down to a single modular multiplication (or even less with Bernstein's lifting). With the most classical algorithm, one modular multiplication for $n$-bit public modulus costs $\approx 2\cdot(n/w)^2$ multiplication-and-addition with $w$-bit multiplicands and $(2\cdot w)$-bit result. That is often low enough for practical use even on a modest 8-bit CPU  (e.g. about $70.000$ multiply-and-add for RSA with $n=1024$-bit modulus, $e=3$, $w=8$).

Most other asymmetric cryptosystems require significantly more work from the verifier, for equivalent security. They are typically implemented using a 32-bit CPU or/and a cryptographic co-processor.

For example, with DSA as defined in section 4 of FIPS186-3, an $n$-bit modulus, and a $h$-bit hash, the cost of verifying a certificate is dominated by two modular exponentiations with $h$-bit exponents and $n$-bit modulus, each using $\approx 1.5\cdot h$ modular multiplications with $n$-bit public modulus (assuming a common, basic exponentiation algorithm). With $h=160$ and $n=1024$ (the minimum specified), that's over 200 times more work than for 1024-bit RSA with $e=3$ (which security is lower, but in the same ballpark).


Breaking RSA using Chinese Remainder Theorem When the same message is encrypted for three people who happen to have same public key but different values of n, it is possible to get the value of message by using Chinese Remainder Theorem.

Wherever I have read about this technique, it says that the message value should be smaller than individual values of n. Will someone please elaborate why this restriction? And why does this technique not work if message is greater than any value of n?

I guess you are refering to the case where three people have the following public keys : $(n_1, 3)$, $(n_2, 3)$ and $(n_3, 3)$ (yes, $e = 3$, and this attack is one of the reasons we don't use $e = 3$ anymore).

In this case, if the same message $m$ is sent to those three persons, we have the following system :
$$
\left\{
    \begin{array}{ll}
        c_1 = & m^3\mod n_1 \\
        c_2 = & m^3\mod n_2 \\
        c_3 = & m^3\mod n_3 \\
    \end{array}
\right.
$$

Applying the CRT to
$$
\left\{
    \begin{array}{ll}
        c_1 = & x\mod n_1 \\
        c_2 = & x\mod n_2 \\
        c_3 = & x\mod n_3 \\
    \end{array}
\right.
$$
with $x = m^3$ will give you $x = m^3\mod n_1\times n_2\times n_3$

However, we know that $m \lt n_1,\ n_2,\ n_3$ so we have $ m^3 \lt n_1\times n_2\times n_3$ so a simple cubic root will give us the original message.

If the message is greater than any $n_i$, you wouldn't be able to recover it with a simple cubic root because you would have a modular result.

Today, we usually use $e=2^{16} + 1 = 65537$ which make this attack much more difficult to apply.


Authenticated encryption with forged verification key Is it part of the (or a common) security model of symmetric authenticated encryption to prevent an adversary from exhibiting a decryption/verification key that makes a given genuine ciphertext verify, yet deciphers differently than it does with the key used to produce that ciphertext?

If not, are some common symmetric authenticated encryption schemes vulnerable to that, and under what hypothesis (known plaintext, chosen plaintext, known genuine encryption key..)?

The question comes in the context of determining if symmetric authenticated encryption followed by signature provides plaintext integrity verifiable by a third party, handed ciphertext, an alleged symmetric key, and ciphertext signature, and knowing the public key.

Suppose we had a 384-bit block cipher $B_k$.  (Making this practical with a 512-bit block cipher like Threefish-512 is left as an easy exercise for the reader.)

For $k_0, k_1, m \in \operatorname{GF}(2^{128})$, define $H_{k_0,k_1}(m) = k_0 m + k_1$, a standard secure polynomial evaluation one-time MAC for a one-block message.

For nonce $n \in \operatorname{GF}(2^{384})$, plaintext $p \in \operatorname{GF}(2^{128})$, and key $k$, define $$F_{k,n}(p) = (p + k_2, H_{k_0,k_1}(p + k_2)),$$ where $$k_0 \mathbin\Vert k_1 \mathbin\Vert k_2 = B_k(n).$$

Under standard assumptions, $F_{k,n}$ should be a secure authenticated encryption scheme, on a limited message space, built roughly as an encrypt-then-MAC composition.  Decryption is the obvious $F_{k,n}^{-1}(c, t) = c + k_2$, to be done only if $t = H_{k_0,k_1}(c)$.

Note that we can also phrase this as

\begin{align*}
  F_{k,n}(p) &= (c, t), \quad\text{where} \\
  c &= p + k_2, \\
  t &= k_0 p + k_0 k_2 + k_1.
\end{align*}

Our task as an adversary, given legitimate ciphertext $c$ and tag $t$ (authenticated, say, by a signature), and forged plaintext $p'$, is to find $k'$ and $n'$ so that $F_{k',n'}(p') = (c, t)$.  We obviously must have $k_2' = p' + c$; then

\begin{align*}
  t &= k_0' p' + k_0' k_2' + k_1' \\
    &= k_0' p' + k_0' p' + k_0' c + k_1' \\
    &= k_0' c + k_1',
\end{align*}

so if we pick $k_0'$ arbitrarily we must have $k_1' = t + k_0' c$.  If we further pick $k'$ arbitrarily, we then find that $n' = B_{k'}^{-1}(k_0' \mathbin\Vert k_1' \mathbin\Vert k_2') = B_{k'}^{-1}\bigl(k_0' \mathbin\Vert (t + k_0' c) \mathbin\Vert (p' + c)\bigr)$ will give the ciphertext and tag we desired.

If you were watching carefully, which you presumably were because you're not new to this game, you probably noticed that I granted myself the latitude to pick the nonce freely.  Is that cheating?  I don't know—it's not clear what the context of your question is, how it fits into a protocol.  Certainly it would be foolish not to sign the nonce too, but maybe the nonce is implied as a message sequence number here, and the designer figured that it would be space- and bandwidth-efficient to omit it from the message on the wire and consequently also omitted it from the inputs to the signature.


Security services provided by digital signature Which of the security services can be provided by digital signature?

data integrity
non-repudiation
sender authentication
receiver authentication

I think it can provide non-repudiation. Because receiver cannot deny the message as it was assigned by the sender.
Am I right? Are the other services provided by the digital signature?

The Digital signature provides following services :
1. Non forgeable : No one else other than signer can sign it
2. Sender Authentication : Signer deliberately signed the document as it uses private key
3. Data integrity : The algorithm uses hashing functionality
4. Non repudiation : Signer cannot claim he/she didn’t sign it
5. Tamperproof : Document cannot be altered after signature
6. Non malleable : Signature cannot be cut /paste to another document
7. Receiver Authentic : No as it uses only receiver public key

Hope this helps


How to run a (provably probably) secure global referendum? The following question is extremely broad and speculative, for which I apologize, but it strikes me as exceedingly important, so I will ask it nonetheless.

Suppose an event of global significance took place, like the detection of an Earth-threatening asteroid or an alien invasion, and humanity were to need to decide collectively how to respond to it. Suppose further -- as is quite likely -- that (a) some individual nation states (US, UK, RU, CN etc) would attempt to control the global response, but (b) citizens of other states would be skeptical of whether the "leader" states' proposals were in their own best interest. In such circumstances, existing political arrangements like the United Nations probably might not suffice to achieve a mechanism for arriving at a true "consensus" that would be (approximately) universally recognised as such. Is there a plausible cryptographic mechanism for conducting  a global referendum that would be (approximately) universally recognised as legitimate?

Some of the issues that I am trying to get at:

What sort of cryptographic guarantee, if satisfied to a reasonable degree of certainty, would ensure "legitimacy"? A presumably-unattainable example illustrates what I mean: if a cryptographic protocol could ensure adherence to the principle of "one person one vote", while simultaneously permitting a sufficiently large fraction of the human population to vote, I would venture to guess that the outcome of the election would enjoy a certain degree of "universal" legitimacy.
Although a layman in cryptography, I'm still well aware that when I interact on the internet I "leak" some information that would suffice to identify me uniquely to a high degree of certainty. (My persistent logins, browser cookies, ...) What fraction of the human population could be identified uniquely, with what degree of certainty, using a cryptographic protocol that could ensure anyone can vote once and only once?
Can and should ordinary, run-of-the-mill elections like those held in the United States for selecting our President, be conducted online? If not, why not? In terms of provable (albeit probabilistic) guarantees about how electoral outcomes compare to the preferences of the electorate, are there any valid reasons to prefer paper ballots to electronic ones? If so, what infrastructure changes could be adopted that would allow us to leverage the efficiencies of online voting? Do we need an international public key infrastructure with private key issuance tied to state identities? Something else?

Regarding the 3rd part of your question, "Can and should ordinary, run of the mill elections be conducted online ..." - If one thinks of an election as a problem around the issue of preserving the privacy of many inputs (a people or population's votes) while correctly producing the right result (i.e. correctly tabulating the outcome of the election) and moreover, if you would like to do this without relying on a trusted central authority (like the election commission) - there are some central results in cryptography that prove the possibility of such a thing under different adversarial assumptions, starting with the landmark paper of Goldreich, Micali and Wigderson entitled "How to Play Any Mental Game - A Completeness Theorem for Protocols with Honest Majority" - this result falls under the general moniker of "Multi Party Computation" (MPC), and represents a provably positive result for MPC with honest majorities.
Since this paper, MPC has evolved quite a bit and has been promoted, among other things, as a means for secure voting - the more recent SPDZ protocol of Damgard, Pastro, Smart and Zakarias is secure against "active static adversaries" and is able to tolerate corruption of up to n − 1 of the n parties involved in the computation.
In terms of successful applications, the following outlines one of the first applications of MPC techniques (the Danish sugar beet auction) "https://www.cs.purdue.edu/homes/aliaga/cs197-10/papers/bogetoft.pdf"


Would this mode of operation be safer? Here the key stream is used as keys for the second level of block cipher encryption.

I guess this is not vulnerable to:

padding oracle attack because it is basically counter mode
stream cipher attack, because it isn't just simply XOR-d
malleability, because XOR-ing something on the ciphertext changes the entire plaintext

A significant disadvantage is that it needs a new key expansion for every element of the keystream.

Am I correct in the above?
Are there any more advantages to this architecture?
Any further disadvantages?

Explanation: I modified the standard CTR mode by replacing the XOR with a full block cipher, which has the Keystream(i) values as keys for encrypting or decrypting the successive blocks of plaintext/ciphertext.

No the mode would not be more secure (than what?).

I guess this is not vulnerable to:

padding oracle attack because it is basically counter mode

That's not correct. As the input of a block cipher is always a full block, you would need to pad the plaintext. Therefore you would likely be vulnerable to padding oracle attacks; they are not avoided by the mode itself.

stream cipher attack, because it isn't just simply XOR-d

Although you would not be vulnerable to a many-time-pad if the nonce is repeated, you would of course still leak information on each block of ciphertext that is identical, at the same location. That's slightly worse than e.g. CBC mode, where a change in plaintext would change all next ciphertext blocks if the IV is ever repeated.

malleability, because XOR-ing something on the ciphertext changes the entire plaintext

It doesn't, it just changes on block of plaintext at the same block offset. You would still be malleable if you would change the entire plaintext by the way (imagine encrypting a single bit, 0 for false or 1 for true!). So you need to expand your ciphertext - usually with an authentication tag - to avoid malleability. This is not a description of an authenticated cipher.

A significant disadvantage is that it needs a new key expansion for every element of the keystream.

Correct. And because you are using a lot of keys, you may run into trouble with regards on how the key space needs to be treated for a specific cipher. You would definitely worry about keys repeating simply due to the birthday paradox.

Are there any more advantages to this architecture?

Not that I see, it adds an additional round that introduces problems, while solving none; counter mode is already considered secure. With double the additional rounds + a key schedule per block it is rather expensive for what it tries to achieve.

Any further disadvantages?

I don't think we need more disadvantages, but I'll show some for learning purposes.
One disadvantage is that your key and block size need to be identical. So using e.g. AES-256 is not possible (even if it would be advisable because you may not want to use a cipher that is vulnerable against related key attacks, even if those are mostly theoretical in nature).
You would lose the pre-computation benefits of counter mode, where you can cache the key stream. You can still do that of course, but the last block encrypt / decrypt can only be performed once the plaintext is available.


Is it necessary to worry about timing attacks when comparing SHA256 or Argon2 hashes? It seems to me that a timing-safe way to compare any two strings is to take a secure hash of both of them and then compare the result.  I would expect that the initial hashing would render any timing attack non-exploitable.

It also seems that when hashing passwords, there is no need for a timing-safe comparison of the hashes, since the salt (which is secret) means that the attacker does not know what is being compared.

Is this intuition justified, or is it incorrect?

Comparing hashes of strings does not fully defeat timing attacks.

For example, if we try to find a password by timing attack of

if (strcmp(sha256str(input),sha256str("honey7dew"))) ...

where sha256str outputs the SHA-256 hash of its input as a 64-char C string in hexadecimal (4 bits per char), and we initially do not know "honey7dew" but suspect that string might be a password with low entropy, we can do the following (assuming we can guess the number of characters matched by strcmp)

let k = "" (the hash prefix known so far)
for each password p in a list of common passwords, by decreasing popularity

let h = sha256str(p)
if h starts with k

submit p as input and find the number n of matching characters
if n is 64, p is the password, stop
set k to the first n characters of h

and it will find the password with only a few hundreds of online submissions (this can be improved significantly by avoiding submission of p that we know are not right, because we previously submitted a p0 with h0 matching h over at least 1 more character than k is).

Update per comment: the attack works just the same if the hash is salted, and the salt known to the attacker (but if there are restrictions to the number of online queries for a given salt, these restrictions might make the attack impractical).
If the hash is entropy-stretching (e.g. Argon2), the attack essentially allows to find the "honey7dew" low-entropy key/password with the same computational cost as if as if its hash was known, replacing that knowledge by a moderate number of online submissions.
If "honey7dew" is replaced by something with high entropy (hopeless to guess), there demonstrably is no attack enabled by timing of the comparison: if there was one, it would break the first preimage resistance of the hash.
If the salt is unknown to the attacker (that's often called pepper) and large enough, it is essentially an extension of the the key/password, and again there demonstrably is no attack enabled by timing of the comparison.


What is a fast good-uniformity hash function that if it's seed and it's hash values are unknown, can be strong as cryptographic hash functions? The hash function is for an application that the input to the hash function is from a user's, hence the user can control the collisions, but the question is that if the collisions, the hash function's outputs, the hash function's seeds are unknown for the user, can there be a (fast and good uniformity) hash function that will prevent the user from making intentional collisions, even if the user knows the hash function name?

I thought CRC would fit here because of it's error-detecting ability (requiring good uniformity and diffusion), but it's somewhat slow on architectures that doesn't support CRC instructions, and above that I am not sure that it's secure enough if it's initial value is unknown.

Is there such hash function that fits the requirements (fast, uniformity and secured for such case)?

A universal hash family[1] (paywall-free) $H_r\colon U \to S$ is a set of functions on an input space $U$ into a hash space $S$ indexed by a random $r$ so that the collision probability $\Pr[H_r(a) = H_r(b)]$ is bounded by a small constant like $1/\#S$ for any distinct $a \ne b$.  Sometimes, we are more concerned with a bound on the difference probability $\Pr[H_r(a) - H_r(b) = \delta]$ for any inputs $a \ne b$ and difference $\delta$, where $S$ has some group structure, e.g. if we are going to use this to make a message authenticator[2]; this implies a bound on the collision probability by choosing $\delta = 0$.

A typical example is a polynomial evaluation hash:

Fix a field $k$, let the hash space $S$ be the field $k$, and let the input space $U$ be the set of polynomials of degree at most $\ell$ over $k$ with zero constant term; then define $H_r(p) = p(r)$ with $r$ uniformly distributed in $k$.  If $H_r(p) = H_r(q)$, then $p(r) - q(r) = 0$, so $r$ is a root of a polynomial of degree $\ell$, of which there are at most $\ell$ possibilities each with probability $1/\#k$, so $$\Pr[H_r(p) = H_r(q)] \leq \frac{\ell}{\#k}.$$
To evaluate a polynomial $a_1 r^\ell + a_2 r^{\ell - 1} + \dots + a_\ell r$, you can use Horner's rule $(\cdots ((a_1 \cdot r + a_2) \cdot r + a_3) \cdots) \cdot r + a_\ell$, which costs exactly $\ell$ multiplications and $\ell - 1$ additions in the field $k$.  The simple algebraic structure means you can easily vectorize it in a $t$-way vector unit by precomputing powers $(r, r^2, r^3, \dots, r^t)$ of $r$.

Two popular polynomial evaluation hashes are Poly1305[3] and GHASH[4], over fields of size $\#k \approx 2^{128}$.  They are so popular that your web browser is probably using at least one of them right now to communicate with the crypto.stackexchange.com web servers.  Poly1305 uses the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$ which admits fast software implementations; GHASH uses the binary field $\operatorname{GF}(2^{128})$ which admits cheap hardware implementations.  They can process data at under 1 cycle per byte on typical CPUs, many times faster than any collision-resistant hash, even the fastest contenders like BLAKE2b, whose fastest implementations on the fastest CPUs haven't broken 2.5 cpb on eBACS even on messages many times longer than yours and which usually run more like 6-12 cpb on message lengths closer to yours.

A CRC works too—viewed this way, it is called a polynomial division hash[5][6]:

Fix a hash length $n$, let the input space $U$ be the set of polynomials of degree at most $\ell$ over $\operatorname{GF}(2)$, and let hash space $S$ be the set of polynomials of degree $n$ over $\operatorname{GF}(2)$; then define $H_r(p) = (p\cdot x^n) \bmod r$, where $r$ is a uniform random irreducible polynomial of degree $n$, of which there are $\pi_2(n)$ possibilities.*

Note that $H_r(a + b) = H_r(a) + H_r(b)$, so $\Pr[H_r(p) = H_r(q)] = \Pr[H_r(p - q) = 0]$.  In this event, $((p - q) \cdot x^n) \bmod r = 0$, so $p - q \equiv 0 \pmod r$, meaning $r$ must divide $p - q$.  Since $\operatorname{GF}(2)[x]$ is a unique factorization domain, $p - q$, a polynomial of degree at most $\ell$, has at most $\ell/n$ factors of degree $n$, each with probability $1/\pi_2(n)$, so $$\Pr[H_r(p) = H_r(q)] = \Pr[H_r(p - q) = 0] \leq \frac{\ell/n}{\pi_2(n)}.$$  In the best case that $n$ is prime, $\pi_2(n) = (2^n - 2)/n$, so this reduces to $$\Pr[H_r(p) = H_r(q)] \leq \frac{\ell/n}{(2^n - 2)/n} = \frac{\ell}{2^n - 2}.$$  However, it is not convenient to use prime bit lengths.  If $n = 2^d$ for some $d$, like $n = 128 = 2^8$, then $\pi_2(n) = (2^n - 2^{n/2})/n$, so we only have $$\Pr[H_r(p) = H_r(q)] \leq \frac{\ell/n}{(2^n - 2^{n/2})/n} = \frac{\ell}{2^n - 2^{n/2}}.$$  Fortunately, this is plenty for security.
To compute a polynomial division hash, you need:

A method to choose irreducible polynomials uniformly at random, like Rabin's[7].

This is considerably costlier than choosing a (near-)uniform random element of a field.  You can make it cheaper by choosing a product of smaller irreducible polynomials instead[8], at a cost to the collision probability that is exponential in the number of irreducible factors.
A method to compute division in $\operatorname{GF}(2)[x]$.

This is cheap in hardware, but most conventional hardware—like the Intel or ARMv8 CPU instructions—is limited to a fixed CRC polynomial so you usually can't take advantage of it unless you're designing custom hardware.

In software, the conventional approach is to precompute a table for byte-sized or word-sized inputs, but precomputing a table is costly—on top of the cost of choosing an irreducible polynomial uniformly at random—and using a table with secret inputs invites timing side channels.  Going bit by bit in constant time instead is extremely expensive.  (Of course, this is not much different from situation with GHASH—which is why Poly1305 is safer than GHASH, and crypto_secretbox_xsalsa20poly1305 is safer than AES-GCM.)

Beware: If the adversary learns anything about the hashes themselves, or finds two messages that collide, then any security of the universal hash evaporates[9].  For example, an adversary with a stopwatch may be able to ascertain whether two elements in a hash table collided, and exploit that for denial of service by flooding it with collisions (‘hash flood’).  If that may happen, what you may want is a PRF, like HMAC-MD5, keyed BLAKE2, KMAC128, etc.  PRFs are generally costlier than universal hashes but may be cheaper than collision-resistant hashes.  A common example of a small PRF used for hash tables is SipHash[10].  Universal hashes can be used to cheaply extend short-input PRFs into long-input PRFs[11].

* The number $\pi_q(n)$ of irreducible polynomials of degree $n$ over the finite field $\mathbb F_q$ is[12][13] $$\frac 1 n \sum_{d \mid n} \mu(n/d) \, q^d,$$ where $\mu$ is the Möbius function.


Verifying identity using a sha-1 hash I was reading http://blog.zorinaq.com/?e=74 which is about a Windows kernel developer. The developer proves that he is an actual developer by posting the SHA1 hash of a particular revision of a file. The actual hash values have been redacted, but I would like to know how knowledge of the hash would prove this.

It doesn't really prove it, and isn't meant to. If he really does know the hash, it's most likely that he has access to the source tree, which almost certainly means he knows more about Microsoft's corporate culture than the average person, which is the most important bit (if he's a Microsoft dev, he also has little incentive to claim to be a kernel dev if he's, say, a UI dev; either one gives him some authority on the subject). The issue is that only another person with source access can verify the hash, but it means that if he made up the hash, someone with source access could go "No, the hash is this instead" -- that's not something subjective, so it wouldn't just be a difference of opinion.

The hash specifically gives some piece of information that strongly implies he has access to the full file (and the full source tree), without actually giving out the file (which is a trade secret). It's not much different than saying "revision 102 had this timestamp," or "the combo to the supply closet last year was 1-2-3-4-5," or (leaving aside privacy) "here's my business card." It doesn't, and isn't intended to, provide a real proof; it just makes it a bit more likely he has some idea what he's talking about, which is the real goal.


If multiple hashing algorithms are chained together, is the compound hash function more collision resistant? The DASH cryptocurrency uses X11, which is a Proof of Work hashing algorithm composed of 11 separate hash functions which are run as a sequence.

Example: $Digest = H_{11}...(H_3(H_2(H_1(Input))))$

Questions:

1) Is this algorithm's collision resistance that of the weakest function in the sequence?

2) Can this algorithm tolerate a hashing collision found in one of the constituent parts and still produce output that is considered safe?

1) Just assume $H_1(x)$ is weak and you can generate two $x_1,x_2$ with the same hash. The other hashes then work on the same input, and hashes are deterministic, so the final output is the same. So on the first glance, it seems at best the collisions resistance is equal to the minimum of the functions. But it could also be worse. On the other hand, it depends on what kind of collisions you can create, because to find a collision for the original input would require finding preimages of the correct size in in the inner hashes.

A much better way would be to concatenate the previous hash with the message, and then hash that with the next one. That might give you the security properties of the strongest algorithm in the chain - but robust combiners also require careful consideration.

2) That depends if you consider all hashes secure. As stated above, that depends at worst on the security of the weakest hash: That is really bad, if you use a decent one and a broken one like SHA-1, then better just use the good one alone. Adding complexity can reduce security.

On a general note: Creating a crypto currency does not require knowledge of cryptography. Re-inventing the Caesar  cipher (or modification in a tiny aspect) would also not make that secure in a modern sense.

That article does not even mention the correct security properties of hash functions (collision resistance, 1st and 2nd preimages resistance), the content doesn't have a single well-founded argument. So the seriousness is questionable.


GCM vs CTR+HMAC tradeoffs So these days I see everyone using AES-GCM. What are its advantages over simple CTR+HMAC modes? Is it speed? Or ciphertext length? And what are the security tradeoffs, both in terms of practical cryptanalysis and theoretical attacks complexity?

AES-GCM uses single block cipher operation and can be processed in parallel, therefore it should be faster.
CTR+HMAC requires block cipher and hash function, which usually can't be processed in parallel. Also it requires 2 keys. It is often miss-implemented (MAC-then-encrypt or MAC-and-encrypt, using single key).
Cipher-text length is the same for same security level. However CTR+HMAC usually has a longer tag, because hash functions have bigger output than block ciphers, but you can truncate tags to the same length.
If implemented correctly and the block cipher / hash function is secure, both are secure. However, because CTR+HMAC has 2 keys compromising one part won't compromise the other part.


Are CFB and OFB really meant for streaming? CFB, OFB and other modes are meant for streaming and don't require padding. Are there still limitations such as the text needs to be greater than key length?

CFB does require padding unless you use a segment size of 1 bit (or 8 bits if your message is byte oriented). Check Section 5.2 in NIST 800-38A:

For the CFB mode, the total number of bits in the plaintext must
be a multiple of a parameter, denoted s, that does not exceed the
block size

OFB indeed does not require any padding.

There are no other limitations on the plaintext (but read very well the requirements about Initialization Vectors!).


Number of plaintext–ciphertext pairs needed to rule out false keys with a reasonable likelihood in AES I am new to cryptography and I've got the following question from Understanding Cryptography:
Imagine that aliens — rather than abducting earthlings and performing strange experiments on them — drop a computer on planet Earth that is particularly suited for AES key searches. In fact, it is so powerful that we can search through 128, 192 and 256 key bits in a matter of days. Provide guidelines for the number of plaintext–ciphertext pairs the aliens need so that they can rule out false keys with a reasonable likelihood.
What I tried
I know that the expected number of keys that encrypt a plaintext $x_1$ to $y_1$ is $2^{k-n}$, where $k$ is the key length in bits, and $n$ is the size of a block in bits.
I also know that given $\{(x_1, y_1), \dots, (x_t, y_t)\}$ PT-CT pairs, the expected number of false keys which encrypt all plaintexts to the corresponding ciphertexts is $2^{k-tn}$.
Therefore, for AES-128, AES-192, and AES-256, I would expect that only two PT-CT pairs is sufficient, given that the expected number of false keys would be, respectively, $2^{-128}$, $2^{-64}$, $2^0=1$.
What the answer manual says
The manual says that, for AES-128, only one pair is sufficient. This one I can see why, since the expected number of keys that map $x_1$ to $y_1$ one be $\frac{2^{128}}{2^{128}}=1$.
For AES-192, the manual says that "in order to find the correct key with a probability of 50 percent, we require $2^{63}$ pairs of plaintexts and ciphertexts". And for AES-256, also with 50% probability, $2^{127}$ PT-CT pairs are required.
I cannot see why such values are required for AES-192 and AES-256.

I cannot see why such values are required for AES-192 and AES-256.

That's because you have a correct understanding of the situation, and the answer manual is wrong.
Your analysis in "what I tried" is correct; there's not a whole lot I can add to it...


Zero Message Length HASH What does it mean by a HASH of a message with zero length or rather why is it required?
What could be a possible scenario where this is used?

Also note that, for a given HASHing algorithm, the hash value of a zero length message is essentially pre-defined.

The hash of a zero-length message is defined for several reasons:

There's no reason not to define it. If (as you assume) it'll never be used, then it doesn't matter whether it's defined and there's no reason to avoid defining it.
Having it undefined would create a weird exceptional case that'd need to be handled by anything that uses the hash, just in case it ever happens. Weird exceptions tend to lead to bugs, bugs tend to cause vulnerabilities, and cryptographers hate vulnerabilities and the design choices that cause them.
In practice, it will be used. One common use of hashes is to create a fingerprint of the contents of files, and empty (zero-length) files are entirely normal.

As for your point that for a given HASHing algorithm, the hash value of a zero length message is essentially pre-defined: that's true, but it's also true of any other specific message. The hash of "a" is essentially pre-defined, as is the hash of "foo", "This is a message", etc.


Single-purpose symmetric encryption scheme for single files I'm writing a simple password manager program that will encrypt/decrypt a single file (it's size will most likely stay under a few K). This is my initial file format design:

1. hmac                        plaintext
2. hmacSalt                    plaintext
3. keySalt                     plaintext
4. iv                          plaintext
5. [file header/metadata]      ciphertext
6. [file content]              ciphertext

Encryption scheme:

$hmacSalt, keySalt, iv := CSPRNG(...)$ where each value is separately assigned
$derivedKey := scrypt(key, keySalt)$ where $key$ resembles the master keyphrase, provided by the user
$C := E(derivedKey, iv, 5 || 6)$ where $5$ and $6$ refer to the lines denoted in my file format design
$hmac := hmac(scrypt(key, hmacSalt), 2 || 3 || 4 || C)$

Decryption scheme:

$derivedKey := scrypt(key, keySalt)$
$compare(hmac, hmac(scrypt(key, hmacSalt), C))$ where $C$ refers to complete file content, with the HMAC's size as offset
$P := D(derivedKey, iv, C)$ where $C$ is the ciphertext (which is composed of $5$ and $6$)
Parse file header and content

The encryption cipher is AES-256 and HMAC's underlying hash is SHA2.

My questions:

As you can make up from this encryption scheme, I'm using the encrypt-then-authenticate approach to enforce ciphertext integrity. In step 2 of the decryption process I perform this authentication step. If the calculated HMAC turns out to be equal to the HMAC in the file, does this mean, apart from the implied ciphertext integrity, that the supplied passphrase is certainly the same as the original passphrase used for the encryption, resulting in this ciphertext? Or should I perhaps use an additional plaintext HMAC, stored in the encrypted file header, to ensure passphrase validity.
I'm unsure which cipher mode of operation would be most suitable for this kind of encryption. I couldn't find much information about this, as most recommendations are based on network-based cryptography. CBC and CTR both seem good options, and I believe the security difference are negligible, as long as the implementation is done correctly. In Cryptography Engineering, the authors used to recommended CTR, but now prefer CBC as it's easier to "get right". CTR seems more susceptible to a poorly generated IV, as it's essentially a stream cipher. Which one would you recommend?
This question partially depends on my choice of cipher mode (question 2). Does generating a new salt and IV for each file mutation really offer a noticeable security benefit? This may sound like a stupid question, but file mutations only take place sporadically, and thus a sufficiently large IV should deter any ciphertext attacks?
According to the Horton Principle, the MAC should "Authenticate what is being meant, not what is being said". I understand this includes the structure of the file etc., but would including salts and IV be wise as well?
In my design I'm using the same underlying key as input for the encryption and HMAC function. Does the use of two separate salts offer any security benefit, or is reusing the same key inherently insecure anyway?

PS: I couldn't decide if this question would be more suited for security.stackexchange.com or not, so please forgive me if that's the case.

As you can make up from this encryption scheme, I'm using the encrypt-then-authenticate approach to enforce ciphertext integrity. In step 2 of the decryption process I perform this authentication step. If the calculated HMAC turns out to be equal to the HMAC in the file, does this mean, apart from the implied ciphertext integrity, that the supplied passphrase is certainly the same as the original passphrase used for the encryption, resulting in this ciphertext? Or should I perhaps use an additional plaintext HMAC, stored in the encrypted file header, to ensure passphrase validity.

If the HMAC verification of the ciphertext checks out, then you can be assured that the password is the same.  Of course HMAC (and any hash algorithm) has many collisions (i.e. lots of inputs that map to the same output), but the chance that you will run into one of these in a real-world scenario with decent-sized hash are near infinitesimal.  A common practice is to put a checksum (e.g. CRC32) on the plaintext to ensure that the decryption happened properly.  If you want to guard against decryption errors (usually not necessary unless you have a "can't fail" super-sensitive system), then you can add such a plaintext checksum.

  I'm unsure which cipher mode of operation would be most suitable for this kind of encryption. I couldn't find much information about this, as most recommendations are based on network-based cryptography. CBC and CTR both seem good options, and I believe the security difference are negligible, as long as the implementation is done correctly. In Cryptography Engineering, the authors used to recommended CTR, but now prefer CBC as it's easier to "get right". CTR seems more susceptible to a poorly generated IV, as it's essentially a stream cipher. Which one would you recommend?

In your scenario, since you are doing encrypt-then-sign, the mode doesn't matter so much.  CTR (a stream mode) and CBC (a block mode) have different error propagation properties, different attacks, but these are somewhat irrelevant because of the pre-decrypt verification that you are doing.  In my experience, CBC is more robust in more situations while CTR tends to be more flexible, but it doesn't matter for you.  Go with CBC if you like.  It's more important to ensure that you get a unique IV for each encryption operation.

  This question partially depends on my choice of cipher mode (question 2). Does generating a new salt and IV for each file mutation really offer a noticeable security benefit? This may sound like a stupid question, but file mutations only take place sporadically, and thus a sufficiently large IV should deter any ciphertext attacks?

You absolutely must use a different IV for each password encryption operation.  There are attacks that can be mounted against either mode if you fail to use a different IV.  If you do this, then there is no need for the salts.  Unique-per-password salts are used when encrypting or hashing individual passwords separately and help resist rainbow table and similar attacks.  Since you are encrypting and entire file at once, I'd recommend skipping the salt and just ensuring that you use a unique IV per encryption (i.e. each time you change the file, or encrypted contents in your lines 5 and 6).

  According to the Horton Principle, the MAC should "Authenticate what is being meant, not what is being said". I understand this includes the structure of the file etc., but would including salts and IV be wise as well?

As I said previously, no need for salts.  However, it is common practice to authenticate (MAC, in your case) the modification-sensitive portions of the plaintext header.  So if you had fields for version number, date, owner, etc, then you should concatenate those fields with your ciphertext and MAC the whole thing together.  You don't show anything like that above, but perhaps you should consider adding such fields for other security reasons.  Technically the IV is not modification-sensitive, but since you don't have a checksum on the plaintext, then it might be good idea to MAC the fields: 4 (IV) || 5 || 6.

  In my design I'm using the same underlying key as input for the encryption and HMAC function. Does the use of two separate salts offer any security benefit, or is reusing the same key inherently insecure anyway?

Again, neither salt is needed in this implementation.  HMAC (with a good underlying SHA like SHA256 or SHA512) and AES do not have practical cryptanalytic attacks and I don't know of any attack that can exploit either one if you were to use the same key for both, but this is generally considered bad practice.  Instead, just make 2 keys.  Or use a key derivation function (see NIST SP 800-108) to derive 2 keys from a single source of entropy/password.

Someone else already mentioned it, but is there a reason that you are using AES-CBC + HMAC instead of just AES-GCM?  AES-GCM is an authenticated, encrypted mode of AES and the authentication tag is over the ciphertext.  There are some nuances that you need to be aware of before using this mode, but it could be a simpler implementation for you.  Otherwise, AES + HMAC is fine and fairly widely used as well.