summaryrefslogtreecommitdiff
path: root/templates/nonce-truncation.html
diff options
context:
space:
mode:
authorcyfraeviolae <cyfraeviolae>2022-08-27 02:55:45 -0400
committercyfraeviolae <cyfraeviolae>2022-08-27 02:55:45 -0400
commit00e2704d0039ed9dbbfec54b2643da395f642f66 (patch)
treee950941b75e49d8b65fac23c1a656bfb767f1f51 /templates/nonce-truncation.html
parent0812e77c8d980773806bd7810a5e0992c180b589 (diff)
key commitment
Diffstat (limited to 'templates/nonce-truncation.html')
-rw-r--r--templates/nonce-truncation.html386
1 files changed, 0 insertions, 386 deletions
diff --git a/templates/nonce-truncation.html b/templates/nonce-truncation.html
deleted file mode 100644
index 0095bb1..0000000
--- a/templates/nonce-truncation.html
+++ /dev/null
@@ -1,386 +0,0 @@
-<!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>
- <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 two MACs, and \(d_i\) be
- the difference between two blocks at position \(i\):
- \[
- e(d_i, h) = (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 different ciphertext with the same MAC.
- </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:
- \[
- e(d_i, h) = M_{d_3}h^2 + M_{d_2}h^3 + M_{d_1}h^4 + M_{d_0}h^5,
- \]
- after which we replace \(h^{2^i}\) by \(S^ih\):
- \[
- e(d_i, h) = 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(d_i, h) = M_{d_3}Sh + M_{d_1}S^2h = (M_{d_3}S + M_{d_1}S^2)h
- \]
- </p>
- <p>
- Let \(d^*\) represent the concatenation of all the remaining \(d_i\)s.
- The length of \(d^*\) will be logarithmic in the size of the original
- ciphertext as we only consider the power-of-2-indexed blocks.
- </p>
- <p>
- \(A_{d^*}\) represents the action on \(h\) by \(d^*\):
- \[
- A_{d^*} = (M_{d_3}S + M_{d_1}S^2)
- \]
- \[
- e(d^*, h) = A_{d^*}h
- \]
- </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_{d^*}\) 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_{d^*}\)</h4>
- <p>
- Changing the bits of \(d^*\) effects a linear change on the
- bits of \(A_{d^*}\). Consider a set of \(8\vert d^* \vert\) &ldquo;basis
- vectors&rdquo; for \(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_{d^*}\). Concatenate
- the first \(M\) rows into a column vector of a dependency matrix \(T\).
- Thus, \(T\) will have \(8\vert d^*\vert\) columns and \(128M\) rows.
- </p>
- <p>
- We want to compute some \(d^*\) that result in the first
- \(M\) rows of \(A_{d^*}\) equaling zero, which is equivalent to saying
- \[ Td^* = 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 \(d^*\)
- that sends the first \(M\) rows of \(A_{d^*}\) 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 \(d^*\), since
- \[ e(d^*, h)[0:N-1] = 0 = A_{d^*}[0:N-1]h \]
- we know that \(h\) is in the kernel of the first \(N\) rows of
- \(A_{d^*}\). The first \(M\) rows of \(A_{d^*}\) are zero,
- 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 by the rank-nullity theorem,
- 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(A_{d^*}, h) = A_{d^*}h = A_{d^*}(Xh') = (A_{d^*}X)h', \]
- where \(A_{d^*}X\) is a matrix of dimensions 128 by 112.
- </p>
- <p>
- When we construct the corresponding dependency matrix \(T\),
- we still have \(8\vert 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 \( 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_{d^*}\) 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.
- </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"
-mac_bytes = 4
-m, aad, = b"yellow_submarine"*(2**17) = b""
-nonce = b"jorgelborges"
-c, mac = gcm_encrypt(k, nonce, aad, m, mac_bytes=MACBYTES)
-def oracle(c, aad, mac, nonce):
- cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=mac_bytes)
- cipher.update(aad)
- cipher.decrypt_and_verify(c, 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>