data

truncation

truncation launch

remove files

5 files changed, 492 insertions, 77 deletions

diff --git a/aesgcmanalysis.py b/aesgcmanalysis.py
index abdfdb3..9e0d5b6 100644
--- a/aesgcmanalysis.py
+++ b/aesgcmanalysis.py
@@ -686,7 +686,8 @@ def find_b(n, basis, ct, mac, nonce, aad, oracle):
                 base[j*16:(j+1)*16] = xor(base[j*16:(j+1)*16], block)
         idx += 1
 
-def compute_auth_key(ct, mac, nonce, mac_bytes, aad, oracle):
+def nonce_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle):
+    orig_ct = ct
     ct = aad + ct
     n = compute_n(ct)
     assert n > (mac_bytes*8//2)
@@ -716,11 +717,23 @@ def compute_auth_key(ct, mac, nonce, mac_bytes, aad, oracle):
             K = np.concatenate([K, incrK])
         _, _, basisKerK = kernel(K, rref_mod_2)
         X = np.array(basisKerK).transpose()
-        print(len(basisKerK))
     _, _, kerK = kernel(K, rref_mod_2)
     assert len(kerK) == 1
     h = kerK[0]
-    return gf128_to_bytes(vec_to_gf128(h))
+
+    zero_tag = gf128_to_vec(bytes_to_gf128(gmac(vec_to_gf128(h), 0, aad, orig_ct)))[:mac_bytes*8]
+    gf128_mac = 0
+    i = 0
+    for b in mac:
+        for j in range(8):
+            if b & (1 << (7-j)):
+                gf128_mac += (1<<i)
+            i += 1
+    def small_gf128_to_vec(x):
+        return [int(n) for n in bin(x)[2:].zfill(mac_bytes*8)[::-1]]
+    mac_vec = small_gf128_to_vec(gf128_mac)
+    s = (np.array(zero_tag) - np.array(mac_vec)) % 2
+    return vec_to_gf128(h), vec_to_gf128(s)
 
 # Demos
 
@@ -757,20 +770,23 @@ def forbidden_attack_demo():
     assert succeeded
 
 def nonce_truncation_demo():
-    k = b'YELLOW_SUBMARINE'
+    # Should 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.
+    k = b'YELLOGIOJEWARINE'
     aad = b'YELLOW_SUBMAFINERELLOWPUBMARINF_'
     MACBYTES=1
-    pt = b'CELERYPATCHWORKS'*(2**9)
+    pt = b'CELERYPATCHWORKS'*(2**5)
     nonce = b'JORGELBORGES'
-    ct, mac = gcm_encrypt(k, nonce, aad, pt, mac_bytes=MACBYTES)
+    ct, mac = gcm_encrypt(k, nonce, aad, pt)
+    # ct, mac = gcm_encrypt(k, nonce, aad, pt, mac_bytes=MACBYTES)
+    mac = mac[:1]
     def oracle(base, aad, mac, nonce):
         cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=MACBYTES)
         cipher.update(aad)
         pt = cipher.decrypt_and_verify(base, mac)
-    h = compute_auth_key(ct, mac, nonce, MACBYTES, aad, oracle)
-    assert h == gf128_to_bytes(authentication_key(k))
-nonce_truncation_demo()
+    h, s = nonce_truncation_recover_secrets(ct, mac, nonce, MACBYTES, aad, oracle)
+    assert h == authentication_key(k)
+    return h, s
 
-# Try with different lengths
-# Make it so we chosoe to generate gen_t on the fly if needed
-# PRofiling
+nonce_truncation_demo()
diff --git a/app.py b/app.py
index d573efc..efc45bf 100644
--- a/app.py
+++ b/app.py
@@ -1,11 +1,12 @@
-import binascii
+import binascii, secrets
 
 from flask import Flask, render_template, request, redirect, url_for
 from flask_wtf import FlaskForm
 from wtforms import StringField
 from wtforms.validators import DataRequired, Length, ValidationError
+from Crypto.Cipher import AES
 
