This was a really fun vulnerability to have the pleasure to consult on:
https://bughunters.google.com/blog/5424842357473280/zen-and-the-art-of-microcode-hacking
It turns out AES-CMAC is not second preimage resistant if you know the key (double so if the key is in an RFC), and 2048 bit numbers are quite often very easy to factor.
Tavis (who did the actual vulnerability research, as opposed to me just commenting on the sidelines), has more:
You can now jailbreak your AMD CPU! 🔥We've just released a full microcode toolchain, with source code and tutorials. https://bughunters.google.com/blog/5424842357473280/zen-and-the-art-of-microcode-hacking
The sample modulus you see in the blog post was somewhat intentionally crafted the way it is, using zeros instead of random numbers as a baseline. You start with an all zero array, set the first and last bit to one, and then compute the sacrificial block and some offset that does not touch those bits. Then you attempt to factor by going through a set of small primes, and run Miller-Rabin on whatever remains. If Miller-Rabin fails, you increment the last number by two, adjust the sacrificial block, and try again.
We can see that factoring succeeded with the least significant byte just being 0x13, so after just 10 attempts, you can find a factorable number.
Computing the probability that this factoring algorithm succeeds is non-trivial, and the best estimate would depend on the Riemann hypothesis.
For a random integer x, we have a probability of about 1/log(x) of x being prime (log being the natural logarithm).
The probability of a number being only divisible by small primes is a bit more complicated, but those numbers are very important in number theory (called smooth numbers), and have been extensively studied. Their probability is given by the Dickman function (https://en.m.wikipedia.org/wiki/Dickman_function) rho(log(x)/log(p)), with p being the upper bound of your smoothness set.
We can combine the two with some integral, to get the probability that x is the product of a smooth function with a prime, but WolframAlpha refuses to compute the integral and my Mathematica installation is out of reach at the moment.
But we can give a lower estimate, since primes would totally work for this, and their probability is as mentioned 1/log(x). That ends up with an estimate of 1 in 1419, so as you can see, the smoothness check increases the odds considerably, but even with just checking primality you would get good results.
Once you have the factorization, you compute the Euler totient by multiplying (p-1)*p^(k-1) for all prime powers p^k that factor your modulus (when implementing this, don't forget the leftover prime!)
You check that this totient is coprime to 65537, compute the extended gcd between 65537 and that totient, and boom, you have a "private key"
You can't really use a standard RSA library at this point, and you probably don't care about performance enough to compute the CRT parameters, but you could do that, too, it would just require some adjustments to account for the fact that we now have multiple prime powers as factors instead of just two primes.
As I'm getting some questions on this: this attack only works due to the combination of specifically RSA with an insecure hash function.
Neither RSA nor AES-CMAC were broken, but AES-CMAC, as opposed to HMAC-SHA2, does not degrade into a secure hash function when the key is known.
But you also need RSA for this to work, ECDSA would have been able to (somewhat) resist this attack:
If we use uncompressed points, it is very unlikely to land on the curve, so a simple point on curve check would have thwarted the attack. While we could choose 48 of the 64 bytes of a point, we have to choose first, and then compute the rest, so that does not help us to land on the curve.
If it was using compressed points, we would be able to find a second point on the curve. But again, this is a point that had half of its bytes chosen at random, so you would not have a way to compute its discrete logarithm. That is, unless you're willing to use a lot of memory, and combine baby step-giant step with a multi user attack. That would work, but still be prohibitively expensive for casual vulnerability research.
Sophie Schmieg
Dan Sugalski
Alex Russell
SpaceLifeForm
ZT