4 ms·

I may be misunderstanding, but this might be the thing already discussed in footnote 2 of the article: "Technically, GCM accepts longer nonces. However, nonces

I may be misunderstanding, but this might be the thing already discussed in footnote 2 of the article: "Technically, GCM accepts longer nonces. However, nonces longer than 96 bits are hashed into a starting 128-bit counter value, leaving no dedicated counter space. (96-bit nonces are instead concatenated with a 32-bit counter.)"

zahllos 3y ago
I missed that, good catch. That said, I find the wording of dedicated counter space a bit bizarre. There are only 128 bits per block in AES - in fact I'm not aware of a widely deployed cipher which a larger block size. Whatever goes through ghash becomes the initial plaintext passed to aes under the key (this is the counter) part and then you just increment. This is just a limitation of counter mode in general: the whole IV is technically counter space and is treated as whole when evaluating the birthday bound issue. The critical part mentioned in the post is that XChaCha "hashes the key+nonce into a fresh key". A very similar technique is used un: AES-GCM-SIV (https://datatracker.ietf.org/doc/html/rfc8452#section-9 https://datatracker.ietf.org/doc/html/rfc8452#section-9). The improved security here comes not from any "counter space" or nonce extension per se but the fact that changing the IV changes the effective key used in the block primitive (i.e. the raw aes-encrypt function) as well as the first block of plaintext fed to AES by deriving these from nonce+key. So I guess this is asking for a somewhat different construction. Personally aside from the fact it is already widely deployed I'm not sure I'd keep GHASH.
- tptacek 3y ago
  The SIVs have somewhat different security properties than straight AEAD; they're usually a win, but not always. Moreover: the whole point of doing an extended-nonce AEAD is to avoid the extra mechanism of a nonce-misuse-resistant AEAD by giving yourself enough headroom to just pick huge random nonces.
  - zahllos 3y ago
    Note that I'm not saying use SIV. I'm just saying that SIV already does the extended nonce part: > The AEADs defined in this document calculate fresh AES keys for each nonce. I guess write an RFC for extended nonce only?
    - tptacek 3y ago
      Gotcha, thanks!
nmadden 3y ago
If you are using random nonces, segregating the nonce space to have a dedicated 32-bit block counter yields worse security bounds anyway. The whole point of that segregation is to avoid collisions when using a deterministic nonce like a counter. Unless your messages approach the size limit then randomizing the whole 128-bit nonce provides much better bounds than current GCM - effectively the same as randomized CTR mode. (ie nearer to 2^48 messages limit). So yes, using GCM with a 128-bit random nonce is already good enough for most of these cases. However IMO all of this is a distraction anyway. One of the most devastating real-world attacks involving nonce reuse was the KRACK attacks, and that involved a protocol error allowing the attacker to force nonce reuse. No amount of extra large random nonces would have saved from that. (And using random nonces in such a protocol significantly bloats the wire format). What we really need to do is move away from hugely fragile polynomial MACs. For 90%+ of usecases a more robust PRF is perfectly performant enough - eg note that the impact of KRACK was less severe against CCM than GCM. Heck, even CTR/CBC+HMAC is perfectly fast enough for many use-cases. Stop with the premature optimisation already.

zahllos 3y ago

I missed that, good catch. That said, I find the wording of dedicated counter space a bit bizarre. There are only 128 bits per block in AES - in fact I'm not aware of a widely deployed cipher which a larger block size. Whatever goes through ghash becomes the initial plaintext passed to aes under the key (this is the counter) part and then you just increment. This is just a limitation of counter mode in general: the whole IV is technically counter space and is treated as whole when evaluating the birthday bound issue. The critical part mentioned in the post is that XChaCha "hashes the key+nonce into a fresh key". A very similar technique is used un: AES-GCM-SIV (https://datatracker.ietf.org/doc/html/rfc8452#section-9 https://datatracker.ietf.org/doc/html/rfc8452#section-9). The improved security here comes not from any "counter space" or nonce extension per se but the fact that changing the IV changes the effective key used in the block primitive (i.e. the raw aes-encrypt function) as well as the first block of plaintext fed to AES by deriving these from nonce+key. So I guess this is asking for a somewhat different construction. Personally aside from the fact it is already widely deployed I'm not sure I'd keep GHASH.

tptacek 3y ago
The SIVs have somewhat different security properties than straight AEAD; they're usually a win, but not always. Moreover: the whole point of doing an extended-nonce AEAD is to avoid the extra mechanism of a nonce-misuse-resistant AEAD by giving yourself enough headroom to just pick huge random nonces.
- zahllos 3y ago
  Note that I'm not saying use SIV. I'm just saying that SIV already does the extended nonce part: > The AEADs defined in this document calculate fresh AES keys for each nonce. I guess write an RFC for extended nonce only?
  - tptacek 3y ago
    Gotcha, thanks!

nmadden 3y ago

If you are using random nonces, segregating the nonce space to have a dedicated 32-bit block counter yields worse security bounds anyway. The whole point of that segregation is to avoid collisions when using a deterministic nonce like a counter. Unless your messages approach the size limit then randomizing the whole 128-bit nonce provides much better bounds than current GCM - effectively the same as randomized CTR mode. (ie nearer to 2^48 messages limit). So yes, using GCM with a 128-bit random nonce is already good enough for most of these cases. However IMO all of this is a distraction anyway. One of the most devastating real-world attacks involving nonce reuse was the KRACK attacks, and that involved a protocol error allowing the attacker to force nonce reuse. No amount of extra large random nonces would have saved from that. (And using random nonces in such a protocol significantly bloats the wire format). What we really need to do is move away from hugely fragile polynomial MACs. For 90%+ of usecases a more robust PRF is perfectly performant enough - eg note that the impact of KRACK was less severe against CCM than GCM. Heck, even CTR/CBC+HMAC is perfectly fast enough for many use-cases. Stop with the premature optimisation already.