summaryrefslogtreecommitdiff
path: root/nonce-reuse.html
diff options
context:
space:
mode:
authorcyfraeviolae <cyfraeviolae>2022-08-24 00:38:04 -0400
committercyfraeviolae <cyfraeviolae>2022-08-24 00:38:04 -0400
commitd4e149445bda4a73dc3bb987e6ba296c7d6fe84e (patch)
tree5edc1b104f45239367a3a380a911de3b97dafa80 /nonce-reuse.html
parent32137f612509ee577703d4316dc6a2ec937da709 (diff)
work
Diffstat (limited to 'nonce-reuse.html')
-rw-r--r--nonce-reuse.html229
1 files changed, 0 insertions, 229 deletions
diff --git a/nonce-reuse.html b/nonce-reuse.html
deleted file mode 100644
index 21c794d..0000000
--- a/nonce-reuse.html
+++ /dev/null
@@ -1,229 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
- <title>Forbidden Salamanders</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">
- <link rel="stylesheet" type="text/css" href="/forbidden-salamanders/static/styles.css">
- <link rel="shortcut icon" type="image/x-icon" href="/forbidden-salamanders/static/favicon.ico">
- </head>
- <body>
- <div class="container">
- <div>
- <div class="home">
- <a href="/forbidden-salamanders" class="home-title">Forbidden Salamanders</a>
- <span> at </span><a href="/">cyfraeviolae.org</a>
- </div>
- <div class="crumbs">
- <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>
- </div>
- </div>
- <p>
- <strong>Nonce reuse.</strong> Due to rising entropy
- prices, Roseacrucis has started to reuse nonces. You must perform the
- Forbidden Attack in order to recover the authentication key and
- forge arbitrary ciphertext.
- </p>
- <br>
- <details>
- <summary>
- Attack outline.
- </summary>
- <p>
- Recall that the AES-GCM ciphertext is computed as the XOR of the
- keystream and the message. One can modify the bits of the
- ciphertext arbitrarily to effect the same change in the decrypted
- plaintext.
- </p>
- <p>
- Where certain bits of the plaintext are already known, the attacker
- can fully determine the same bits of the forged plaintext. If
- nonces are reused, the keystream will be identical, allowing us to
- recover plaintext via
- <a href="https://samwho.dev/blog/toying-with-cryptography-crib-dragging/">
- crib dragging</a>, which makes this attack particularly effective:
- \[
- c' = c \oplus m \oplus m'.
- \]
- </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
- \[
- mac = s + (len)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.
- </p>
- <p>
- If we intercept a second ciphertext \(c'\) encrypted under the same key and nonce,
- we can compute
- \[
- 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
- 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 matter of finding the roots by <a href="https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields">factoring the
- polynomial</a>.
- </p>
- <p>
- 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. Note that there may be multiple possible monomial roots;
- in this case, one can check each possibility online.
- </p>
- </details>
- <br>
- <form>
- <div>
- <label for="key">Key (16 bytes in hex)</label>
- <input id="key" type="text" value="59454c4c4f575f5355424d4152494e45">
- </div>
-
- <div>
- <label for="nonce">Nonce (12 bytes in hex)</label>
- <input id="nonce" type="text" value="4a4f5247454c424f52474553">
- </div>
-
- <div>
- <label for="m1">First message (in ASCII)</label>
- <input id="m1" type="text">
- </div>
-
- <div>
- <label for="m2">Second message (in ASCII)</label>
- <input id="m2" type="text">
- </div>
-
- <div>
- <label for="mf">Forged message; shorter than the first message (in ASCII)</label>
- <input id="mf" type="text">
- </div>
-
- <div>
- <input type="button" value="Recover authentication key and forge MAC">
- </div>
- </form>
- <div>
- <label for="h">Authentication key</label>
- <input id="h" type="text" disabled value="deadbeef">
- </div>
- <div>
- <label for="mf">Forged ciphertext, assuming first message is known</label>
- <input id="mf" type="text">
- </div>
- <div>
- <label for="mac">Forged MAC</label>
- <input id="mac" type="text" disabled value="deadbeef">
- </div>
- <br>
- <details>
- <summary>
- Show me the code.
- </summary>
- <pre>
-from <a href="/git/forbidden-salamanders">aesgcmanalysis</a> 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"
-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</pre></details>
- <details>
- <summary>
- Show me the math.
- </summary>
- <p>
- A description of the construction of GMAC can be found at the <a
- href="/forbidden-salamanders">mission homepage</a>.
- </p>
- <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>, 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 &ldquo;greater&rdquo; 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: {
- extensions: ["AMSmath.js", "AMSsymbols.js"]
- }
-};
-</script>
-<script id="MathJax-script" async
- src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js">
-</script>
- </body>
-</html>
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 23:43:54 +0000