"Feng Li" lifeng8425@stu.xmu.edu.cn writes:
We have identified a security issue in Nettle’s GCM implementation. An adversary can exploit this to recover the authentication subkey H and forge arbitrary messages with valid tags. We provide the detail below.
Thanks for the report.
What happens when the nonce (IV) is empty (Corresponding to this part of the code https://github.com/gnutls/nettle/blob/master/gcm.c ).
let len(IV) = 0 bits.
Step 1. H = AES_K(0^128)
Step 2. Compute J0:
s = 128 * ceil(0/128) - 0 = 0
The input to GHASH is: IV||0^(s+64)||[len(IV)]_64 = (empty)||0^64||0^64 = 0^128.
So J0 = GHASH_H(0^128) = 0^128. (The GHASH accumulator starts at zero, XOR with the zero block remains zero, then multiply by H gives zero. So GHASH_H(0^128) = 0^128.)
Step 4. Authentication tag:
The mask used to XOR the GHASH result is AES_K(J0) = AES_K(0^128).
But by definition this is exactly H. Therefore: T = S XOR H (where S = GHASH_H(A||C||length block)).
This equation contains only one unknown variable: H. All other values (A, C, lenblock, T) are known to an attacker.
I agree it looks bad that AES_K(J0) (intended to hide the raw ghash value) in this case happen to be the same as the ghash subkey H.
Now, GHASH_H is a polynomial function in H over GF(2^128). For m blocks of input (A, C, and the length block), the GHASH result can be expressed as: S = B1 * H^m XOR B2 * H^(m-1) XOR ... XOR Bm * H where the B_i are known from the input blocks. Therefore the tag equation becomes: B1 * H^m XOR B2 * H^(m-1) XOR ... XOR (Bm XOR 1) * H XOR T = 0. This is a polynomial equation of degree m in H over the finite field GF(2^128).
Once the attacker recovers H, they have the authentication subkey.
One question on this recovery: I think the polynomial equation can have multiple roots. My abstract algebra is a bit rusty, but I would expect at most m distinct roots, with actual number depending on what the factors of the polynomial look like: each unique linear factor corresponds to a root, and hence both repeated linear factors, and irreducible factors of higher degree, reduce the number of roots. To the attacker, each of the roots is a candidate for H, and as far as I understand, for a successful attack, the attacker has to identify, or guess, the right one. Does that make sense?
We suggest following the NIST standard and prohibiting an empty IV.
I agree this makes a lot of sense. This would be a documentation change, backed up by an
assert (length > 0);
in gcm_set_iv. Does that seem right?
Regards, /Niels