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

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?

-
Yes, but not for a reason completely unrelated to your first paragraph. $\;$ –  Ricky Demer Dec 11 '13 at 5:22
@RickyDemer Meanwhile, I realized that too. ;) –  e-sushi Dec 11 '13 at 20:18

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.
-
1024 bit key sizes have been known to be in the danger zone for much longer than last Juli. What's happening now is the enforcement instead of the recommendation to switch to larger key sizes (and to better hash algorithms as well) –  Maarten Bodewes Dec 11 '13 at 17:42

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.

-