# Precomputation attacks on RSA

Are precomputation attacks - such as outlined in RFC 3610 chapter 5 - possible on RSA PKCS#1 v1.5 signature generation? If yes, are such attacks taken into account when calculating the cryptographic key strength of RSA? Do they have the same impact on the security strength of RSA as on block ciphers (i.e. halving the cryptographic strength of the block cipher)?

I presume this kind of attack - if applicable - is thwarted by the PSS padding scheme?

-
Reading through CCM and wondering if this was not applicable in any of my implementations, could not find info for RSA. –  owlstead Jun 2 at 11:58
I know no attack on RSA PKCS#1 v1.5 signature, precomputation or not. Known working attacks are on faulty implementations. –  fgrieu Jun 2 at 13:09
For "precomputation attacks, you would not be able to look up the result" of what? $\hspace{.9 in}$ "Furthermore, the hash is what is verified", which is why an adversary could submit one message of a $\hspace{.1 in}$ hash collision for signing and then present that signature with the other message of the hash collision. $\hspace{.24 in}$ –  Ricky Demer Jun 5 at 8:46

No, these sorts of attacks are not of any use against RSA -- they are much harder to perform than other existing attacks (and in particular, attacks that factor an RSA modulus).

Here is how this precomputation attack works; you assume that someone generating the keys will always MAC (or sign) a specific message:

$$S_i = MAC_{K_i}( FixedMessage )$$

And so you treat this as a fixed function of key $K_i$ to tag $S_i$.

The legitimate key generator creates a long series of keys $K_1, K_2, ..., K_a$, and corresponding tags $S_1, S_2, ..., S_a$

The attacker generates a long series of random keys $K'_1, K'_2, ..., K'_b$, and corresponding tags $S'_1, S'_2, ..., S'_b$

Now, let us call the key space of the MAC in question $n$ bits. If $a \times b \approx 2^n$, then there is a decent chance that one of the keys $K'_j$ will happen to be the same as one of the legitimate keys $K_i$, and this will be detectable because $S_i = S'_j$; this can be detected by (say) a rainbow table lookup. Because of this, the attacker learns $K_i$.

With $n = 128$, e.g. AES-CMAC with 128 bit keys, this is just on the border of plausibility; if the legitimate generator creates $2^{50}$ keys (which is a huge, but not inherently implausible number), then the attacker would need to generate about $2^{78}$ keys; a huge but not inherently implausible number (and will perhaps be a bit more likely after a few more years of Moore's Law).

All that said, let us take a look at this attack in terms of RSA. With RSA, we have much larger keys. Currently, any key much smaller than 1k can be factored, so let us take a look at how this would apply to a set of 1k RSA keys. An RSA modulus is a product of two primes; there are a bit over $2^{500}$ 512 bit primes, and so there are approximately $2^{1000}$ RSA modulii that are 1024 bits long.

Now, if we assume that our legitimate generator creates $2^{50}$ keys, that means that we'd need to create about $2^{950}$ keys to have a decent chance of creating a collision -- that amount of work is completely and utterly implausble. In addition, if we were able to assemble anywhere close to that amount of computational power, factoring a 1k RSA key would be trivial. Hence, factoring one of the RSA modulii would be far easier than the collision method.

So, why does the collision method have such a hard time with RSA? Well, RSA keys need to be as big as they are to address attack methods that use the inherent mathematical structure within RSA. This collision method ignores this mathematical structure, and by ignoring this structure, doesn't work nearly as well.

-
Yeah, I was hoping that the sheer size of the key space was enough, but I wasn't 100% sure. I presume correctly that it is even harder if not impossible for PSS (given that the implementation is correct, of course)? –  owlstead Jun 2 at 13:12
@poncho : $\;\;\;$ Where does that signature scheme use anything about the message other than it's length and it's hash? $\:$ If it doesn't, then there is trivially a precomputation attack based on finding a hash collision whose messages have the same short length, submitting one of them to the signing oracle, and then outputting the other along with the signature. $\;\;\;\;\;\;\;$ –  Ricky Demer Jun 2 at 16:24
@RickyDemer: how does this precomputation attack work against RSA used properly, that is, with a collision resistant hash function? –  poncho Jun 2 at 16:33
@RickyDemer: that part is true; however if the hash function is chosen properly, it is still harder than factoring the modulus (albeit not to such an extreme extent) –  poncho Jun 2 at 16:55
I would anticipate getting out of trouble via randomized hashing. $\;$ –  Ricky Demer Jun 2 at 23:32