Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I wonder if there's a good explanation for non-experts that gives at least an idea how an attacker would exploit the (key, nonce) pair reuse and why everything fails so catastrophically?


With both AES-GCM and ChaCha20-Poly1305, confidentiality is provided by XORing the plaintext with a keystream generated by either AES or ChaCha20. If the nonce is the same, then the same keystream is used.

Consider two plaintexts, p₁ and p₂, encrypted with the same (key, nonce) pair. The ciphertexts will, in part, contain p₁⊕k and p₂⊕k, where k is the keystream and ⊕ is XOR.

An attacker can XOR those ciphertexts together and get p₁⊕k⊕p₂⊕k = p₁⊕p₂⊕k⊕k = p₁⊕p₂. If the attacker has any knowledge of p₁ or p₂ then the confidentiality of the other falls as well.

The failure of the authenticator is more complex. Both AES-GCM and ChaCha20-Poly1305 use polynomial authenticators and, in short, duplicating a (key, nonce) pair allows the attacker to solve an equation and that's very bad.


I can do you one better:

http://cryptopals.com/sets/1/challenges/6/

http://cryptopals.com/sets/3/challenges/20/

In the literature, nonce reuse on things like GCM can fail even more spectacularly, with respect to to the authenticator's key.


AES-GCM and ChaCha20-Poly1305 work in roughly the same way. They both use the key and nonce to produce a pseudo-random sequence of bits. A small part of that sequence is used as an authentication key to make the message authentication code using a polynomial function over the ciphertext, the rest is xored together with the message to make the ciphertext.

When a (key, nonce) pair is reused, these constructs fail in two ways:

The first way is the same for all stream ciphers: since the same stream is xored with both messages, the attacker gets to see the xor of the messages together. From this you get a fun puzzle, e.g. assuming English text you might deduce something like 'alphabet neighbours, followed by the same letter, followed by the same letters but different case...', from which you can often deduce parts or whole of the plaintexts by statistical methods.

The second is due to the polynomial structure of the message authentication code. In a secure MAC, an attacker must not be able to deduce the key from seeing the authentication code. But for GCM and Poly1305, this is only true if the attacker doesn't see multiple messages authenticated with the same authentication key. With multiple tags from the same key, an attacker can solve for the authentication key.

Together this lets the attacker know both the keystream and the authentication key, from which they can forge basically any message they want for that key and nonce.

Compare this to e.g. ChaCha20-then-HMAC: a reused nonce would still let the attacker deduce the plaintext, but having two messages signed with the same HMAC key tells you nothing about the key. ChaCha20-Poly1305 is secure when used correctly, but ChaCha20-then-HMAC is more misuse-resistant, since a reused nonce breaks confidentiality but not authenticity.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: