diff options
| -rw-r--r-- | aesgcmanalysis.py | 40 | ||||
| -rw-r--r-- | app.py | 43 | ||||
| -rw-r--r-- | templates/index.html | 13 | ||||
| -rw-r--r-- | templates/nonce-reuse.html | 87 | ||||
| -rw-r--r-- | templates/nonce-truncation.html | 386 |
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() @@ -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’ 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 · 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 “greater” is defined for polynomials in terms of degree. When used in algorithms, gcd refers to the <em>monic</em> gcd, which is unique.</li> + <li>The <a href="https://math.stackexchange.com/a/943626/1084004">inverse Frobenius automorphism</a> (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}}\).</li> + </ul> <p> Readers who wish to implement this attack themselves can try <a href="https://cryptopals.com/">Cryptopals</a>; specifically @@ -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 “greater” is defined for polynomials in terms of degree. When used in algorithms, gcd refers to the <em>monic</em> gcd, which is unique.</li> - <li>The <a href="https://math.stackexchange.com/a/943626/1084004">inverse Frobenius automorphism</a> (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}}\).</li> - </ul> - </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 · 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\) “basis + vectors” 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> |