diff options
Diffstat (limited to 'aesgcmanalysis.py')
| -rw-r--r-- | aesgcmanalysis.py | 470 |
1 files changed, 276 insertions, 194 deletions
diff --git a/aesgcmanalysis.py b/aesgcmanalysis.py index db919e1..0b81522 100644 --- a/aesgcmanalysis.py +++ b/aesgcmanalysis.py @@ -1,10 +1,12 @@ -import random, struct, hmac +import random, struct, hmac, itertools from Crypto.Cipher import AES import numpy as np ## Computation in GF(2^128)/(x^128 + x^7 + x^2 + x^1 + 1) +## Elements are represented as an integer n where (n & (1 << i)) is the coefficient for x^i. class X: + """A helper class for specifying elements of GF(2^n).""" def __pow__(self, y): return 1 << y x = X() @@ -54,7 +56,7 @@ def gf128_mul(a, b): return p def gf128_divmod(a, b): - """Compute q, r such that a = qb + r. + """Compute q, r such that a = qb + r; gf128_deg(r) < gf128_deg(b). >>> assert gf128_divmod(x**20 + x**5 + 1, x**13 + x**2) == (x**7, x**9 + x**5 + 1) >>> assert gf128_divmod(x**90, x**80) == (x**10, 0) """ @@ -127,87 +129,131 @@ def gf128_exp(a, n): rec = gf128_mul(rec, a) return rec +def gf128_sqrt(x): + """Compute y such that y^2 = x: the inverse Frobenius automorphism. + Reference: https://math.stackexchange.com/questions/943417/square-root-for-galois-fields-gf2m + >>> assert gf128_sqrt(1) == 1 + >>> assert gf128_sqrt(x**2 + 1) == x**1 + 1 + >>> assert gf128_sqrt(x**3 + 1) == x**126 + x**123 + x**120 + x**117 + x**114 + x**111 + x**108 + x**105 + x**102 + x**99 + x**96 + x**93 + x**90 + x**87 + x**84 + x**81 + x**78 + x**75 + x**72 + x**69 + x**66 + x**63 + x**62 + x**60 + x**59 + x**57 + x**56 + x**54 + x**53 + x**51 + x**50 + x**48 + x**47 + x**45 + x**44 + x**42 + x**41 + x**39 + x**38 + x**36 + x**35 + x**33 + x**32 + x**30 + x**29 + x**27 + x**26 + x**24 + x**23 + x**21 + x**20 + x**18 + x**17 + x**15 + x**14 + x**12 + x**11 + x**9 + x**8 + x**6 + x**3 + 1 + """ + return gf128_exp(x, 2**127) + ## 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. + +def gf128poly_lead(x): + """Compute the leading coefficient of x. + >>> assert gf128poly_lead([x**3, x**1, 1]) == 1 + >>> assert gf128poly_lead([x**3, x**1, x**2, x**4]) == x**4 + >>> assert gf128poly_lead([1]) == 1 + """ + assert len(x) > 0 + return x[-1] -# Get rid of trailing zeros? def collapse(x): if len(x) == 0: - return x - if x[-1] == 0: + return [] + if gf128poly_lead(x) == 0: return collapse(x[:-1]) -# CAN WE REMOVE MOD? - return [gfmod(y, m) for y in x] + return [gf128_mod(y, gcm_modulus) for y in x] -def gf128polyring_deg(x): +def gf128poly_deg(x): + """Compute the degree of x. + >>> assert gf128poly_deg([x**3, x**1, 1]) == 2 + >>> assert gf128poly_deg([x**2, x**3]) == 1 + >>> assert gf128poly_deg([x**15]) == 0 + >>> assert gf128poly_deg([1]) == 0 + >>> assert gf128poly_deg([]) == -1 + """ return len(x) - 1 -# assert gf128deg([x**1, x**1, x**1]) == 2 -def gf128polyring_add(a, b): - return collapse([gfadd(x, y) for x, y in zip_longest(a, b, fillvalue=0)]) -# assert gf128add([x**1, x**1, x**1, x**1], [x**2, x**3, x**4]) == [x**1+x**2, x**1+x**3, x**1+x**4, x**1] -def gf128polyring_sub(a, b): - return gf128add(a, b) - -def gf128polyring_cmul(c, a): - return collapse([gfmul(x, c) for x in a]) - -def gf128polyring_mul(a, b): - a = a.copy() - b = b.copy() - + +def gf128poly_add(a, b): + """Compute a + b. + >>> assert gf128poly_add([x**3, x**1, 1], [x**2 + 1, x**3]) == [x**3 + x**2 + 1, x**1 + x**3, 1] + >>> assert gf128poly_add([x**2, x**3], [x**5, x**12, x**2, x**4]) == [x**5 + x**2, x**12 + x**3, x**2, x**4] + >>> assert gf128poly_add([x**15], []) == [x**15] + >>> assert gf128poly_add([x**15], [x**15]) == [] + """ + return collapse([gf128_add(x, y) for x, y in itertools.zip_longest(a, b, fillvalue=0)]) + +def gf128poly_mul(a, b): + """Compute ab. + >>> assert gf128poly_mul([x**3, x**1, 1], [x**2 + 1, x**3]) == [x**5 + x**3, x**6 + x**3 + x**1, x**4 + x**2 + 1, x**3] + >>> assert gf128poly_mul([x**2, x**3], [x**5, x**12, x**2, x**4]) == [x**7, x**14 + x**8, x**15 + x**4, x**6 + x**5, x**7] + >>> assert gf128poly_mul([x**15], []) == [] + >>> assert gf128poly_mul([x**15], [1]) == [x**15] + >>> assert gf128poly_mul([0, x**15], [0, x**15]) == [0, 0, x**30] + >>> assert gf128poly_mul([x**70], [1, x**70, 1]) == [x**70, x**19 + x**14 + x**13 + x**12, x**70] + """ p = [] - while gf128deg(a) >= 0: - p = gf128add(p, gf128cmul(a[0], b)) + while gf128poly_deg(a) >= 0: + p = gf128poly_add(p, [gf128_mul(x, a[0]) for x in b]) a = a[1:] b = [0] + b return collapse(p) -def gf128polyring_divmod(a, b): - q, r = [], [] - while gf128deg(a) >= gf128deg(b): - highA = a[-1] - highB = b[-1] - highBinv = 1 if highB == 1 else gfmodinv(highB, m) - #print(highA, highBinv) - qq = gfmodmul(highA, highBinv, m) - #qq, rr = gfdivmod(highA, highB) - #assert rr == 0 - de = gf128deg(a) - gf128deg(b) +def gf128poly_divmod(a, b): + """Compute q, r such that a = qb + r; gf128poly_deg(r) < gf128poly_deg(b). + >>> assert gf128poly_divmod([x**5 + x**3, x**6 + x**3 + x**1, x**4 + x**2 + 1, x**3], [x**2 + 1, x**3]) == ([x**3, x**1, 1], []) + >>> assert gf128poly_divmod([x**7, x**14 + x**8, x**15 + x**4, x**6 + x**5, x**7], [x**2, x**3]) == ([x**5, x**12, x**2, x**4], []) + >>> assert gf128poly_divmod([x**15], [1]) == ([x**15], []) + >>> assert gf128poly_divmod([x**15], [x**15]) == ([1], []) + >>> assert gf128poly_divmod([0, 0, x**30], [0, x**15]) == ([0, x**15], []) + >>> assert gf128poly_divmod([x**70, x**19 + x**14 + x**13 + x**12, x**70], [1, x**70, 1]) == ([x**70], []) + >>> assert gf128poly_divmod([x**18, x**18, x**3], [x**3, x**3]) == ([x**15 + 1, 1], [x**3]) + """ + assert b != [], 'divide by zero' + q = [] + while gf128poly_deg(a) >= gf128poly_deg(b): + highA = gf128poly_lead(a) + highB = gf128poly_lead(b) + highBinv = 1 if highB == 1 else gf128_inv(highB) + qq = gf128_mul(highA, highBinv) + de = gf128poly_deg(a) - gf128poly_deg(b) new_term = [0]*(de+1) new_term[de] = qq - q = gf128add(q, new_term) - fact = gf128mul(b, new_term) - a = gf128sub(a, fact) - + q = gf128poly_add(q, new_term) + fact = gf128poly_mul(b, new_term) + a = gf128poly_add(a, fact) return collapse(q), collapse(a) -def InverseFrobeniusAutomorphismGF128(x): - return gfmodexp(x, 2**127, m) # https://math.stackexchange.com/questions/943417/square-root-for-galois-fields-gf2m - -def gf128polyring_sqrt(p): - p = p.copy() +def gf128poly_sqrt(p): + """Compute q such that q^2 = p for p such that p' = 0. + >>> assert gf128poly_sqrt([1, 0, 1, 0, 1, 0, 1]) == [1, 1, 1, 1] + >>> assert gf128poly_sqrt([1, 0, 1, 0, 0, 0, 1]) == [1, 1, 0, 1] + >>> assert gf128poly_sqrt([1, 0, x**4]) == [1, x**2] + >>> assert gf128poly_sqrt([1, 0, x**3]) == [1, x**126 + x**123 + x**120 + x**117 + x**114 + x**111 + x**108 + x**105 + x**102 + x**99 + x**96 + x**93 + x**90 + x**87 + x**84 + x**81 + x**78 + x**75 + x**72 + x**69 + x**66 + x**63 + x**62 + x**60 + x**59 + x**57 + x**56 + x**54 + x**53 + x**51 + x**50 + x**48 + x**47 + x**45 + x**44 + x**42 + x**41 + x**39 + x**38 + x**36 + x**35 + x**33 + x**32 + x**30 + x**29 + x**27 + x**26 + x**24 + x**23 + x**21 + x**20 + x**18 + x**17 + x**15 + x**14 + x**12 + x**11 + x**9 + x**8 + x**6 + x**3] + """ + assert gf128poly_formal_derivative(p) == [] q = [] for x in p: if x == 0 or x == 1: q.append(x) else: - inv = InverseFrobeniusAutomorphismGF128(x) - q.append(inv) - #print(q) - p = q - for i in range(2,len(p),2): - p[i//2] = gfadd(p[i//2], p[i]) - p[i] = 0 - return collapse(p) + q.append(gf128_sqrt(x)) + for i in range(2, len(q), 2): + q[i//2] = q[i] + q[i] = 0 + return collapse(q) -def gf128polyring_monic(p): - p = p.copy() - finalCoeff = p[-1] - if finalCoeff == 1: +def gf128poly_monic(p): + """Compute p/p_lead for p such that gf128poly_deg(p) >= 0. + >>> assert gf128poly_monic([x**54, x**2]) == [x**52, 1] + >>> assert gf128poly_monic([x**2, x**3]) == [x**127 + x**6 + x**1 + 1, 1] + """ + assert len(p) > 0 + lead = gf128poly_lead(p) + if lead == 1: return p - inv = gfmodinv(finalCoeff, m) - return [gfmodmul(x, inv, m) for x in p] - -def gf128polyring_formal_derivative(p): + lead_inv = gf128_inv(lead) + return [gf128_mul(x, lead_inv) for x in p] + +def gf128poly_formal_derivative(p): + """Compute p'. + >>> assert gf128poly_formal_derivative([]) == [] + >>> assert gf128poly_formal_derivative([x**25]) == [] + >>> assert gf128poly_formal_derivative([x**25, x**3 + x**1, x**10, x**7]) == [x**3 + x**1, 0, x**7] + """ q = [] for i, x in enumerate(p): if i == 0: @@ -219,128 +265,158 @@ def gf128polyring_formal_derivative(p): q.append(e) return collapse(q) -def gf128polyring_sff(f): +def gf128poly_modexp(a, n, m): + """Compute a^n (mod m). + >>> assert gf128poly_modexp([x**2, x**3, x**4], 0, [x**3, x**2, 1]) == [1] + >>> assert gf128poly_modexp([x**2, x**3, x**4], 1, [x**3, x**2, 1, x**5]) == [x**2, x**3, x**4] + >>> assert gf128poly_modexp([x**2, x**3, x**4], 5, [x**3, x**2, 1]) == [x**39 + x**38 + x**37 + x**36 + x**35 + x**33 + x**32 + x**30 + x**27 + x**26 + x**25 + x**24 + x**21 + x**20 + x**15 + x**10, x**38 + x**36 + x**35 + x**33 + x**32 + x**31 + x**26 + x**24 + x**23 + x**22 + x**21 + x**20 + x**14 + x**11] + """ + def modmul(a, b, m): + q, r = gf128poly_divmod(gf128poly_mul(a, b), m) + return r + + if n == 0: + return [1] + rec = gf128poly_modexp(a, n//2, m) + rec = modmul(rec, rec, m) + if n % 2 == 1: + rec = modmul(rec, a, m) + return rec + +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). + >>> 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] + >>> assert gf128poly_monic_gcd([x**3, 0, 0, x**6], [x**3, x**8 + x**4, x**9 + x**7, x**8]) == [x**127 + x**6 + x**1 + 1, 1] + """ + assert gf128poly_deg(a) >= 0 or gf128poly_deg(b) >= 0 + if gf128poly_deg(a) < 0: + return b + if gf128poly_deg(b) < 0: + return a + q, r = gf128poly_divmod(b, a) + ret = gf128poly_monic_gcd(r, a) + return gf128poly_monic(ret) + +def gf128poly_square_free_factorization(f): + """Compute the square-free factorization of a monic polynomial f. + Reference: https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Square-free_factorization + >>> a = [x**1, x**2, 1] + >>> b = [x**2, x**3+1, 1] + >>> c = [x**3, x**4, x**5, 1] + >>> asq = gf128poly_mul(a, a) + >>> acb = gf128poly_mul(asq, a) + >>> bsq = gf128poly_mul(b, b) + >>> acbbsq = gf128poly_mul(acb, bsq) + >>> p = gf128poly_mul(acbbsq, c) + >>> assert gf128poly_square_free_factorization([1]) == [([1], 1)] + >>> assert gf128poly_square_free_factorization(p) == [([x**3, x**4, x**5, 1], 1), ([x**1, x**2, 1], 3), ([x**2, x**3 + 1, 1], 2)] + """ R = [] assert f[-1] == 1, 'monic' - fprime = gf128formal_derivative(f) - #print('fprime', fprime) - c = gf128gcd(f, fprime) - #print('c', c) - w, r = gf128divmod(f, c) - #print('w', w) + if f == [1]: + return [([1], 1)] + fprime = gf128poly_formal_derivative(f) + c = gf128poly_monic_gcd(f, fprime) + w, r = gf128poly_divmod(f, c) assert r == [] i = 1 while w != [1]: - y = gf128gcd(w, c) - #print('y', i, y) - fac, r = gf128divmod(w, y) - #print('fac', i, fac) + y = gf128poly_monic_gcd(w, c) + fac, r = gf128poly_divmod(w, y) assert r == [] R.append((fac, i)) w = y - c, r = gf128divmod(c, y) - #print('c', i, c, r) + c, r = gf128poly_divmod(c, y) assert r == [] i = i + 1 - if c != [1]: - #print('sqrt of', ds(c)) - c = gf128sqrt(c) - c = gf128monic(c) - #print('rec', ds(c)) - Rrec = gf128sff(c) + if c != [1]: + c = gf128poly_sqrt(c) + c = gf128poly_monic(c) + Rrec = gf128poly_square_free_factorization(c) R += [(fac, i*2) for (fac, i) in Rrec] - return R - # Frobenius automorphism??? - -def gf128polyring_modmul(a, b, m): - c = gf128mul(a, b) - q, r = gf128divmod(c, m) - return r -def gf128polyring_modexp(a, n, m): - if n == 0: - return [1] - rec = gf128modexp(a, n//2, m) - rec2 = gf128modmul(rec, rec, m) - if n % 2 == 1: - rec2 = gf128modmul(rec2, a, m) - return rec2 -def ddf(f): + return [(fac, mult) for fac, mult in R if fac != [1]] + +def gf128poly_distinct_degree_factorization(f): + """Compute the distinct-degree factorization of a square-free monic polynomial f. + Reference: https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Distinct-degree_factorization + >>> a = [x**1, 1] + >>> b = [x**2, 1] + >>> ab = gf128poly_mul(a, b) + >>> assert gf128poly_distinct_degree_factorization(ab) == {((x**3, x**2 + x**1, 1), 1)} + """ i = 1 S = set() f_ = f.copy() - - while gf128deg(f_) >= 2 * i: - qq = gf128modexp([0, 1], 2**(128*i), f_) - qq = gf128add(qq, [0, 1]) - g = gf128gcd(f_, qq) - #print('gcd', ds(f_), '||', qq, '||', ds(g)) + while gf128poly_deg(f_) >= 2*i: + qq = gf128poly_modexp([0, 1], 2**(128*i), f_) + qq = gf128poly_add(qq, [0, 1]) + g = gf128poly_monic_gcd(f_, qq) if g != [1]: S.add((tuple(g), i)) - q, r = gf128divmod(f_, g) + q, r = gf128poly_divmod(f_, g) assert r == [] f_ = q i += 1 if f_ != [1]: - #print('last') - S.add((tuple(f_), gf128deg(f_))) + S.add((tuple(f_), gf128poly_deg(f_))) if len(S) == 0: return {(tuple(f), 1)} else: return S -exp = (2**128-1)//3 -def gfrand(): - return random.randint(0, 2**128-1) -def gf128polyring_rand(degree): - qq= [gfrand() for _ in range(degree+1)] - return qq -def edf(f, d): - n = gf128deg(f) +def gf128poly_equal_degree_factorization(f, d): + """Compute the equal-degree factorization of a square-free monic polynomial f whose factors are all of degree d. + Uses the Cantor-Zassenhaus algorithm. + Reference: https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Equal-degree_factorization + >>> a = [x**1, 1] + >>> b = [x**2, 1] + >>> ab = gf128poly_mul(a, b) + >>> assert gf128poly_equal_degree_factorization(ab, 1) == {(x**2, 1), (x**1, 1)} + """ + def gf128_rand(): + return random.randint(0, 2**128-1) + + def gf128poly_rand(degree): + return [gf128_rand() for _ in range(degree+1)] + + exp = (2**128-1)//3 + n = gf128poly_deg(f) r = n//d S = {tuple(f)} while len(S) < r: - h = gf128rand(n-1) - g = gf128gcd(h, f) + h = gf128poly_rand(n - 1) + g = gf128poly_monic_gcd(h, f) if g == [1]: - g = gf128add(gf128modexp(h, exp, f), [1]) + g = gf128poly_add(gf128poly_modexp(h, exp, f), [1]) for u in list(S): u = list(u) - if gf128deg(u) == d: + if gf128poly_deg(u) == d: continue - gugcd = gf128gcd(g, u) + gugcd = gf128poly_monic_gcd(g, u) if gugcd != [1] and gugcd != u: S.remove(tuple(u)) S.add(tuple(gugcd)) - qq, rr = gf128divmod(u, gugcd) + qq, rr = gf128poly_divmod(u, gugcd) assert rr == [] S.add(tuple(qq)) - #print("Iteration", S) return S -def factorize(f): - #print('Computing factors over GF(2^128)/[y](x^128+x^7+x^2+x+1) of', ds(f)) +def gf128poly_factorize(f): + """Compute the factors of a polynomial f. Does not return multiplicity. + """ factors = set() - f = gf128monic(f) - #print('Reduced to monic polynomial', ds(f)) - fs = gf128sff(f) + f = gf128poly_monic(f) + fs = gf128poly_square_free_factorization(f) for p, _ in fs: - #print('Computed square-free factor', ds(p)) - qs = ddf(p) + qs = gf128poly_distinct_degree_factorization(p) for q, d in qs: - #print('Computed distinct-degree factor', ds(q), 'of degree', d) - rs = edf(list(q), d) - #for r in rs: - # print('Computed equal-degree factor', ds(r)) + rs = gf128poly_equal_degree_factorization(list(q), d) factors |= rs return factors -def monic_roots(factors): - roots = [] - for factor in factors: - if gf128deg(factor) == 1: - roots.append(factor[0]) - return roots - ## AES-GCM def reverse_mask(b): @@ -371,9 +447,17 @@ def gf128_to_bytes(n): assert len(s) == 16 return s +def pad(xs): + return xs + b'\x00' * ((16 - len(xs)) % 16) + +def build_blocks(aad, c): + padded_aad = pad(aad) + padded_c = pad(c) + length = struct.pack('>QQ', len(aad)*8, len(c)*8) + return padded_aad + padded_c + length + def gmac(h, s, aad, c): - assert len(n) == 12 - blocks = build_blockseq(ad, c) + blocks = build_blocks(aad, c) g = 0 for i in range(len(blocks)//16): block = bytes_to_gf128(blocks, i*16, (i + 1)*16) @@ -394,7 +478,7 @@ def gctr(k, nonce, x): ctr = (int.from_bytes(nonce, 'big') << 32) + 2 i = 0 while len(y) < len(x): - c += xor(x[i*16:(i + 1)*16], ecb_encrypt(k, ctr.to_bytes(16, 'big'))) + y += xor(x[i*16:(i + 1)*16], ecb_encrypt(k, ctr.to_bytes(16, 'big'))) ctr += 1 i += 1 return y @@ -402,7 +486,7 @@ def gctr(k, nonce, x): def authentication_key(k): return bytes_to_gf128(ecb_encrypt(k, b'\x00'*16)) -def blind(k, n): +def blind(k, nonce): return bytes_to_gf128(ecb_encrypt(k, nonce + b'\x00\x00\x00\x01')) def gcm_encrypt(k, nonce, aad, m, mac_bytes=16): @@ -413,70 +497,68 @@ def gcm_encrypt(k, nonce, aad, m, mac_bytes=16): def gcm_decrypt(k, nonce, aad, c, mac, mac_bytes=16): m = gctr(k, nonce, c) expected_mac = gmac(authentication_key(k), blind(k, nonce), aad, c)[:mac_bytes] - assert hmac.compare_digest(mac, exp_mac), f'Expected MAC {exp_mac.hex()}, got {mac.hex()}' + assert hmac.compare_digest(mac, expected_mac) return m ## Forbidden Attack -def compute_polydiff(ad1, ct1, mac1, ad2, ct2, mac2): - bs1 = build_blockseq(ad1, ct1) - bs2 = build_blockseq(ad2, ct2) +def compute_forbidden_polynomial(aad1, aad2, c1, c2, mac1, mac2): + bs1 = build_blocks(aad1, c1) + bs2 = build_blocks(aad2, c2) if len(bs1) < len(bs2): bs1 = b'\x00'*(len(bs2)-len(bs1)) + bs1 else: bs2 = b'\x00'*(len(bs1)-len(bs2)) + bs2 assert len(bs1) == len(bs2) - #print(bs1.hex()) - #print(bs2.hex()) f = [] N = len(bs1)//16 for i in range(N): - b1 = binToGF128(bs1[i*16:(i+1)*16]) - b2 = binToGF128(bs2[i*16:(i+1)*16]) - c = gfadd(b1, b2) - f.append(c) - mac1gf = binToGF128(mac1) - mac2gf = binToGF128(mac2) - macSgf = gfadd(mac1gf, mac2gf) - f.append(macSgf) + b1 = bytes_to_gf128(bs1[i*16:(i+1)*16]) + b2 = bytes_to_gf128(bs2[i*16:(i+1)*16]) + f.append(gf128_add(b1, b2)) + f.append(gf128_add(bytes_to_gf128(mac1), bytes_to_gf128(mac2))) return list(reversed(f)) -def forge_gcm_tag(h, origAd, origCt, newAd, newCt, tag, n): - # First recover s for the nonce - tag_ = gmac(h, 0, origAd, origCt, n) - s = gfadd(binToGF128(tag), binToGF128(tag_)) - tag = gmac(h, s, newAd, newCt, n) - return tag -def gcm_repeatednonce_attack(factors, n, ad1, ct1, mac1, ad2, ct2, mac2): - #f=compute_polydiff(ad1, ct1, mac1, ad2, ct2, mac2) - #factors = factorize(f) - roots = monic_roots(factors) - h = None - tags = [] - for root in roots: - forged_tag = forge_gcm_tag(root, ad1, ct1, ad2, ct2, mac1, n) - tags.append(forged_tag) - return tags -# tag_guesses = gcm_repeatednonce_attack(factors, n, ad1, ct1, mac1, ad2, ct2, mac2) - - -def d(n): - if n == 0: - return '0' - s = [] - k = 0 - while n > 0: - if n & 1 == 0: - k += 1 - n >>= 1 - continue - if k == 0: - s.append('1') - elif k == 1: - s.append('x') - else: - s.append('x^' + str(k)) - n >>= 1 - k += 1 - return ' + '.join(reversed(s)) - +def nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2): + f = compute_forbidden_polynomial(aad1, aad2, c1, c2, mac1, mac2) + factors = gf128poly_factorize(f) + secrets = [] + for factor in factors: + if gf128poly_deg(factor) == 1: + h = factor[0] + zero_tag = gmac(h, 0, aad1, c1) + s = gf128_add(bytes_to_gf128(mac1), bytes_to_gf128(zero_tag)) + secrets.append((h, s)) + return secrets + +def demo(): + k = b"tlonorbistertius" + nonce = b"jorgelborges" + m1 = b"The universe (which others call the Library)" + aad1 = b"The Anatomy of Melancholy" + m2 = b"From any of the hexagons one can see, interminably" + aad2 = b"Letizia Alvarez de Toledo" + + c1, mac1 = gcm_encrypt(k, nonce, aad1, m1) + c2, mac2 = gcm_encrypt(k, nonce, aad2, m2) + + # Recover the authentication key and blind from public information + possible_secrets = nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2) + + # Forge the ciphertext + m_forged = b"As was natural, this inordinate hope" + assert len(m_forged) <= len(m1) + c_forged = xor(c1, xor(m1, m_forged)) + aad_forged = b"You who read me, are You sure of understanding my language?" + + # Check possible candidates for authentication key + succeeded = False + for h, s in possible_secrets: + mac_forged = gmac(h, s, aad_forged, c_forged) + try: + assert gcm_decrypt(k, nonce, aad_forged, c_forged, mac_forged) == m_forged + succeeded = True + print(c_forged.hex(), mac_forged.hex()) + except AssertionError: + pass + assert succeeded |