diff options
Diffstat (limited to 'templates/nonce-reuse.html')
| -rw-r--r-- | templates/nonce-reuse.html | 87 |
1 files changed, 33 insertions, 54 deletions
diff --git a/templates/nonce-reuse.html b/templates/nonce-reuse.html index e60cc95..94dcb2c 100644 --- a/templates/nonce-reuse.html +++ b/templates/nonce-reuse.html @@ -1,7 +1,7 @@ <!DOCTYPE html> <html> <head> - <title>Forbidden Salamanders</title> + <title>Forbidden Salamanders · Nonce Reuse</title> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <link rel="stylesheet" type="text/css" href="/static/styles.css"> @@ -19,9 +19,9 @@ <a href="/git/forbidden-salamanders">source code</a> <span class="sep"> · </span> <a href="/forbidden-salamanders/nonce-reuse"><strong>nonce reuse</strong></a> - <!-- <span class="sep"> · </span> <a href="/forbidden-salamanders/nonce-truncation">nonce truncation</a> + <!-- <span class="sep"> · </span> <a href="/forbidden-salamanders/key-commitment">key commitment</a> --> @@ -48,7 +48,7 @@ {% endif %} <form action="/forbidden-salamanders/nonce-reuse" method="post"> <div><em> - Roseacrucis chooses a key, a nonce, and two messages. He encrypts both messages under the same nonce. + Roseacrucis chooses a key, a nonce, and encrypts two messages under the same nonce. </em></div><br> <div> @@ -62,17 +62,19 @@ </div> <div> - <label for="m1">First intercepted message</label> + <label for="m1">First message</label> <input name="m1" id="m1" type="text" required maxlength=64 value="{{m1 if m1 else 'The universe (which others call the Library)'}}"> </div> <div> - <label for="m2">Second intercepted message</label> + <label for="m2">Second message</label> <input name="m2" id="m2" type="text" required maxlength=64 value="{{m2 if m2 else 'From any of the hexagons one can see, interminably'}}"> </div> <br><div><em> - After intercepting the ciphertexts, you choose a new message to forge under the same key and nonce. + After intercepting the ciphertexts and recovering the + authentication key, you choose a new message to forge under the + same key and nonce. </em></div><br> <div> @@ -139,9 +141,10 @@ </p> <p> 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. </p> + <p> + One can use SageMath to compute factors of a polynomial: + </p> + <pre> +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)</pre> + <p> + However, the library powering this demonstration implements <a href="https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields">polynomial factoring over finite fields</a> from scratch, which is an edifying exercise. + </p> + <p> + We present advice for those who wish to implement polynomial factorization as well: + </p> + <ul> + <li>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 <em>monic</em> gcd, which is unique.</li> + <li>The <a href="https://math.stackexchange.com/a/943626/1084004">inverse Frobenius automorphism</a> (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}}\).</li> + </ul> <p> Readers who wish to implement this attack themselves can try <a href="https://cryptopals.com/">Cryptopals</a>; 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))</pre></details> - <details> - <summary> - Show me the math. - </summary> - <p> - Once the polynomial difference is computed, one can use SageMath - to compute the factors: - </p> - <pre> -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)</pre> - <p> - However, the library powering this demonstration implements <a href="https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields">polynomial factoring over finite fields</a> from scratch, which is an edifying exercise. - </p> - <p> - We present advice for those who wish to implement polynomial factorization as well: - </p> - <ul> - <li>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 <em>monic</em> gcd, which is unique.</li> - <li>The <a href="https://math.stackexchange.com/a/943626/1084004">inverse Frobenius automorphism</a> (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}}\).</li> - </ul> - </details> <script> MathJax = { tex: { |