-from aesgcmanalysis import xor, gmac, gcm_encrypt, nonce_reuse_recover_secrets, gf128_to_bytes
+from aesgcmanalysis import xor, gmac, gcm_encrypt, nonce_reuse_recover_secrets, gf128_to_bytes, nonce_truncation_recover_secrets
 
 app = Flask(__name__)
 
@@ -21,7 +22,6 @@ def hex_check(form, field):
 
 def not_equal_to(other):
     def helper(form, field):
-        print(other, form['m1'], field)
         if other not in form:
             return
         if form[other].data == field.data:
@@ -46,10 +46,10 @@ def nonce_reuse():
         if form.validate():
             skey = binascii.unhexlify(key)
             snonce = binascii.unhexlify(nonce)
-            c_forged, macs = solve(skey, snonce, bytes(m1, 'utf-8'), bytes(m2, 'utf-8'), bytes(mf, 'utf-8'))
+            c_forged, macs = solve_nonce_reuse(skey, snonce, bytes(m1, 'utf-8'), bytes(m2, 'utf-8'), bytes(mf, 'utf-8'))
     return render_template('nonce-reuse.html', form=form, key=key, nonce=nonce, m1=m1, m2=m2, mf=mf, c_forged=c_forged, macs=macs)
 
-def solve(k, nonce, m1, m2, mf):
+def solve_nonce_reuse(k, nonce, m1, m2, mf):
     aad1 = aad2 = b""
     c1, mac1 = gcm_encrypt(k, nonce, aad1, m1)
     c2, mac2 = gcm_encrypt(k, nonce, aad2, m2)
@@ -63,3 +63,36 @@ def solve(k, nonce, m1, m2, mf):
         macs.append((gf128_to_bytes(h), s, mac))
     return c_forged, macs
 
+class NonceTruncationForm(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})
+    key = nonce = None
+    mf = ''
+    h = c_forged = mac = None
+    if form.is_submitted():
+        key, nonce, mf = form.key.data, form.nonce.data, form.mf.data
+        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,
+                           mf=mf, h=h, c_forged=c_forged, mac=mac)
+
+def solve_nonce_truncation(k, nonce, mf):
+    aad = b""
+    m = secrets.token_bytes(512)
+    c, mac = gcm_encrypt(k, nonce, aad, m, mac_bytes=1)
+
+    def oracle(base, aad, mac, nonce):
+        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)
+    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]
diff --git a/templates/index.html b/templates/index.html
index baf6a6d..1dbcc79 100644
--- a/templates/index.html
+++ b/templates/index.html
@@ -19,9 +19,9 @@
                 <a href="/git/forbidden-salamanders">source code</a>
                 <span class="sep"> · </span>
                 <a href="/forbidden-salamanders/nonce-reuse">nonce reuse</a>
-                <!--
                 <span class="sep"> · </span>
                 <a href="/forbidden-salamanders/nonce-truncation">nonce truncation</a>
+                <!--
                 <span class="sep"> · </span>
                 <a href="/forbidden-salamanders/key-commitment">key commitment</a>
                 -->
@@ -42,13 +42,14 @@
             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="#">Nonce truncation</a>.</strong> The sorcerer
-            aims to conserve bandwidth by truncating nonces from twelve bytes
-            to four. Use the enemy as a decryption oracle to once again,
-            recover the authentication key and forge arbitrary ciphertext.
+            <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
+            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
diff --git a/templates/nonce-reuse.html b/templates/nonce-reuse.html
index e60cc95..94dcb2c 100644
--- a/templates/nonce-reuse.html
+++ b/templates/nonce-reuse.html
@@ -1,7 +1,7 @@
 <!DOCTYPE html>
 <html>
   <head>
-    <title>Forbidden Salamanders</title>
+    <title>Forbidden Salamanders &middot; Nonce Reuse</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">
@@ -19,9 +19,9 @@
                 <a href="/git/forbidden-salamanders">source code</a>
                 <span class="sep"> · </span>
                 <a href="/forbidden-salamanders/nonce-reuse"><strong>nonce reuse</strong></a>
