init

author: cyfraeviolae <cyfraeviolae> 2022-08-23 02:40:04 -0400
committer: cyfraeviolae <cyfraeviolae> 2022-08-23 02:40:04 -0400
commit: 8595c70d789183c71dac1469eb8bd484284589c5 (patch)
tree: 5043f386657d0855fc12f16818d76ae8ef6b753b /nonce-reuse.html
1 files changed, 185 insertions, 0 deletions
diff --git a/nonce-reuse.html b/nonce-reuse.html
new file mode 100644
index 0000000..0795386
--- /dev/null
+++ b/nonce-reuse.html
@@ -0,0 +1,185 @@
+<!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.
+        </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 simple matter of finding the roots by <a href="https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields">factoring the
+            polynomial</a> using a computer algebra system such as SageMath.
+        </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.
+        </p>
+        </details>
+        <br>
+        <form>
+            <div>
+            <input type="button" value="Autofill example">
+            </div>
+
+            <div>
+            <label for="key">Key (16 bytes in hex)</label>
+            <input id="key" type="text">
+            </div>
+
+            <div>
+            <label for="nonce">Nonce (12 bytes in hex)</label>
+            <input id="nonce" type="text">
+            </div>
+
+            <div>
+            <label for="m1">First message (in ASCII)</label>
+            <input id="m1" type="text">
+            </div>
+
+            <div>
+            <label for="aad1">First additional authenticated data (in ASCII)</label>
+            <input id="aad1" type="text">
+            </div>
+
+            <div>
+            <label for="m2">Second message (in ASCII)</label>
+            <input id="m2" type="text">
+            </div>
+
+            <div>
+            <label for="aad2">Second additional authenticated data (in ASCII)</label>
+            <input id="aad2" type="text">
+            </div>
+
+            <div>
+            <label for="c">Forged ciphertext (in hex)</label>
+            <input id="c" type="text">
+            </div>
+
+            <div>
+            <input type="button" value="Compute 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="mac">Forged MAC</label>
+        <input id="mac" type="text" disabled value="deadbeef">
+        </div>
+        <br>
+        <pre>
+from <a href="#">aesgcmanalysis</a> 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."""
+aad1 = b"The Anatomy of Melancholy"
+m2 = b"From any of the hexagons one can see, interminably, the upper and lower floors."
+aad2 = b"Letizia Alvarez de Toledo"
+c1, mac1 = gcm_encrypt(k, nonce, m1, aad1)
+c2, mac2 = gcm_encrypt(k, nonce, m2, aad2)
+
+# Recover the authentication key and blind from public information
+h, s = 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))
+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
+        </pre>
+		<details>
+			<summary>
+                Show me the code.
+			</summary>
+        </details>
+		<details>
+			<summary>
+                Show me the math.
+			</summary>
+            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.
+        </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>
author	cyfraeviolae <cyfraeviolae>	2022-08-23 02:40:04 -0400
committer	cyfraeviolae <cyfraeviolae>	2022-08-23 02:40:04 -0400
commit	8595c70d789183c71dac1469eb8bd484284589c5 (patch)
tree	5043f386657d0855fc12f16818d76ae8ef6b753b /nonce-reuse.html