key commitment

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()
diff --git a/app.py b/app.py
index 9aade4e..800b263 100644
--- a/app.py
+++ b/app.py
@@ -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
new file mode 100644
index 0000000..dbda080
--- /dev/null
+++ b/static/axolotl.jpg
diff --git a/static/kitten.bmp b/static/kitten.bmp
new 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&rsquo; 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&rsquo; 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 &middot; 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&rsquo; 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&rsquo;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 (&lt;150KB)</label>
+			<input type="file" id="jpeg" name="jpeg" accept="image/jpeg">
+            </div>
+
+            <div>
+            <label for="bmp">BMP file (&lt;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 &gt; "$TEMP" &lt;&lt;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) &lt; 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 &gt; first.jpg
+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.
+        </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 &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>
+        <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 &middot; Nonce Truncation</title>
+    <title>Forbidden Salamanders &middot; 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>