Note that this attack (and library) should work for up to a MAC length of 4 bytes, which is an allowed parameter by NIST and many cryptography libraries. However, the attack is too slow to demonstrate on the web: download the library to run it locally.

This attack was shown by Dutch cryptographer Niels Ferguson in Authentication weaknesses in GCM. He notes that a (then-)competing mode, CWC, avoids this attack by encrypting the GMAC polynomial with the block cipher before adding \(s\). This breaks the linear relationship between the ciphertext and the MAC.

Review the nonce reuse attack to learn why recovering the authentication key is enough to forge MACs over arbitrary ciphertexts.

After intercepting a ciphertext and MAC, our initial goal is to compute a variant of the ciphertext that has the same MAC. Simplifying for a ciphertext \(c\) of four blocks and no additional authenticated data, the GMAC MAC is computed as \[ mac = s + \vert c\vert{}h + c_3h^2 + c_2h^3 + c_1h^4 + c_0h^5, \] where \(s\) is a constant depending on the AES-GCM key and the nonce, and \(h\) is the authentication key depending only on the AES-GCM key.

Given a different ciphertext \(c'\) of the same length encrypted with the same key and nonce, the difference in their MACs can be computed as \[ mac-mac' = (c_3-c_3')h^2 + (c_2-c_2')h^3 + (c_1-c_1')h^4 + (c_0-c_0')h^5, \]

Let \(e\) be the difference between two MACs, and \(d_i\) be the difference between two blocks at position \(i\): \[ e(d_i, h) = (d_3)h^2 + (d_2)h^3 + (d_1)h^4 + (d_0)h^5, \] We want to achieve \(e=0\) but with at least one \(d_i \not= 0\) in order to obtain a different ciphertext with the same MAC.

Linear Operations in \(\mathbb{K}=\mathbb{F}_{2^{128}}\)

As described in the mission home page, each block of ciphertext, the authentication key \(h\), and the MAC are 16-byte blocks that can be interpreted as elements of the finite field \(\mathbb{K}=\mathbb{F}_{2^{128}}\).

The elements of \(\mathbb{K}\) are usually represented as polynomials with coefficients in \(\mathbb{F}_2\) of degree less than 128, where multiplication is performed modulo an irreducible polynomial given by the AES-GCM specification. This gives us a way to multiply, add, and even divide two blocks.

For this problem we will use an alternate representation: a 128-length bit vector, where the \(i\)th bit of the vector represents the coefficient of \(\alpha^i\) in the polynomial representation.

The transformation \(f(a) = ca\) for \(c, a \in \mathbb{K}\) is linear; thus, it can be represented as matrix \(M_c\). We set each column to the transformation by \(f\) of the basis vectors \(1, \alpha, \alpha^2, \ldots\): \[ M_c = \begin{bmatrix} c & c\alpha & c\alpha^2 & \ldots & c\alpha^{127} \end{bmatrix}. \]

The squaring operation \(g(a) = a^2\) is also linear: since \(2 = 0 \in \mathbb{K}\), \[(a+b)^2 = a^2 + 2ab + b^2 = a^2 + b^2,\] and for \(k \in \mathbb{F}_2\), \[(ka)^2 = k^2a^2 = ka^2. \]

