nonce truncation

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