Slashdot Mirror
TWIRL: Are 1024-bit RSA Keys Unsafe?
This came across the
Interesting-People list
today: a
preliminary draft of a paper,
co-authored by Adi Shamir, that proposes new hardware for factoring large numbers. It is claimed that a machine could be built which would be "3-4 orders of magnitude more cost effective than the best previously published designs," and that "the NFS sieving step for 1024-bit RSA keys can be completed in less than a year by a $10M device." For background, here's a
primer
on key length in symmetric and asymmetric crypto.
more here: link
1024 bit RSA composites have been considered the low end of the secure sizes, for a while now.
As always, as hardware and techniques get better, this needs to be revised - it seems likely that a large threat model (intelligence agency or very large corporation with money to waste on pointless cryptanalysis), today, could factor a 1024-bit key within a year. However, the resources necessary to smash a 1024 bit key are so great, in comparison with the cost of key theft/keylogger attacks, you'd have to be nuts to actually factor them. If someone wants your key that badly, they'll bug your keyboard, catch the passphrase and steal it, and that attack works against any keysize.
Planning ahead, though, 1024-bit RSA keys are unsuitable for use in new applications, and moving to 1536 or, if you can, 2048 or greater is strongly suggested.
Elgamal et al are roughly as complex as RSA (slightly more resistant to attacks, it seems). You shouldn't be using new Elgamal keys of 1024 bits or less either.
This does present one clear problem: the NSA's Digital Signature Algorithm (DSA - used commonly by PGP 5.x and up and GnuPG, as well as many other diverse cryptosystems) currently only specifies a 1024-bit modulus (for use with the SHA-1 160-bit hash). Larger modulus sizes would need larger standard hashes, and although these have now been developed (SHA-256, SHA-384, and SHA-512, collectively and informally known as SHA-2), the NSA have not yet blessed an extended DSA specification, making them useless to DSA for the time being (as extended sizes apparently violate the standard, and what generators to use with larger sizes?).
So it may, with a large threat model, millions of dollars and a year, be possible to find someone's PGP signing key and forge signatures. Whether or not this will be worth it is another matter (attacking the threat model like this would not stick very well, as if they ever see a forged signature of theirs, they'll revoke their key and shout loudly about it).
It is noteworthy, in the PGP field, that the 'new-style' RSA v4 keys, which can be used by GnuPG, PGP 6.5.8ckt08 and PGP 7.x and 8.x, allow the use of larger signature keys. No-one is going to break a 4096/4096 RSA new-style PGP key using SHA-512 as the hash anytime soon, unless someone is hiding a magic quantum computer.
If you need keys for secure communications, and speed may be somewhat critical (SSH or SSL come to mind), go 2048 bit or 1536 bit if you're in urgent need of space. If you're using them for anything else, especially long-term keys, think about 3072 or 4096 bits (you never know what the future holds, but you can be damn sure computers will keep getting faster).
The NFS sieve step is only half the problem, you still have to invert a huge matrix and that requires a closely coupled machine.
Adi has been describing machines of this type for years, he proposed twinkle a while back. The big problem is that only one half of the problem has a trivial parallelism.
OK there is a tradeoff between the sieve stage and the matrix stage. But it is not that helpfull. Basically to halve your work at the matrix stage you have to increase your sieving at least four-fold. This does not get you too far since the sieve stage is still pretty stiff.
Wow. Looks like somebody's winning the $200k after all
Not likely since the XBox key is 2048 bits, as are most of the major keys in use. The competent CAs plan about 10 years in advance. There are 2048 bit roots embedded in the browsers that can be used as soon as there is a need.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
The TWIRL paper refers to Bernstein's "Circuits for integer factoizaion" which was later partially debunked by "Analysis of Bernstein's factoring circuit" by Lenstra, Shamir, Tomlinson and Tromer, however they agreed that mesh-routing for doing the linear algebra step (solving a huge matrix) was an extremely attractive and feasible idea.
TWIRL appears to be an improvement of the previous TWINKLE hardware, also by Shamir, which proposed using optoelectronics in the sieving step. I don't know if that was ever built.
TWIRL is both faster and cheaper than TWINKLE, for instance as it uses a common silicon process as opposed to GaAs, and the actual sieving process is more efficient as well. I have only skimmed over the paper so I don't know about details.
The previous papers were more or less theoretical, but this TWIRL device appears to be perfectly feasible to build today.
Alex
Heisenberg may have been here
The version currently circulating is indeed a draft. The final version, when available, will be placed at my homepage, and specifically here.
-- Eran Tromer