Strategy for random CTR initial counter values

Question

Alice has a secret key which she uses to encrypt messages in CTR mode. CTR mode is critically vulnerable to counter reuse, and Alice has a problem: she has terrible memory and no pen to write anything down. She has good enough memory to send one message, but between messages she sometimes forgets the counter values that she has used. She has the key tattooed on her forearm. She doesn't have a watch that would give her a convenient non-repeating input. She has a balanced coin which she can flip to generate random numbers. She wants to ensure that she won't reuse a counter value, because Eve is lurking around, makes xoring things a hobby and she can even suggest some plaintexts for Alice to encrypt.

In other words, I have an embedded device which has some code and a key in ROM, and a hardware RNG, but no clock (unlike Making counter (CTR) mode robust against application state loss) and no persistent rewritable storage (unlike CTR mode nonce with aggressive key rotation policy). This device emits messages encrypted with AES-CTR, using that one key in ROM. Integrity of these messages is beyond the scope of this question. The device can lose power at any time, and at that point, it loses track of the previous counter value. It typically sends many messages between resets, but in some circumstances an attacker could arrange to cut power off at inopportune times.

What is the best strategy to avoid counter reuse, and after how much traffic does the probability of counter reuse get non-negligible? For example, I can generate a new initial counter for every message, or a new initial counter on every reset. I can start each message at the current counter value, or use a scheme such as 96 bits of randomness and a per-message counter starting at 0. (No message is more than $2^{32}-2$ blocks long.) Does this make a difference in the probability of collisions?

Answer 1

Let $2^m$ be the average message length in blocks.

1. When using an independent random nonce for the whole 128-bit IV of each block, you would expect a collision after $2^{64}$ blocks, i.e. $2^{64-m}$ messages. (But you double the data size.)

2. When using a 96-bit nonce and a 32-bit counter, you would expect a nonce collision after $2^{48}$ messages. This is better than the above if $m > 16$ and of course more efficient because fewer nonces are generated.

3. When using a 128-bit initial nonce for the message that gets incremented for subsequent blocks, the math gets a bit trickier. The probability that two $2^m$-block messages get overlapping counter ranges is about $2^{-(128-m-1)}$ because they overlap when the second message has an initial nonce within $2^m$ of the first in either direction. That would mean at least $2^{64 - (m+1)/2}$ messages, which is better than either of the above if $1 < m < 32$.

   The exact message length distribution affects how many blocks vs. messages can be sent, but normally there's a practical maximum on message size which is not orders of magnitude larger than the average, so changing $m$ above to reflect that would give a worst case estimate.

4. Letting the next message continue from the previous nonce until a reset would be the same as above, but with longer "messages" equal to the concatenation of all those sent between resets. With $2^k$ messages between resets that's at least $2^{64-(m+k+1)/2}$ expected sessions before a collision, i.e. $2^{64-(m-k+1)/2}$ messages, which is better if $k>0$.

   However, if you assume an attacker who can control when resets happen, it becomes worse. After each message the attacker can either cause a reset (if no collisions are in the near future) or let the counter continue its journey towards a collision. Reusing the $k$ from above for a normal reset frequency the attacker can expect, two resets would have about a $2^{-(128-m-k)}$ chance of collision so the expected number of resets before collision is on the order of $2^{64-(m+k)/2}$, which is worse than the previous option.

5. Use the 96-bit nonce and 32-bit counter construction, but keep track of where the previous message ended. As long as there's space for the message within the 32-bit block defined by the nonce, select the IV so that it continues from where the previous message ended. If the block runs out or the device has been reset since the previous message, choose a new one randomly.

   In the best case you stuff $2^{32-m}$ messages per nonce and get a collision only after $2^{48+32-m}=2^{80-m}$ blocks, which is better than any of the above. Even in the worst case where an attacker resets the device after each message you are guaranteed the $2^{48}$ expected messages before collision.

In practice I would choose the 32-bit counter, with or without the optimization for continuing from a previous message – i.e. either 2. or 5. above. There's no attack that can make it worse than $2^{48}$ messages and the math is easy.