-				<!--
                 <span class="sep"> · </span>
                 <a href="/forbidden-salamanders/nonce-truncation">nonce truncation</a>
+				<!--
                 <span class="sep"> · </span>
                 <a href="/forbidden-salamanders/key-commitment">key commitment</a>
 				-->
@@ -48,7 +48,7 @@
 		{% endif %}
         <form action="/forbidden-salamanders/nonce-reuse" method="post">
 			<div><em>
-				Roseacrucis chooses a key, a nonce, and two messages. He encrypts both messages under the same nonce.
+				Roseacrucis chooses a key, a nonce, and encrypts two messages under the same nonce.
 			</em></div><br>
 
             <div>
@@ -62,17 +62,19 @@
             </div>
 
             <div>
-            <label for="m1">First intercepted message</label>
+            <label for="m1">First message</label>
 			<input name="m1" id="m1" type="text" required maxlength=64 value="{{m1 if m1 else 'The universe (which others call the Library)'}}">
             </div>
 
             <div>
-            <label for="m2">Second intercepted message</label>
+            <label for="m2">Second message</label>
 			<input name="m2" id="m2" type="text" required maxlength=64 value="{{m2 if m2 else 'From any of the hexagons one can see, interminably'}}">
             </div>
 
 			<br><div><em>
-				After intercepting the ciphertexts, you choose a new message to forge under the same key and nonce.
+                After intercepting the ciphertexts and recovering the
+                authentication key, you choose a new message to forge under the
+                same key and nonce.
 			</em></div><br>
 
             <div>
@@ -139,9 +141,10 @@
         </p>
         <p>
             However, we still need to compute a new MAC over the forged ciphertext.
