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.
A $10,000,000 machine dedicated to breaking into a single encrypted communication for a full year will be able to break it! This makes encryption completely worthless!
-- 'The' Lord and Master Bitman On High, Master Of All
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?
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.
You didn't read the primer we linked to :)
An increase in 3 bits in symmetric keys corresponds to an increase of about 160 bits at this size of asymmetric key. As I understand it (and this is probably an oversimplification), this is because while you can pick any symmetric key you want, your choice of asymmetric key is limited to prime numbers.
So a change of 4 orders of magnitude in cost-effectiveness would be about the same as shaving 13 bits off a symmetric key. But if the table credited to Lenstra and Verheul is correct, that would correspond to reducing a 1028-bit asymmetric key's effectiveness to 488 bits.
I think.
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
I wonder if this is complementary to the hardware-based approach discussed here?
me karma am bad
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/
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?
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 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.
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 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
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
The point of this paper is NOT that 1024-bit keys are "unsafe" for some definition of "unsafe".
This is a brilliant refinement on a brilliant idea. A few years back, Shamir published "TWINKLE", a factoring technology that used optoelectronics to great effect-- rather than using a (slow) software loop to test the smoothness of certain numbers, TWINKLE used LEDs of varying brightness to represent factors of a given number-- the brighter the combined output of the LCDs, the smoother the number.
This is a VERY intelligent refinement on the idea; the original TWINKLE had to use GaAs wafers and (partially due to the optical part of the design) was going to be VERY difficult to manufacture. This new device uses only electronic components, but it essentially parallelizes the original TWINKLE idea.
The implications are enormous. First of all, 512-bit keys are officially dead-- $10000 and 10 minutes may be a bit optimistic, but it's surely no more than half an hour with this device. And, yes, there ARE people and organizations still using 512-bit keys (stupid people and organizations, yes, but they exist).
Second of all, this approach scales incredibly well. A 1024-bit number is $10 million and one year. But because of its reliance on cheap silicon parts, you can bet that the price and speed will get better in accordance with Moore's law.
As well, because the time/cost relationship is essentially linear, it becomes easier to model threats (read Schneier's "Attack Landscapes" paper, this will give you an idea of what I'm saying).
Plus, the paper is just plain cool. Shamir is a bright guy (he's not just the 'S' in RSA, you know-- he co-invented differential cryptanalysis with Eli Biham, and he has done some amazing work with hash functions and block cipher cryptanalysis, not to mention TWINKLE and TWIRL), and when he publishes a paper, people pay attention.
The version currently circulating is indeed a draft. The final version, when available, will be placed at my homepage, and specifically here.
-- Eran Tromer
Prime numbers can only account for so much -- their distribution is asymptotic to n/(ln n) by the PNT. So at this size only 1 out of ln 2^1024 = 710 numbers is prime on average. That would account for ~9.5 bits shaved on RSA around this range for each symmetric key bit shaved.
Actually most of this can be credited to much faster algorithms for number-theoretic problems (like the subexponential NFS for factoring, being discussed on this article) whereas usually the best known method for cracking a symmetric-key algorithm is brute force, which is of course exponential.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/