Forbidden Salamanders · Key Commitment

+ Forbidden Salamanders + at cyfraeviolae.org +

+ source code + · + key commitment + · + nonce reuse + · + mac truncation +

+ Key commitment. 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. +

+
+ {% if form.errors %} +

+ Errors: +

{{name}}: {{ error }}

+ {% endif %} +

+ The Library’s agent chooses two images: a JPEG file containing + confidential information, and a BMP file that looks innocuous. +

+ + + Use sample JPEG and BMP files:
+
+

+
+
+ + Select custom files:
+ +

+ JPEG file (<150KB) + +

+ +

+ BMP file (<50KB) + +

+ +

+ 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. +

+ +

+ Key 1: 5c3cb198432b0903e58de9c9647bd241 +
+ Key 2: df923ae8976230008a081d23205d7a4f +
+ Nonce: 4a4f5247454c424f52474553 +

+
+ +

+ +

+ You can test your ciphertext with Go. Run the following in a shell + and then try opening first.jpg and second.bmp in an image viewer. +

+ Show testing code. +

+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   ") }
+  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
+

+
+

+ Attack outline. +

+ 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. +

+ 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 + + crib dragging, which makes this attack particularly effective: + \[ + c' = c \oplus m \oplus m'. + \] +

+ 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. +

+ 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 factoring the + polynomial. +

+ 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. +

+ One can use SageMath to compute factors of a polynomial: +

+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)

+ However, the library powering this demonstration implements polynomial factoring over finite fields from scratch, which is an edifying exercise. +

+ We present advice for those who wish to implement polynomial factorization as well: +

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 monic gcd, which is unique.
The inverse Frobenius automorphism (i.e., square root) in \(\mathbb{F}_{2^{128}}\) is given by \(\sqrt{x} = x^{2^{127}}\).

+ Readers who wish to implement this attack themselves can try + Cryptopals; specifically + Set 8 Problem 62. +

+ Show me the code. +

+from aesgcmanalysis 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))

+ + + + -- cgit v1.2.3