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
For most things for the near future. It's still plenty to prevent Joe Cracker from intercepting my SSL connection and decrypting it. Sure, a few large groups will have the ability to do it in a "reasonable" time, but, that's probably right anyway. If I have something that's worth $10 million and a year to crack, well, I should probably be encrypting it with a 2048 bit key.
If you have sensitive information, you want to encrypt it based on what you think will be difficult to crack years from now, not just today. Otherwise, interested third parties can simply store away an intercepted transmission until it becomes technologically feasible to crack it.
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).
So at this moment in time they *may* have the ability to crack a few hundred keys in one person's lifetime. (Remember, the machine is theoretical). That's a lot of money and time to crack relatively few keys, using a machine that doesn't exist. Maybe it would be worthwhile to use against AlQueda. As for the rest of us here on /., we probably don't have much to worry about. If you are worried then make a 2048-bit key for yourself. Case closed ... until a few years down the road. Then do the same again.
Wouldn't it be nice if instead of focusing on the problem ("1024 is unsafe!"/"the government might find the password to my hotmail account!") we focused on the solution ("make a bigger key!"/"don't inherently trust technology to be the final solution").
We can quip about 1024 being unsecure just like a few years ago we quiped about 512 being unsecure. That's why the key lengths keep going up. Any encryption is a preventative measure, not an absolute.
So Are 1024-bit RSA Keys Unsafe.
Right now, the answer would be No, they are not unsafe, relatively.
Of course they are. I just read an article the other day on how to file them down and make a master key out of them.
;)
Slashdot and their damn dupes
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/
A lot of talk about breaking encryption comes from the perspective of
the private key still being private. How secure is something like PGP
if the attacker has the private key but not the password?
Assuming maximum PGP 6.5.8 security of 4096 bit keys, with a good
strong passphrase (70+ chars, including non-alphanumeric), how long
would it take to break? Any reasonably accurate figures would be
appreciated.
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