summaryrefslogtreecommitdiff
path: root/templates
diff options
context:
space:
mode:
Diffstat (limited to 'templates')
-rw-r--r--templates/key-commitment.html184
-rw-r--r--templates/mac-truncation.html17
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