Recall that the AES-GCM ciphertext is computed as the XOR of the keystream and the message. One can modify the bits of the ciphertext arbitrarily to effect the same change in the decrypted plaintext.

Where certain bits of the plaintext are already known, the attacker can fully determine the same bits of the forged plaintext. If nonces are reused, the keystream will be identical, allowing us to recover plaintext via crib dragging, which makes this attack particularly effective: \[ c' = c \oplus m \oplus m'. \]

However, we still need to compute a new MAC over the forged ciphertext. Simplifying for a ciphertext \(c\) of two blocks, the GMAC MAC is computed as \[ mac = s + (len)h + c_1h^2 + c_0h^3, \] 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.

If we intercept a second ciphertext \(c'\) encrypted under the same key and nonce, we can compute \[ mac + mac' = (s + s') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3, \] Since \(s = s'\) and \(x+x=0\) in \(\mathbb{F}_{2^{128}}\), we are left with the polynomial equation \[ 0 = (mac + mac') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3 \] where all variables are known other than \(h\). Thus, recovering \(h\) is a matter of finding the roots by factoring the polynomial.

We plug \(h\) back into the first equation to recover \(s\), and finally, we can forge the MAC for arbitary ciphertext under the same nonce. Note that there may be multiple possible monomial roots; in this case, one can check each possibility online.

from aesgcmanalysis import xor, gmac, gcm_encrypt, gcm_decrypt, nonce_reuse_recover_secrets

k = b"tlonorbistertius"
nonce = b"jorgelborges"
m1 = b"The universe (which others call the Library)"
aad1 = b"The Anatomy of Melancholy"
m2 = b"From any of the hexagons one can see, interminably"
aad2 = b"Letizia Alvarez de Toledo"

c1, mac1 = gcm_encrypt(k, nonce, aad1, m1)
c2, mac2 = gcm_encrypt(k, nonce, aad2, m2)

# Recover the authentication key and blind from public information
possible_secrets = nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2)

# Forge the ciphertext
m_forged = b"As was natural, this inordinate hope"
assert len(m_forged) <= len(m1)
c_forged = xor(c1, xor(m1, m_forged))
aad_forged = b"You who read me, are You sure of understanding my language?"

# Check possible candidates for authentication key
succeeded = False
for h, s in possible_secrets:
    mac_forged = gmac(h, s, aad_forged, c_forged)
    try:
        assert gcm_decrypt(k, nonce, aad_forged, c_forged, mac_forged) == m_forged
        succeeded = True
        print(c_forged.hex(), mac_forged.hex())
    except AssertionError:
        pass
assert succeeded

Once the polynomial difference is computed, one can use SageMath to compute the factors:

K = GF(2**128, name='x', modulus=x^128+x^7+x^2+x+1)
x = K.gen()
S = PolynomialRing(K, 'y')
y = S.gen()
p = (x^127 + x^125 + x^121 + x^118 + x^117 + x^116 + x^113 + x^111 + x^108 + x^105 + x^102 + x^99 + x^97 + x^95 + x^89 + x^87 +
 x^85 + x^84 + x^81 + x^78 + x^73 + x^71 + x^69 + x^67 + x^65 + x^63 + x^62 + x^59 + x^57 + x^55 + x^54 + x^53 + x^52 + x^51 +
x^49 + x^47 + x^46 + x^45 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^33 + x^29 + x^28 + x^25 + x^21 + x^20 + x^17 + x^15 + x
^13 + x^9 + x^7 + x^4 + x^3 + x)*y^5 + (x^127 + x^125 + x^121 + x^118 + x^117 + x^116 + x^113 + x^111 + x^108 + x^105 + x^102 +
 x^99 + x^97 + x^95 + x^89 + x^87 + x^85 + x^84 + x^81 + x^78 + x^73 + x^71 + x^69 + x^67 + x^65 + x^63 + x^62 + x^59 + x^57 +
x^55 + x^54 + x^53 + x^52 + x^51 + x^49 + x^47 + x^46 + x^45 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^33 + x^29 + x^28 + x
^25 + x^21 + x^20 + x^17 + x^15 + x^13 + x^9 + x^7 + x^4 + x^3 + x)*y^4 + (x^127 + x^125 + x^124 + x^123 + x^122 + x^120 + x^11
9 + x^118 + x^115 + x^112 + x^111 + x^110 + x^109 + x^108 + x^106 + x^101 + x^100 + x^99 + x^98 + x^96 + x^93 + x^88 + x^87 + x
^84 + x^83 + x^82 + x^78 + x^77 + x^74 + x^71 + x^70 + x^69 + x^68 + x^65 + x^62 + x^61 + x^60 + x^57 + x^55 + x^53 + x^50 + x^
49 + x^47 + x^46 + x^44 + x^43 + x^41 + x^40 + x^39 + x^37 + x^36 + x^35 + x^34 + x^33 + x^31 + x^30 + x^25 + x^19 + x^16 + x^1
4 + x^13 + x^12 + x^11 + x^10 + x^5 + x^2 + x + 1)*y^3 + (x^124 + x^123 + x^121 + x^120 + x^119 + x^118 + x^117 + x^116 + x^115
 + x^113 + x^112 + x^110 + x^107 + x^106 + x^104 + x^103 + x^101 + x^99 + x^98 + x^95 + x^94 + x^83 + x^82 + x^81 + x^80 + x^79
 + x^77 + x^76 + x^75 + x^73 + x^72 + x^67 + x^64 + x^63 + x^62 + x^61 + x^59 + x^57 + x^56 + x^54 + x^53 + x^51 + x^49 + x^48
+ x^46 + x^45 + x^44 + x^42 + x^36 + x^35 + x^34 + x^33 + x^31 + x^28 + x^22 + x^21 + x^17 + x^12 + x^11 + x^10 + x^8 + x^5 + x
^4 + 1)*y^2 + (x^120 + x^119 + x^56 + x^55)*y + (x^127 + x^126 + x^125 + x^124 + x^123 + x^118 + x^117 + x^116 + x^115 + x^114
+ x^113 + x^105 + x^103 + x^98 + x^96 + x^94 + x^91 + x^90 + x^89 + x^87 + x^86 + x^85 + x^83 + x^81 + x^80 + x^78 + x^77 + x^7
0 + x^66 + x^63 + x^62 + x^59 + x^58 + x^54 + x^53 + x^52 + x^50 + x^47 + x^45 + x^44 + x^42 + x^40 + x^39 + x^37 + x^35 + x^34
 + x^30 + x^29 + x^27 + x^26 + x^25 + x^23 + x^18 + x^16 + x^14 + x^13 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3
+ 1)
for factor, _ in p.factor():
    if factor.degree() == 1:
        print('Authentication key:', factor - y)

However, the library powering this demonstration implements polynomial factoring over finite fields from scratch, which is an edifying exercise.

We present advice for those who wish to implement polynomial factorization as well:

• The gcd of two polynomials is unique only up to multiplication by a non-zero constant because “greater” is defined for polynomials in terms of degree. When used in algorithms, gcd refers to the monic gcd, which is unique.
• The inverse Frobenius automorphism (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}})\).