Does it make sense to block RSA keys under 1024 bits?

Question

A paper I found (http://eprint.iacr.org/2012/064.pdf, which was submitted to a cryptography conference about two years ago), is based on the analysis of some 7.1 million 1024-bit RSA keys published online. By subjecting the modulus of each public key to an algorithm first postulated more than 2,000 years ago by the Greek mathematician Euclid, the researchers looked for underlying factors that were used more than once. Almost 27,000 of the keys they examined were cryptographically worthless because one of the factors used to generate them was used by at least one other key.

As these findings were related to 1024-bit RSA keys (and even those show some points of weakness), does it make sense to generally block all RSA keys under 1024 bits to enforce/strengthen used crypto?

Answer 1

Yes, it does make sense to block them.

Seeing you've asked this question in July, it's funny to think you might have had some kind of unintentional foresight of what meanwhile has become reality.

Some hard facts:

1. As raw computing power increases over time it becomes possible to factor or crack smaller sized RSA keys. Key sizes smaller than 1024 bits were voluntarily discontinued by Microsoft on 12 December, 2012.
2. As a proactive measure, effective 31 December, 2013, the NATIONAL INSTITUTE OF STANDARDS and TECHNOLOGY [NIST] has recommended that 1024-bit RSA certificates be eliminated and replaced with 2048-bit or stronger keys.
3. As a result of the NIST recommendation, the Certification Authority/ Browser (CA/B) Forum, created to develop best practices within the SSL/TLS industry, created a mandate to bring the 1024-bit RSA key size to end of life by December 31st, 2013.

Answer 2

Those findings were based on a broken PRNG. A broken PRNG affects all keys generated on such a device, no matter the size or the algorithm.

Common primes were how the problem was detected, but the problem itself is unrelated to primes or RSA. If RSA keys of a specific size where affected, that's only incidental because that's what the broken devices generated.

Blocking keys smaller than 1024 bits can be a good idea, because their security margin against factoring attacks has grown pretty thin, even when they're correctly generated. But that threat isn't related to the paper you link.

Answer 3

Hard to answer impartially, expect opinion-colored answers here.

The paper you are mentioning has essentially nothing to do with keysizes. Instead they show that bad use of randomness during RSA key generation may have major security impact. If so, why did they essentially find problems with 1024-bit key ? Well, mostly because they could collect much more 1024-bit keys and also to a certain extend because implementations that take the pain to use 2048-bit keys are probably written with more care.

Does this imply that blocking 1024-bit key would be a good idea ? May be not, but this would give some forward momentum to move away from 1024-bit keys (see How big an RSA key is considered secure today? for more about when they are expected to be really not enough).

We could even dream that people would move away from RSA and go for elliptic-curve.