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.
they did develop a neural net a few years back that cracked 32 bit RSA in 3 days (more bits made it exponentially slower) so honestly how much better is 1024 bit given some of the hardware available today? A year on a 10 million dollar device is a month on a 100 million dollar device and are we to believe that our government or others (Russia) dont have better devices than that?
Spend enough money and just about anything can be solved.
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
Unless of course he's talking about reducing the cost, rather than reducing the difficulty. And from the wording, it sounds more like the cost is being reduced by 3-4 orders of magnitude. So from $10mil to $10k-$1k is a pretty good step. Would mean that for the same price they could crack 1000-10000 more keys per unit time.
Daniel
Carpe Diem
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.
Why not just send and store a lot of decoy payloads encrypted with decoy keys of the same strength as the legit key? It takes a year and $10M to decrypt a 1024 key? Fine. For every valid key I use, I'll pass around 5-10 random messages with throwaway keys.
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
There's a reason why cryptographers talk about 10 and 20 year security. If you have information that is worth $1 million and will still be worth $1 million 10 years ago, it may be in danger. Lets say the adversary waits 5 years and builds one of these machines for only $2 million. Now he can crack one key per year for at least 5 years and more than recover his investment.
-a
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!