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.
I wonder if this is complementary to the hardware-based approach discussed here?
me karma am bad
they get... the ability to pretend to be you, online.
Well, those people who were too stupid not to create a revocation certificate, at least.
By the time "they" get your credit card number by breaking the bytes of an SSL connection that you used to pay online with one year ago, one of these will probably have happened:
- Robbers broke into your house when you weren't home and stole your home entertainment system (you say you have insurance on your household items; well, your bank also insures your credit card against fraud).
- or, your car may have been stolen (oh no! while I was worrying about 1024-bit keys being unsecure my car was stolen!)
- or, Somebody kidnapped you and held a gun to your head until you gave them your PIN #. (A gun is much cheaper than a 10M computer).
- or, you lost your credit card and somebody bought something on it, or somebody got your number from a carbon copy slip in the garbage can
- or, you went bankrupt so "they" can have as much access to that account as "they" want
- etc. etc.
I honestly don't think that the common person has much to worry about if 1024 encryption is hard to crack right now. If so, then just use a lengthier key, like 2048. Problem salve
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 NFS sieve step is only half the problem, you still have to invert a huge matrix and that requires a closely coupled machine.
The TWIRL paper describes all that. They propose using a mesh-routing algorithm for doing the matrix job, as described in the paper "Analysis of Bernstein's factorization circuit" by Lenstra, Shamir, Tomlinson and Tromer, which they estimate can be built to solve a matrix for a 1024 bit GNFS factorization for only $5000. This is a somewhat optimistic estimate, basically they have to get a 30cm custom designed silicon waver produced which will cost a bunch more than $5000 for a one-off job, but the design is still perfectly feasible.
In the new paper they describe how the previous TWINKLE sieving hardware can be improved to be both faster and cheaper, reducing the estimated cost to do the sieving for a 1024 bit GNFS factorizaion in a year to only $10M. This is amazing.
Alex
Heisenberg may have been here
The reason cracking machines are built is that they don't leave trails. A key keeps increasing in value when its unsuspecting owner keeps using it after it has been cracked.
Trusted Computing FAQ | Free Dawit Isaak!