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.
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.
Who has data that needs to be so secure that their competitors spending 10 million dollars and a year of their time to do it is a problem? My only thoughts were of governemnt/military/big corps, but couldn't all of them use longer keys?
Even if you read "3-4" to mean 5 orders of magnitude, that means that the factoring cost is reduced by a factor of 100,000.
In other words, a 1024-bit key will only be as safe, after this cost-reduction, as a 1007-bit key is today for the same amount of money.
I'm not worried.
As always, the tinfoil hat crowd will point out that a machine with such capabilities may already have been constructed and be in use. The NSA, perhaps. And they might be right.
Let's say the NSA has one. Let's say it's actually really good and 100x faster than the system proposed by Shamir and Tromer. That means it can plough through 100 1024-bit RSA keys per year. There are about 280 million people in the US (give or take). Let's say 0.3% of them encrypt using 1024-bit RSA (or below). That gives us about a million people. Let's say each one of those only has a single piece of important data. That's a million pieces of data, and you can crack a hundred of them. Be afraid?
It might be useful if you can (big if) decide exactly what data to go after, and it happens to be RSA = 1024 bit (or anything else equally amenable to being factored using NFS). But if it's 2048-bit RSA, this thing won't have a shot -- it's not fancy knew math that "breaks" RSA, it's a faster implementation of an existing technique. And it's probably not the cue for Joe Public to get paranoid.
I'm so scared, they only need $10M of hardware running for a year to be able to steal the $3,000 I have stashed at the back....
Seriously, everybody knows that any key length can be broken given enough time/hardware power. Then the keys will get larger, the hardware will get faster, rinse, repeat....
If someone can make a device as fast as they claim, then those people that have information/assets/whatever worth more than a $10M machine, should begin using larger keys. As simple as that. No big deal really
Unless you use a key only once, (possible, but definitly an odd way to do it), then for their $10M and a year, they get _all_ of your encrypted communications, and the ability to pretend to be you, online.
They say disceting a joke is like disecting a frog: No one really enjoys it, and at the end you have a dead frog.
Sorry for killing your frog.
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.
Nope - the Xbox key is 2048 bits, would take 2^1024 times longer to crack than a 1024 bir key. Besides, who would build a $10M machine to win a $200K proze?
It's hard to be religious when certain people are never incinerated by bolts of lightning.
Imagine an evil (good?) corporation that decided to crack the encryption for a message sent with the Coca Cola recipe, and that it was only a 1024.
"There is no teacher but the enemy."-Mazer Rackham
Yes. With enough computing power, any key size is unsafe.
The real question is; are they safe enough?
A lot of you are missing the point. $10 million isn't that much. They could build 100 such machines for a billion dollars, not an unreasonable sum for the NSA, especially if it is spread out over a few years.
Furthermore, technology continues to improve. Moore's law will speed up the chips, and this design is probably not the last word. There could be significant improvements ahead.
good point, but still, $10 million dollars to pretend to be me? thinking economies-of-scale here, on that $10M machine, and assuming (perhaps wrongly) similarities between me and other users...
I estimate the owner of that machine will need to be able to pretend to be about 10,000 people like me to make that investment worthwhile.
One has to wonder at whom a $10M encryption-breaking machine would be targeted...almost assuredly not to any old user, probably to someone with something worth having (stealing, duplicating, masquerading, etc.) And it's *these* folks, I think, that should be concerned most about their choice of technology and cypher.
doesn't hurt to recheck your own priorities, but speaking for myself i can assure you that my identity is worth much less than the cost of this machine.
Yeah, just got to that bit, I am suprised that that paper had not received more comment since that is the step that has been limitting.
I still think that Adi significantly underestimates the costs. The thing that made deep crack practical was that it completed the run in a pretty short length of time (days). So the system did not require a lot of extra engineering to cope with unreliable processors etc.
I don't think we are going to see this built for at least five years or so. Of course others might build it and not let on. And even then Deep crack was built to prove a political point, not just for the cryptographic fun of it.
Even so, there is no particular reason to insist on continuing to use 1024 bit keys at this stage. The 2048 bit roots have been distributed for some time. Most computer systems are now sufficiently fast that the longer keys can be used without unacceptable delays.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
If this guy's math is correct, that moving from 1024 bit keys to 2048 bit keys increases the computational cost of breaking the key by a factor of 2^1024, then this guy must also believe--in some dark corner of his brain--that the first 1024 bits of key also requires 2^1024 operations to crack. I think this fellow needs to sit in a corner and count his way up to 2^1024 before he posts again.
/. lamers we read the initial three words of whichever link we clicked first and immediately jump to one of serveral interpretations:
/. posters in category (4) would get jobs as microwave oven repair persons. Then everyone would become a lot more cautious about their dialectic coefficients.
Unlike the symmetric ciphers, the public key cipher does not have a pure exponential structure. If it did, we'd be using 128 bit keys and that would be more than adequate.
Let's just pull a sample key strength function out of some dark place. Let S represent the effective public key bit strength.
S = 1/4 * log2(N) * sqrt(N)
N=256 S=32
N=512 S=50
N=1024 S=80
N=2048 S=124
The new discovery modifies this relationship, but since we are all
1) S = 1/4 * log2(N) * sqrt(N) - 10
// constant factor improved
2) S = log2(pi) + e/4 * log2(N) * cuberoot(N)
// root improved
3) S = 1/4 * sqrt(N)
// log2(N) term eliminated
To confuse matters, it happens that (1) and (3) amount to pretty much the same thing: a rough factor of 1000 in the computational cost of cracking a key.
orig (1) (2) (3) (4)
N=256 32 22 36 24 -698
N=512 50 40 51 41 -442
N=1024 80 70 70 70 70
N=2048 124 114 97 113 1094
N=4096 192 182 132 180 3142
N=8192 294 284 180 281 7238
I didn't mention column (4). That would be the hypothesis of the post I'm responding to, where S is linear in N with an origin in the vicinity of 2^70 (a high speed computer running for one year) for N=1024.
In a perfect world all the