Nonces are bad and we should stop using them

Once upon a time, there were Feistel ciphers. Because of Feistel ciphers, we got used to (1) block ciphers with (2) key schedules. This was a bad idea, but we didn’t know better at the time.

Why was it a bad idea?

Block ciphers were a bad idea because they are required to be invertible: you must be able to unambiguously decrypt everything that you encrypt. This, combined with the fact that each block has finite size, results in the famous “bitmapped penguin” image, where a block cipher reveals all sorts of incredible patterns in its data. So block ciphers on their own can’t actually protect anything.

The crypto community realized this and then spent a while trying to invent ways to link a cipher’s blocks together by mixing the output of one operation with the input of another in various more-or-less ingenious ways. Eventually, the crypto community largely realized that the best way to use a block cipher was as an approximation of the ideal cipher: a one-time pad. A one-time pad based on true random data is information theoretically unbreakable. There is literally no attack that can be attempted against it, because every single plaintext is equi-probable. This got us the CTR mode, where the actual block cipher can be used to generate a keystream of the same length as the message, and then the keystream is XORed directly into the message to produce the ciphertext. For our purposes today, everything I say about CTR mode is also true of its authenticating cousin GCM.

But it turns out that block ciphers aren’t the best choice for a keystream generator, because they aren’t even attempting to be pseudorandom functions. Because block ciphers have a decrypt, block ciphers are pseudorandom permutations (PRPs), not pseudorandom functions (PRFs). This means that an attacker can be 100% assured that two identical output blocks came from different inputs. This is a perfect crib to brute-force against: try a certain key, and if you see repeated output blocks anywhere in the keystream, you know that key isn’t right.

The net effect is that all of the security proofs around block ciphers have ugly n² terms in them, where each new invocation of your cipher decreases its security by an amount proportional amount of data that has previously passed through it. This is the cryptographic reason why AES-CTR keys must be rotated, and rather frequently (as opposed to the practical reason, which is: sometimes secrets leak by non-cryptographic means).

So, if you want to approximate a PRF with AES-CTR, you have to build a system ahead of it to pseudorandomly generate keys for the underlying block cipher. This sucks, and is largely left as an exercise to the reader rather than done by a standards body or government agency.

The upshot is that it is generally a good idea, from a cryptographic perspective, to reinitialize the block cipher every now and then. But since AES has a key expansion step that produces its key schedule, you now have to incur the combined CPU cost of 1) running your key-generating PRF and 2) doing the AES key expansion process. There’s also the memory cost of keeping the key schedule around, but that is mostly a problem for memory-constrained environments that want to communicate using many different keys.

This brings us to nonces. In AES-CTR, the nonce’s purpose is to enable the same cipher to be reused multiple times under the same key. This is desirable, of course, because the cipher would be a lot slower if it had to re-do its key expansion step for every block. But if we really wanted the best approximation of a stream cipher, that’s what we’d do. We’d pick a key k and use it to encrypt our first block. Then we’d use k+1 to encrypt the next block, and so on. Since we don’t want to spend that amount of CPU time, we have nonces.

AES has 128 bits of space in its block. NIST set aside 96 bits for a nonce, and 32 bits for a counter. The idea is that your counter will ascend sequentially from zero as you output new blocks, and after some number of blocks strictly beneath 2^32, your message ends. This is 68 gigabytes of message, which takes only about 30 seconds to encrypt on a consumer-grade laptop. Naturally you have the other 96 bits to use for numbering messages, and these can be chosen sequentially or randomly. Random incurs issues due to collisions or bad RNGs, whereas sequential incurs risks when systems crash or otherwise corrupt their state.

If your message ends before the 68 gigabyte counter rolls over, you don’t get any of those bytes back. In practice, protocols like TLS “burn” a nonce for each record, which is 16 KB, and allow for at most 24 million records to be sent under a single key (RFC8446). That means that under a single AES-GCM key, TLS can send at most 384 gigabytes. The fact that we’re dealing with numbers in the millions when designing a cryptographic protocol is absurd; we should be talking in terms of numbers that cannot be counted before the heat death of the universe.

So: block cipher nonces are bad. They are an artifact of the fact that some block ciphers require key expansion steps that are non-negligible relative to their encryption steps. Wherever you were going to use a nonce, the thing to do instead is to generate a new key by a deterministic random process.

Thank you for coming to my TED talk. You may realize that none of this is new news: there are plenty of stream ciphers out there that solve these issues effortlessly. Most of them only require add, rotate, and xor CPU instructions, which is also nice.