diff options
Diffstat (limited to 'templates/key-commitment.html')
| -rw-r--r-- | templates/key-commitment.html | 184 |
1 files changed, 101 insertions, 83 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 > 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 “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> + \[ + 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: { |