diff options
| author | cyfraeviolae <cyfraeviolae> | 2022-08-27 02:55:45 -0400 |
|---|---|---|
| committer | cyfraeviolae <cyfraeviolae> | 2022-08-27 02:55:45 -0400 |
| commit | 00e2704d0039ed9dbbfec54b2643da395f642f66 (patch) | |
| tree | e950941b75e49d8b65fac23c1a656bfb767f1f51 /templates/key-commitment.html | |
| parent | 0812e77c8d980773806bd7810a5e0992c180b589 (diff) | |
key commitment
Diffstat (limited to 'templates/key-commitment.html')
| -rw-r--r-- | templates/key-commitment.html | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/templates/key-commitment.html b/templates/key-commitment.html new file mode 100644 index 0000000..619f010 --- /dev/null +++ b/templates/key-commitment.html @@ -0,0 +1,245 @@ +<!DOCTYPE html> +<html> + <head> + <title>Forbidden Salamanders · Key Commitment</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/key-commitment"><strong>key commitment</strong></a> + <span class="sep"> · </span> + <a href="/forbidden-salamanders/nonce-reuse">nonce reuse</a> + <span class="sep"> · </span> + <a href="/forbidden-salamanders/mac-truncation">mac truncation</a> + </div> + </div> + <p> + <strong>Key commitment.</strong> One of + our agents has infiltrated Roseacrucis’ inner circle, but all + secret keys are required to be surrendered to the + counterintelligence authority. Help her send ciphertexts back to + the Library that decrypt to confidential information under one key, + but innocuous banter under another. + </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/key-commitment" method="post" enctype="multipart/form-data"> + <div><em> + The Library’s agent chooses two images: a JPEG file containing + confidential information, and a BMP file that looks innocuous. + </em></div><br> + + <input type="radio" id="sample" name="mode" value="sample" required checked> + <label for="sample">Use sample JPEG and BMP files:</label><br> + <br> + <img class="responsive-img" src="/forbidden-salamanders/static/axolotl.jpg"> + <img class="responsive-img" src="/forbidden-salamanders/static/kitten.bmp"> + <br> + <br> + <input type="radio" id="custom" name="mode" value="custom" required> + <label for="custom">Select custom files:</label><br> + + <div> + <label for="jpeg">JPEG file (<150KB)</label> + <input type="file" id="jpeg" name="jpeg" accept="image/jpeg"> + </div> + + <div> + <label for="bmp">BMP file (<50KB)</label> + <input type="file" id="bmp" name="bmp" accept="image/bmp"> + </div> + + <br><div><em> + The agent now computes two keys, a nonce and constructs a single + ciphertext. When decrypted under the first key, it will look + identical to the JPEG file; when decrypted under the second + key, it will look identical to the BMP file. + </em></div> + + <p> + Key 1: <code>5c3cb198432b0903e58de9c9647bd241</code> + <br> + Key 2: <code>df923ae8976230008a081d23205d7a4f</code> + <br> + Nonce: <code>4a4f5247454c424f52474553</code> + </p> + <br> + + <div> + <button type="submit">Download polyglot ciphertext</button> + </div> + </form> + <form action="/forbidden-salamanders/key-commitment" method="get"> + <div> + <button type="submit">Reset</button> + </div> + </form> + <p> + You can test your ciphertext with Go. Run the following in a shell + and then try opening <code>first.jpg</code> and <code>second.bmp</code> in an image viewer. + </p> + <details> + <summary> + Show testing code. + </summary> +<pre style="font-size: small"> +TEMP="$(mktemp).go" +cat > "$TEMP" <<EOF +package main +import ("crypto/aes"; "crypto/cipher"; "encoding/hex"; "os") +func main() { + var key, nonce, ciphertext, plaintext []byte; var block cipher.Block; var aesgcm cipher.AEAD; var err error + if len(os.Args) < 4 { panic("usage: go run salamander.go <key> <nonce> <ciphertext-filename>") } + if key, err = hex.DecodeString(os.Args[1]); err != nil { panic(err.Error()) } + if nonce, err = hex.DecodeString(os.Args[2]); err != nil { panic(err.Error()) } + if ciphertext, err = os.ReadFile(os.Args[3]); err != nil { panic(err.Error()) } + if block, err = aes.NewCipher(key); err != nil { panic(err.Error()) } + if aesgcm, err = cipher.NewGCM(block); err != nil { panic(err.Error()) } + if plaintext, err = aesgcm.Open(nil, nonce, ciphertext, nil); err != nil { panic(err.Error()) } + if _, err = os.Stdout.Write(plaintext); err != nil { panic(err.Error()) } +} +EOF +go run "$TEMP" 5c3cb198432b0903e58de9c9647bd241 4a4f5247454c424f52474553 polyglot.enc > first.jpg +go run "$TEMP" df923ae8976230008a081d23205d7a4f 4a4f5247454c424f52474553 polyglot.enc > second.bmp +</pre> + </details> + <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 and no additional + authenticated data, the GMAC MAC is computed as + \[ + 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. + </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 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 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 + Set 8 Problem 62. + </p> + </details> + <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, aad1 = b"The universe (which others call the Library)", b"" +m2, aad2 = b"From any of the hexagons one can see, interminably", b"" + +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" +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> +<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> |