// ------------------------------------------------------------ 64. Key-Recovery Attacks on GCM with a Truncated MAC This one is my favorite. It's somewhat common to use a truncated MAC tag. For instance, you might be authenticating with HMAC-SHA256 and shorten the tag to 128 bits. The idea is that you can save some bandwidth or storage and still have an acceptable level of security. This is a totally reasonable thing to want. In some protocols, you might take this to the extreme. If two parties are exchanging lots of small packets, and the value of forging any one packet is pretty low, they might use a 16-bit tag and expect 16 bits of security. In GCM, this is a disaster. To see how, we'll first review the GCM MAC function. We make a calculation like this: t = s + c1*h + c2*h^2 + c3*h^3 + ... + cn*h^n We're making some notational changes here for convenience; most notably, we using one-based indexing. The c1 block encodes the length, and [c2, cn] are blocks of ciphertext. We'll also ignore the possibility of AD blocks here, since they don't matter too much for our purposes. Recall that our coefficients (and our authentication key h) are elements in GF(2^128). We've seen a few different representations, namely polynomials in GF(2) and unsigned integers. To this we'll add one more: a 128-degree vector over GF(2). It's basically just a bit vector; not so different from either of our previous representations, but we want to get our heads in linear algebra mode. The key concept we want to explore here is that certain operations in GF(2^128) are linear. One of them is multiplication by a constant. Suppose we have this function: f(y) = c*y With c and y both elements of GF(2^128). This function is linear in the bits of y. That means that this function is equivalent: g(y) = c*y[0] + c*y[1] + c*y[2] + ... + c*y[127] Any linear function can be represented by matrix multiplication. So if we think of y as a vector, we can construct a matrix Mc such that: Mc*y = f(y) = c*y To construct Mc, just calculate c*1, c*x, c*x^2, ..., c*x^127, convert each product to a vector, and let the vectors be the columns of your matrix. You can verify by performing the matrix multiplication against y and checking the result. I'm going to assume you either know how matrix multiplication works or have access to Wikipedia to look it up. Squaring is also linear. This is because (a + b)^2 = a^2 + b^2 in GF(2^128). Again, this means we can replace this function: f(y) = y^2 With a matrix multiplication. Again, compute 1^2, x^2, (x^2)^2, ..., (x^127)^2, convert the results to vectors, and make them your columns. Then verify that: Ms*y = f(y) = y^2 Okay, let's put these matrices on the back burner for now. To forge a ciphertext c', we'll start with a valid ciphertext c and flip some bits, hoping that: sum(ci * h^i) = sum(ci' * h^i) Another way to write this is: sum((ci - ci') * h^i) = 0 If we let ei = ci - ci', we can simplify this: sum(ei * h^i) = 0 Note that if we leave a block unmolested, then ei = ci - ci' = 0. We're going to leave most ei = 0. In fact, we're only going to flip bits in blocks di = e(2^i). These are blocks d0, d1, d2, ..., dn (note that we're back to zero-based indexing) such that: sum(di * h^(2^i)) = 0 We hope it equals zero, anyway. Maybe it's better to say: sum(di * h^(2^i)) = e Where e is some error polynomial. In other words, the difference in the MAC tag induced by our bit-flipping. At this point, we'll recall the matrix view. Recall that multiplications by a constant and squaring operations are both linear. That means we can rewrite the above equation as a linear operation on h: sum(Mdi * Ms^i * h) = e sum(Mdi * Ms^i) * h = e Ad = sum(Mdi * Ms^i) Ad * h = e We want to find an Ad such that Ad * h = 0. Let's think about how the bits in the vector e are calculated. This just falls out of the basic rules of matrix multiplication: e[0] = Ad[0] * h e[1] = Ad[1] * h e[2] = Ad[2] * h e[3] = Ad[3] * h ... In other words, e[i] is the inner product of row i of Ad with h. If we can force rows of Ad to zero, we can force terms of the error polynomial to zero. Every row we force to zero will basically double our chances of a forgery. Suppose the MAC is 16 bits. If we can flip bits and force eight rows of Ad to zero, that's eight bits of the MAC we know are right. We can flip whatever bits are left over with a 2^-8 chance of a forgery, way better than the expected 2^-16! It turns out to be really easy to force rows of Ad to zero. Ad is the sum of a bunch of linear operations. That means we can simply determine which bits of d0, d1, ..., dn affect which bits of Ad and flip them accordingly. Actually, let's leave d0 alone. That's the block that encodes the ciphertext length. Things could get tricky pretty quickly if we start messing with it. We still have d1, ..., dn to play with. That means n*128 bits we can flip. Since the rows of Ad are each 128 bits, we'll have to settle for forcing n-1 of them to zero. We need some bits left over to play with. Check the strategy: we'll build a dependency matrix T with n*128 columns and (n-1)*128 rows. Each column represents a bit we can flip, and each row represents a cell of Ad (reading left-to-right, top-to-bottom). The cells where they intersect record whether a particular free bit affects a particular bit of Ad. Iterate over the columns. Build the hypothetical Ad you'd get by flipping only the corresponding bit. Iterate over the first (n-1)*128 cells of Ad and set the corresponding cells in this column of T. After doing this for each column, T will be full of ones and zeros. We're looking for sets of bit flips that will zero out those first n-1 rows. In other words, we're looking for solutions to this equation: T * d = 0 Where d is a vector representing all n*128 bits you have to play with. If you know a little bit of linear algebra, you'll know that what we really want to find is a basis for N(T), the null space of T. The null space is exactly that set of vectors that solve the equation above. Just what we're looking for. Recall that a basis is a minimal set of vectors whose linear combinations span the whole space. So if we find a basis for N(T), we can just take random combinations of its vectors to get viable candidates for d. Finding a basis for the null space is not too hard. What you want to do is transpose T (i.e. flip it across its diagonal) and find the reduced row echelon form using Gaussian elimination. Now perform the same operations on an identity matrix of size n*128. The rows that correspond to the zero rows in the reduced row echelon form of T transpose form a basis for N(T). Gaussian elimination is pretty simple; you can more or less figure it out yourself once you know what it's supposed to do. Now that we have a basis for N(T), we're ready to start forging messages. Take a random vector from N(T) and decode it to a bunch of bit flips in your known good ciphertext C. (Remember that you'll be flipping bits only in the blocks that are multiplied by h^(2*i) for some i.) Send the adjusted message C' to the oracle and see if it passes authentication. If it fails, generate a new vector and try again. If it succeeds, we've gained more than just an easy forgery. Examine your matrix Ad. It should be a bunch of zero rows followed by a bunch of nonzero rows. We care about the nonzero rows corresponding to the bits of the tag. So if your tag is 16 bits, and you forced eight bits to zero, you should have eight nonzero rows of interest. Pick those rows out and stuff them in a matrix of their own. Call it, I don't know, K. Here's something neat we know about K: K * h = 0 In other words, h is in the null space of K! In our example, K is an 8x128 matrix. Assuming all its rows are independent (none of them is a combination of any of the others), N(K) is a 120-dimensional subspace of the larger 128-dimensional space. Since we know h is in there, the range of possible values for h went from 2^128 to 2^120. 2^120 is still a lot of values, but hey - it's a start. If we can produce more forgeries, we can find more vectors to add to K, reducing the range of values further and further. And check this out: our newfound knowledge of h is going to make the next forgery even easier. Find a basis for N(K) and put the vectors in the columns of a matrix. Call it X. Now we can rewrite h like this: h = X * h' Where h' is some unknown 120-bit vector. Now instead of saying: Ad * h = e We can say: Ad * X * h' = e Whereas Ad is a 128x128 matrix, X is 128x120. And Ad * X is also 128x120. Instead of zeroing out 128-degree row vectors, now we can zero out 120-degree vectors. Since we still have the same number of bits to play with, we can (maybe) zero out more rows than before. The general picture is that if we have n*128 bits to play with, we can zero out (n*128) / (ncols(X)) rows. Just remember to leave at least one nonzero row in each attempt; otherwise you won't learn anything new. So: start over and build a new T matrix, but this time to nullify rows of Ad * X. Forge another message and harvest some new linear equations on h. Stuff them in K and recalculate X. Lather, rinse, repeat. The endgame comes when K has 127 linearly independent rows. N(K) will be a 1-dimensional subspace containing exactly one nonzero vector, and that vector will be h. Let's try it out: 1. Build a toy system with a 32-bit MAC. This is the smallest tag length NIST defines in the GCM specification. 2. Generate valid messages of 2^17 blocks for the attacker to play with. 3. As the attacker, build your matrices, forge messages, and recover the key. You should be able to zero out 16 bits of each tag to start, and you'll only gain leverage from there.