Breaking AES GCM part 2
In the first part I discussed some background on why AES GCM exists. GCM stands for Galois Counter Mode. Now we will take a dive into the Galois part!
Galois Field
Galois field, or finite field is a set in which the basic math operations are defined - addition, subtraction, multiplication and division. There is obviously a lot of rules for a field, but a major one is that the field must be isomorphic, i.e all elements in the field must have an inverse. Therefore Galois Fields are only defined with the order of (number of elements) p. Where p is a prime or a prime power, p^k, where k is a positive integer.
GCM and Galois
GCM works in GF(2^128) with the irreducible polynom.
x^128+x^7+x^2+x+1
In a Galois Field the irreducible polynom is like a prime number, i.e it has no factors (in that field).
Here is a python implementation of addition, multiplication and division in GF(2^k).
# Returns the degree of the polynomial
def deg(a):
deg = len(bin(a)[2:])-1
return deg
# Add and subtract is the same. Since it's GF(2^k)
def add(a,b):
return a^b
def divmod(a, b):
q, r = 0, a
while deg(r) >= deg(b):
d = deg(r) - deg(b)
q = q ^ (1 << d)
r = r ^ (b << d)
return q, r
# Multiplicative over GF(2^k)
def gf_mul(a,b,m):
# Peasant multiplication from wikipedia
p = 0
while a > 0:
if a & 1:
p = p^b
a = a >> 1
b = b << 1
# Modulus the polynomial m
if deg(b) == deg(m):
b = b^m
return p
Now when we can do math in GF(2^k), let’s implement the GHASH
GHASH
-
Pick the MAC secret. Which is a block of zero bytes encrypted with your AES key.
-
Zero pad the ciphertext and additional data block by block, so it’s divisible by the block length (AES-128=16). Then concatenate the blocks.
-
Add a block which concatenates the bit length of the ciphertext and AD.
-
For each of the concatenated blocks, do:
tag += block
tag *= MAC secret
- Mask the tag with a nonce-derived secret
mask = AES(nonce || 1)
tag += mask
Now you have derived a hash from the ciphertext, additional data, nonce and AES-key. Cool!
Here’s my GHASH implemenation in Python3.
import struct
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
# The code shown above...
from galois import *
# GF(2^128)
# p = x^128+x^7+x^2+x+1
def convert_to_field_element(a):
p = 340282366920938463463374607431768211591
if deg(a) >= deg(p):
return a^p
else:
return a
class GHASH():
def __init__(self, K, nonce, CT, AD=None):
self.K = K
self.nonce = nonce
self.CT = CT
self.AD = AD
# MAC secret
self.H = convert_to_field_element(bytes_to_long(self.E_K(b'\x00'*AES.block_size)))
# Calculate Length block
AD_len = 0 if AD==None else len(AD)
len_block = struct.pack('<Q', AD_len*8)+struct.pack('<Q', len(CT)*8)
# Pad CT and AD :-)
self.pad()
# Concatenate stuff
self.data = self.CT+len_block if self.AD == None else self.AD+self.CT+len_block
def E_K(self, data):
cipher = AES.new(self.K)
return cipher.encrypt(data)
def pad(self):
if len(self.CT) % AES.block_size != 0:
self.CT = self.CT+b'\x00'*(AES.block_size-(len(self.CT) % AES.block_size))
if self.AD != None:
if len(self.AD) % AES.block_size != 0:
self.AD = self.AD+b'\x00'*(AES.block_size-(len(self.AD) % AES.block_size))
def round(self):
g = 0
for b in self.data:
b = convert_to_field_element(bytes_to_long(b))
g ^= b
g = gf_mul(g,self.H,340282366920938463463374607431768211591)
return g
def derive(self):
# Calculate the rounds
g = self.round()
# Mask tag
s = bytes_to_long(self.E_K(self.nonce+struct.pack('<i',4)))
self.tag = g^s
return self.tag
Tag structure
Basically what the tag looks like is this (MS is MAC secret):
tag = (((((block1*MS)+block2)*MS)+len)*MS)+mask
Which becomes
tag = block1*MS^3+block2*MS^2+len*MS+mask
Vulnerability
Now we know how the tag is calculated. Say that we accidentally repeat a nonce using the same AES key. What could possibly go wrong? Well, let’s look at it.
tag1 = b1*MS^3+b2*MS^2+len1*MS+mask
tag2 = d1*MS^3+d2*MS^2+len2*MS+mask
What do they have in common? MS, of course, since it’s AES(key, ‘\x00’*block_length). What else?
The mask!
Since we work in GF(2^k) where addition and subtraction is the same, we can add the two tags together to remove the mask.
tag1+2 = (b1^d1)*MS^3+(b2^d2)*MS^2+(len1^len2)*MS
The validation of the tag is that we plug in the mac secret into the polynomial and check if the result equals zero. So the mac secret is a root to tag.
tag = f(MS) = 0
The attack is then to factor the polynomial tag1+2 to find the mac secret. If we find the MAC secret, we can fake the authentication tags for all ciphertexts under the same AES key.
