diff options
| -rw-r--r-- | aesgcmanalysis.py | 275 |
1 files changed, 242 insertions, 33 deletions
diff --git a/aesgcmanalysis.py b/aesgcmanalysis.py index 73a9ef8..abdfdb3 100644 --- a/aesgcmanalysis.py +++ b/aesgcmanalysis.py @@ -1,4 +1,4 @@ -import random, struct, hmac, itertools +import random, struct, hmac, itertools, math from Crypto.Cipher import AES import numpy as np @@ -77,9 +77,9 @@ def gf128_mod(a, m=gcm_modulus): def gf128_egcd(a, b): """Compute g, x, y such that g | a, g | b, g = ax + by; - for any h such that h | a and h | b, gf128_deg(g) >= gf128_deg(h). + for any h such that h | a and h | b, gf128_deg(g) >= gf128_deg(h). >>> assert gf128_egcd(x**2 + 1, x**1 + 1) == (x**1 + 1, 0, 1) - >>> assert gf128_egcd(x**12 + x**4, x**5 + 1) == (x**1 + 1, x**3 + x**2 + 1, x**10 + x**9 + x**7 + x**5 + x**4 + x**1 + 1) + >>> assert gf128_egcd(x**12 + x**4, x**5 + 1) == (x**1 + 1, x**3 + x**2 + 1, x**10 + x**9 + x**7 + x**5 + x**4 + x**1 + 1) >>> assert gf128_egcd(x**64 + x**2, x**37 + x**12 + 1) == (1, x**35 + x**34 + x**33 + x**31 + x**30 + x**28 + x**27 + x**25 + x**24 + x**21 + x**20 + x**18 + x**17 + x**15 + x**14 + x**12 + x**11 + x**9 + x**7 + x**6 + x**4 + x**3 + x**1 + 1, x**62 + x**61 + x**60 + x**58 + x**57 + x**55 + x**54 + x**52 + x**51 + x**48 + x**47 + x**45 + x**44 + x**42 + x**41 + x**39 + x**38 + x**37 + x**35 + x**34 + x**32 + x**31 + x**29 + x**28 + x**26 + x**25 + x**24 + x**22 + x**21 + x**19 + x**18 + x**16 + x**15 + x**13 + x**12 + x**11 + x**9 + x**8 + x**6 + x**5 + x**3 + x**2 + 1) """ orig_a = a @@ -138,6 +138,97 @@ def gf128_sqrt(x): """ return gf128_exp(x, 2**127) +def gf128_to_vec(x): + return [int(n) for n in bin(x)[2:].zfill(128)[::-1]] + +def vec_to_gf128(vs): + x = 0 + for i, v in enumerate(vs): + if v: + x += (1 << i) + return x + +def reverse_mask(b): + # from https://stackoverflow.com/a/2602885 + b = (b & 0xF0) >> 4 | (b & 0x0F) << 4; + b = (b & 0xCC) >> 2 | (b & 0x33) << 2; + b = (b & 0xAA) >> 1 | (b & 0x55) << 1; + return b; + +def bytes_to_gf128(xs, st=None, en=None): + if st is None and en is None: + st = 0 + en = 16 + a, b = struct.unpack('<QQ', bytes(reverse_mask(xs[i]) for i in range(st, en))) + return a + (b << 64) + +def gf128_to_bytes(n): + s = b'' + while n != 0: + c = n & 0xff + f = 0 + for i in range(8): + if c & (1 << i): + f += (1 << (7-i)) + s += int.to_bytes(f, 1, 'big') + n >>= 8 + s += b'\x00' * (16 - len(s)) + assert len(s) == 16 + return s + +def Ms(): + vs = [] + for i in range(0, 128): + v = gf128_to_vec(gf128_mod(1 << (2*i))) + vs.append(v) + return np.array(vs).transpose() + +def Mc(c): + vs = [] + pr = c + for i in range(0, 128): + vs.append(gf128_to_vec(pr)) + pr = gf128_mul(x**1, pr) + return np.array(vs).transpose() + +# Adapted from Wiki +def rref_mod_2(M): + M = M.copy().astype('int') + + lead = 0 + rowCount, columnCount = M.shape + adj = np.eye(rowCount, rowCount).astype('int') + + for r in range(rowCount): + if columnCount <= lead: + return M, adj + i = r + while M[i][lead] == 0: + i = i + 1 + if rowCount == i: + i = r + lead = lead + 1 + if columnCount == lead: + return M, adj + if i != r: + M[[i, r]] = M[[r, i]] + adj[[i, r]] = adj[[r, i]] + for j in range(rowCount): + if M[j][lead] == 1 and j != r: + M[j] ^= M[r] + adj[j] ^= adj[r] + lead = lead + 1 + return M, adj + +def kernel(M, f): + mt = M.transpose() + N, adj = f(mt) + basis = [] + for i, row in enumerate(N): + if np.all(np.isclose(row, 0)): + basis.append(adj[i]) + return N, adj, basis + ## Computation in GF(2^128)[X]/(x^128 + x^7 + x^2 + x^1 + 1) ## Elements are represented as arrays where the ith element is the coefficient for x^i. @@ -285,7 +376,7 @@ def gf128poly_modexp(a, n, m): def gf128poly_monic_gcd(a, b): """Compute g such that g | a, g | b, gf128poly_lead(g) = 1; - for any h such that h | a and h | b, gf128poly_deg(g) >= gf128poly_deg(h). + for any h such that h | a and h | b, gf128poly_deg(g) >= gf128poly_deg(h). >>> assert gf128poly_monic_gcd([x**3, x**2, x**4], [x**3, x**2, x**4]) == [x**127 + x**6 + x**1 + 1, x**127 + x**126 + x**6 + x**5 + x**1, 1] >>> assert gf128poly_monic_gcd([1], [1]) == [1] >>> assert gf128poly_monic_gcd([x**5 + x**2], []) == [x**5 + x**2] @@ -422,34 +513,6 @@ def gf128poly_factorize(f, degree=None): ## AES-GCM -def reverse_mask(b): - # from https://stackoverflow.com/a/2602885 - b = (b & 0xF0) >> 4 | (b & 0x0F) << 4; - b = (b & 0xCC) >> 2 | (b & 0x33) << 2; - b = (b & 0xAA) >> 1 | (b & 0x55) << 1; - return b; - -def bytes_to_gf128(xs, st=None, en=None): - if st is None and en is None: - st = 0 - en = 16 - a, b = struct.unpack('<QQ', bytes(reverse_mask(xs[i]) for i in range(st, en))) - return a + (b << 64) - -def gf128_to_bytes(n): - s = b'' - while n != 0: - c = n & 0xff - f = 0 - for i in range(8): - if c & (1 << i): - f += (1 << (7-i)) - s += int.to_bytes(f, 1, 'big') - n >>= 8 - s += b'\x00' * (16 - len(s)) - assert len(s) == 16 - return s - def pad(xs): return xs + b'\x00' * ((16 - len(xs)) % 16) @@ -534,7 +597,134 @@ def nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2): secrets.append((h, s)) return secrets -def demo(): +## Nonce Truncation Attack + +def gen_blocks(n, js): + blocks = b'\x00'*16*n + for j in js: + whichbyte = j // 8 + whichbit = j % 8 + newbyte = blocks[whichbyte] ^ (1 << (7-whichbit)) + blocks = blocks[:whichbyte] + bytes([newbyte]) + blocks[whichbyte+1:] + return blocks + +squarer = np.array(Ms()) +matsqlookup = np.load(open('squares.np', 'rb')) +adlookup = np.load(open('ad.np', 'rb')) + +def gen_ad(blocks): + matret = np.zeros((128, 128)) + for i in range(len(blocks)//16): + block = blocks[(i*16):(i+1)*16] + if block == b'\x00'*16: + continue + j = i + 1 # first is taken up by length block + mat = None + d = bytes_to_gf128(block) + matd = Mc(d) + if len(matsqlookup) > j: + matsq = matsqlookup[j] + else: + matsq = np.linalg.matrix_power(squarer, j) % 2 + mat = matd @ matsq + matret += mat + return matret % 2 # Because the elements of Ad are in GF2 we can mod 2 + +def gen_t(n, macbytes, X=None, minrows=8): + T = [] + for j in range(n*128): + if j < len(adlookup): + Ad = adlookup[j] + else: + blocks = gen_blocks(n, [j]) + Ad = gen_ad(blocks) + + if X is not None: + rows = min((n*128)//(X.shape[1]) - 1, macbytes*8-minrows) + else: + rows = min((n*128)//(Ad.shape[1]) - 1, macbytes*8-minrows) + + if X is not None: + Ad = (Ad[:rows] @ X) % 2 + z = np.concatenate(Ad[:rows]) + T.append(z) + return (np.array(T)).transpose().astype('int') + +def gen_flips(b): + return np.nonzero(b)[0] + +def compute_n(ct): + num_blocks = len(ct)//16 + ns = [1] # 1-indexed + while (ns[-1]*2)<=(num_blocks): + ns.append(2*ns[-1]) + ns = [n-1 for n in ns] # 0-indexed into c + n = len(ns) - 1 + return n + +def chunk(xs, n=16): + return [xs[i*n:(i+1)*n] for i in range(len(xs)//16)] + +def find_b(n, basis, ct, mac, nonce, aad, oracle): + base = bytearray(ct) + idx = 0 + while True: + choice = random.sample(basis, random.randint(1, 12)) + b = sum(choice) % 2 + flips = gen_flips(b) + blocks = gen_blocks(n, flips) + for i, block in enumerate(chunk(blocks)): + j = (len(base)//16)-(2**(i+1)-1) + base[j*16:(j+1)*16] = xor(base[j*16:(j+1)*16], block) + try: + oracle(base[len(aad):], base[:len(aad)], mac, nonce) + return b + except ValueError as e: + assert str(e) == 'MAC check failed' + for i, block in enumerate(chunk(blocks)): + j = (len(base)//16)-(2**(i+1)-1) + base[j*16:(j+1)*16] = xor(base[j*16:(j+1)*16], block) + idx += 1 + +def compute_auth_key(ct, mac, nonce, mac_bytes, aad, oracle): + ct = aad + ct + n = compute_n(ct) + assert n > (mac_bytes*8//2) + assert len(ct) % 16 == 0 + assert len(aad) % 16 == 0 + X = None + K = None + basisKerK = None + while K is None or (basisKerK is None or len(basisKerK) > 1): + T = gen_t(n, mac_bytes, X, minrows=7) + _, _, basisKerT = kernel(T, rref_mod_2) + assert len(basisKerT[0]) == n*128 + + b = find_b(n, basisKerT, ct, mac, nonce, aad, oracle) + flips = gen_flips(b) + blocks = gen_blocks(n, flips) + Ad = gen_ad(blocks) + + if X is not None: + AdRelevant = ((Ad @ X) % 2)[:mac_bytes*8] + else: + AdRelevant = Ad[:mac_bytes*8] + incrK = Ad[:mac_bytes*8][np.any(AdRelevant, axis=1)] + if K is None: + K = incrK + else: + K = np.concatenate([K, incrK]) + _, _, basisKerK = kernel(K, rref_mod_2) + X = np.array(basisKerK).transpose() + print(len(basisKerK)) + _, _, kerK = kernel(K, rref_mod_2) + assert len(kerK) == 1 + h = kerK[0] + return gf128_to_bytes(vec_to_gf128(h)) + +# Demos + +def forbidden_attack_demo(): k = b"tlonorbistertius" nonce = b"jorgelborges" m1 = b"The universe (which others call the Library)" @@ -565,3 +755,22 @@ def demo(): except AssertionError: pass assert succeeded + +def nonce_truncation_demo(): + k = b'YELLOW_SUBMARINE' + aad = b'YELLOW_SUBMAFINERELLOWPUBMARINF_' + MACBYTES=1 + pt = b'CELERYPATCHWORKS'*(2**9) + nonce = b'JORGELBORGES' + ct, mac = gcm_encrypt(k, nonce, aad, pt, mac_bytes=MACBYTES) + def oracle(base, aad, mac, nonce): + cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=MACBYTES) + cipher.update(aad) + pt = cipher.decrypt_and_verify(base, mac) + h = compute_auth_key(ct, mac, nonce, MACBYTES, aad, oracle) + assert h == gf128_to_bytes(authentication_key(k)) +nonce_truncation_demo() + +# Try with different lengths +# Make it so we chosoe to generate gen_t on the fly if needed +# PRofiling |