Thus we can construct \[ S = \begin{bmatrix} 1^2 & \alpha^2 & (\alpha^2)^2 & \ldots & (\alpha^{127})^2 \end{bmatrix}, \] and \(g(a) = a^2\) can alternately be written \(g'(a) = Sa\), interpreting \(a\) as a vector.

Reframing the Problem

We can now rewrite our equation for \(e\) in terms of matrices and vectors: \[ e(d_i, h) = M_{d_3}h^2 + M_{d_2}h^3 + M_{d_1}h^4 + M_{d_0}h^5, \] after which we replace \(h^{2^i}\) by \(S^ih\): \[ e(d_i, h) = M_{d_3}Sh + M_{d_2}h^3 + M_{d_1}S^2h + M_{d_0}h^5. \]

To ensure that \(e\) will be a linear transformation on \(h\), we set \(d_i = 0\) if the corresponding \(h^j\) term does not have \(j\) as a power of 2, resulting in \[ e(d_i, h) = M_{d_3}Sh + M_{d_1}S^2h = (M_{d_3}S + M_{d_1}S^2)h \]

Let \(d^*\) represent the concatenation of all the remaining \(d_i\)s. The length of \(d^*\) will be logarithmic in the size of the original ciphertext as we only consider the power-of-2-indexed blocks.

\(A_{d^*}\) represents the action on \(h\) by \(d^*\): \[ A_{d^*} = (M_{d_3}S + M_{d_1}S^2) \] \[ e(d^*, h) = A_{d^*}h \]

In order for a full forgery, we need \(e=0\), but if the MAC length is reduced to \(N\) bits, we only need the first \(N\) bits of \(e\) to be zero, rather than all 128 bits. This will be satisfied if the first \(N\) rows of \(A_{d^*}\) are all zero, regardless of \(h\). In practice, zeroing out all \(N\) rows will be too difficult, so we settle for zeroing out \(M \lt N\) rows instead.

The remaining \(N-M\) relevant bits of \(e\) will be random, but we shall see it will be small enough to brute force.

Zeroing Out Rows of \(A_{d^*}\)

Changing the bits of \(d^*\) effects a linear change on the bits of \(A_{d^*}\). Consider a set of \(8\vert d^* \vert\) “basis vectors” for \(d^*\) (one for each bit), the \(i\)th basis vector having a 1 in the \(i\)th position and 0 everywhere else.

For each basis vector, compute the corresponding \(A_{d^*}\). Concatenate the first \(M\) rows into a column vector of a dependency matrix \(T\). Thus, \(T\) will have \(8\vert d^*\vert\) columns and \(128M\) rows.

We want to compute some \(d^*\) that result in the first \(M\) rows of \(A_{d^*}\) equaling zero, which is equivalent to saying \[ Td^* = 0. \]

The solution space is given by the null space (or kernel) of \(T\). Note that we need \(T\) to have more columns than rows for the matrix to be linearly dependent and thus have a non-trivial kernel.

The vectors of \(\ker T\) each represents a potential \(d^*\) that sends the first \(M\) rows of \(A_{d^*}\) to zero. Any linear combination of the vectors of the kernel will have the same effect.

Executing the Attack

Consider a random linear combination of \(\ker T\). Since these are difference vectors, they can be thought of as specifying bit flips of the original ciphertext at the appropriate positions (remember to leave the non-power-of-2 blocks alone).

By design, the first \(M\) bits of \(e\) will be zero, meaning that the first \(M\) bits of the MAC of the modified ciphertext will equal the original MAC. The remaining bits of the MAC will match with \(\frac{1}{2^{N-M}}\) probability.

Say the MAC length is \(N=32\) bits, and we let \(M=16\) (this requires intercepting a ciphertext of length \(2^{16+1}\)). We can compute random linear combinations of \(\ker T\), sending the modified ciphertexts and original MAC to Roseacrucis. If they accept (which they should after roughly \(2^{16}=65536\) attempts), we've succeeded in a forgery.

In addition to the forgery, the acceptance gives us information on \(h\): for the successful \(d^*\), since \[ e(d^*, h)[0:N-1] = 0 = A_{d^*}[0:N-1]h \] we know that \(h\) is in the kernel of the first \(N\) rows of \(A_{d^*}\). The first \(M\) rows of \(A_{d^*}\) are zero, but the next \(N-M\) rows are likely linearly independent rows. If we put these rows into a new matrix \(K\), we have \[ 0 = Kh. \] The dimensions of \(K\) are \((N-M, 128) = (16, 128)\). The kernel of such a matrix is 112-dimensional by the rank-nullity theorem, which is not enough to guess \(h\) yet.

However, each additional forgery (with good probability) gives us more linearly independent vectors to add into \(K\). Once we collect 127 linearly independent vectors (there can be no more since we know the kernel is non-trivial), the kernel of \(K\) will be 1-dimensional, and the only vector in the kernel will be \(h\).

Speeding up the Attack

Once we have our first successful forgery, we have \(K\) such that \(h \in \ker K\), meaning that some linear combination of basis vectors of \(\ker K\) equals \(h\). Let \(X\) be a basis set for \(K\), and so write \[ h = Xh'. \] We don't know \(h'\), but it is a 112-dimensional vector. Now rewrite our equation for \(e\): \[ e(A_{d^*}, h) = A_{d^*}h = A_{d^*}(Xh') = (A_{d^*}X)h', \] where \(A_{d^*}X\) is a matrix of dimensions 128 by 112.

When we construct the corresponding dependency matrix \(T\), we still have \(8\vert d^*\vert\) columns, but each row only takes 112 bits to zero out rather than 128. This lets us set more rows to zero, which in turn gives us a better chance of succeeding in the next \( d^*\) forgery.

We can continue in this fashion, each step getting more and more efficient until we collect 127 vectors in \(K\). Remember to leave at least one relevant row of \(A_{d^*}\) to be non-zero; otherwise, the forgery will succeed but won't tell us any more information about \(h\).

To complete the attack, one can recover the first \(N\) rows of \(s\) and compute a forged MAC for arbitrary ciphertext under the same nonce as in the nonce reuse attack.

Readers who wish to implement this attack themselves can try Cryptopals; specifically Set 8 Problem 64.

from aesgcmanalysis import xor, gmac, gcm_encrypt, mac_truncation_recover_secrets
from Crypto.Cipher import AES

k = b"tlonorbistertius"
mac_bytes = 4
m, aad, = b"yellow_submarine"*(2**17) = b""
nonce = b"jorgelborges"
c, mac = gcm_encrypt(k, nonce, aad, m, mac_bytes=MACBYTES)
def oracle(c, aad, mac, nonce):
	cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=mac_bytes)
	cipher.update(aad)
	cipher.decrypt_and_verify(c, mac)

h, s = mac_truncation_recover_secrets(c, mac, nonce, mac_bytes, aad, oracle)

m_forged = b"As was natural, this inordinate hope"
c_forged, aad_forged = xor(c, xor(m, m_forged)), b""
mac_forged = gmac(h, s, aad_forged, c_forged)