"At first glance, this seems fine, but it is not. If an attacker knows the plaintext p1 and the ciphertext c1, then they can compute the keystream by XORing p1 and c1 together"<p>Also, if the attacker only has c1 and c2, if the nonce is reused then c1 xor c2 will be the same as p1 xor p2. In most cases, two plaintexts xored with each other are trivial to decode.
Not just AES-GCM.<p>The vast majority of encryption algorithms must be used in a nonce-respecting scenario. This is part of the contract to achieve the claimed security properties.<p>Alternatives require multiple passes over the data, which is not applicable to some protocols in addition to having performance implications.<p>Common protocols such as TLS transparently handle nonces in a safe way. But the primitives used in TLS may require additional steps to be safely used is other contexts, especially in distributed systems.<p>Whenever applications try to use these primitives directly, using a fixed key and picking nonces at random is a very common practice. Unfortunately, due to their small size, nonces collisions can quickly happen.<p>We're missing standard constructions with large nonces that would alleviate this problem, because IETF protocols haven't needed them. But there's a lot of evidence that many custom applications and protocols do.<p>There are multiple great proposals to derive AES-GCM subkeys and nonces from a key and a large nonce. We may expect convergence and adoption in crypto libraries soon.<p>Until then, constructions such as XSalsa20 and XChaCha20 are widely implemented and deployed. If you don't need NIST compliance, they're excellent choices.<p>But my recommendation today would be to replace AES-GCM with the AEGIS family of algorithms whenever possible. They have nice properties that AES-GCM doesn't have, including more comfortable usage limits, much better performance and large nonces up to 256 bits.<p>This page [1] and that draft [2] summarize usage limits of common constructions, including when using random nonces.<p>[2] <a href="https://doc.libsodium.org/secret-key_cryptography/aead" rel="nofollow">https://doc.libsodium.org/secret-key_cryptography/aead</a><p>[3] <a href="https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits/" rel="nofollow">https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits...</a>
I find the article a little confusing. IMHO the point is that you must NEVER reuse an XOR key sequence for stream cipher encryption. With RC4, this meant that you could never use the same key. With modern stream ciphers there is the nonce for this - the CTR mode of a block cipher is also a stream cipher. (GCM mode is just an extension of CTR mode for authentication).<p>I've put together a little online demo tutorial (in my teaching and learning programming language).<p><a href="https://easylang.online/apps/tut_cipher.html?v=2405e" rel="nofollow">https://easylang.online/apps/tut_cipher.html?v=2405e</a>
I'm curious for the use-cases where people have to maintain a key over a long period where the choice of nonce can't be made strictly non-decreasing or otherwise prevent nonce reuse (per key).<p>I can imagine VPNs or other packetized communications potentially running into this problem, e.g. with N parties needing to encrypt messages under the same key to each other without coordination on nonces. The worst case I can think of is a large number of devices with a baked-in key and secure RNG but no non-volatile storage. They can't generate more than 2^48 messages with AES-GCM or risk collision.<p>Full disk encryption has always had a similar problem; generally a single long-lived master key that individual sectors or blocks are encrypted by, often without the additional storage set aside for IVs or nonces (which would break exact sector to sector mapping of encrypted virtual disk to plaintext disk). That leaves IV-derivation to be static per block offset/number, or key derivation on master key and block offset/number.<p>Devices without secure RNGs are also at risk (microcontrollers with no non-volatile storage that restart a lot, for example).<p>I'm curious if there are any other hard cases where nonce reuse becomes a risk in practice.
Great post! Thanks for taking the time to put this up.<p>What do you think the ratios are regarding improper use of nonce with this mode?<p>Most implementations that I am familiar with intentionally generate a random nonce to help lower the percentage of app devs doing this very thing
It's worth mentioning AES-GCM-SIV[1], which is the fix for this issue.<p>[1] <a href="https://www.rfc-editor.org/rfc/rfc8452.html" rel="nofollow">https://www.rfc-editor.org/rfc/rfc8452.html</a>
GCM is well known to have sudden death on nonce reuse, which is why we used GCM-SIV for the ZeroTier v1 protocol. (Our new protocol that stiiiil is not in product is Noise based.)<p>Nonce reuse in SIV is much less catastrophic. Reuse of a nonce can reveal if two packets are identical but doesn’t let you do anything else.<p>Of course there are categorically better modes than GCM but they are not widely supported. ChaChaPoly is better cryptographically but no hardware acceleration, which matters on small devices.
I understand that nonce reuse is catastrophic, but I don't think I understand when it can be abused. Does the attacker have to know which two messages share a nonce? Is knowing that out of N messages, at least one pair shares a nonce already enough?