diff options
| -rw-r--r-- | aesgcmanalysis.py | 150 | ||||
| -rw-r--r-- | app.py | 91 | ||||
| -rw-r--r-- | static/axolotl.jpg | bin | 0 -> 70374 bytes | |||
| -rw-r--r-- | static/kitten.bmp | bin | 0 -> 23258 bytes | |||
| -rw-r--r-- | static/styles.css | 8 | ||||
| -rw-r--r-- | templates/index.html | 30 | ||||
| -rw-r--r-- | templates/key-commitment.html | 245 | ||||
| -rw-r--r-- | templates/mac-truncation.html (renamed from templates/nonce-truncation.html) | 31 | ||||
| -rw-r--r-- | templates/nonce-reuse.html | 8 |
9 files changed, 507 insertions, 56 deletions
diff --git a/aesgcmanalysis.py b/aesgcmanalysis.py index 259cf69..b833376 100644 --- a/aesgcmanalysis.py +++ b/aesgcmanalysis.py @@ -1,3 +1,4 @@ +from binascii import unhexlify import random, struct, hmac, itertools, math from Crypto.Cipher import AES import cryptography @@ -600,7 +601,7 @@ def nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2): secrets.append((h, s)) return secrets -## Nonce Truncation Attack +## MAC Truncation Attack def gen_blocks(n, js): blocks = b'\x00'*16*n @@ -689,7 +690,7 @@ def find_b(n, basis, ct, mac, nonce, aad, oracle): base = orig_base.copy() idx += 1 -def nonce_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle, compute_T_once=False): +def mac_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle, compute_T_once=False): orig_ct = ct ct = aad + ct n = compute_n(ct) @@ -743,6 +744,134 @@ def nonce_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle, com s = (np.array(zero_tag) - np.array(mac_vec)) % 2 return vec_to_gf128(h), vec_to_gf128(s) +# Key Commitment Attack + +def gmac_blind(k, nonce): + return bytes_to_gf128(ecb_encrypt(k, nonce + b'\x00\x00\x00\x01')) +def encode_lengths(ad_length, ct_length): + return struct.pack('>QQ', ad_length*8, ct_length*8) +def collide(k1, k2, nonce, c): + h1 = gmac_key(k1) + h2 = gmac_key(k2) + p1 = gmac_blind(k1, nonce) + p2 = gmac_blind(k2, nonce) + assert len(c) % 16 == 0 + mlen = len(c)//16+1 + lens = bytes_to_gf128(encode_lengths(0, len(c) + 16)) + 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))) + c_append = gf128_mul(acc, inv) + c_ = c + gf128_to_bytes(c_append) + mac = gmac(h1, p1, b'', c_) + return (c_, mac) + +def collide_penultimate(k1, k2, nonce, c): + h1 = authentication_key(k1) + h2 = authentication_key(k2) + p1 = gmac_blind(k1, nonce) + p2 = gmac_blind(k2, nonce) + assert len(c) % 16 == 0 + mlen = len(c)//16 + lens = bytes_to_gf128(encode_lengths(0, len(c))) + acc = gf128_mul(lens, gf128_add(h1, h2)) + acc = gf128_add(acc, gf128_add(p1, p2)) + n=4 + h1Running = gf128_exp(h1, 4) + h2Running = gf128_exp(h2, 4) + for i in reversed(range(0, mlen-2)): + # print(mlen+1-(i)) + # i = mlen-2-1-i + hi = gf128_add(h1Running, h2Running) + h1Running = gf128_mul(h1Running, h1) + h2Running = gf128_mul(h2Running, h2) + n+=1 + # hi = gf128_add(gf128_exp(h1, mlen+1-i), gf128_exp(h2, mlen+1-i)) + #print('block', i, pt[i*16:(i+1)*16], 'exp', mlen+1-i) + acc = gf128_add(acc, gf128_mul(bytes_to_gf128(c[i*16:(i+1)*16]), hi)) + # for i in range(0, mlen-2): + # print(i,mlen+1-i) + # hi = gf128_add(gf128_exp(h1, mlen+1-i), gf128_exp(h2, mlen+1-i)) + # acc = gf128_add(acc, gf128_mul(bytes_to_gf128(c[i*16:(i+1)*16]), hi)) + hi = gf128_add(gf128_exp(h1, 2), gf128_exp(h2, 2)) + i = mlen-1 + #print('block', i, pt[i*16:(i+1)*16], 'exp', 2) + acc = gf128_add(acc, gf128_mul(bytes_to_gf128(c[i*16:(i+1)*16]), hi)) + inv = gf128_inv(gf128_add(gf128_exp(h1, 3), gf128_exp(h2, 3))) + c_append = gf128_mul(acc, inv) + c_ = c[:-32] + gf128_to_bytes(c_append) + c[-16:] + mac = gmac(h1, p1, b'', c_) + return (c_, mac) + +def gctr_oneblock(k, pt, nonce): + enckeyval = nonce + b'\x00\x00\x00\x02' + stream = ecb_encrypt(k, enckeyval) + return xor(pt, stream) + +def key_search(nonce, init_bytes1, init_bytes2): + seen1 = dict() + seen2 = dict() + while True: + k1 = secrets.token_bytes(16) + k2 = secrets.token_bytes(16) + ct1 = gctr_oneblock(k1, init_bytes1, nonce) + ct2 = gctr_oneblock(k2, init_bytes2, nonce) + seen1[ct1] = k1 + seen2[ct2] = k2 + if ct1 in seen2: + return k1, seen2[ct1] + if ct2 in seen1: + return seen1[ct2], k2 + +def att_merge_jpg_bmp(jpg, bmp, aad): + # Precomputed with key_search; works for any files + k1 = unhexlify('5c3cb198432b0903e58de9c9647bd241') + k2 = unhexlify('df923ae8976230008a081d23205d7a4f') + nonce = b'JORGELBORGES' + + 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') + + # 1 byte + r += bmpstream[5:6] + + # len(bmp) bytes + bmpenc = xor(bmp[6:], bmpstream[6:6+len(bmp)]) + r += bmpenc + + comlen = (0xff << 8) + (jpgstream[5] ^ bmpstream[5]) + + # finish comment with padding + r += b'\x00'*(comlen - len(bmpenc)) + + # jpg + r += xor(jpg[2:-2], jpgstream[6+comlen:]) + + # comment; include penultimate block to be overwritten; therefore must be at least 3 blocks long + # also serves to block-align to 14 bytes so the final ciphertext will be complete blocks + + endcomlen = (28 - (len(r) % 16)) + 16 + 14 + + tail = b'\xff\xfe' + struct.pack('>H', endcomlen) + b'\x00'*endcomlen + b'\xff\xd9' + 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) + + return cfin, macfin + # Demos def forbidden_attack_demo(): @@ -777,7 +906,7 @@ def forbidden_attack_demo(): pass assert succeeded -def nonce_truncation_demo(): +def mac_truncation_demo(): # Doesn't work with non-block size multiples. # Need to modify to consider padding, but we can't mess with the bits in the padding, # nor can we extend ad/ct unless we also change length block. @@ -795,10 +924,17 @@ def nonce_truncation_demo(): decryptor.authenticate_additional_data(aad) decryptor.update(base) + decryptor.finalize() - h, s = nonce_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle, compute_T_once=mac_bytes==1) + h, s = mac_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle, compute_T_once=mac_bytes==1) assert h == authentication_key(k) if __name__ == "__main__": - import resource - nonce_truncation_demo() - print(resource.getrusage(resource.RUSAGE_SELF).ru_maxrss) + pass + # mac_truncation_demo() + jpg = open('static/axolotl.jpg', 'rb').read() + bmp = open('static/kitten.bmp', 'rb').read() + c, mac = att_merge_jpg_bmp(jpg, bmp, aad=b"") + print(mac.hex()) + f = open('c.txt', 'wb') + f.write(c) + f.write(mac) + f.close() @@ -1,12 +1,14 @@ -import binascii, secrets +import binascii, secrets, io -from flask import Flask, render_template, request, redirect, url_for +from flask import Flask, render_template, request, redirect, url_for, send_file from flask_wtf import FlaskForm -from wtforms import StringField -from wtforms.validators import DataRequired, Length, ValidationError +from flask_wtf.file import FileField, FileAllowed +from werkzeug.datastructures import CombinedMultiDict +from wtforms import StringField, RadioField +from wtforms.validators import DataRequired, Length, ValidationError, InputRequired from Crypto.Cipher import AES -from aesgcmanalysis import xor, gmac, gcm_encrypt, nonce_reuse_recover_secrets, gf128_to_bytes, nonce_truncation_recover_secrets +from aesgcmanalysis import xor, gmac, gcm_encrypt, nonce_reuse_recover_secrets, gf128_to_bytes, mac_truncation_recover_secrets, att_merge_jpg_bmp app = Flask(__name__) @@ -72,14 +74,14 @@ def solve_nonce_reuse(k, nonce, m1, m2, mf): macs.append((gf128_to_bytes(h), s, mac)) return c_forged, macs -class NonceTruncationForm(FlaskForm): +class MACTruncationForm(FlaskForm): key = StringField('key', validators=[DataRequired(), Length(min=32, max=32), hex_check]) nonce = StringField('nonce', validators=[DataRequired(), Length(min=24, max=24), hex_check]) mf = StringField('forged message', validators=[DataRequired(), Length(min=1, max=64)]) -@app.route('/nonce-truncation', methods=['GET', 'POST']) -def nonce_truncation(): - form = NonceTruncationForm(meta={'csrf': False}) +@app.route('/mac-truncation', methods=['GET', 'POST']) +def mac_truncation(): + form = MACTruncationForm(meta={'csrf': False}) key = nonce = None mf = '' h = c_forged = mac = None @@ -88,11 +90,11 @@ def nonce_truncation(): if form.validate(): skey = binascii.unhexlify(key) snonce = binascii.unhexlify(nonce) - h, c_forged, mac = solve_nonce_truncation(skey, snonce, bytes(mf, 'utf-8')) - return render_template('nonce-truncation.html', form=form, key=key, nonce=nonce, + h, c_forged, mac = solve_mac_truncation(skey, snonce, bytes(mf, 'utf-8')) + return render_template('mac-truncation.html', form=form, key=key, nonce=nonce, mf=mf, h=h, c_forged=c_forged, mac=mac) -def solve_nonce_truncation(k, nonce, mf): +def solve_mac_truncation(k, nonce, mf): m = secrets.token_bytes(512) aad = b"" c, mac = gcm_encrypt(k, nonce, aad, m, mac_bytes=1) @@ -103,7 +105,70 @@ def solve_nonce_truncation(k, nonce, mf): cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=1) cipher.update(aad) cipher.decrypt_and_verify(base, mac) - h, s = nonce_truncation_recover_secrets(c, mac, nonce, 1, aad, oracle) + h, s = mac_truncation_recover_secrets(c, mac, nonce, 1, aad, oracle) c_forged, aad_forged = xor(c, xor(m, mf)), b"" mac = gmac(h, s, aad_forged, c_forged) return gf128_to_bytes(h), c_forged, mac[:1] + +class RequiredIf(InputRequired): + # adapted from https://stackoverflow.com/a/8464478 + # a validator which makes a field required if + # another field is set and has a truthy value + + def __init__(self, other_field_name, other_field_val, *args, **kwargs): + self.other_field_name = other_field_name + self.other_field_val = other_field_val + super(RequiredIf, self).__init__(*args, **kwargs) + + def __call__(self, form, field): + other_field = form._fields.get(self.other_field_name) + if other_field is None: + raise Exception('no field named "%s" in form' % self.other_field_name) + if other_field.data == self.other_field_val: + super(RequiredIf, self).__call__(form, field) + +def FileSizeLimit(max_bytes, magic_start=None, magic_end=None): + # adapted from https://stackoverflow.com/a/67172432 + def file_length_check(form, field): + if not field.data: + return + s = field.data.read() + n = len(field.data.read()) + 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): + raise ValidationError(f"Not a valid file; wrong initial magic bytes") + if magic_end and not s.endswith(magic_end): + raise ValidationError(f"Not a valid file; wrong final magic bytes") + field.data.seek(0) + return file_length_check + +class KeyCommitmentForm(FlaskForm): + mode = RadioField('mode', choices=[('sample', 'sample'), ('custom', 'custom')], validators=[DataRequired()]) + jpeg = FileField('jpeg_file', validators=[FileAllowed(['jpg', 'jpeg']), + RequiredIf('mode', 'custom'), FileSizeLimit(150000, b'\xff\xd8', b'\xff\xd9')]) + bmp = FileField('bmp_file', validators=[FileAllowed(['bmp']), + RequiredIf('mode', 'custom'), FileSizeLimit(50000, b'\x42\x4d')]) + +@app.route('/key-commitment', methods=['GET', 'POST']) +def key_commitment(): + form = KeyCommitmentForm(CombinedMultiDict((request.files, request.form)), meta={'csrf': False}) + k1 = None + k2 = None + nonce = None + c = None + + if form.is_submitted(): + if form.validate(): + if form.mode.data == 'sample': + jpeg_bytes = open('static/axolotl.jpg', 'rb').read() + bmp_bytes = open('static/kitten.bmp', 'rb').read() + else: + jpeg_bytes = form.jpeg.data.read() + bmp_bytes = form.bmp.data.read() + c, mac = att_merge_jpg_bmp(jpeg_bytes, bmp_bytes, aad=b"") + ct = c + mac + f = io.BytesIO(ct) + return send_file(f, mimetype='application/octet-stream', as_attachment=True, download_name="polyglot.enc") + + return render_template('key-commitment.html', form=form, k1=k1, k2=k2, nonce=nonce, c=c) diff --git a/static/axolotl.jpg b/static/axolotl.jpg Binary files differnew file mode 100644 index 0000000..dbda080 --- /dev/null +++ b/static/axolotl.jpg diff --git a/static/kitten.bmp b/static/kitten.bmp Binary files differnew file mode 100644 index 0000000..16b553b --- /dev/null +++ b/static/kitten.bmp diff --git a/static/styles.css b/static/styles.css index 9688050..5ea8a95 100644 --- a/static/styles.css +++ b/static/styles.css @@ -46,3 +46,11 @@ input[type="text"] { code { word-wrap: anywhere; } + +.responsive-img { + max-height: 200px; + max-width: 300px; + min-height: 150px; + /* width: 48%; */ + /* height: auto; */ +} diff --git a/templates/index.html b/templates/index.html index 1dbcc79..accbca7 100644 --- a/templates/index.html +++ b/templates/index.html @@ -18,13 +18,11 @@ <div class="crumbs"> <a href="/git/forbidden-salamanders">source code</a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/nonce-reuse">nonce reuse</a> + <a href="/forbidden-salamanders/key-commitment">key commitment</a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/nonce-truncation">nonce truncation</a> - <!-- + <a href="/forbidden-salamanders/nonce-reuse">nonce reuse</a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/key-commitment">key commitment</a> - --> + <a href="/forbidden-salamanders/mac-truncation">mac truncation</a> </div> </div> <p> @@ -37,28 +35,26 @@ Choose one of the following missions. </p> <p> + <strong><a href="/forbidden-salamanders/key-commitment">Key commitment</a>.</strong> One of + our agents has infiltrated Roseacrucis’ inner circle, but all + secret keys are required to be surrendered to the + counterintelligence authority. Help her send ciphertexts back to + the Library that decrypt to confidential information under one key, + but innocuous banter under another. + </p> + <p> <strong><a href="/forbidden-salamanders/nonce-reuse">Nonce reuse</a>.</strong> Due to rising entropy prices, Roseacrucis has started to reuse AES-GCM nonces. You must perform the Forbidden Attack in order to recover the authentication key and forge arbitrary ciphertext. </p> <p> - <strong><a href="/forbidden-salamanders/nonce-truncation">Nonce + <strong><a href="/forbidden-salamanders/mac-truncation">MAC truncation</a>.</strong> The sorcerer aims to conserve - bandwidth by truncating nonces. Use the enemy as a decryption + bandwidth by truncating MACs. Use the enemy as a decryption oracle to once again, recover the authentication key and forge arbitrary ciphertext. </p> - <!-- - <p> - <strong><a href="#">Key commitment</a>.</strong> One of - our agents has infiltrated Roseacrucis’ inner circle, but all - secret keys are required to be surrendered to the - counterintelligence authority. Help her send ciphertexts to the - Library that decrypt to confidential information under one key, but - innocuous banter under another. - </p> - --> <br> <details> <summary> diff --git a/templates/key-commitment.html b/templates/key-commitment.html new file mode 100644 index 0000000..619f010 --- /dev/null +++ b/templates/key-commitment.html @@ -0,0 +1,245 @@ +<!DOCTYPE html> +<html> + <head> + <title>Forbidden Salamanders · Key Commitment</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/key-commitment"><strong>key commitment</strong></a> + <span class="sep"> · </span> + <a href="/forbidden-salamanders/nonce-reuse">nonce reuse</a> + <span class="sep"> · </span> + <a href="/forbidden-salamanders/mac-truncation">mac truncation</a> + </div> + </div> + <p> + <strong>Key commitment.</strong> One of + our agents has infiltrated Roseacrucis’ inner circle, but all + secret keys are required to be surrendered to the + counterintelligence authority. Help her send ciphertexts back to + the Library that decrypt to confidential information under one key, + but innocuous banter under another. + </p> + <br> + {% if form.errors %} + <div class="errors"> + Errors: + <ul> + {% for name, errors in form.errors.items() %} + {% for error in errors %} + <li> {{name}}: {{ error }} </li> + {% endfor %} + {% endfor %} + </ul> + </div> + {% endif %} + <form action="/forbidden-salamanders/key-commitment" method="post" enctype="multipart/form-data"> + <div><em> + The Library’s agent chooses two images: a JPEG file containing + confidential information, and a BMP file that looks innocuous. + </em></div><br> + + <input type="radio" id="sample" name="mode" value="sample" required checked> + <label for="sample">Use sample JPEG and BMP files:</label><br> + <br> + <img class="responsive-img" src="/forbidden-salamanders/static/axolotl.jpg"> + <img class="responsive-img" src="/forbidden-salamanders/static/kitten.bmp"> + <br> + <br> + <input type="radio" id="custom" name="mode" value="custom" required> + <label for="custom">Select custom files:</label><br> + + <div> + <label for="jpeg">JPEG file (<150KB)</label> + <input type="file" id="jpeg" name="jpeg" accept="image/jpeg"> + </div> + + <div> + <label for="bmp">BMP file (<50KB)</label> + <input type="file" id="bmp" name="bmp" accept="image/bmp"> + </div> + + <br><div><em> + The agent now computes two keys, a nonce and constructs a single + ciphertext. When decrypted under the first key, it will look + identical to the JPEG file; when decrypted under the second + key, it will look identical to the BMP file. + </em></div> + + <p> + Key 1: <code>5c3cb198432b0903e58de9c9647bd241</code> + <br> + Key 2: <code>df923ae8976230008a081d23205d7a4f</code> + <br> + Nonce: <code>4a4f5247454c424f52474553</code> + </p> + <br> + + <div> + <button type="submit">Download polyglot ciphertext</button> + </div> + </form> + <form action="/forbidden-salamanders/key-commitment" method="get"> + <div> + <button type="submit">Reset</button> + </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. + </p> + <details> + <summary> + Show testing code. + </summary> +<pre style="font-size: small"> +TEMP="$(mktemp).go" +cat > "$TEMP" <<EOF +package main +import ("crypto/aes"; "crypto/cipher"; "encoding/hex"; "os") +func main() { + var key, nonce, ciphertext, plaintext []byte; var block cipher.Block; var aesgcm cipher.AEAD; var err error + if len(os.Args) < 4 { panic("usage: go run salamander.go <key> <nonce> <ciphertext-filename>") } + if key, err = hex.DecodeString(os.Args[1]); err != nil { panic(err.Error()) } + if nonce, err = hex.DecodeString(os.Args[2]); err != nil { panic(err.Error()) } + if ciphertext, err = os.ReadFile(os.Args[3]); err != nil { panic(err.Error()) } + if block, err = aes.NewCipher(key); err != nil { panic(err.Error()) } + if aesgcm, err = cipher.NewGCM(block); err != nil { panic(err.Error()) } + if plaintext, err = aesgcm.Open(nil, nonce, ciphertext, nil); err != nil { panic(err.Error()) } + if _, err = os.Stdout.Write(plaintext); err != nil { panic(err.Error()) } +} +EOF +go run "$TEMP" 5c3cb198432b0903e58de9c9647bd241 4a4f5247454c424f52474553 polyglot.enc > first.jpg +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. + </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'. + \] + </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 + \[ + mac = s + \vert c\vert 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 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> + <p> + Readers who wish to implement this attack themselves can try + <a href="https://cryptopals.com/">Cryptopals</a>; specifically + Set 8 Problem 62. + </p> + </details> + <details> + <summary> + 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"" + +for h, s in possible_secrets: + print("MAC candidate": gmac(h, s, aad_forged, c_forged))</pre></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> diff --git a/templates/nonce-truncation.html b/templates/mac-truncation.html index 0095bb1..cf91149 100644 --- a/templates/nonce-truncation.html +++ b/templates/mac-truncation.html @@ -1,7 +1,7 @@ <!DOCTYPE html> <html> <head> - <title>Forbidden Salamanders · Nonce Truncation</title> + <title>Forbidden Salamanders · MAC Truncation</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"> @@ -18,19 +18,16 @@ <div class="crumbs"> <a href="/git/forbidden-salamanders">source code</a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/nonce-reuse">nonce reuse</a> + <a href="/forbidden-salamanders/key-commitment">key commitment</a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/nonce-truncation"><strong>nonce truncation</strong></a> - <!-- + <a href="/forbidden-salamanders/nonce-reuse">nonce reuse</a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/key-commitment">key commitment</a> - --> + <a href="/forbidden-salamanders/mac-truncation"><strong>mac truncation</strong></a> </div> </div> <p> - <strong><a href="/forbidden-salamanders/nonce-truncation">Nonce - truncation</a>.</strong> The sorcerer aims to conserve - bandwidth by truncating nonces. Use the enemy as a decryption + <strong>MAC truncation.</strong> The sorcerer aims to conserve + bandwidth by truncating MACs. Use the enemy as a decryption oracle to once again, recover the authentication key and forge arbitrary ciphertext. </p> @@ -47,7 +44,7 @@ </ul> </div> {% endif %} - <form action="/forbidden-salamanders/nonce-truncation" method="post"> + <form action="/forbidden-salamanders/mac-truncation" method="post"> <div><em> Roseacrucis chooses a key, a nonce, and a truncated MAC length; then encrypts an arbitrary 512-byte length message. @@ -91,7 +88,7 @@ <button type="submit">Recover authentication key and forge MAC</button> </div> </form> - <form action="/forbidden-salamanders/nonce-truncation" method="get"> + <form action="/forbidden-salamanders/mac-truncation" method="get"> <div> <button type="submit">Reset</button> </div> @@ -112,6 +109,12 @@ <summary> Attack outline. </summary> + <p> + Note that this attack (and library) should work for up to a MAC + length of 4 bytes, which is an allowed parameter by NIST and many + cryptography libraries. However, the attack is too slow to demonstrate + on the web: <a href="#show-code">download the library</a> to run it locally. + </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 @@ -348,12 +351,12 @@ Set 8 Problem 64. </p> </details> - <details> + <details id="show-code"> <summary> Show me the code. </summary> <pre> -from <a href="/git/forbidden-salamanders">aesgcmanalysis</a> import xor, gmac, gcm_encrypt, nonce_truncation_recover_secrets +from <a href="/git/forbidden-salamanders">aesgcmanalysis</a> import xor, gmac, gcm_encrypt, mac_truncation_recover_secrets from Crypto.Cipher import AES k = b"tlonorbistertius" @@ -366,7 +369,7 @@ def oracle(c, aad, mac, nonce): cipher.update(aad) cipher.decrypt_and_verify(c, mac) -h, s = nonce_truncation_recover_secrets(c, mac, nonce, mac_bytes, aad, oracle) +h, s = mac_truncation_recover_secrets(c, mac, nonce, mac_bytes, aad, oracle) m_forged = b"As was natural, this inordinate hope" c_forged, aad_forged = xor(c, xor(m, m_forged)), b"" diff --git a/templates/nonce-reuse.html b/templates/nonce-reuse.html index 94dcb2c..249d00e 100644 --- a/templates/nonce-reuse.html +++ b/templates/nonce-reuse.html @@ -18,13 +18,11 @@ <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> + <a href="/forbidden-salamanders/key-commitment">key commitment</a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/nonce-truncation">nonce truncation</a> - <!-- + <a href="/forbidden-salamanders/nonce-reuse"><strong>nonce reuse</strong></a> <span class="sep"> · </span> - <a href="/forbidden-salamanders/key-commitment">key commitment</a> - --> + <a href="/forbidden-salamanders/mac-truncation">mac truncation</a> </div> </div> <p> |
