2
$\begingroup$

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)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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'

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – MotiNK
    Commented Aug 1, 2018 at 22:43
  • $\begingroup$ 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}$) $\endgroup$
    – MotiNK
    Commented Aug 1, 2018 at 23:39
  • $\begingroup$ So please update your answer to include that reference to the second fixed block and I'll accept. $\endgroup$
    – MotiNK
    Commented Aug 1, 2018 at 23:41
  • $\begingroup$ I am accepting since this was a good answer (even without the reference to XOR-ing by a fixed second block). $\endgroup$
    – MotiNK
    Commented Sep 4, 2018 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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