Q: Has a change taken place in factoring RSA keys?
Hi, One of the local Linux user groups had a talk at their meeting as well as some extended discussion on the mailing list regarding RSA keys and factoring. In particular a claim was made that recent technology has come to light that allows factoring of 1024 bit RSA keys at $1B (US)/day. The basic gist was that they were claiming that 1024 keys were no longer reasonable outside of a life time of approx. a year. That 2048 keys were by extension weaker, and that larger keys should be the norm. There was some discussion about hacking GPG to generate 8k keys. I'm wondering if anyone might comment on this with regard to sources of info or other efforts? In particular I'm interested in any leads regarding this supposed hardware breakthrough. I spent about an hour googling around and didn't really come up with anything substantial. Thanks. -- -- Open Forge, LLC 24/365 Onsite Support for PCs, Networks, & Game Consoles 512-695-4126 (Austin, Tx.) help@open-forge.com irc.open-forge.com Hangar 18 Open Source Distributed Computing Using Plan 9 & Linux 512-451-7087 http://open-forge.org/hangar18 irc.open-forge.org James Choate 512-451-7087 ravage@ssz.com jchoate@open-forge.com
On Tue, 28 Oct 2003 05:08:28 -0600 (CST), Jim Choate said:
In particular a claim was made that recent technology has come to light that allows factoring of 1024 bit RSA keys at $1B (US)/day. The basic gist was that
Adi Shamir's TWINKLE, I guess.
time of approx. a year. That 2048 keys were by extension weaker, and that larger keys should be the norm. There was some discussion about hacking GPG to generate 8k keys.
That won't help unless you find a way to get random number as good as the keysize. The hack itself is trivial but I don't do it because large keys are a headache for low-end machines and they trick users into false security assumptions. I am pretty sure that any PC or usage of GnuPG can be broken by spending far less money. Werner -- Werner Koch <wk@gnupg.org> The GnuPG Experts http://g10code.com Free Software Foundation Europe http://fsfeurope.org
In particular a claim was made that recent technology has come to light that allows factoring of 1024 bit RSA keys at $1B (US)/day. The basic gist was that
Adi Shamir's TWINKLE, I guess.
I think that's the source as well - when the most recent of the TWINKLE and TWIRL papers came out, Lucky Green was talking about whether it was still safe to use 1024-bit keys, and $1B for 1 key/day is similar to Shamir & Tromer's estimate of ( http://www.wisdom.weizmann.ac.il/~tromer/papers/cbtwirl.pdf ) $20M upfront plus $10M for a 1 key/year capacity. (The alternative is that it's people believing the usual FUD sources, whether they're the pro-government serious FUD sources or the fun-yanking-people's-chains clueless FUDsters.)
There was some discussion about hacking GPG to generate 8k keys.
But if 1024-bit keys are too weak, RSA is still near-exponential, and 2048-bit keys are roughly 2**100 times harder to crack than 1024-bit, vs. 4-8 times as slow to use. 4096 is a lot harder than that; even if you allow for Moore's law and medium mathematical breakthroughs, you're still not going to fit a 4096-bit cracker on the planet. Basically, by the time you're interesting enough for them to spend $10M and a year to crack your machine, you'd better be using 2048-bit keys for tactical applications and maybe 4096-bit for long-term military secrets, and since they're targeting YOU, it's a lot cheaper for them to black-bag your PC or plant cameras in your ceiling or bribe your janitor.
That won't help unless you find a way to get random number as good as the keysize.
Large random numbers aren't that hard if you're using them for long-term signature keys, as opposed to DH or symmetric session keys; it just takes a bit longer to generate the bits. Also, once you're up above the 1024-bit range, incremental quality is less important, because attacks on the keyspace are hard to combine with factoring attacks on the keys, especially if you're whitening them. But as you say, taking GPG from 4kbit to 8kbit keys doesn't matter, because it's no longer close to the weakest link by then.
participants (3)
-
Bill Stewart -
Jim Choate -
Werner Koch