summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorcyfraeviolae <cyfraeviolae>2022-08-25 02:16:03 -0400
committercyfraeviolae <cyfraeviolae>2022-08-26 04:18:14 -0400
commit96a52a1030c1bb27619372c6cebb633e02017847 (patch)
tree25dfcd7eb8a3c7a0ba71bd3edb8516f7fc401287
parent62d6a6167e4121a536b813c883ac73773fef3ad7 (diff)
data
truncation truncation launch remove files
-rw-r--r--aesgcmanalysis.py40
-rw-r--r--app.py43
-rw-r--r--templates/index.html13
-rw-r--r--templates/nonce-reuse.html87
-rw-r--r--templates/nonce-truncation.html386
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>