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)

+ + + + + -- cgit v1.2.3