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
SWORDFISH
Don't go telling anyone.
"Not knowing when the dawn will come, I open every door." - Emily Dickinson
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.
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
Can it factor large primes in mere seconds? I've designed a processor that can! I'm just looking for investors now...
Spend enough money and just about anything can be solved.
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
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.
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
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 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.
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
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/
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
size matters.
I bet NSA have had this for years.
You have the driest sense of humor I've ever seen. My hat is off to you.
[Set Cain on fire and steal his lute.]
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
They use a symmetric cipher to encrypt your private key on disk. Depending on which cipher is used, likey IDEA, AES or 3DES. You're looking at a 112, 128, 168, 192, or 256bit symmetric block cipher and the effort it takes to break that. RFC 2440 states that a hash is applied to your pass phrase to expand it or reduce it to the proper key space (your 70character phrase doesn't buy you any more than a 32character phrase,) MD5 or SHA is probably used and then a cipher which isn't specified. However MD5 and IDEA are chosen for backwards compatibility, implicitely.
So how long does it take to decrypt an IDEA encrypted message? 64bit blocks, 128bit key space. A lot less time than it does to factor a 4096bit Blum integer.
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
As pointed out in David Deutsche's The Fabric of Reality , no encryption based on large primes is ever indefinitely secure.
... and currently decoherence is the largest obstacle to overcome.
...
While the factorization of large prime numbers is currently an intractable task, quantum computing is very likely to make it as tractable as multiplication.
For instance, Shor's Algorithm, first discovered in 1994, has already been implemented to factor the number 15 -- to 3 and 5 with 80% accuracy. (If anyone knows what it got the other 20% of the time, I'm interested!)
Now certainly 15 isn't comparable to a 1024-bit RSA key, but it's only a start for quantum computers. Using entanglement and interference, one can have very large primes factored in a matter of minutes! All we have left to do is actually build a device that does it
So, if you really want information to be secure, and remain secure indefinitely, a better method of encryption which does not rely on the factorization of large primes needs to be implemented.
Peter Shor even wrote a poem about it. =P
-------
If you don't take responsibility
for what goes into your mind
Someone Else Will!
-=[You cannot consistently judge this statement to be true.]=-
Schneier, page 234:
... it's vulnerable to an elaborate dictionary attack?
"The rate of normal English takes various values between 1.0 bits per letter and 1.5 bits per letter... [Shannon] indicated a rate of 2.3 bits/letter for 8-bit chunks, but the rate drops to between 1.3 and 1.5 for 16-letter chunks. Thomas Cover used a gambling estimating technique and found an entropy of 1.3 bits/character."
I like to use 1.5 for my ballpark figures, since it makes the math easier; but assuming the most conservative value of 1.3, that still means a 70-character passphrase in plain English has 91 bits of entropy.
That's a freaking lot, incidentally.
How long did it take the RC5-64 challenge to succeed? Multiply that by 128 million. That's how long it would take them, on average, to break a 91-bit passphrase.
Would you care to revise your statement about not very long, since your passphrase is probably just a text sentence type string, and language has extremely low entropy
Imagine a beowulf cluster of these . Hmmmm you could crack God's answering machine remote . Think of the messages "Hello God this is Satan you think i could be someone else besides Bill Gates for awhile . I hate being so damn nerdy. Oh an i was thinking we could give the DOJ the plague or maybe just the antitrust section . Gotta get back to my new version of windows for life support machines ....muhahahaha "
There are a few other technical errors in the paper, at first glance. The large stations seem to call for 2000 banks of tiny DRAMs. Unfortunately, DRAM on an ASIC is not available at such a fine granularity. He would have to use SRAMs to implement this memory, and lose quite a bit on area. One could argue for a custom DRAM implementation, but DRAMs are black magic in the process industry and you really don't want to get into that business if you can avoid it, especially at half a million bucks per spin of the chip!
otoh, the architecture looks pretty systolic and repeated, so yield can be made near-perfect if some kind of fault-detecting bank-switching scheme is designed into the chip.
These ancillary costs start to grow in comparison to the 10 million dollar figure to crack RSA-1024, and it is enormous in comparison to the numbers quoted for cracking RSA-512 and RSA-768. In particular, the observation about how the cost of the machine would be smaller than the prize money awarded for breaking RSA-768 should include the non-recurring costs, since presumably the only reason for someone to build such a cracking machine would either be to break a challenge such as this (public awareness), or to perform real espionage (you're funded elsewhere). In the case of real espionage, you probably wouldn't publicize the power of your machine by claiming the RSA-768 prize, anyways, so the cost of the machine relative to the prize amount is not as relevant :-)
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/
RSA is a pain to decypher because the assumed 1:1 for public and private keys. That isn't true. Its 1:N where N is a very larage number and may be N:M.
this code shows a simple 10 bit RSA in perl (its too slow to do much more) and it will generage one public key and several private keys. Doing it for 1024 bit is left as an exercise for the reader.
RSA's 1:1 is based on a short cut of a nasty operation via the Euclidian algorithm and it turns out the math works quite well if you do things the hard way but it takes a long time even on a modern computer.