summaryrefslogtreecommitdiff
path: root/templates
diff options
context:
space:
mode:
authorcyfraeviolae <cyfraeviolae>2022-08-24 00:38:04 -0400
committercyfraeviolae <cyfraeviolae>2022-08-24 00:38:04 -0400
commitd4e149445bda4a73dc3bb987e6ba296c7d6fe84e (patch)
tree5edc1b104f45239367a3a380a911de3b97dafa80 /templates
parent32137f612509ee577703d4316dc6a2ec937da709 (diff)
work
Diffstat (limited to 'templates')
-rw-r--r--templates/index.html148
-rw-r--r--templates/nonce-reuse.html236
2 files changed, 384 insertions, 0 deletions
diff --git a/templates/index.html b/templates/index.html
new file mode 100644
index 0000000..fdcddd8
--- /dev/null
+++ b/templates/index.html
@@ -0,0 +1,148 @@
+<!DOCTYPE html>
+<html>
+ <head>
+ <title>Forbidden Salamanders</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">aes-gcm nonce reuse</a>
+ <span class="sep"> · </span>
+ <a href="/forbidden-salamanders/nonce-truncation">aes-gcm nonce truncation</a>
+ <span class="sep"> · </span>
+ <a href="/forbidden-salamanders/key-commitment">aes-gcm key commitment</a>
+ </div>
+ </div>
+ <p>
+ The FIPS-compliant sorcerer Roseacrucis uses the <a href="https://en.wikipedia.org/wiki/Galois/Counter_Mode">Advanced Encryption Standard in Galois/Counter Mode</a>
+ to correspond with his retinue. The Library&rsquo;s cryptanalysts
+ have intercepted the communication channel, but we need your
+ help to exploit their broken protocols.
+ </p>
+ <p>
+ Choose one of the following missions.
+ </p>
+ <p>
+ <strong><a href="/forbidden-salamanders/nonce-reuse">Nonce
+ reuse</a>.</strong> Due to rising entropy prices, Roseacrucis has
+ started to reuse 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.
+ </p>
+ <p>
+ <strong><a href="#">Key commitment</a>.</strong> One of
+ our agents has infiltrated Roseacrucis&rsquo; inner circle, but all
+ secret keys are required to be surrendered to the
+ counterintelligence authority. Help her send ciphertexts to the
+ Library that decrypt to confidential information under one key, but
+ innocuous banter under another.
+ </p>
+ <br>
+ <details>
+ <summary>
+ Though it is not required to complete your missions, we now
+ review the construction of AES-GCM.
+ </summary>
+ <p>
+ AES-GCM is a block cipher that accepts a key of 16 bytes,
+ a nonce of 12 bytes, plaintext, and additional authenticated data.
+ It returns ciphertext and a message authentication code (MAC).
+ </p>
+ <p>
+ The ciphertext is computed as in <a href="https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Counter_(CTR)">counter mode</a>, whereas the MAC is computed using the algorithm GMAC.
+ </p>
+ <p>
+ Let
+ \[
+ m = \alpha^{128}+\alpha^7 + \alpha^2 + \alpha + 1
+ \]
+ \[
+ \mathbb{K} = \mathbb{F}(2^{128})/m.
+ \]
+ </p>
+ <p>
+ The finite field \(\mathbb{K}\) can be
+ interpreted as the set of polynomials with coefficients in \(\mathbb{F}_2\)
+ of degree less than \(128\). Multiplication
+ is performed modulo \(m\). This field is of characteristic 2;
+ e.g., \((\alpha^5 + 1)+(\alpha^5 + 1) = 0\).
+ </p>
+ <p>
+ We interpret 16-byte blocks as elements in \(\mathbb{K}\)
+ in little-endian bit order:
+ \[
+ b_0b_1b_2\ldots{}b_{127} \mapsto
+ b_0 + b_1\alpha + b_2\alpha^2 + \ldots + b_{127}\alpha^{127},
+ \]
+ where \(b_0\) is the least significant bit of the first byte of
+ the block.
+ </p>
+ <p>
+ 12-byte nonces are interpreted as 96-bit integers in big-endian
+ byte order. Let \(\operatorname{Byte} = [0, 2^8-1]\) and
+ \(x_i\) refer to the \(i\)th 16-byte chunk of the bytestring
+ \(x\).
+ </p>
+ <p>
+ \(\operatorname{encode_{big}}(x, n)\) encodes an integer \(x\) into \(n\) bytes in big-endian
+ byte order. \(\operatorname{pad_n}(x, p)\) pads the length of
+ the bytestring \(x\) to the nearest multiple of \(n\) with the
+ byte \(p\). \(\operatorname{AES}(k, x)\) refers to
+ the <a href="https://en.wikipedia.org/wiki/Advanced_Encryption_Standard">128-bit AES block cipher</a>.
+ </p>
+ <br>
+ <div class="algorithm">
+ <p>\(\operatorname{GMAC}(h\in \mathbb{K}, s\in \mathbb{K}, aad\in \operatorname{Byte}^{y}, c\in \operatorname{Byte}^{z})\)</p>
+ <ol class="algorithm-code">
+ <li>\( len = \operatorname{encode_{big}}(8y, 8) \mathbin\Vert \operatorname{encode_{big}}(8z, 8) \)</li>
+ <li>\( blocks = \operatorname{pad}_{16}(aad, 0) \mathbin\Vert \operatorname{pad}_{16}(c, 0) \mathbin\Vert len \mathbin\Vert s \)</li>
+ <li>\( N = \frac{\vert blocks \vert}{16} \)</li>
+ <li>\( \operatorname{return} \sum\limits_{i=1}^{N} blocks_{N-i} h^{i-1}\)</li>
+ </ol>
+ </div>
+ <br>
+ <br>
+ <div class="algorithm">
+ <p>\(\operatorname{AES-GCM}(k\in \operatorname{Byte}^{16}, n\in \operatorname{Byte}^{12}, aad\in \operatorname{Byte}^{y}, m\in \operatorname{Byte}^{z})\)</p>
+ <ol class="algorithm-code">
+ <li> \( r = \mathop{\Vert}\limits_{n'=2^{32}n+2}^{2^{32}n+2^{32}-1} \operatorname{AES}(k, n') \)</li>
+ <li> \( c = r \oplus m \) </li>
+ <li> \( h = \operatorname{AES}(k, 0) \) </li>
+ <li> \( s = \operatorname{AES}(k, 2^{32}n + 1) \) </li>
+ <li> \( \operatorname{return} c, \operatorname{GMAC}(h, s, aad, c) \)</li>
+ </ol>
+ </div>
+ </details>
+ <!-- <script id="MathJax-script" async src="/forbidden-salamanders/static/mathjax.js"></script> -->
+ <!-- <script type="text/x-mathjax-config"> -->
+ <!-- MathJax.Hub.Config({ TeX: { extensions: ["AMSmath.js", "AMSsymbols.js"] }}); -->
+ <!-- </script> -->
+<script>
+MathJax = {
+ tex: {
+ extensions: ["AMSmath.js", "AMSsymbols.js"]
+ }
+};
+</script>
+<script id="MathJax-script" async
+ src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js">
+</script>
+ </body>
+</html>
diff --git a/templates/nonce-reuse.html b/templates/nonce-reuse.html
new file mode 100644
index 0000000..9761955
--- /dev/null
+++ b/templates/nonce-reuse.html
@@ -0,0 +1,236 @@
+<!DOCTYPE html>
+<html>
+ <head>
+ <title>Forbidden Salamanders</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"><strong>aes-gcm nonce reuse</strong></a>
+ <span class="sep"> · </span>
+ <a href="/forbidden-salamanders/nonce-truncation">aes-gcm nonce truncation</a>
+ <span class="sep"> · </span>
+ <a href="/forbidden-salamanders/key-commitment">aes-gcm key commitment</a>
+ </div>
+ </div>
+ <p>
+ <strong>Nonce reuse.</strong> Due to rising entropy
+ prices, Roseacrucis has started to reuse nonces. You must perform the
+ Forbidden Attack in order to recover the authentication key and
+ forge arbitrary ciphertext.
+ </p>
+ <br>
+ <details>
+ <summary>
+ Attack outline.
+ </summary>
+ <p>
+ Recall that the AES-GCM ciphertext is computed as the XOR of the
+ keystream and the message. One can modify the bits of the
+ ciphertext arbitrarily to effect the same change in the decrypted
+ plaintext.
+ </p>
+ <p>
+ Where certain bits of the plaintext are already known, the attacker
+ can fully determine the same bits of the forged plaintext. If
+ nonces are reused, the keystream will be identical, allowing us to
+ recover plaintext via
+ <a href="https://samwho.dev/blog/toying-with-cryptography-crib-dragging/">
+ crib dragging</a>, which makes this attack particularly effective:
+ \[
+ c' = c \oplus m \oplus m'.
+ \]
+ </p>
+ <p>
+ However, we still need to compute a new MAC over the forged ciphertext.
+ Simplifying for a ciphertext \(c\) of two blocks, the GMAC MAC is computed as
+ \[
+ mac = s + (len)h + c_1h^2 + c_0h^3,
+ \]
+ where \(s\) is a constant depending on the AES-GCM key and the nonce, and \(h\)
+ is the authentication key depending only on the AES-GCM key.
+ </p>
+ <p>
+ If we intercept a second ciphertext \(c'\) encrypted under the same key and nonce,
+ we can compute
+ \[
+ mac + mac' = (s + s') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3,
+ \]
+ Since \(s = s'\) and \(x+x=0\) in \(\mathbb{F}_{2^{128}}\), we are
+ left with the polynomial equation
+ \[
+ 0 = (mac + mac') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3
+ \]
+ where all variables are known other than \(h\). Thus, recovering \(h\)
+ is a matter of finding the roots by <a href="https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields">factoring the
+ polynomial</a>.
+ </p>
+ <p>
+ We plug \(h\) back into the first equation to recover \(s\),
+ and finally, we can forge the MAC for arbitary ciphertext under the
+ same nonce. Note that there may be multiple possible monomial roots;
+ in this case, one can check each possibility online.
+ </p>
+ </details>
+ <br>
+ <form action="/forbidden-salamanders/nonce-reuse" method="post">
+ <div>
+ <label for="key">Key (16 bytes in hex)</label>
+ <input name="key" id="key" type="text" value="{{ key.hex() if key else '59454c4c4f575f5355424d4152494e45' }}" minlength=32 maxlength=32>
+ </div>
+
+ <div>
+ <label for="nonce">Nonce (12 bytes in hex)</label>
+ <input name="nonce" id="nonce" type="text" value="{{ nonce.hex() if nonce else '4a4f5247454c424f52474553' }}" minlength=24 maxlength=24>
+ </div>
+
+ <div>
+ <label for="m1">First intercepted message (in ASCII)</label>
+ <input name="m1" id="m1" type="text" required maxlength=100 value="{{m1}}">
+ </div>
+
+ <div>
+ <label for="m2">Second intercepted message (in ASCII)</label>
+ <input name="m2" id="m2" type="text" required maxlength=100 value="{{m2}}">
+ </div>
+
+ <div>
+ <label for="mf">Forged message; shorter than the first message (in ASCII)</label>
+ <input name="mf" id="mf" type="text" required maxlength=100 value="{{mf}}">
+ </div>
+
+ <div>
+ <button type="submit">Recover authentication key and forge MAC</button>
+ </div>
+ </form>
+ {% if macs %}
+ <div>
+ <p>
+ Forged ciphertext: <code>{{ c_forged.hex() }}</code>
+ </p>
+ Forged MAC candidates:
+ <ul>
+ {% for h, _, mac in macs %}
+ <li>
+ MAC: <code>{{mac.hex()}}</code>
+ <ul>
+ <li>Authentication key: <code>{{h.hex()}}</code></li>
+ </ul>
+ </li>
+ {% endfor %}
+ </ul>
+ <form action="/forbidden-salamanders/nonce-reuse" method="get">
+ <div>
+ <button type="submit">Reset</button>
+ </div>
+ </form>
+ </div>
+ {% endif %}
+ <br>
+ <details>
+ <summary>
+ Show me the code.
+ </summary>
+ <pre>
+from <a href="/git/forbidden-salamanders">aesgcmanalysis</a> import xor, gmac, gcm_encrypt, gcm_decrypt, nonce_reuse_recover_secrets
+
+k = b"tlonorbistertius"
+nonce = b"jorgelborges"
+m1 = b"The universe (which others call the Library)"
+aad1 = b"The Anatomy of Melancholy"
+m2 = b"From any of the hexagons one can see, interminably"
+aad2 = b"Letizia Alvarez de Toledo"
+
+c1, mac1 = gcm_encrypt(k, nonce, aad1, m1)
+c2, mac2 = gcm_encrypt(k, nonce, aad2, m2)
+
+# Recover the authentication key and blind from public information
+possible_secrets = nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2)
+
+# Forge the ciphertext
+m_forged = b"As was natural, this inordinate hope"
+assert len(m_forged) <= len(m1)
+c_forged = xor(c1, xor(m1, m_forged))
+aad_forged = b"You who read me, are You sure of understanding my language?"
+
+# Check possible candidates for authentication key
+succeeded = False
+for h, s in possible_secrets:
+ mac_forged = gmac(h, s, aad_forged, c_forged)
+ try:
+ assert gcm_decrypt(k, nonce, aad_forged, c_forged, mac_forged) == m_forged
+ succeeded = True
+ print(c_forged.hex(), mac_forged.hex())
+ except AssertionError:
+ pass
+assert succeeded</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: {
+ 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>