4 ms·

From the NIST doc for GCM: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecial

From the NIST doc for GCM: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpubli... The IV can be any length up to 2^64-1. The reason for picking 96-bit IVs is that other values require an extra invocation of GHASH (page 15). The document recommends 96-bit for interoperability but that's by no means a requirement. The X part is thus in theory already allowed.

JoshTriplett 3y ago
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.
tptacek 3y ago
As I understand it, the limitation people are concerned about is that of the IV/counter block. It's not that you can't hash an arbitrarily large nonce down to 96 bits; you obviously can. It's that ultimately you've only got 96 bits on the wire to express your nonce, and if they collide GCM falls apart. That's the X trick in XSalsa: the wider nonce gets laundered into the key.
- amadvance 3y ago
  Looking at the implementation, the longer nonce is hashed to 128 bits, with the last 32 used as a starting counter. So, if you don't use the whole 32 bits space of the counter, you are effectively using more than 96 bits nonce. Sure, no more than 128 bits, but indeed better than 96.
  - nmadden 3y ago
    Right, and 128 bits is way better than 96. The only thing to potentially be aware of is that the randomized block counter may end up overflowing if it happens to end up with a large initial value (or you encrypt large messages). That should be fine, but it's quite likely that some GCM implementations are not expecting that and either blow up when the counter resets to 0 or do something else unexpected. So although I think this is theoretically a fine thing to do, I absolutely wouldn’t trust my sensitive data to it.

JoshTriplett 3y ago

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.

tptacek 3y ago

As I understand it, the limitation people are concerned about is that of the IV/counter block. It's not that you can't hash an arbitrarily large nonce down to 96 bits; you obviously can. It's that ultimately you've only got 96 bits on the wire to express your nonce, and if they collide GCM falls apart. That's the X trick in XSalsa: the wider nonce gets laundered into the key.

amadvance 3y ago
Looking at the implementation, the longer nonce is hashed to 128 bits, with the last 32 used as a starting counter. So, if you don't use the whole 32 bits space of the counter, you are effectively using more than 96 bits nonce. Sure, no more than 128 bits, but indeed better than 96.
- nmadden 3y ago
  Right, and 128 bits is way better than 96. The only thing to potentially be aware of is that the randomized block counter may end up overflowing if it happens to end up with a large initial value (or you encrypt large messages). That should be fine, but it's quite likely that some GCM implementations are not expecting that and either blow up when the counter resets to 0 or do something else unexpected. So although I think this is theoretically a fine thing to do, I absolutely wouldn’t trust my sensitive data to it.