From 36b27e733c83e02ac54d7a6c1aa0a43938d1fc1f Mon Sep 17 00:00:00 2001 From: cyfraeviolae Date: Sat, 27 Aug 2022 05:46:17 -0400 Subject: key com --- aesgcmanalysis.py | 4 - app.py | 3 +- templates/key-commitment.html | 184 +++++++++++++++++++++++------------------- templates/mac-truncation.html | 17 ++-- 4 files changed, 111 insertions(+), 97 deletions(-) diff --git a/aesgcmanalysis.py b/aesgcmanalysis.py index b833376..13bfca3 100644 --- a/aesgcmanalysis.py +++ b/aesgcmanalysis.py @@ -761,8 +761,6 @@ def collide(k1, k2, nonce, c): acc = gf128_mul(lens, gf128_add(h1, h2)) acc = gf128_add(acc, gf128_add(p1, p2)) for i in range(1, mlen): - if i % 2048 == 0: - print(i, end=', ') hi = gf128_add(gf128_exp(h1, mlen+2-i), gf128_exp(h2, mlen+2-i)) acc = gf128_add(acc, gf128_mul(bytes_to_gf128(c[(i-1)*16:((i-1)+1)*16]), hi)) inv = gf128_inv(gf128_add(gf128_mul(h1, h1), gf128_mul(h2, h2))) @@ -837,7 +835,6 @@ def att_merge_jpg_bmp(jpg, bmp, aad): total_len = 6 + (0xff<<8) + 0xff + len(jpg) jpgstream, _ = gcm_encrypt(k1, nonce, aad, b'\x00'*total_len) bmpstream, _ = gcm_encrypt(k2, nonce, aad, b'\x00'*total_len) - print("enc") # 5 bytes r = xor(jpgstream, b'\xff\xd8\xff\xfe\xff') @@ -866,7 +863,6 @@ def att_merge_jpg_bmp(jpg, bmp, aad): tailx = xor(tail, jpgstream[6+comlen+len(jpg)-4:]) r += tailx assert len(r) % 16 == 0 - print("collide") cfin, macfin = collide_penultimate(k1, k2, nonce, r) diff --git a/app.py b/app.py index 800b263..01bdef6 100644 --- a/app.py +++ b/app.py @@ -133,7 +133,8 @@ def FileSizeLimit(max_bytes, magic_start=None, magic_end=None): if not field.data: return s = field.data.read() - n = len(field.data.read()) + n = len(s) + print(max_bytes, n) if n > max_bytes: raise ValidationError(f"File size must be less than {max_bytes}B") if magic_start and not s.startswith(magic_start): 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 @@

- You can test your ciphertext with Go. Run the following in a shell - and then try opening first.jpg and second.bmp in an image viewer. + You can test your ciphertext with Go. Run the following in a shell, + then try opening first.jpg and second.bmp + in an image viewer.

- Show testing code. + Test script. 
 TEMP="$(mktemp).go"
@@ -126,85 +127,114 @@ go run "$TEMP" 5c3cb198432b0903e58de9c9647bd241 4a4f5247454c424f52474553 polyglo
 go run "$TEMP" df923ae8976230008a081d23205d7a4f 4a4f5247454c424f52474553 polyglot.enc > second.bmp
-
Attack outline.

- 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 Fast Message Franking: From Invisible Salamanders to Encryptment. +

+

+ 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. +

+

+ 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.

- 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 - - crib dragging, 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.

- 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. -

-

- 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 factoring the - polynomial. -

-

- 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. -

-

- One can use SageMath to compute factors of a polynomial: -

- 
-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)
-

- However, the library powering this demonstration implements polynomial factoring over finite fields from scratch, which is an edifying exercise. -

-

- We present advice for those who wish to implement polynomial factorization as well: -

- + \[ + 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} + \] +

+

+ 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. +

+

+ 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. +

+

+ All JPEG files start with the magic bytes ffd8 and end + with ffd9. We will place a JPEG comment immediately + after the initial magic bytes, which is indicated by fffe and is followed by a 2-byte big-endian encoding of the comment length. + All BMP files start with the magic bytes 424d followed by a 4-byte little-endian encoding of the file length. +

+

+ Because the JPEG comment has a maximum length, our BMP file will need to be less than ffff=65536 bytes. + Thus, we desire the JPEG file to start with ffd8 fffe ffff and the BMP file to start with 424d wxyz 0000, + where wxyz is the actual length of our BMP file. +

- Readers who wish to implement this attack themselves can try - Cryptopals; 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 ff00=65280 bytes. +

+

+ 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. +

+

+ 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\). +

+

+ Finally, add two more bytes of ciphertext that will make the final two + bytes of the JPEG file into the appropriate final magic bytes + ffd9. +

+

+ 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 ffd9 + and thus would be invalid. Instead, we need to modify it to change + the penultimate block. +

+

+ 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 ffd9 as + desired.

@@ -212,25 +242,13 @@ for factor, _ in p.factor(): Show me the code. 
-from aesgcmanalysis 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 aesgcmanalysis import att_merge_jpg_bmp
 
-for h, s in possible_secrets:
-    print("MAC candidate": gmac(h, s, aad_forged, c_forged))
+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"")