Dear Nettle maintainers,
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.
Recall GCM:
Given: Key K, Nonce IV, Plaintext P, Additional authenticated data A
Step 1. Compute the subkey H: H = AES_K(0^128).
Step 2. Compute the initial counter block J0: If len(IV) == 96 bits: J0 = IV||0^31||1 Else: s = 128 * ceil(len(IV)/128) - len(IV) J0 = GHASH_H(IV||0^(s+64)||[len(IV)]_64) where [len(IV)]_64 is the 64-bit big‑endian representation of the bit length of IV.
Step 3. Generate the keystream: The counter blocks are inc_32(J0), inc_32(inc_32(J0)), ... where inc_32 increments the lowest 32 bits modulo 2^32. Each counter block is encrypted with AES under key K to produce the keystream blocks. The plaintext blocks are XORed with the keystream blocks to obtain ciphertext C.
Step 4. Compute the authentication tag: S = GHASH_H( A||C||[len(A)]_64||[len(C)]_64 ), T = S XOR AES_K(J0).
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.
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. They can now compute valid GHASH for any chosen A' and C' and generate a valid tag for any forged message: T' = GHASH_H(A'||C'||lenblock) XOR H.
We suggest following the NIST standard and prohibiting an empty IV.
Sincerely,
Feng Li and Yaobin Shen