@@ -139,9 +141,10 @@

However, we still need to compute a new MAC over the forged ciphertext. - Simplifying for a ciphertext \(c\) of two blocks, the GMAC MAC is computed as + Simplifying for a ciphertext \(c\) of two blocks and no additional + authenticated data, the GMAC MAC is computed as \[ - mac = s + (len)h + c_1h^2 + c_0h^3, + mac = s + \vert c\vert h + c_1h^2 + c_0h^3, \] where \(s\) is a constant depending on the AES-GCM key and the nonce, and \(h\) is the authentication key depending only on the AES-GCM key. @@ -167,6 +170,28 @@ Note that there may be multiple possible monomial roots; in this case, one can check each possibility against the enemy.

+ One can use SageMath to compute factors of a polynomial: +

+K = GF(2**128, name='x', modulus=x^128+x^7+x^2+x+1)
+x = K.gen()
+S = PolynomialRing(K, 'y')
+y = S.gen()
+p = (1)*y^4 + (x^7)*y^3 + (x^9 + x^4 + 1)*y^2 + (x^12 + x^2)*y + (x^10 + x^5)
+for factor, _ in p.factor():
+    if factor.degree() == 1:
+        print('Authentication key:', factor - y)

+ However, the library powering this demonstration implements polynomial factoring over finite fields from scratch, which is an edifying exercise. +

+ We present advice for those who wish to implement polynomial factorization as well: +

The gcd of two polynomials is unique only up to multiplication by a non-zero constant because “greater” is defined for polynomials in terms of degree. When used in algorithms, gcd refers to the monic gcd, which is unique.
The inverse Frobenius automorphism (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}}\).

Readers who wish to implement this attack themselves can try Cryptopals; specifically @@ -197,52 +222,6 @@ c_forged, aad_forged = xor(c1, xor(m1, m_forged)), b"" for h, s in possible_secrets: print("MAC candidate": gmac(h, s, aad_forged, c_forged)) -

- Show me the math. -

- Once the polynomial difference is computed, one can use SageMath - to compute the factors: -

-K = GF(2**128, name='x', modulus=x^128+x^7+x^2+x+1)
-x = K.gen()
-S = PolynomialRing(K, 'y')
-y = S.gen()
-p = (x^127 + x^125 + x^121 + x^118 + x^117 + x^116 + x^113 + x^111 + x^108 + x^105 + x^102 + x^99 + x^97 + x^95 + x^89 + x^87 +
- x^85 + x^84 + x^81 + x^78 + x^73 + x^71 + x^69 + x^67 + x^65 + x^63 + x^62 + x^59 + x^57 + x^55 + x^54 + x^53 + x^52 + x^51 +
-x^49 + x^47 + x^46 + x^45 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^33 + x^29 + x^28 + x^25 + x^21 + x^20 + x^17 + x^15 + x
-^13 + x^9 + x^7 + x^4 + x^3 + x)*y^5 + (x^127 + x^125 + x^121 + x^118 + x^117 + x^116 + x^113 + x^111 + x^108 + x^105 + x^102 +
- x^99 + x^97 + x^95 + x^89 + x^87 + x^85 + x^84 + x^81 + x^78 + x^73 + x^71 + x^69 + x^67 + x^65 + x^63 + x^62 + x^59 + x^57 +
-x^55 + x^54 + x^53 + x^52 + x^51 + x^49 + x^47 + x^46 + x^45 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^33 + x^29 + x^28 + x
-^25 + x^21 + x^20 + x^17 + x^15 + x^13 + x^9 + x^7 + x^4 + x^3 + x)*y^4 + (x^127 + x^125 + x^124 + x^123 + x^122 + x^120 + x^11
-9 + x^118 + x^115 + x^112 + x^111 + x^110 + x^109 + x^108 + x^106 + x^101 + x^100 + x^99 + x^98 + x^96 + x^93 + x^88 + x^87 + x
-^84 + x^83 + x^82 + x^78 + x^77 + x^74 + x^71 + x^70 + x^69 + x^68 + x^65 + x^62 + x^61 + x^60 + x^57 + x^55 + x^53 + x^50 + x^
-49 + x^47 + x^46 + x^44 + x^43 + x^41 + x^40 + x^39 + x^37 + x^36 + x^35 + x^34 + x^33 + x^31 + x^30 + x^25 + x^19 + x^16 + x^1
-4 + x^13 + x^12 + x^11 + x^10 + x^5 + x^2 + x + 1)*y^3 + (x^124 + x^123 + x^121 + x^120 + x^119 + x^118 + x^117 + x^116 + x^115
- + x^113 + x^112 + x^110 + x^107 + x^106 + x^104 + x^103 + x^101 + x^99 + x^98 + x^95 + x^94 + x^83 + x^82 + x^81 + x^80 + x^79
- + x^77 + x^76 + x^75 + x^73 + x^72 + x^67 + x^64 + x^63 + x^62 + x^61 + x^59 + x^57 + x^56 + x^54 + x^53 + x^51 + x^49 + x^48
-+ x^46 + x^45 + x^44 + x^42 + x^36 + x^35 + x^34 + x^33 + x^31 + x^28 + x^22 + x^21 + x^17 + x^12 + x^11 + x^10 + x^8 + x^5 + x
-^4 + 1)*y^2 + (x^120 + x^119 + x^56 + x^55)*y + (x^127 + x^126 + x^125 + x^124 + x^123 + x^118 + x^117 + x^116 + x^115 + x^114
-+ x^113 + x^105 + x^103 + x^98 + x^96 + x^94 + x^91 + x^90 + x^89 + x^87 + x^86 + x^85 + x^83 + x^81 + x^80 + x^78 + x^77 + x^7
-0 + x^66 + x^63 + x^62 + x^59 + x^58 + x^54 + x^53 + x^52 + x^50 + x^47 + x^45 + x^44 + x^42 + x^40 + x^39 + x^37 + x^35 + x^34
- + x^30 + x^29 + x^27 + x^26 + x^25 + x^23 + x^18 + x^16 + x^14 + x^13 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3
-+ 1)
-for factor, _ in p.factor():
-    if factor.degree() == 1:
-        print('Authentication key:', factor - y)

- However, the library powering this demonstration implements polynomial factoring over finite fields from scratch, which is an edifying exercise. -

- We present advice for those who wish to implement polynomial factorization as well: -

The gcd of two polynomials is unique only up to multiplication by a non-zero constant because “greater” is defined for polynomials in terms of degree. When used in algorithms, gcd refers to the monic gcd, which is unique.
The inverse Frobenius automorphism (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}}\).

+ + + -- cgit v1.2.3