From 32137f612509ee577703d4316dc6a2ec937da709 Mon Sep 17 00:00:00 2001 From: cyfraeviolae Date: Tue, 23 Aug 2022 23:16:44 -0400 Subject: work --- nonce-reuse.html | 140 ++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 92 insertions(+), 48 deletions(-) (limited to 'nonce-reuse.html') diff --git a/nonce-reuse.html b/nonce-reuse.html index 0795386..21c794d 100644 --- a/nonce-reuse.html +++ b/nonce-reuse.html @@ -48,7 +48,10 @@ nonces are reused, the keystream will be identical, allowing us to recover plaintext via - crib dragging, which makes this attack particularly effective. + crib dragging, which makes this attack particularly effective: + \[ + c' = c \oplus m \oplus m'. + \]

However, we still need to compute a new MAC over the forged ciphertext. @@ -65,35 +68,32 @@ \[ mac + mac' = (s + s') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3, \] - Since \(s = s'\) and \(x+x=0 \in \mathbb{F}_{2^{128}}\), we are + Since \(s = s'\) and \(x+x=0\) in \(\mathbb{F}_{2^{128}}\), we are left with the polynomial equation \[ 0 = (mac + mac') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3 \] where all variables are known other than \(h\). Thus, recovering \(h\) - is a simple matter of finding the roots by factoring the - polynomial using a computer algebra system such as SageMath. + is a matter of finding the roots by factoring the + polynomial.

We plug \(h\) back into the first equation to recover \(s\), and finally, we can forge the MAC for arbitary ciphertext under the - same nonce. + same nonce. Note that there may be multiple possible monomial roots; + in this case, one can check each possibility online.


-
- -
-
- +
- +
@@ -101,28 +101,18 @@
-
- - -
-
- - + +
- - -
- -
- +
@@ -130,46 +120,100 @@
+ + +
+

+
+ + Show me the code. + 
-from aesgcmanalysis import xor, gcm_encrypt, nonce_reuse_recover_secrets, forge_gmac
-k = b"YELLOW_SUBMARINE"
-nonce = b"JORGELBORGES"
-m1 = b"""The universe (which others call the Library) is composed of an indefinite and
-perhaps infinite number of hexagonal galleries, with vast air shafts between,
-surrounded by very low railings."""
+from aesgcmanalysis import xor, gcm_encrypt, gcm_decrypt, nonce_reuse_recover_secrets
+
+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, the upper and lower floors."
+m2 = b"From any of the hexagons one can see, interminably"
 aad2 = b"Letizia Alvarez de Toledo"
-c1, mac1 = gcm_encrypt(k, nonce, m1, aad1)
-c2, mac2 = gcm_encrypt(k, nonce, m2, aad2)
+
+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
-h, s = nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2)
+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 was followed by an excessive depression."
-c_forged = xor(c2, xor(m2, m_forged))
+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?"
-mac_forged = forge_gmac(nonce, h, s, c_forged, aad_forged)
-assert gcm_decrypt(k, nonce, c_forged, aad_forged, mac_forged) == m_forged
-
-
- - Show me the code. - -
+ +# 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
Show me the math. - see homepage - The forged ciphertext can be computed as a xor from original ciphertext, - which should be particularly easy as nonce reuse reveals the XOR and then - crib dragging. +

+ A description of the construction of GMAC can be found at the mission homepage. +

+

+ 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, which is an edifying exercise. +

+

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

+