Forbidden Salamanders

+ Forbidden Salamanders + at cyfraeviolae.org +

+ source code + · + aes-gcm nonce reuse + · + aes-gcm nonce truncation + · + aes-gcm key commitment +

+ The FIPS-compliant sorcerer Roseacrucis uses the Advanced Encryption Standard in Galois/Counter Mode + to correspond with his retinue. The Library’s cryptanalysts + have intercepted the communication channel, but we need your + help to exploit their broken protocols. +

+ Choose one of the following missions. +

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

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

+ 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 to the + Library that decrypt to confidential information under one key, but + innocuous banter under another. +

+
+

+ Though it is not required to complete your missions, we now + review the construction of AES-GCM. +

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

+ The ciphertext is computed as in counter mode, whereas the MAC is computed using the algorithm GMAC. +

+ Let + \[ + m = \alpha^{128}+\alpha^7 + \alpha^2 + \alpha + 1 + \] + \[ + \mathbb{K} = \mathbb{F}(2^{128})/m. + \] +

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

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

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

+ \(\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 128-bit AES block cipher. +

+
+

\(\operatorname{GMAC}(h\in \mathbb{K}, s\in \mathbb{K}, aad\in \operatorname{Byte}^{y}, c\in \operatorname{Byte}^{z})\)

\( len = \operatorname{encode_{big}}(8y, 8) \mathbin\Vert \operatorname{encode_{big}}(8z, 8) \)
\( blocks = \operatorname{pad}_{16}(aad, 0) \mathbin\Vert \operatorname{pad}_{16}(c, 0) \mathbin\Vert len \mathbin\Vert s \)
\( N = \frac{\vert blocks \vert}{16} \)
\( \operatorname{return} \sum\limits_{i=1}^{N} blocks_{N-i} h^{i-1}\)

+
+
+

\(\operatorname{AES-GCM}(k\in \operatorname{Byte}^{16}, n\in \operatorname{Byte}^{12}, aad\in \operatorname{Byte}^{y}, m\in \operatorname{Byte}^{z})\)

\( r = \mathop{\Vert}\limits_{n'=2^{32}n+2}^{2^{32}n+2^{32}-1} \operatorname{AES}(k, n') \)
\( c = r \oplus m \)
\( h = \operatorname{AES}(k, 0) \)
\( s = \operatorname{AES}(k, 2^{32}n + 1) \)
\( \operatorname{return} c, \operatorname{GMAC}(h, s, aad, c) \)

+ + + + + + + + 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 @@ + + + + Forbidden Salamanders + + + + + + + +

+ Forbidden Salamanders + at cyfraeviolae.org +

+ source code + · + aes-gcm nonce reuse + · + aes-gcm nonce truncation + · + aes-gcm key commitment +

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

+
+

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

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

+
+ + {% if macs %} +

+ Forged ciphertext: {{ c_forged.hex() }} +

+ Forged MAC candidates: +

+ MAC: {{mac.hex()}} +
- Authentication key: {{h.hex()}}
+

+ +

+ {% endif %} +
+

+ Show me the code. +

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

+ Show me the math. +

+ Once the polynomial difference is computed, one can use SageMath + to compute the factors: +

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

+ 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}})\).

+ + + + -- cgit v1.2.3