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

+ + + + diff --git a/templates/mac-truncation.html b/templates/mac-truncation.html new file mode 100644 index 0000000..cf91149 --- /dev/null +++ b/templates/mac-truncation.html @@ -0,0 +1,389 @@ + + + + Forbidden Salamanders · MAC Truncation + + + + + + + +

+ Forbidden Salamanders + at cyfraeviolae.org +

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

+ MAC truncation. The sorcerer aims to conserve + bandwidth by truncating MACs. Use the enemy as a decryption + oracle to once again, recover the authentication key and forge + arbitrary ciphertext. +

+
+ {% if form.errors %} +

+ Errors: +

{{name}}: {{ error }}

+ {% endif %} +

+ Roseacrucis chooses a key, a nonce, and a truncated MAC length; + then encrypts an arbitrary 512-byte length message. +

+ +

+ Key (16 bytes in hex) + +

+ +

+ Nonce (12 bytes in hex) + +

+ +

+ MAC length + + +

+ +

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

+ +

+ Finally, you choose a new message to forge under the same key + and nonce. +

+ +

+ Forged message + +

+ +

+ + {% if h %} +

+ Forged ciphertext: {{ c_forged.hex() }} +
+ Forged MAC: {{mac.hex()}} +
+ Authentication key: {{h.hex()}} +

+ {% endif %} +
+

+ Attack outline. +

+ Note that this attack (and library) should work for up to a MAC + length of 4 bytes, which is an allowed parameter by NIST and many + cryptography libraries. However, the attack is too slow to demonstrate + on the web: download the library to run it locally. +

+ Review the nonce reuse attack + to learn why recovering the authentication key is enough to forge MACs over + arbitrary ciphertexts. +

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

+ 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, + \] +

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

Linear Operations in \(\mathbb{K}=\mathbb{F}_{2^{128}}\)

+ As described in the mission home page, + 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}}\). +

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

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

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

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

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

Reframing the Problem

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

+ 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 + \] +

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

+ \(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 + \] +

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

+ The remaining \(N-M\) relevant bits of \(e\) will be random, but we + shall see it will be small enough to brute force. +

Zeroing Out Rows of \(A_{d^*}\)

+ Changing the bits of \(d^*\) effects a linear change on the + bits of \(A_{d^*}\). Consider a set of \(8\vert d^* \vert\) “basis + vectors” for \(d^*\) (one for each bit), the \(i\)th basis + vector having a 1 in the \(i\)th position and 0 everywhere else. +

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

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

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

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

Executing the Attack

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

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

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

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

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

Speeding up the Attack

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

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

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

+ 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 nonce reuse attack. +

Addendum

+ This attack was first shown by Dutch cryptographer Niels Ferguson + in his paper Authentication weaknesses in GCM. + 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. +

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

+ Show me the code. +

+from aesgcmanalysis import xor, gmac, gcm_encrypt, mac_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 = mac_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)

+ + + + + diff --git a/templates/nonce-reuse.html b/templates/nonce-reuse.html index 94dcb2c..249d00e 100644 --- a/templates/nonce-reuse.html +++ b/templates/nonce-reuse.html @@ -18,13 +18,11 @@

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

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 @@ - - - - Forbidden Salamanders · Nonce Truncation - - - - - - - -

- Forbidden Salamanders - at cyfraeviolae.org -

- source code - · - nonce reuse - · - nonce truncation - -

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

-
- {% if form.errors %} -

- Errors: -

{{name}}: {{ error }}

- {% endif %} -

- Roseacrucis chooses a key, a nonce, and a truncated MAC length; - then encrypts an arbitrary 512-byte length message. -

- -

- Key (16 bytes in hex) - -

- -

- Nonce (12 bytes in hex) - -

- -

- MAC length - - -

- -

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

- -

- Finally, you choose a new message to forge under the same key - and nonce. -

- -

- Forged message - -

- -

- - {% if h %} -

- Forged ciphertext: {{ c_forged.hex() }} -
- Forged MAC: {{mac.hex()}} -
- Authentication key: {{h.hex()}} -

- {% endif %} -
-

- Attack outline. -

- Review the nonce reuse attack - to learn why recovering the authentication key is enough to forge MACs over - arbitrary ciphertexts. -

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

- 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, - \] -

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

Linear Operations in \(\mathbb{K}=\mathbb{F}_{2^{128}}\)

- As described in the mission home page, - 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}}\). -

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

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

- 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}. - \] -

- 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. \] -

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

Reframing the Problem

- 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. - \] -

- 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 - \] -

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

- \(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 - \] -

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

- The remaining \(N-M\) relevant bits of \(e\) will be random, but we - shall see it will be small enough to brute force. -

Zeroing Out Rows of \(A_{d^*}\)

- Changing the bits of \(d^*\) effects a linear change on the - bits of \(A_{d^*}\). Consider a set of \(8\vert d^* \vert\) “basis - vectors” for \(d^*\) (one for each bit), the \(i\)th basis - vector having a 1 in the \(i\)th position and 0 everywhere else. -

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

- 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. \] -

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

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

Executing the Attack

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

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

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

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

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

Speeding up the Attack

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

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

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

- 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 nonce reuse attack. -

Addendum

- This attack was first shown by Dutch cryptographer Niels Ferguson - in his paper Authentication weaknesses in GCM. - 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. -

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

- Show me the code. -

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

- - - - - -- cgit v1.2.3