4 ms·

I don't think it is _just_ as brittle. There are two mitigating factors: 1. XChaCha20-Poly1305 (I think you _should_ be using the extended nonce version if you

I don't think it is _just_ as brittle. There are two mitigating factors: 1. XChaCha20-Poly1305 (I think you _should_ be using the extended nonce version if you're going for a random nonce) ihas twice the amount of bits of AES-GCM. That alone make birthday collisions an entire universe of order of magnitudes less likely. 2. I might be wrong here, but I'm not quite sure if the Poly1305 MAC itself is as brittle as the GHASH MAC in GCM. That being said, if you're really paranoid about your RNG, even the greater safety margins won't help. If you use the Sony PS3 RNG which always returns 4, it doesn't matter how many bits of random nonce you've got. You do have nonce-misuse resistant constructions such AES-GCM-SIV. I'm not a cryptographer so I can't comment about how well reviewed they are, but they are only claim to protect you against accidental nonce misuse, not intentionally fixed nonces, so if you have the legendary PS3 RNG, I guess it's no dice (sorry for the pun).

KMag 5y ago
Point taken about different partitions of the IV into counter and nonce. As far as GCM GHASH vs Poly1305, they use the same math. Just one is in a Galois field modulo the prime 2**130 - 5 and the other is in a 128-bit binary Galois field reduced by a fixed primitive polynomial (the lexographically smallest 128-bit primitive binary polynomial, IIRC). Poly1305 does drop two bits of the 130-bit result field element when outputting the tag, so I guess that does provide a bit more work for an attacker, but they're both simple polynomial evaluations in finite fields of similar size. Breaking them is just finite field algebra if the r and s values are reused. Poly1305 is a MAC taken by calculating the tag: def tag(r, s, message): v = 0 # No associated data case for chunk in message: v += chunk + 2**128 v = (v * r) % (2**130 - 5) return ((v + s) % (2**130 - 5)) % 2**128 The GCM GHASH tag is: # multiply() is multiplication in GF 2**128 # add() is addition in GF 2**128 (a.k.a. 128-bit XOR) def tag(key, iv, message): r = AES_encrypt(key, 0) s = AES_encrypt(key, iv) v = 0 # No associated data case for chunk in message: v = add(v, chunk) v = multiply(v, r) return add(v, s) (I think the extra 2**128 addition inside the Poly1305 loop is to ensure the function doesn't have a fixed point at zero, but I'm not sure.)
- KMag 5y ago
  Ahh... I've misunderstood that extra bit, and I think it's never at the 2**128 position. I've misread the code for padding. A stop bit is used to disambiguate zero padding from messages that end in zeroes, similar to most hash function message padding. How silly of me.
  - tptacek 5y ago
    There's several issues with GCM; the most obvious is the susceptibility to repeated nonces (notice that I compared GCM to CBC+HMAC, the most common generic composition) but there's also GCM's weakness with shortened tags, the fact that GCM relies on a multiplication operation that wants tables for efficient software implementations, and the short nonce, which makes it dicey to use random nonces and also limits how much you can encrypt. The original chapoly constructions aren't as brittle, but share the biggest problem (the nonce uniqueness requirement). But later chapoly constructions allow for wide nonces, which makes it reasonable to use fully random nonces. I don't care if people use GCM or not; I'd comfortably use it if it was the only AEAD available in my standard library. But I agree with the root comment on this thread that suggests it's a weird thing to brag about.

KMag 5y ago

Point taken about different partitions of the IV into counter and nonce. As far as GCM GHASH vs Poly1305, they use the same math. Just one is in a Galois field modulo the prime 2**130 - 5 and the other is in a 128-bit binary Galois field reduced by a fixed primitive polynomial (the lexographically smallest 128-bit primitive binary polynomial, IIRC). Poly1305 does drop two bits of the 130-bit result field element when outputting the tag, so I guess that does provide a bit more work for an attacker, but they're both simple polynomial evaluations in finite fields of similar size. Breaking them is just finite field algebra if the r and s values are reused. Poly1305 is a MAC taken by calculating the tag: def tag(r, s, message): v = 0 # No associated data case for chunk in message: v += chunk + 2**128 v = (v * r) % (2**130 - 5) return ((v + s) % (2**130 - 5)) % 2**128 The GCM GHASH tag is: # multiply() is multiplication in GF 2**128 # add() is addition in GF 2**128 (a.k.a. 128-bit XOR) def tag(key, iv, message): r = AES_encrypt(key, 0) s = AES_encrypt(key, iv) v = 0 # No associated data case for chunk in message: v = add(v, chunk) v = multiply(v, r) return add(v, s) (I think the extra 2**128 addition inside the Poly1305 loop is to ensure the function doesn't have a fixed point at zero, but I'm not sure.)

KMag 5y ago
Ahh... I've misunderstood that extra bit, and I think it's never at the 2**128 position. I've misread the code for padding. A stop bit is used to disambiguate zero padding from messages that end in zeroes, similar to most hash function message padding. How silly of me.
- tptacek 5y ago
  There's several issues with GCM; the most obvious is the susceptibility to repeated nonces (notice that I compared GCM to CBC+HMAC, the most common generic composition) but there's also GCM's weakness with shortened tags, the fact that GCM relies on a multiplication operation that wants tables for efficient software implementations, and the short nonce, which makes it dicey to use random nonces and also limits how much you can encrypt. The original chapoly constructions aren't as brittle, but share the biggest problem (the nonce uniqueness requirement). But later chapoly constructions allow for wide nonces, which makes it reasonable to use fully random nonces. I don't care if people use GCM or not; I'd comfortably use it if it was the only AEAD available in my standard library. But I agree with the root comment on this thread that suggests it's a weird thing to brag about.