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, 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.
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
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
Basically what the tag looks like is this (MS is MAC secret):
tag = (((((block1*MS)+block2)*MS)+len)*MS)+mask
tag = block1*MS^3+block2*MS^2+len*MS+mask
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?
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.