Slashdot Mirror
1024-bit RSA keys In Danger Of Compromise?
antiher0 writes "According to an email from Lucky Green that came across bugtraq yesterday, 1024-bit encryption should no longer be considered pristine. Bernstein released a proposal that outlines the creation of a machine capable of breaking 1024-bit crypto on the order of minutes or even seconds for the measly cost of ~$1B USD. For a more thorough discussion, check out the original email."
Update: 03/26 03:16 GMT by T : And don't forget to revisit Bruce Schneier's analysis of Bernstein's claims, which cast doubt on the practicality of breaking such large keys anytime soon.
Here?
The basis for this story was on slashdot almost a month ago. A repeat? something derived from the previous story's information? the key point here is Bernstein's paper on factoring huge numbers, about which some people have commented, and which appears to "work out" on a mathematical level.
Here's the link to their write up, commenting on Bruce Schneier's take No Big Deal .
Anyway, we all know they've been reading our sekrit kees by telepathy for years now, right?
Hexayurt - open source refugee shelter,
RC5 is not a public-key algorithm and has nothing to do with factoring, so this is irrelevent. Factoring is of importance only to RSA and similar algorithms.
It's hard to be religious when certain people are never incinerated by bolts of lightning.
It *is* a measly sum - as the email says - how many government agencies have this sort of funding? More than just a couple of US agencies that's for sure.
Assuming the email is correct (and having read it, it does't seem to be that incredible) That $1B investment gets you the infrastructure, systems and processes to routinely break 1024 bit keys (and therefore the contents of the encrypted payload) in a fairly short order.
Since many people believe that a 1024-bit key is essentially uncrackable today, tomorrow and next century, 1024-bit keys are still going to be popular.
If an organisation can amortise the cost over 3-4 years (which is the likely life of short (1024 or smaller) keys). That gives you quite a return on investment.
If that $1B allows you to break one key every 5 minutes, over a 4 year period, you can break ~420,000 keys - which works out to a cost of less than $2500 per key. If you can intelligently target who's keys you wish to compromise, the benefits could be significant.
Fast, cheap & reliable. Pick two.
The US government recently relaxed export regulation for public key cryptography to make it the same as the domestic restrictions. The reasonable implication that we can take from this is that they have a way to crack that length of key, or they know they can do it, if they really have to.
Either that, or the American government suddenly have benevolent feelings to the rest of mankind and a minority of their software community. Yeah right.
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"That intro is deceptive at best and is, well incorrect. Remember DES and other symmetric ciphers that currently use about 128-bit or so encryption are unaffected by this. Certainly, 1024-bit symmetric encryption (your typical secret password encryption) is going to be unbreakable for centuries based on current predictions. The intro should read asymmetric or public key encryption at 1024-bits
Secondly, the advances being talked about are in factoring large numbers into their prime factors using the Number Field Sieve (NFS). This algorithm is the most advanced known factoring algorithm and if you believe the article improvements show that factoring 1024-bit length primes is doable for 1 billion dollars or so. (It was only a few years ago this kind of cost was attached to building a DES cracking machine... today I could probably crack DES on my uni computers given the software. 1024-bit factoring is only a matter of time before it is easy). However, not all public key schemes rely on the difficulty of prime factoring. Elliptic curves rely on a different hard problem
Conclusion, the intro should read "1024-bit asymmetric encryption that relies on the difficulty of prime factoring (e.g RSA) should no longer be considered pristine"
That's kindof the idea behind Triple-DES. Description here. DES was deemed too easy to break, so Triple-DES was born and is still used in some applications today. Used properly, it turns the effective 56-bit key length of DES into 168 bits in Triple-DES.
Ah... the old security through obscurity notion. Someone else can carry the debate here but trying to get security by trying to hide what layers of algorithms you are using is defeating the point of security research. A "secure algorithm" is basically one such that it does not matter whether the hacker has access to the algorithm or not. Cracking a "secure algorithm" should be as hard as cracking by brute force. If your security relies on obscurity, then you are asking for trouble in general
As for layering in general. Well it works for the most part (e.g 3DES) although there are caveats (2DES would not be safe). But the real point is that layering is slow. Doing 1024-bit RSA encryption is slow. And try generating a 2048-bit key instead of a 1024-bit key. It takes ages (possibly minutes on some computers). You may be increasing security but decreasing performance.
Now going back to the first point about a "secure algorithm", you are better of say doubling your key size and exponentially increasing the keyspace on your existing algorithm then either inventing your own layering scheme that may or may not work AND will be slow nad memory wasteful by using many algorithms. The short answer is, you don't need layering, just make larger keys.
Actually that's a very good point. At some point it does become more economical to buy off a person on the 'inside' of what ever organization you want to get secrets from... Hell I'd sell my personal secrets for a $1.50. Of course I don't have anything worth mentioning except my infatuation with girls with southern accents... oops well there's a freebie.
Business News and Resources: www.usasource.net
Actually Bernstein says that he does not expect his factoring device to have any significant speed advantage over other factoring techniques for "short" keys, "short" being significantly more than 1024 bits.
The reason is that the speed up is asymptotic with a suspected slow convergence.
But I agree that for security critical application 1024 bits is too short, even if only because there is not enough safety margin.
Find the paper by D.J. Bernstein here.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted and ignored otherwise.
he sais that the article referenced by slashdot has caused him to re-examine the CUMULATIVE effects of a number different recent development, not just the Bernstein paper
Hmm. Dicrete log (the one-way part of Diffie-Hellman, probably quite a few others too) is usually considered about as difficult a problem as factorization. Anyone know how easy it would be to change the machine to crack that too?
Each bit that you add roughly doubles the amount of time it takes to crack. 2048-bit encryption, although slow, is possible.
What this means is that, assuming that a 1024-bit key can be factored in 1 second, it would take roughly
57004475357125694689539104223396268823502567825
5466151385601004275993538836
5721983584043465919703756942
8489528438551201241199355703
7710357939232321268887397337
years to crack 2048 bit encryption. I'm not all that worried.
"But really, I think life is just a game of Mao Nomic." -Purplebob
However, in a follow-up post to the cypherpunks mailing list, Ian said that he did not agree with the calculations.
In fact he says that the physical properties of the factoring machine seem "implausible", and that there is no reason to believe that the result applies to "real" key lengths like 1024 bit keys.
It is generally regarded that the NSA and the military have technology that is about 20 years, yes 20, ahead of what is publicly known.
The NSA has the budget to hire the best and brightest mathematicians money can buy. Whose to say that the NSA hasn't know about this for years? Sure, Bernstein could have simply "rediscovered" what the NSA has known for years.
There have long been rumrors of a $2-3B machine that the NSA has for breaking encryption. Taking time into account, that translates to that $1B machine now.
The NSA has likely been able to break these keys for years.
I'm afraid that this story is altogether misleading.
:-)
When the paper first came to prominence, yes, it looked worrying.
However... the speedup factor appears only to apply to LARGE numbers, not necessarily to smaller ones. Exactly how much advantage one gets for smaller ones is unclear.
Note that this paper is a "research proposal", not a finished item of research. It's a very interesting read, nevertheless
However, if you're worried then you should be using 2048-bit original-style RSA PGP keys anyway (or 3072 or even 4096 bit new-style RSA keys). You might want to avoid the DH/DSS keys since the signature part cannot exceed 1024 bit....
It'll really be interesting when they start to get to ~64-bits of resolution (at least if they don't run into Heisenberg uncertainty problems when the resolution approaches Planck's constant.) Will the resolution of this technology scale that far? But things don't get interesting for public-key crypto until you're at ~512 bits.
Also, there are some problems that quantum computers can accelerate and some that it can't. For instance, factoring is tractable, if you've got enough resolution, and there's a quantum computer that was able to factor the number 15 into 5 and 3. So RSA and Diffie-Hellman are toast, at least for 4-bit keys :-) Perhaps for much longer keys, if QC can be developed, but perhaps not. It's not clear whether elliptic curves can be cracked by quantum computers, but then, it's not clear that they can't be cracked by better mathematics.
Basically, if They can crack everything using public-key technology, you're back to private-key methodology like Kerberos, or traditional methods like one-time pads and guys with Kevlar briefcases handcuffed to their wrists.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Diffie-Hellman and El-Gamal are closely enough related to RSA that you don't get much diversity by picking them. Elliptic Curve is a nice possibility, though it's possible somebody will find the math to crack that. NTRU is a lot different - I don't know that any of the academic cryptographers are calling it really secure yet, but the people who've looked at it don't seem to be calling it "snake oil" either.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
The NFS factoring algorithm is subexponential - adding a bit doesn't even nearly double the strength.
"Mary had a crypto key, she kept it in escrow, and everything that Mary said, the Feds were sure to know."