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