GCM
GCM¶
GCM is a Combination of Counter Mode (CTR) with a Message Authentication Code (MAC) using an algorithm GMAC.
Security¶
This provides both authentication and encryption.
- Vulnerable to nonce Reuse
- Might not be timing safe
https://github.com/SalusaSecondus/CryptoGotchas#aes-gcmgmac
Zero Nonce¶
If the nonce is set to All Zeros then the first block of the encryption can leak the authentication key.
This is because the Authentication key is the encryption of zero data. Using XOR you can recover the keystream if you know the plaintext.
This does depend on how GCM creates its IVs. If the IV starts off at 1 then it is possible to over flow the counter and get all IV and counter to 0.
Example:
message = b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
#Generate the GCM Key using the encryption_key and null data
auth_key = aes.ecb_encryption(b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00")
gmac = GMAC(auth_key)
# IV is 96 bytes
iv = bytes.fromhex("000000000000000000000000")
#Encrypt plaintext in Counter Mode
ciphertext = aes.ctr_encryption(iv, message)
#Use the IV as Additional authenticated data (AAD)
#So if the iv changes then the tag changes
tag_iv = gmac.digest(b"", ciphertext)
#Then Encrypt the new data with the
tag = aes.ctr_encryption(tag_iv, tag)
print(f"auth_key: {auth_key.hex()}, tag_iv: {tag_iv.hex()}, iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}")
#auth_key: aa1908ba6ab97a18ea6349b72eb1ba15, tag_iv: 00000000000000000000000000000000, iv: 000000000000000000000000, ciphertext: aa1908ba6ab97a18ea6349b72eb1ba15, tag: d387e6b9293ead8758976e85dd9e064b
Static/Repeated IV¶
Since AES-GCM encrypts the message by XORing it with the output of AES-CTR, a duplicate nonce will result in identical AES-CTR output. If you know a plaintext and the ciphertext of one message then you can decrypt the other message
Duplicate Keystream:
message = b"Cool new message that"
message2 = b'This is a testMessage'
#Initialize AES Key
#encryption_key = os.urandom(16)
encryption_key = bytes.fromhex("bb98a1ffb3ece7a0a284cb5f5cd748ec")
aes = AES(encryption_key)
#Do AES GCM for message 1
iv, ciphertext, tag = aes_gcm(aes, bytes.fromhex("4ff34dcd6d2738f70bdab5f7"), message)
print(f"iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}")
#iv: 4ff34dcd6d2738f70bdab5f7, ciphertext: 9c4f37ccd0f521bd2dc4437ebe0c1a0b87e909a6dc, tag: 11944bc91a02aaf0b72b3f1b06d6d207
#### Do AES GCM for message 2
#Do AES GCM for message 1
iv2, ciphertext2, tag2 = aes_gcm(aes, bytes.fromhex("4ff34dcd6d2738f70bdab5f7"), message2)
print(f"iv: {iv2.hex()}, ciphertext: {ciphertext2.hex()}, tag: {tag2.hex()}")
#iv: 4ff34dcd6d2738f70bdab5f7, ciphertext: 8b4831d3d0f237ea6c895268be19300bd4ee00a0cd, tag: 9d316f98882a5cf704a2e5d6bdf44474
#### XOR the known plaintext to get the keystream data
keystream = fixedlen_xor(ciphertext, b"Cool new message that")
print(f"Keystream: {keystream.hex()}")
#Keystream: df2058a0f09b44ca0da9260dcd6d7d6ea79d61c7a8
#### XOR The keystream data to get the unknown message2
plaintext = fixedlen_xor(ciphertext2, keystream)
print(f"plaintext: {plaintext}")
#plaintext: b'This is a testMessage'
assert plaintext == message2
Source
Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS
Forgery Attacks with nonce Reuse¶
When an IV is Reused with a different message or aad it can be used to recover the GMAC secret. Using this Secret you can forge messages
Example Code
"""
VolgaCTF Quals 2018 forbidden crypto task
This implements the forbidden attack on Galois/Counter Mode AES
useage: sage -python forb_expl.py
"""
from binascii import unhexlify, hexlify
from sage.all import *
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import (
Cipher, algorithms, modes
)
def encrypt(iv, key, plaintext, associated_data):
encryptor = Cipher(
algorithms.AES(key),
modes.GCM(iv),
backend=default_backend()
).encryptor()
encryptor.authenticate_additional_data(associated_data)
ciphertext = encryptor.update(plaintext) + encryptor.finalize()
return (ciphertext, encryptor.tag)
def decrypt(key, associated_data, iv, ciphertext, tag):
decryptor = Cipher(
algorithms.AES(key),
modes.GCM(iv, tag),
backend=default_backend()
).decryptor()
decryptor.authenticate_additional_data(associated_data)
return decryptor.update(ciphertext) + decryptor.finalize()
def slice_and_pad(b_str, bsize=16):
b_str += b"\x00" * (len(b_str) % bsize)
return [bytearray(b_str[k:k+bsize]) for k in range(0, len(b_str), bsize)]
def unhex_blocks(h_str, bsize=16):
if len(h_str) %2 != 0:
h_str = "0" + h_str
h_str = unhexlify(h_str)
return slice_and_pad(h_str, bsize)
def xor(a, b):
assert(len(a) == len(b))
return bytearray([a[i] ^ b[i] for i in range((len(a)))])
def byte_to_bin(byte):
b = bin(byte)[2:]
return "0" * (8 - len(b)) + b
def block_to_bin(block):
assert(len(block) == 16)
b = ""
for byte in block:
b += byte_to_bin(byte)
return b
def bytes_to_poly(block, a):
f = 0
for e, bit in enumerate(block_to_bin(block)):
f += int(bit) * a**e
return f
def poly_to_int(poly):
a = 0
for i, bit in enumerate(poly._vector_()):
a |= int(bit) << (127 - i)
return a
def poly_to_hex(poly):
return (hex(poly_to_int(poly))[2:]).upper()
def recover_mac_key(authed_plaintext1, authed_plaintext2, authed_plaintext3, ciphertext_1, ciphertext_2, ciphertext_3, tag1, tag2):
# Assuming aad1 == aad2 and len1 == len2
# => (tagA + tagB) = ( CTA[0] x CTB[0]) * H ** 2
# => H ** 2 = (tagA + tagB) * Inv( CTA[0] x CTB[0])
# => H = sqrt((tagA + tagB) * Inv( CTA[0] x CTB[0]))
assert len(authed_plaintext1) == len(authed_plaintext2)
assert len(ciphertext_1) == len(ciphertext_2)
plantext_length = (len(ciphertext_1) // 2) * 8
authed_planetext_len = len(authed_plaintext1) * 8
length_block = unhex_blocks(hex((authed_planetext_len << 64) | (plantext_length * 8))[2:-1])
ciphertexts = [ xor(ct1, ct2) for ct1, ct2 in zip(ciphertext_1, ciphertext_2) ]
tags = xor(tag1, tag2)
authed_plaintext = [ xor(ct1, ct2) for ct1, ct2 in zip(authed_plaintext1, authed_plaintext2) ]
F, a = GF(2**128, name="a").objgen()
R, H = PolynomialRing(F, name="H").objgen()
#Set up f1
#f1 = A1_p * H**5 + C1_p[0] * H**4 + C1_p[1] * H**3 + C1_p[2] * H**2 + L_p * H + T1_p
f1 = bytes_to_poly(authed_plaintext1[0], a)
for data in authed_plaintext1[1:]:
f1 = f1 * H + bytes_to_poly(data, a)
for data in ciphertext_1:
f1 = f1 * H + bytes_to_poly(data, a)
f1 = f1 * H + bytes_to_poly(length_block[0], a)
f1 = f1 * H + bytes_to_poly(tag1, a)
#Setup F3
#f3 = A3_p * H**5 + C3_p[0] * H**4 + C3_p[1] * H**3 + C3_p[2] * H**2 + L_p * H
f3 = bytes_to_poly(authed_plaintext3[0], a)
for data in authed_plaintext3[1:]:
f3 = f3 * H + bytes_to_poly(data, a)
for data in ciphertext_3:
f3 = f3 * H + bytes_to_poly(data, a)
f3 = f3 * H + bytes_to_poly(length_block[0], a)
f3 = f3 * H
#Setup P
#p = A_p * H**5 + C_p[0] * H**4 + C_p[1] * H**3 + C_p[2] * H**2 + T_p
p = bytes_to_poly(authed_plaintext[0], a)
for data in authed_plaintext[1:]:
p = p * H + bytes_to_poly(data, a)
for data in ciphertexts:
p = p * H + bytes_to_poly(data, a)
p = p * H
p = p * H + bytes_to_poly(tags, a)
keys = []
f_tags = []
for root, _ in p.roots():
keys.append(poly_to_hex(root))
EJ = f1(root)
f_tags.append(poly_to_hex(f3(root) + EJ))
return keys, f_tags
static_iv = bytes.fromhex("9315225df88406e555909c5aff5269aa")
key = bytes.fromhex("9b43198e0832b5f8090f496f9384e91146816d22d51c4294cd4d3edc24d99597")
ciphertext_1, tag_1 = encrypt(static_iv, key, b"From: John Doe\nTo: John Doe\nSend 100 BTC", b"John Doe")
authed_plaintext1 = slice_and_pad(b"John Doe")
ciphertext_2, tag_2 = encrypt(static_iv, key, b"From: VolgaCTF\nTo: VolgaCTF\nSend 0.1 BTC", b"VolgaCTF")
authed_plaintext2 = slice_and_pad(b"VolgaCTF")
ciphertext_3, tag_3 = encrypt(static_iv, key, b"From: John Doe\nTo: VolgaCTF\nSend ALL BTC", b"John Doe")
authed_plaintext3 = slice_and_pad(b"John Doe")
print(f"{ciphertext_1.hex()}, {tag_1.hex()}")
print(f"{ciphertext_2.hex()}, {tag_2.hex()}")
print(f"{ciphertext_3.hex()}, {tag_3.hex()}")
cipher = Cipher(
algorithms.AES(key),
modes.ECB(),
backend=default_backend()
).encryptor()
output = cipher.update(b"\x00" * 16) + cipher.finalize()
print(f"Auth Key: {output.hex()}")
# tagA = (((((aad1 * H) + CTA[0]) * H) + len1) * H) + X
# tagB = (((((aad2 * H) + CTB[0]) * H) + len2) * H) + X
# tagA + tagB = ((((aad1 * H) + CTA[0]) * H) + len1) * H) + (((((aad * H) + CB1) * H) + len2) * H) + (X xor X)
# = (aad1 * H^3 + CA1 * H^2 + len1 * H) + (aad2 * H^3 + CB1 * H^2 + len2 * H)
# = (aad1 x aad2) * H^3 + (CA1 x CB2) * H^2 + (len1 x len2) * H
# Assuming aad1 == aad2 and len1 == len2
# => (tagA + tagB) = ( CTA[0] x CTB[0]) * H ** 2
# => H ** 2 = (tagA + tagB) * Inv( CTA[0] x CTB[0])
# => H = sqrt((tagA + tagB) * Inv( CTA[0] x CTB[0]))
auth_keys, forged_tags = recover_mac_key(authed_plaintext1, authed_plaintext2, authed_plaintext3, slice_and_pad(ciphertext_1), slice_and_pad(ciphertext_2), slice_and_pad(ciphertext_3), tag_1, tag_2)
print(f"GMAC Key: {auth_keys}")
print(f"Forged Tag: {forged_tags}")
"""
368b81e98fe704c132229db5a2f2f61fc34cb88f1fd42e20904fc1a7d55c95740f0144978f224cda, e27ee66ab816204123cab7eb243ac616
368b81e98fe718c1362bdcb299d1f61fc34cb8931fd027619774e2a7d55c95740f005a968f224cda, 98c5ccf4ebce1cd2e2db5fc854a2dce4
368b81e98fe704c132229db5a2f2f61fc34cb8931fd027619774e2a7d55c95740f7138eb8f224cda, b04867e368349d384d963b5150d6660d
Auth Key: 5d8f12b1723fad9cc6e60ad0258def6f
GMAC Key: ['62771BC867FD0D2CF6144C43E3F4A15A', '5D8F12B1723FAD9CC6E60AD0258DEF6F']
Forged Tag: ['87A972FB4AE90C941E72E5E47A61DA36', 'B04867E368349D384D963B5150D6660D']
"""
Implementation¶
Implications change depending on library
- https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L181
import os
from aes_lib import AES
from cryptopals_lib import fixedlen_xor, to_blocks, bytes_to_int, int_to_bytes
class GMAC():
def __init__(self, authentication_key):
self.length = 16
self.authentication_key = authentication_key
def mult_Galios_Feild(self, y):
"""Multiply two polynomials in GF(2^m)/g(w)
g(w) = w^128 + w^7 + w^2 + w + 1
(operands and result bits reflected)"""
temp_key = bytes_to_int(self.authentication_key)
y = bytes_to_int(y)
z = 0
#print(temp_key,y,z)
while y & ((1<<128)-1):
if y & (1<<127):
z ^= temp_key
y <<= 1
if temp_key & 1:
temp_key = (temp_key>>1)^(0xe1<<120)
else:
temp_key >>= 1
return z
def xor_Mult_with_key(self, p,q):
#print("p = {}, q = {}".format(p,q))
test = fixedlen_xor(p,q)
#print("xor {}".format(test))
test = self.mult_Galios_Feild(test)
test = int_to_bytes(test).rjust(self.length, b'\x00')
#print("output {}".format(test))
#print()
return test
def gLen(self, s):
#Get Byte length * 8
return (len(s) << 3).to_bytes(2, byteorder="big")
def digest(self, additional_authenticated_data, input_data):
output = b"\x00"*16
#Pad additional_authenticated_data
additional_authenticated_data_padded = additional_authenticated_data + bytes((self.length-len(additional_authenticated_data)%self.length)%self.length)
#print("Padded Authenticated Data: {}".format(additional_authenticated_data_padded))
#Pad Input Data
input_data_padded = input_data + bytes((self.length-len(input_data)%self.length)%self.length)
#print("Input Data: {}".format(input_data_padded))
#For each block of Padded additional_authenticated_data xor and mult with the auth key
for aad_block in to_blocks(additional_authenticated_data_padded, self.length):
output = self.xor_Mult_with_key(output, aad_block)
#print("ADD OutputData: {}".format(input_data_padded))
#For each block of Padded input_data xor and mult with the auth key
for input_block in to_blocks(input_data_padded, self.length):
output = self.xor_Mult_with_key(output, input_block)
#Also XOR and mult with the length of the data
len_input = self.gLen(additional_authenticated_data) + self.gLen(input_data)
return self.xor_Mult_with_key(output, len_input.rjust(self.length, b'\x00'))
def aes_gcm(aes_obj, iv, message):
#Generate the GCM Key using the encryption_key and null data
auth_key = aes.ecb_encryption(b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00")
gmac = GMAC(auth_key)
# IV is 96 bytes
if iv == None:
iv = bytes.fromhex("4ff34dcd6d2738f70bdab5f7")
#iv = os.urandom(16)
# If tag is 96 bytes then shift and add 1 to make it 128 bits long
# Else GMAC the IV
if len(iv) == 12:
tag_iv = iv + b"\x00\x00\x00\x01"
else:
tag_iv = gmac.digest(iv, b"")
#Encrypt plaintext in Counter Mode
ciphertext = aes.ctr_encryption(iv, message)
#Use the IV as Additional authenticated data (AAD)
#So if the iv changes then the tag changes
tag = gmac.digest(b"", ciphertext)
#Then Encrypt the new data with the
tag = aes.ctr_encryption(tag_iv, tag)
#print(f"auth_key: {auth_key.hex()}, tag_iv: {tag_iv.hex()}, iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}")
return [iv, ciphertext, tag]
if __name__ == '__main__':
message = b"Cool new message that"
#Initialize AES Key
#encryption_key = os.urandom(16)
encryption_key = bytes.fromhex("bb98a1ffb3ece7a0a284cb5f5cd748ec")
aes = AES(encryption_key)
#Do AES GCM for message 1
iv, ciphertext, tag = aes_gcm(aes, bytes.fromhex("4ff34dcd6d2738f70bdab5f7"), message)
print(f"iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}")
#iv: 4ff34dcd6d2738f70bdab5f7, ciphertext: 9c4f37ccd0f521bd2dc4437ebe0c1a0b87e909a6dc, tag: 11944bc91a02aaf0b72b3f1b06d6d207