AES-CTR with ephemeral keys vs IV

Question

Let's say that we have a key exchange of some sort, which leaves A and B sharing the long-term secret $S$. Then, A and B want to use AES-CTR for the communication, which leaves us with several possible strategies:

1. During the key exchange, A and B both generate and send nonces $N_a$ and $N_b$ which are mixed in the key derivation function with $S$ to produce a unique key for the exchange. We leave the IV = 0.
2. During the key exchange, A and B both generate and send nonces $N_a$ and $N_b$ which are mixed to produce and IV. The key is derived from S.
3. During the key exchange, A and B both generate and send $N_a$, $N'_a$, $N_b$, $N'_b$. $N_a$ and $N_b$ are mixed with $S$ to produce the key. $N'_a$ and $N'_b$ are mixed to produce the IV.

In other words: random key/fixed IV, fixed key/random IV or random key/random IV.

Which one is preferable? (Assume HMAC-SHA256 or similar for mixing keys/IV)

Answer 1

First, there is a non-security argument in favor of option 2.: if you can cache the AES key across key exchanges, you can save time in key setup. Whether that's relevant I'll leave for you to decide.

CTR fails when the same key-input pair is used twice. Let's first assume the nonces $N_a$ and $N_b$ are always unique, and that key derivation and mixing is strong.

1. Birthday bound for a key collision is $2^{64}$ for AES-128, $2^{128}$ for AES-256 etc.
2. If generating a 96-bit nonce, to use with a 32-bit counter, the birthday bound is $2^{48}$. With a 128-bit nonce and messages shorter than $2^{32}$ you can get a higher value, but unless you only have one block messages it's less than $2^{64}$.
3. With a 96-bit AES nonce the birthday bound is $2^{112}$ for AES-128 or $2^{176}$ for AES-256. Again, you can get a bit better bounds with a larger nonce and shorter messages, approaching $2^{128}$ and $2^{192}$.

Clearly the last is "best", but even with just a random 96-bit nonce you could have billions of key exchanges with a very small chance of even one collision. That one is a bit borderline, but any of the other options I would consider good enough.

Note the assumption made, that nonces are unique. If the nonces themselves collide, any data derived from them will also collide. For random nonces you'd want them to be at least as long as the total data derived from them. In addition, the exchange of nonces should be designed such that an attacker cannot affect it and cause a collision.

---

As an aside, option 3. doesn't necessarily require two sets of nonces. You can derive both a 128-bit key and a nonce with a single HMAC-SHA-256, or you can derive more material with two differently salted HMACs. Doing so will make the nonces depend on $S$, but that doesn't seem like a problem.

Answer 2

Points "1" and "3" have equivalent security. Obviously "1" is less work. "2" leaves more potential for (key, IV) collisions if the $N$'s are too small or the attacker can control the $N$'s.