key com

2 files changed, 109 insertions, 92 deletions

diff --git a/templates/key-commitment.html b/templates/key-commitment.html
index 619f010..ab72df2 100644
--- a/templates/key-commitment.html
+++ b/templates/key-commitment.html
@@ -98,12 +98,13 @@
 		</div>
 		</form>
 		<p>
-			You can test your ciphertext with Go. Run the following in a shell
-			and then try opening <code>first.jpg</code> and <code>second.bmp</code> in an image viewer.
+            You can test your ciphertext with Go. Run the following in a shell,
+            then try opening <code>first.jpg</code> and <code>second.bmp</code>
+            in an image viewer.
 		</p>
 		<details>
 			<summary>
-				Show testing code.
+                Test script.
 			</summary>
 <pre style="font-size: small">
 TEMP="$(mktemp).go"
@@ -126,85 +127,114 @@ go run "$TEMP" 5c3cb198432b0903e58de9c9647bd241 4a4f5247454c424f52474553 polyglo
 go run "$TEMP" df923ae8976230008a081d23205d7a4f 4a4f5247454c424f52474553 polyglot.enc &gt; second.bmp
 </pre>
 		</details>
-        <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.
+            This attack was shown by Yevgeniy Dodis, Paul Grubbs, Thomas Ristenpart, and Joanne Woodage
+            in <a href="https://eprint.iacr.org/2019/016">Fast Message Franking: From Invisible Salamanders to Encryptment</a>.
+        </p>
+        <p>
+            First, we will describe a general strategy to create a ciphertext that yields the same MAC
+            with two different keys. Then we will show how to construct a ciphertext that yields
+            meaningful results when decrypted with those two keys.
+        </p>
+        <p>
+            Consider arbitrary keys \(k_1, k_2\), nonce \(n\), and ciphertext
+            \(c\) (additional associated data can be accounted for in a
+            straightforward manner). \(k_1, k_2\) are associated
+            with authentication keys \(h_1, h_2\) and blinds \(s_1, s_2\), respectively.
         </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'.
-			\]
+            Given a ciphertext of three blocks, we will attempt to add a fourth ciphertext block \(c_3\), set the MACs equal to each other,
+            and solve for \(c_3\). Remember that in \(\mathbb{F}_{2^{128}}\), addition is the same as subtraction.
         </p>
         <p>
-            However, we still need to compute a new MAC over the forged ciphertext.
-			Simplifying for a ciphertext \(c\) of two blocks and no additional
-			authenticated data, the GMAC MAC is computed as
+            For the resulting ciphertext of four blocks, the MACs for each key are computed as
             \[
-                mac = s + \vert c\vert h + c_1h^2 + c_0h^3,
+                mac_{1} = s_1 + \vert c\vert{}h_1 + c_3h_1^2 + c_2h_1^3 + c_1h_1^4 + c_0h_1^5
+            \]
+            \[
+                mac_{2} = s_2 + \vert c\vert{}h_2 + c_3h_2^2 + c_2h_2^3 + c_1h_2^4 + c_0h_2^5
             \]
             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
+            is the authentication key depending only on the AES-GCM key. We can now set the MACs equal to each other and solve for \(c_3\).
             \[
-                mac + mac' = (s + s') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3,
+                s_1 + \vert c\vert{}h_1 + c_3h_1^2 + c_2h_1^3 + c_1h_1^4 + c_0h_1^5 = s_2 + \vert c\vert{}h_2 + c_3h_2^2 + c_2h_2^3 + c_1h_2^4 + c_0h_2^5
             \]
-            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
+                c_3(h_1^2 + h_2^2) = (s_1 + s_2) + \vert c \vert (h_1 + h_2) + c_2(h_1^3+h_2^3) + c_1(h_1^4 + h_2^4) + c_0(h_1^5 + h_2^5)
             \]
-            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 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 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 &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>
+            \[
+                c_3 = \frac{(s_1 + s_2) + \vert c \vert (h_1 + h_2) + c_2(h_1^3+h_2^3) + c_1(h_1^4 + h_2^4) + c_0(h_1^5 + h_2^5)}{h_1^2 + h_2^2}
+            \]
+        </p>
+        <p>
+            Note that the choice to place the extra block in the final position was arbitrary. For the attack below we will instead need
+            to change the penultimate block rather than adding a block; the computation is similar.
+        </p>
+        <p>
+            For the next phase, we construct a ciphertext that decrypts to a valid JPEG under one key and a valid BMP under another.
+            The basic strategy is to place the JPEG bytes and BMP bytes at different locations, carefully arranging it so
+            each parser will ignore the other data for the file. JPEG files can include comments, in which we will include the
+            BMP data. The BMP parser will stop reading as soon as the indicated length of the BMP has been read, after which
+            we will include the JPEG data. In each decrypted file, the data for the other image will be scrambled as we are using
+            a different key, but it will not matter as the garbage data will be in a location that is ignored by the image parser.
+        </p>
+        <p>
+            All JPEG files start with the magic bytes <code>ffd8</code> and end
+            with <code>ffd9</code>. We will place a JPEG comment immediately
+            after the initial magic bytes, which is indicated by <code>fffe</code> and is followed by a 2-byte big-endian encoding of the comment length.
+            All BMP files start with the magic bytes <code>424d</code> followed by a 4-byte little-endian encoding of the file length.
+        </p>
+        <p>
+            Because the JPEG comment has a maximum length, our BMP file will need to be less than <code>ffff=65536</code> bytes.
+            Thus, we desire the JPEG file to start with <code>ffd8 fffe ffff</code> and the BMP file to start with <code>424d wxyz 0000</code>,
+            where <code>wxyz</code> is the actual length of our BMP file.
+        </p>
         <p>
