# Why is GCM not vulnerable at the birthday bound for 128 bit IV?

According to this article, which looks at attacks on Caesar candidates beyond what they claim, they include an attack on page 6 for nonce-respecting adversaries for AES-GCM which allows IVs longer than 128-bits at the birthday bound (i.e., $2^{64}$).

My question is why is GCM not susceptible to this attack for 128-bit IVs? I could understand this if the GHASH calculation for a 128 bit IV acts as a permutation (and if so, could someone please prove this)?

Actually, it turns out that GHASH on 128 bit values is a permutation (unless $H=0$; this happens with probability $2^{-128})$

GHASH of a 128 bit value $X$ simplifies to $\text{GHASH}_H(X) = H \times X$, where $H$ is a function of the key (that is, will always be the same for a specific key), and $\times$ is multiplication in the field $GF(2^{128})$.

This is a permutation, as $GF(2^{128})$ is a field, and multiplication in a field by a fixed nonzero value is always a permutation.

As for the 'collision' you mention in your comments, that actually can't happen.

If we have $H \times I_1 = 128$, that means that $H \ne 0$ and $I_1 = 128 \times H^{-1}$

If we have $H \times ((H \times I_2) \oplus 128) = 0$, that can happen only if $H = 0$ (which can't happen if the first equation holds) or $(H \times I_2) \oplus 128 = 0$, which holds only if $H \times I_2 = 128$, that is, if $I_2 = 128 \times H^{-1}$

Hence, for both to hold, we must have $I_1 = I_2$, and thus this isn't a 'collision'

• GHASH on 128-bit value is a permutation. However, the calculation of the initial block is a 256-bit value: $GHASH_H(IV||0^{64}||0^{56}10^7)$; i.e., the second block is 0 in 64 bits, then the length of the IV = 128 in 64 bits. Aug 1 '18 at 22:43
• Ok, now that I think about it XOR-ing by a fixed second block still leaves a permutation (although at probability $2^{-128}$ the first permutation gave us the value of the second block, in which case after we're XOR we'll get a result of 0); and multiplying through again by $H$ is still a permutation. So there's some additional small probability of collision (i.e., for non-zero $H$ there exists an IV $I_1$ such that $H \times I_1 = 128$, and there exists another IV, $I_2$ such that $H \times (H \times I_2 \oplus 128) = 0$, however the probability of locating that pair is just over $2^{-256}$) Aug 1 '18 at 23:39
• So please update your answer to include that reference to the second fixed block and I'll accept. Aug 1 '18 at 23:41
• I am accepting since this was a good answer (even without the reference to XOR-ing by a fixed second block). Sep 4 '18 at 15:00