Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)

share|improve this question
    
I'd mix everything to generate a 256 bit master-key from which I'd derive both the keys and the IVs. –  CodesInChaos Jul 8 '13 at 12:59
    
Definitely don't use an IV of 0 because then it is trivial to break the first block. To decide further, however, we need to know more about the threat model, and what your encryption is trying to defend against. Is AES-CTR a requirement, or could you upgrade to AES-GCM? –  xorbyte Jul 9 '13 at 22:16
    
@xorbyte in this case, this is simply protecting client-server communication for an online multiplayer game. The goal is to prevent players from eavesdropping, as well as sabotaging another player's turn by posing as that other player or replaying/modifying some of their actions. Finally, all player authentication and registration is done encrypted, so personal information is sent in the clear. –  Nuoji Jul 10 '13 at 12:21
    
@xorbyte AES-GCM used to be problematic because there aren't always standard implementations available. That said, even with GCM I would need an IV, right? –  Nuoji Jul 10 '13 at 22:11
    
Will $S$ be used to for only one plaintext/ciphertext? $\:$ If yes, why are you calling it "long-term"? $\hspace{.73 in}$ If no, will new nonce pairs be exchanged for additional messages? $\:$ In either case, there are likely $\hspace{.46 in}$ to be problems if you don't MAC the AES-CTR ciphertext with a computationally independent key. $\;\;\;$ –  Ricky Demer Jul 12 '13 at 3:44

2 Answers 2

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-nonce pair is used twice. Let's assume the nonces 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 authenticated 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.

share|improve this answer

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.

share|improve this answer
2  
How do you figure (2) being sensitive to collisions? –  Nuoji Jul 12 '13 at 12:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.