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
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.
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.
99% of encryption can be broken given enough time. You really only have to worry about the information in question being encrypted as long as it is considered sensitive.
For instance, I tell my friend "Mee my at the bar tomorrow at 9 pm". I only have to make sure that the message is secure until tomorrow at 9 pm. If it takes longer to break the message, the content of the message is no longer valid.
It's a waste of time to try to make the message more secure.
Je ne parle pas francais.
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).
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/
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
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
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.