README.md

Forbidden Attack on AES-GCM

Prerequisites:

1. Finite Fields
2. AES-GCM

In this section, we will discuss an attack on AES-GCM due to reusage of nonce during encryption process. The attack can reveal value of H which can then help the attacker to forge authentication tag T.

We will be using the same symbols as we did while discussing the internals of AES-GCM

Deriving Polynomial for Authentication Tag

In this section, we will see polynomial representation of authentication tag generation.

We know that the tag is generated using a series of multiplication over finite field GF(2²⁵⁶) and GF(2**256) is an Extension Field.

There are broadly two categories of Finite Fields: Prime Fields and Extension Fields. Prime Fields are of the form GF(p) where p is a prime number and consist of integers in {0,..., p}. Extension fields are of the form GF(p^m), where p is a prime number and m is a positive integer and consist of polynomials of the form

a_m-1x^m-1 + a_m-2x^m-2 + ... + a₁x + a₀

Here, a can assume values in {0,..., p-1}

GF(2^m) is one of the most frequently used fields in cryptography. Since multiplication in AES-GCM happens over Finite Field GF(2²⁵⁶) (Extension Field), elements of this Finite Field are polynomials.

Hence, all the computation discussed in authtag generation process of AES-GCM is over polynomials (The function mod_polynomial_mult(self, a, b, p) in authtag process is an implementation of multiplication of two polynomials a and b modulo an irreducible polynomial f = 1 + x + x<sup>2</sup> + x<sup>7</sup> + x<sup>128</sup> over GF(2²⁵⁶)).

We will discuss a trivial case scenario in encryption and authtag generation part of AES-GCM, and then derive the generalised polynomial that can be used to generate authentication tag.

Note: Polynomial Addition over a Finite Field GF(2^m) is equivalent to XOR operation over integers.

Case Scenario-1: Alice (sender) wants to use AES-GCM to encrypt one block of plaintext (16 bytes) and generate authentication tag for one block of associated data and one block of ciphertext corresponding to the one block of plaintext.

Authentication Tag in this case can be written as:

g(X) = ((A₁X + C₁)X + L)X + S

where L is len(A) || len(C), S is E_k(J₀) and X is the authentication key. The above polynomial is equal to:

g(X) = A₁X³ + C₁X² + LX + S

Case Scenario-2: Alice (sender) wants to use AES-GCM to encrypt two blocks of plaintext (32 bytes) and generate authentication tag for two blocks of associated data and two blocks of ciphertext corresponding to two blocks of plaintext.

Authentication Tag in this case can be written as:

((((A₁X + A₂)X + C₁)X + C₂)X + L)X + S

This is equal to:

A₁X⁵ + A₂X⁴ + C₁X³ + C₂X² + LX + S

Generalised polynomial: We can now define polynomial for generation of authentication tag with m blocks of associated data and n blocks of plaintext:

g(X) = A₁X^m+n+1 + ... + A_mXⁿ⁺² + C₁Xⁿ⁺¹ + ... + C_nX² + LX + S

where L is len(A) || len(C), S is E_k(J₀) and X is the authentication key. Also, when X=H, g(H) = T (T is the authentication tag generated in AES-GCM)

Now that we have derived polynomial expression for authentication tag generation in AES-GCM, let us see how the Forbidden Attack works!

The Forbidden Attack

For simplicity of understanding, consider a scenario where Alice (sender) sends two messages containing one block of plaintext (16 bytes) each (no associated data blocks) and generates authentication tag for ciphertext of each message using the same nonce. Our intention, as an attacker is to find out the value of H that is the authentication key.

Note: An important condition for this attack to work is for nonce to be reused in generating ciphertext and authentication tag pair of two different messages.

We denote authentication tag polynomials for the two messages as g₁(X) and g₂(X). Each polynomial can be written as:

g₁(X) = C_1,1X² + L₁X + S
g₂(X) = C_2,1X² + L₂X + S

where C_1,1 and C_2,1 signify first block of ciphertext corresponding to the first message and first block of ciphertext corresponding to the second message respectively.

Note that S and L are same for both the polynomial expressions.
We know that L = len(A) || len(C), none of the messages have any associated data and both of them have same lengths of ciphertext = 16 bytes. Hence, L is same for both polynomial expressions.
We also know that S = E_k(J₀) and J₀ contains Nonce. Since the two messages use same Nonce, we have same values of S for the above polynomial expressions.

Also, we cannot solve any of the above polynomials separately and get the value of X. Why? Because we don't know the value of S = E_k(J₀). If by any method we can eliminate S from the expression, and equate the polynomial to zero, we can simply solve the quadratic equation and get the value of X (authentication key). Let us now see how we can do that.

We know that g₁(H) = T₁ and g₂(H) = T₂, adding T₁ on both sides of polynomial 1 and T₂ on both sides of polynomial 2, we can write:

g'₁(X) = C_1,1X² + L₁X + S + T₁
g'₂(X) = C_2,1X² + L₂X + S + T₂

g'₁(H) = g'₂(H) = 0, (Since g(H) = T, g(H) + T over a Finite Field of the form GF(2^m) will be equivalent to g(h) ^ T = 0). Now we add the two polynomials to get:

f(X) = (C_1,1+C_2,1)X² + (L₁ + L₂)X + (T₁ + T₂)

We know that f(H) = 0, so we can easily solve the above quadratic equation to get all possible values of H. The number of possible values of H will be equal to the degree of the polynomial which, in turn, depends upon the number of plaintext and associated data blocks.

After we get the value of H we can easily generate authentication tag for any message by calling the authtag_gen() function from AES-GCM-implementation.py!

References

1. Nonce Disrespecting Adverseries: Practical Forgery Attacks on GCM in TLS