-            Readers who wish to implement this attack themselves can try
-            <a href="https://cryptopals.com/">Cryptopals</a>; specifically
-            Set 8 Problem 62.
+            To make it easier, we will only require the first five bytes to match; we can modify ciphertext afterwards to satisfy the final
+            byte of the BMP header. The final byte of the JPEG header will be arbitrary, but this is the least significant part of the
+            comment length, so we will restrict our BMP file length to less than <code>ff00=65280</code> bytes.
+        </p>
+        <p>
+            Since these must be in the same location at the start of the file,
+            we will need to brute-force search for two keys \(k_1, k_2\) and a nonce that
+            encrypt to the same ciphertext. The easiest way to do this is via a
+            birthday attack: fix an arbitrary nonce, then generate random keys
+            for both the JPEG header and the BMP header. Encrypt each and store
+            them in a lookup table. Repeat until two keys are found that
+            encrypt their respective headers to the same ciphertext bytes.
+        </p>
+        <p>
+            To the ciphertext header, add the encryption of the BMP file
+            (without the header) under \(k_2\), then pad with arbitrary data to reach the end of the JPEG comment (this will be ignored by the BMP
+            parser, which has already finished reading the file). After the
+            JPEG comment is over, add the encryption of the JPEG file (without the header and final magic bytes) under
+            \(k_1\).
+        </p>
+        <p>
+            Finally, add two more bytes of ciphertext that will make the final two
+            bytes of the JPEG file into the appropriate final magic bytes
+            <code>ffd9</code>.
+        </p>
+        <p>
+            These ciphertexts do not have the same MAC yet. If we tried to use
+            the strategy outlined at the beginning where we add an extra block
+            at the end, the JPEG file would no longer end in <code>ffd9</code>
+            and thus would be invalid. Instead, we need to modify it to change
+            the penultimate block.
+        </p>
+        <p>
+            However, we don't want any data from the penultimate block to show
+            up in our JPEG image. Thus, after the JPEG file data ends, we start
+            another comment that will extend until the penultimate block,
+            hiding it from the parser. Care must be taken to ensure the
+            penultimate block is really on a block boundary (the comment can be
+            padded to increase the length if necessary). After this second
+            comment will appear the final magic bytes <code>ffd9</code> as
+            desired.
         </p>
         </details>
 		<details>
@@ -212,25 +242,13 @@ for factor, _ in p.factor():
                 Show me the code.
 			</summary>
         <pre>
-from <a href="/git/forbidden-salamanders">aesgcmanalysis</a> import xor, gmac, gcm_encrypt, gcm_decrypt, nonce_reuse_recover_secrets
-
-k = b"tlonorbistertius"
-nonce = b"jorgelborges"
-m1, aad1 = b"The universe (which others call the Library)", b""
-m2, aad2 = b"From any of the hexagons one can see, interminably", b""
-
-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"
-c_forged, aad_forged = xor(c1, xor(m1, m_forged)), b""
+from <a href="/git/forbidden-salamanders">aesgcmanalysis</a> import att_merge_jpg_bmp
 
-for h, s in possible_secrets:
-    print("MAC candidate": gmac(h, s, aad_forged, c_forged))</pre></details>
+with open('first.jpg', 'rb') as h:
+    jpg = h.read()
+with open('second.bmp', 'rb') as h:
+    bmp = h.read()
+c, mac = att_merge_jpg_bmp(jpg, bmp, aad=b"")</pre></details>
 <script>
 MathJax = {
   tex: {
diff --git a/templates/mac-truncation.html b/templates/mac-truncation.html
index cf91149..1cbd629 100644
--- a/templates/mac-truncation.html
+++ b/templates/mac-truncation.html
@@ -116,6 +116,14 @@
 			on the web: <a href="#show-code">download the library</a> to run it locally.
 		</p>
         <p>
+            This attack was shown by Dutch cryptographer Niels Ferguson
+            in <a href="https://csrc.nist.gov/csrc/media/projects/block-cipher-techniques/documents/bcm/comments/cwc-gcm/ferguson2.pdf">Authentication weaknesses in GCM</a>.
+            He notes that a (then-)competing mode, CWC, avoids this attack by
+            encrypting the GMAC polynomial with the block cipher before adding
+            \(s\). This breaks the linear relationship between the ciphertext
+            and the MAC.
+        </p>
+        <p>
             Review the <a href="/forbidden-salamanders/nonce-reuse">nonce reuse attack</a>
             to learn why recovering the authentication key is enough to forge MACs over
             arbitrary ciphertexts.
@@ -336,15 +344,6 @@
 			and compute a forged MAC for arbitrary ciphertext under the same nonce
             as in the <a href="/forbidden-salamanders/nonce-reuse">nonce reuse attack</a>.
 		</p>
-        <h4>Addendum</h4>
-        <p>
-            This attack was first shown by Dutch cryptographer Niels Ferguson
-            in his paper <a href="https://csrc.nist.gov/csrc/media/projects/block-cipher-techniques/documents/bcm/comments/cwc-gcm/ferguson2.pdf">Authentication weaknesses in GCM</a>.
-            He notes that a (then-)competing mode, CWC, avoids this attack by
-            encrypting the GMAC polynomial with the block cipher before adding
-            \(s\). This breaks the linear relationship between the ciphertext
-            and the MAC.
-        </p>
         <p>
             Readers who wish to implement this attack themselves can try
             <a href="https://cryptopals.com/">Cryptopals</a>; specifically