-            Simplifying for a ciphertext \(c\) of two blocks, the GMAC MAC is computed as
+			Simplifying for a ciphertext \(c\) of two blocks and no additional
+			authenticated data, the GMAC MAC is computed as
             \[
-                mac = s + (len)h + c_1h^2 + c_0h^3,
+                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.
@@ -167,6 +170,28 @@
             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
@@ -197,52 +222,6 @@ 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>
-		<details>
-			<summary>
-                Show me the math.
-			</summary>
-            <p>
-                Once the polynomial difference is computed, one can use SageMath
-                to compute the factors:
-            </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 = (x^127 + x^125 + x^121 + x^118 + x^117 + x^116 + x^113 + x^111 + x^108 + x^105 + x^102 + x^99 + x^97 + x^95 + x^89 + x^87 +
- x^85 + x^84 + x^81 + x^78 + x^73 + x^71 + x^69 + x^67 + x^65 + x^63 + x^62 + x^59 + x^57 + x^55 + x^54 + x^53 + x^52 + x^51 +
-x^49 + x^47 + x^46 + x^45 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^33 + x^29 + x^28 + x^25 + x^21 + x^20 + x^17 + x^15 + x
-^13 + x^9 + x^7 + x^4 + x^3 + x)*y^5 + (x^127 + x^125 + x^121 + x^118 + x^117 + x^116 + x^113 + x^111 + x^108 + x^105 + x^102 +
- x^99 + x^97 + x^95 + x^89 + x^87 + x^85 + x^84 + x^81 + x^78 + x^73 + x^71 + x^69 + x^67 + x^65 + x^63 + x^62 + x^59 + x^57 +
-x^55 + x^54 + x^53 + x^52 + x^51 + x^49 + x^47 + x^46 + x^45 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^33 + x^29 + x^28 + x
-^25 + x^21 + x^20 + x^17 + x^15 + x^13 + x^9 + x^7 + x^4 + x^3 + x)*y^4 + (x^127 + x^125 + x^124 + x^123 + x^122 + x^120 + x^11
-9 + x^118 + x^115 + x^112 + x^111 + x^110 + x^109 + x^108 + x^106 + x^101 + x^100 + x^99 + x^98 + x^96 + x^93 + x^88 + x^87 + x
-^84 + x^83 + x^82 + x^78 + x^77 + x^74 + x^71 + x^70 + x^69 + x^68 + x^65 + x^62 + x^61 + x^60 + x^57 + x^55 + x^53 + x^50 + x^
-49 + x^47 + x^46 + x^44 + x^43 + x^41 + x^40 + x^39 + x^37 + x^36 + x^35 + x^34 + x^33 + x^31 + x^30 + x^25 + x^19 + x^16 + x^1
-4 + x^13 + x^12 + x^11 + x^10 + x^5 + x^2 + x + 1)*y^3 + (x^124 + x^123 + x^121 + x^120 + x^119 + x^118 + x^117 + x^116 + x^115
- + x^113 + x^112 + x^110 + x^107 + x^106 + x^104 + x^103 + x^101 + x^99 + x^98 + x^95 + x^94 + x^83 + x^82 + x^81 + x^80 + x^79
- + x^77 + x^76 + x^75 + x^73 + x^72 + x^67 + x^64 + x^63 + x^62 + x^61 + x^59 + x^57 + x^56 + x^54 + x^53 + x^51 + x^49 + x^48
-+ x^46 + x^45 + x^44 + x^42 + x^36 + x^35 + x^34 + x^33 + x^31 + x^28 + x^22 + x^21 + x^17 + x^12 + x^11 + x^10 + x^8 + x^5 + x
-^4 + 1)*y^2 + (x^120 + x^119 + x^56 + x^55)*y + (x^127 + x^126 + x^125 + x^124 + x^123 + x^118 + x^117 + x^116 + x^115 + x^114
-+ x^113 + x^105 + x^103 + x^98 + x^96 + x^94 + x^91 + x^90 + x^89 + x^87 + x^86 + x^85 + x^83 + x^81 + x^80 + x^78 + x^77 + x^7
-0 + x^66 + x^63 + x^62 + x^59 + x^58 + x^54 + x^53 + x^52 + x^50 + x^47 + x^45 + x^44 + x^42 + x^40 + x^39 + x^37 + x^35 + x^34
- + x^30 + x^29 + x^27 + x^26 + x^25 + x^23 + x^18 + x^16 + x^14 + x^13 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3
-+ 1)
-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>
-        </details>
 <script>
 MathJax = {
   tex: {
diff --git a/templates/nonce-truncation.html b/templates/nonce-truncation.html
new file mode 100644
index 0000000..35f8aea
--- /dev/null
+++ b/templates/nonce-truncation.html
@@ -0,0 +1,386 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Forbidden Salamanders &middot; Nonce 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">
+    <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/nonce-reuse">nonce reuse</a>
+                <span class="sep"> · </span>
+				<a href="/forbidden-salamanders/nonce-truncation"><strong>nonce truncation</strong></a>
+				<!--
+                <span class="sep"> · </span>
+                <a href="/forbidden-salamanders/key-commitment">key commitment</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
+            oracle to once again, recover the authentication key and forge
+            arbitrary ciphertext.
+        </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/nonce-truncation" method="post">
+			<div><em>
+				Roseacrucis chooses a key, a nonce, and a truncated MAC length;
+				then encrypts an arbitrary 512-byte length message.
+			</em></div><br>
+
+            <div>
+            <label for="key">Key (16 bytes in hex)</label>
+			<input name="key" id="key" type="text" value="{{ key if key else '746c6f6e6f7262697374657274697573' }}" minlength=32 maxlength=32 required>
+            </div>
+
+            <div>
+            <label for="nonce">Nonce (12 bytes in hex)</label>
+			<input name="nonce" id="nonce" type="text" value="{{ nonce if nonce else '4a4f5247454c424f52474553' }}" minlength=24 maxlength=24 required>
+            </div>
+
+            <div>
+            <label for="mac_len">MAC length</label>
+
+			<select name="mac_len" id="mac_len">
+				<option value="1">1 byte</option>
+			</select>
+            </div>
+
+			<br><div><em>
+				After intercepting the ciphertext, you create new
+				specially-crafted messages and guess their corresponding MACs.
+				You send your guesses to Roseacrucis; whether he accepts gives
+				you enough information to recover the authentication key.
+			</em></div>
+
+			<br><div><em>
+				Finally, you choose a new message to forge under the same key
+				and nonce.
+			</em></div><br>
+
+            <div>
+            <label for="mf">Forged message</label>
+			<input name="mf" id="mf" type="text" required maxlength=64 value="{{mf}}">
+            </div>
+            <div>
+				<button type="submit">Recover authentication key and forge MAC</button>
+            </div>
+        </form>
+		<form action="/forbidden-salamanders/nonce-truncation" method="get">
+		<div>
+			<button type="submit">Reset</button>
+		</div>
+		</form>
+		{% if h %}
+        <div class="solution">
+			<p>
+				Forged ciphertext: <code>{{ c_forged.hex() }}</code>
+				<br>
+				Forged MAC: <code>{{mac.hex()}}</code>
+				<br>
+				Authentication key: <code>{{h.hex()}}</code>
+			</p>
+        </div>
+		{% endif %}
+        <br>
+		<details>
+			<summary>
+                Attack outline.
+			</summary>
+        <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.
+        </p>
+        <p>
+            After intercepting a ciphertext and MAC, our initial goal is to compute
+            a variant of the ciphertext that has the same MAC.
+			Simplifying for a ciphertext \(c\) of four blocks and no additional
+			authenticated data, the GMAC MAC is computed as
+            \[
+                mac = s + \vert c\vert{}h + c_3h^2 + c_2h^3 + c_1h^4 + c_0h^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>
+        <h4>Differences</h4>
+        <p>
+            Given a different ciphertext \(c'\) of the same length encrypted
+            with the same key and nonce, the difference in their MACs can be computed
+            as
+            \[
+                mac-mac' = (c_3-c_3')h^2 + (c_2-c_2')h^3 + (c_1-c_1')h^4 + (c_0-c_0')h^5,
+            \]
+        </p>
+        <p> Let \(e\) be the difference between the two MACs, and \(d_i\) be
+            the difference between two blocks at position \(i\):
+            \[
+                e = (d_3)h^2 + (d_2)h^3 + (d_1)h^4 + (d_0)h^5,
+            \]
+            We want to achieve \(e=0\) but with at least one \(d_i \not= 0\) in order
+            to obtain a non-trivial forgery.
+        </p>
+        <h4>Linear Operations in \(\mathbb{K}=\mathbb{F}_{2^{128}}\)</h4>
+        <p>
+            As described in the <a href="/forbidden-salamanders">mission home page</a>,
+            each block of ciphertext, the authentication key \(h\), and the MAC are 16-byte
+            blocks that can be interpreted as elements of the finite field
+            \(\mathbb{K}=\mathbb{F}_{2^{128}}\).
+        </p>
+        <p>
+            The elements of \(\mathbb{K}\) are usually represented as
+            polynomials with coefficients in \(\mathbb{F}_2\) of degree less
+            than 128, where multiplication is performed modulo an irreducible
+            polynomial given by the AES-GCM specification. This gives us a way
+            to multiply, add, and even divide two blocks.
+        </p>
+        <p>
+            For this problem we will use an alternate representation: a
+            128-length bit vector, where the \(i\)th bit of the vector
+            represents the coefficient of \(\alpha^i\) in the polynomial
+            representation.
+        </p>
+        <p>
+            The transformation \(f(a) = ca\) for \(c, a \in \mathbb{K}\) is
+            linear; thus, it can be represented as matrix \(M_c\).  We set each
+            column to the transformation by \(f\) of the basis vectors \(1, \alpha,
+            \alpha^2, \ldots\):
+            \[
+            M_c = \begin{bmatrix}
+            c & c\alpha & c\alpha^2 & \ldots & c\alpha^{127}
+            \end{bmatrix}.
+            \]
+        </p>
+        <p>
+            The squaring operation \(g(a) = a^2\) is also linear: since \(2 = 0 \in \mathbb{K}\),
+            \[(a+b)^2 = a^2 + 2ab + b^2 = a^2 + b^2,\]
+            and for \(k \in \mathbb{F}_2\),
+            \[(ka)^2 = k^2a^2 = ka^2. \]
+        </p>
+        <p>
+            Thus we can construct
+            \[
+            S = \begin{bmatrix}
+            1^2 & \alpha^2 & (\alpha^2)^2 & \ldots & (\alpha^{127})^2
+            \end{bmatrix},
+            \]
+            and \(g(a) = a^2\) can alternately be written \(g'(a) = Sa\), interpreting \(a\)
+            as a vector.
+        </p>
+        <h4>Reframing the Problem</h4>
+        <p>
+            We can now rewrite our equation for \(e\) in terms of matrices and vectors,
+            replacing \(h^{2^i}\) by \(S^ih\).
+            \[
+                e = M_{d_3}Sh + M_{d_2}h^3 + M_{d_1}S^2h + M_{d_0}h^5,
+            \]
+        </p>
+        <p>
+            To ensure that \(e\) will be a linear transformation on \(h\), we set
+            \(d_i = 0\) if the corresponding \(h^j\) term does not have \(j\) as
+            a power of 2, resulting in
+            \[
+                e = M_{d_3}Sh + M_{d_1}S^2h = (M_{d_3}S + M_{d_1}S^2)h
+            \]
+        </p>
+        <p>
+            Let \(\hat{d}\) represent the concatenation of all the remaining \(d_i\)s.
+            The length of \(\hat{d}\) will be logarithmic in the size of the original
+            ciphertext as we only consider the power-of-2-indexed blocks.
+        </p>
+        <p>
+            \(A\) represents the action on \(h\) by \(\hat{d}\):
+            \[
+            A = (M_{d_3}S + M_{d_1}S^2)
+            \]
+            \[
+            e = Ah
+            \]
+        </p>
+        <p>
+            In order for a full forgery, we need \(e=0\), but if the MAC length
+            is reduced to \(N\) bits, we only need the first \(N\) bits of
+            \(e\) to be zero, rather than all 128 bits. This will be satisfied if the first \(N\)
+            <em>rows</em> of \(A\) are all zero, regardless of \(h\). In
+            practice, zeroing out all \(N\) rows will be too difficult, so we
+            settle for zeroing out \(M \lt N\) rows instead.
+        <p>
+            The remaining \(N-M\) relevant bits of \(e\) will be random, but we
+            shall see it will be small enough to brute force.
+        </p>
+        <h4>Zeroing Out Rows of \(A\)</h4>
+        <p>
+            Changing the bits of \(\hat{d}\) effects a linear change on the
+            bits of \(A\). Consider a set of \(8\vert\hat d\vert\) &ldquo;basis
+            vectors&rdquo; for \(\hat d\) (one for each bit), the \(i\)th basis
+            vector having a 1 in the \(i\)th position and 0 everywhere else.
+        </p>
+        <p>
+            For each basis vector, compute the corresponding \(A\). Concatenate
+            the first \(M\) rows into a column vector of a dependency matrix \(T\).
+            Thus, \(T\) will have \(8\vert\hat{d}\vert\) columns and \(128M\) rows.
+        </p>
+        <p>
+            We want to compute some \(\hat d\) that result in the first
+            \(M\) rows of \(A\) equaling zero, which is equivalent to saying
+            \[ T\hat{d} = 0. \]
+        </p>
+        <p>
+            The solution space is given by the null space (or kernel) of
+            \(T\). Note that we need \(T\) to have more columns than rows for
+            the matrix to be linearly dependent and thus have a non-trivial
+            kernel.
+        </p>
+        <p>
+            The vectors of \(\ker T\) each represents a potential \(\hat d\)
+            that sends the first \(M\) rows of \(A\) to zero. Any linear
+            combination of the vectors of the kernel will have the same effect.
+        </p>
+        <h4>Executing the Attack</h4>
+        <p>
+            Consider a random linear combination of \(\ker T\). Since these
+            are difference vectors, they can be thought of as specifying
+            bit flips of the original ciphertext at the appropriate positions
+            (remember to leave the non-power-of-2 blocks alone).
+        </p>
+        <p>
+            By design, the first \(M\) bits of \(e\) will be zero, meaning that
+            the first \(M\) bits of the MAC of the modified ciphertext will
+            equal the original MAC. The remaining bits of the MAC will match
+            with \(\frac{1}{2^{N-M}}\) probability.
+        </p>
+        <p>
+            Say the MAC length is \(N=32\) bits, and we let \(M=16\) (this requires
+            intercepting a ciphertext of length \(2^{16+1}\)). We can compute
+            random linear combinations of \(\ker T\), sending the modified ciphertexts
+            and original MAC to Roseacrucis. If they accept (which they should after
+            roughly \(2^{16}=65536\) attempts), we've succeeded in a forgery.
+        </p>
+        <p>
+            In addition to the forgery, the acceptance gives us
+            information on \(h\): for the successful \(\hat d\), since
+            \[ e[0:N-1] = 0 = A[0:N-1]h \]
+            we know that \(h\) is in the kernel of the first \(N\) rows of
+            \(A\). The first \(M\) rows of \(A\) are zero so this is trivial,
+            but the next \(N-M\) rows are likely linearly independent rows. If
+            we put these rows into a new matrix \(K\), we have \[ 0 = Kh. \]
+            The dimensions of \(K\) are \((N-M, 128) = (16, 128)\). The kernel
+            of such a matrix is 112-dimensional, which is not enough to guess
+            \(h\) yet.
+        </p>
+        <p>
+            However, each additional forgery (with good probability) gives us
+            more linearly independent vectors to add into \(K\). Once we
+            collect 127 linearly independent vectors (there can be no more
+            since we know the kernel is non-trivial), the kernel of \(K\) will be 1-dimensional,
+            and the only vector in the kernel will be \(h\).
+        </p>
+        <h4>Speeding up the Attack</h4>
+        <p>
+            Once we have our first successful forgery, we have \(K\) such that
+            \(h \in \ker K\), meaning that some linear combination
+            of basis vectors of \(\ker K\) equals \(h\). Let \(X\) be
+            a basis set for \(K\), and so write
+            \[ h = Xh'. \]
+            We don't know \(h'\), but it is a 112-dimensional vector.
+            Now rewrite our equation for \(e\):
+            \[ e = Ah = A(Xh') = (AX)h', \]
+            where \(AX\) is a matrix of dimensions 128 by 112.
+        </p>
+        <p>
+            When we construct the corresponding dependency matrix \(T\),
+            we still have \(8\vert\hat d\vert\) columns, but each row
+            only takes 112 bits to zero out rather than 128. This lets us
+            set more rows to zero, which in turn gives us a better chance of
+            succeeding in the next \(\hat d\) forgery.
+        </p>
+        <p>
+            We can continue in this fashion, each step getting more and more
+            efficient until we collect 127 vectors in \(K\). Remember to leave
+            at least one relevant row of \(A\) to be non-zero; otherwise, the
+            forgery will succeed but won't tell us any more information about
+            \(h\).
+        </p>
+		<p>
+			To complete the attack, one can recover the first \(N\) rows of \(s\)
+			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
+            Set 8 Problem 64. Hint: in general the description has left out
+            whether variables are in \(\mathbb{F}_2\), \(\mathbb{F}_{2^{128}}\),
+            \(\mathbb{Z}\), etc. Consider this before you code each function.
+        </p>
+        </details>
+		<details>
+			<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 Crypto.Cipher import AES
+
+k = b"tlonorbistertius"
+aad = b''
+mac_bytes = 4
+m = b'yellow_submarine'*(2**17)
+nonce = b'jorgelborges'
+c, mac = gcm_encrypt(k, nonce, aad, m, mac_bytes=MACBYTES)
+def oracle(base, aad, mac, nonce):
+	cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=mac_bytes)
+	cipher.update(aad)
+	cipher.decrypt_and_verify(base, mac)
+h, s = nonce_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""
+mac_forged = 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>