1
$\begingroup$

Can anybody explain in detail why repeating nonce is dangerous in CTR mode?

Two cases to explain

  1. When plain text is repeated for each nonce.
  2. When plain text is unique for each nonce

.

$\endgroup$
  • $\begingroup$ What do you mean with “nonce/counter pair”? The CTR block cipher mode of operation uses a counter (the “nonce” usually denoting the value at which the counter starts). $\endgroup$ – xorhash Apr 11 at 9:10
  • $\begingroup$ I thought counter is appended to nonce. In sense that, if block is 128 bit, then the most significant 64 bits are nonce and the least significant 64 bits are the counter. After all, i have edited my question $\endgroup$ – m.nasim Apr 11 at 9:18
  • 1
    $\begingroup$ Some answers Using 0 nonce for AES-256 in CTR mode, Repeated NONCE in CTR mode. The magic keyword is crib-dragging. $\endgroup$ – kelalaka Apr 11 at 9:34
  • 2
    $\begingroup$ @xorhash Generally the nonce and counter are seen as separate in standards documents, but most implementations simply perform addition of one over the entire $2^{128}$ block, leaving the check on overflow to the user (that way any nonce size is automatically handled). So yeah, there may be some confusion there. $\endgroup$ – Maarten Bodewes Apr 11 at 10:26
  • 1
    $\begingroup$ @m.nasim the attacker had some plaintext and maybe the firs plaintext is the longest one of them. Even it is the smallest the result is the failure of the Confidentiality! $\endgroup$ – kelalaka Apr 11 at 14:31
1
$\begingroup$

In counter mode the block cipher operates as a PRNG, essentially like the keystream generator of a synchronous stream cipher. The key and the nonce determines the starting-point of the PRNG, thus if the nonce is ever reused with the same key, the keystream produced is the same.

Why is this bad? Because if you ever figure out the plaintext corresponding to the ciphertext of one message encrypted with the repeating keystream, deducing the keystream is trivial ( ciphertext = plaintext XOR keystream ), and you may easily decrypt any other message encrypted with the same keystream. (Essentially a known-plaintext attack).

To answer your specific questions:

  1. If the same plaintext is encrypted with the same nonce (and the same key), the ciphertext is identical.
  2. If the plaintext is "unique" (different is perhaps more accurate), the ciphertext is different. But as explained above, if the adversary gains knowledge of any plaintext-ciphertext pair, (s)he may decrypt all the other messages.
| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks T.Rocket, This is actually what I understand. Plain text is never known to attacker. If I am the attacker and I know the plain text, why should I bother doing Key = C XOR P? I just know the P. My Questions: 1st case will yield repeated ciphertext, which tells the attacker that plain text is repeated, but what is it?. 2nd case yields totally random bits as the same keystream is XORed to a totally different plain text bits. $\endgroup$ – m.nasim Apr 11 at 13:27
  • $\begingroup$ Revisiting Venova Project, one can see that Americans could realize repeated usage of OTP key stream in Soviet messages. Can you explain how Americans discovered that reuse, given that messages are different. And even if we considered repeated words in the start of each message something like Hay Hitler as claimed by Allan Turing during the World War II. What is the chances that every repeated message happen to start at the same key stream position? not to say, what is this repeated word? Unknown plain text. $\endgroup$ – m.nasim Apr 11 at 13:47
  • $\begingroup$ I think one of the comments by kelalaka answers your first question. Regarding the second question: How the Americans detected repeated use of a key, I don't know. However, as an example, this could be detected if one gains knowledge to the key of one specific message, and then attempt to reuse this key on a set of other ciphertexts. If the decryption makes sense, the message is likely to have been encrypted with that key. This is related to a concept called unicity distance. In any case: A cryptosystem relying on the secrecy of the plaintext is fatally flawed. $\endgroup$ – T.Rocket Apr 11 at 17:34
  • $\begingroup$ your answer and kelalaka comments very close. You gained the correct answer flag ;) $\endgroup$ – m.nasim Apr 11 at 17:41
  • $\begingroup$ As long as you understand why reusing the nonce is bad, I am happy :-) $\endgroup$ – T.Rocket Apr 11 at 17:49
0
$\begingroup$

Reusing key/nonce affects security of CTR mode and Stream ciphers in general. Assume that you have two ciphertexts encrypted with the same key, say E(A) and E(B).

E(A) = key xor A
E(B) = key xor B

Now try XORing the two ciphertexts as follows

E(A) xor E(B) = key xor A XOR key xor B
= A xor key xor key xor B // algebraic property of xor
= A xor 0 xor B           // because key xor key yields 0
= A xor B                 // XORing 0 with anything yields that thing

Given that A and B are normal English letters, the guessing of A and B will be trivial, as you lost the key space of the stream cipher. Now, you are just trying 26 letters.

The worst case scenario applies when A and B have the same length. Efficiently, you will break two ciphertexts at one shot.

That mathematical fact is terrifying and tells you loudly Never REUSE the key

I used to use ChaCha in my password manager to encrypt the database before uploading to the cloud. As ChaCha is a stream cipher, the above mathematical fact will apply to any two versions of my database. Now, my cloud provider can XOR two versions of my database and get my secrets without bothering cracking the key. I am going to to change my critical passwords and revert back to my old friend Twofish.

-- Edited to add --

My Password manager changes the key each time I click "Save". It seems It uses a sort of salt or something in its PBKDF, as I don't change the master key each time I change an entry. No need to change old passwords, as the previous attack would reveal

E(A) xor E(B)
= key1 xor A XOR key2 xor B

also, if the database didn't change at all, the attack will reveal only NULL.

E(A) xor E(A) = 0    // same key and same database

One fear is about changing the key while database is intact. That would reveal

E1(A) xor E2(A)
= key1 xor A XOR key2 xor A
= key1 xor key2

Not sure if the result of key1 xor key2 would help the attacker anyway. If someone knows, please comment.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.