Slashdot Log In
1024-bit RSA keys In Danger Of Compromise?
Posted by
Hemos
on Mon Mar 25, 2002 08:05 PM
from the well-of-course-they-are dept.
from the well-of-course-they-are dept.
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.
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
$1Billion (Score:2, Funny)
Is the company you work for hirring? God I wish I could call a billion dollars measly!!
Re:$1Billion (Score:2, Insightful)
Break out those one-time key pads and pigeons, boys, the government will own your electronic crytposouls before you know it.
Re:$1Billion (Score:3, Informative)
The NFS factoring algorithm is subexponential - adding a bit doesn't even nearly double the strength.
Re:$1Billion (Score:5, Informative)
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.
Parent
Re:$1Billion (Score:3, Interesting)
Exactly.
For those of you who would like a breakdown of how a system like this would work, you may want to read Cracking DES by the Electronic Frontier Foundation [oreilly.com]. (Note, this book is out of print, but the EFF has made versions available online. [eff.org])
It discusses building a computer from scratch that can crack DES quite fast. This same principle can be applied to any brute-force technique. And if the cost is $1Billion now, it will be considerably less in a few years.
Re:Maybe I'm missing something... (Score:5, Insightful)
Second, if you'd read the e-mail on Security Focus, the estimated price range is several hundred million dollars to about 1 billion dollars, lower if they have access to a chip fab. It also mentions that the NSA and several other countries' intelligence agencies have their own fabs. So it's not as prohibitively expensive as it sounds. The e-mail's author goes as far as saying The NSA would have to be derelict of duty to not already have built such a decryption device.
Parent
I'm sure I've heard this somewhere before... (Score:3, Informative)
Re:I'm sure I've heard this somewhere before... (Score:3)
This is about professionals (Banking security) getting together and talking about the ramifications of DJB's idea.
It's not 100% new, but it's not 100% recycled either. Of note is the fact that $1B is not out of their league ($2B satellites are standard items), and that they would be irresponsible to NOT have done this already.
It's more data, take it or leave it as you will.
Re:I'm sure I've heard this somewhere before... (Score:2)
previously reported (Score:2, Informative)
Re:previously reported (Score:3, Interesting)
It seems to me that this story is hitting slashdot because, well, it hit slashdot.
The original was passed around a few small mailing lists, where it got some comment but nothing big. Then it hit slashdot a month ago, and the number of places I saw it popping up increased. I also saw a story about DJB cranking at some reporter for misunderstanding the exact nature of the information, which tells me that someone thought it was suddenly big enough to have a reporter look into.
And now, perhaps based on all this "publicity," Lucky Green or whoever is setting up discussion of it at some conference and revoking his old key. Note that he didn't do it a month ago, when the story was on all the crypto lists - presumably the more attention it got, the more real it became.
Maybe I'm off base here, but I think this is one of those examples of the media gestalt manipulating and being manipulated by the media consumers - the story had to get big before it could be taken seriously, and it had to be taken seriously before it could get big... and the slashdot story a month ago was probably one of the bigger steps along the way.
The slashdot effect... It isn't just for websites anymore!
It's funny, laugh. (IHNRTA) (Score:3, Funny)
I'm certain that qcrack will be poorly documented and require the addition of 5,000 users to whatever supercomputer it happens to operate properly on.
Then DJB will speak incessantly about how it differs from other encryption cracking techniques with its "modular design" (which is actually the application of many patches in order to obtain features found in most SMTP daemons, err cracking programs). Yeah.
(Disclaimer: I love qmail.)
Cheap. (Score:2)
It is way easier for you to move up a few orders of magnitude of encryption than for them to build a machine that can crack it.
However, this will mean a bigger supercomputer for all kinds of numbering tasks - basic research and math, physics, and astronomy will eventually benefit.
Break my crypto for $1B? (Score:5, Funny)
Re:Break my crypto for $1B? (Score:3, Interesting)
$1
$100
$1000
$10000
$100000
$100000000
M
Not so fast.. (Score:5, Insightful)
Parent
Been all over SecurityFocus Already. (Score:2, Informative)
Anyway, we all know they've been reading our sekrit kees by telepathy for years now, right?
Would this be a solution? (Score:5, Insightful)
Give that a brute force attack is orders of magnitude more computationally intensive than the original encryption, would this allow you to stay ahead of the curve?
Also, although the papers seem to indicate that the proposed system could try multiple forms of attacks on the encrypted data, would modifying or customizing the encryption algorithm at each layer of encryption help? Computers are great at brute force attacks, but I highly doubt a system such as this proposed one can do much in the way of analysis or reverse engineering of the encryption algorithms used...at some point, you'd have to resort to good old (and slow) human deduction...
Re:Would obscurity be a solution? (Score:5, Informative)
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.
Parent
Re:Would obscurity be a solution? (Score:5, Funny)
Parent
Re:Would this be a solution? (Score:3, Insightful)
If you modify the encryption algorithm then you're probably introducing new holes into it or at the very least you have to distribure those modifications to whomever you want to decrypt it. In essance a type of one time pad. Either you have to create a new encryption algorithm for each message or group of messages that you send or choose one and stick with it. If you constantly change algorithms or modify you have to have some secure way of getting those modifications to whomever wants to decrypt it, which can be difficult. You could simply create or modify an algorithm and not tell anyone what it is except for the recipient but to do that you'd have to know alot about cryptography and hopefully know the benefits of peer review. The people that encrpt DVDs know the benefits of peer review, now, after they released DVDs using CSS. If your modified algorithm is broken you'd probably never know because who would tell you? The guys that are trying to read your encrypted data or the ones that don't want to read your email and don't have access to your modified algorithm?
The safest thing to do is either use a very long key or learn cryptography develop your own algorithm, get it peer reveiwed and then most likely use a very long key.
Re:Would this be a solution? (Score:3, Interesting)
what would you do if you had a million dollars? (Score:2, Interesting)
would it be worth going for the brute force attack or would it be worth finding a different solution? not to mention how much money you could win and how much cancer you could cure with the idle time.
Re:what would you do if you had a million dollars? (Score:2)
When it comes to terrorism, encryption really isn't the main problem. Identifying, isolating and eliminating causes (be they philosophies -- such as a desire for complete theocratic control -- or individual people) is.
Pay attention. Security = risk management. (Score:5, Insightful)
Don't any of you bozos pay attention to prior articles? Security is about risk management. If you have something to protect that is worth $1bn for someone to steal and the only protection you have on it is 1024-bit crypto, you deserve to have it stolen.
Your homework for today is to (re)read Secrets and Lies. There will be a quiz.
The US government has something like this (Score:4, Informative)
Either that, or the American government suddenly have benevolent feelings to the rest of mankind and a minority of their software community. Yeah right.
Clearing up the deceptive intro (Score:5, Informative)
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"
Re:Clearing up the deceptive intro (Score:5, Funny)
Oops, Mr. Smarty Pants! I can factor 1024-bit primes for $0!
Parent
Re:But can you prove that they are prime? (Score:3, Funny)
Arbitrary costing = $1B (Score:5, Funny)
<TELEPHONE CORRESPONDANCE>
SHADY GOVERNMENT OPERATIVE: So how much will this 1024 decryption system cost?
PIMPLY TEEN HACKER: $1B US dollars to be deposited into my secure off-shore bank account and safe passage to the Maldives.
SHADY GOVERNMENT OPERATIVE: Excellent. The money is being transferred as we speak. Begin work.
</TELEPHONE CORRESPONDANCE>
<PIMPLY TEEN HACKER INTERNAL MONOLOGUE>
Sweet! I've just charged the US government 1 billion dollars for a beowulf cluster of dreamcasts running home-brew linux.
</PIMPLY TEEN HACKER INTERNAL MONOLOGUE>
<SHADY GOVERNMENT OPERATIVE INTERNAL MONOLOGUE>
Sweet! We will retrieve the 1 billion dollars once we crack the secure off-shore bank account's 1024 bit encryption system
</SHADY GOVERNMENT OPERATIVE INTERNAL MONOLOGUE>
:)
Read the Paper! (Score:5, Informative)
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. [cr.yp.to]
Maybe I'm not clear on this but... (Score:3, Insightful)
Haha fools!!! (Score:4, Funny)
2048 bit (Score:3, Informative)
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.
Re:2048 bit (Score:3, Insightful)
The problem has to be tackled at a more fundamental level - maybe by finding an inherent weakness in the algorithm, which can be used to decrypt the message without having to go through all possible key values.
For example, if a few (plain text, encrypted text) pairs are known, we can search for a pattern, apply the pattern in reverse to an encrypted message, and get back the original plain text message.
a slightly-less-Amerocentric thought... (Score:3, Insightful)
ObDisclaimer: this isn't some pinko commie "FUCK YOU AMERIKKKA!" post... it's just an observation that I haven't yet seen made by another poster in the thread. I see a lot of people talking about the NSA, and breaking into banks, etc etc... but middle-class white male citizens of post-industrial western economies aren't the only people who have good reasons to use crypto, you know?
Ian Goldberg isn't worried (Score:4, Informative)
However, in a follow-up post [inet-one.com] 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.
1024-bit RSA is in no danger. Not yet, anyway. (Score:5, Insightful)
Even Bernstein's original paper is clear to point out that while his mathematical results are correct, and that his proposal does allow RSA keys of size n bits to be factored in the time we currently think it takes to crack keys of size n/~3.009, he proved this to be true *only in the asymptotic case*!!
This means that for very, very large n Bernstein's results are known to hold. His paper is actually a grant proposal requesting funding so that he can spend the next few years finding out if it's possible to apply the same techniques to practical-sized keys. As I understand it, what Bernstein wants to study will still be purely theoretical. He wants to calculate what the savings factor is for smaller keys. The reduction factor for smaller keys may be as large as 3, or it may be smaller but still worthwhile, or it may be negligible.
Even after Bernstein has done his calculations for smaller keys (which will take years) the results will still be purely theoretical, and there will likely remain a great number of practical challenges in building the rather unique kind of hardware Bernstein is proposing. It's possible that even if the theory holds for smaller keys, building a real machine may still be impractical.
For more detailed discussion than you're likely to be able to digest, go read sci.crypt.
From what I've read, I would say that if you have secrets you need to keep for more than 5 years, you might consider using a 2048-bit RSA key, or switching from RSA to ECC.
Misleading article (Score:4, Informative)
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....
Re:a billion here, a billion there (Score:2)
Nope (Score:2, Interesting)
2^2048 is 2^1024 times more than 2^1024 (that is, it's 2^1024 squared). Meaning that to crack 2^2048 - in theory - it would take roughly 1.797e308 times as long to crack.
More numbers: If this $1B computer could crack a 1024-bit key in one second (consistently), it would take 5.7e300 years to crack a 2048-bit. That's much longer than the life of the universe.
All this stuff is theoretical, of course. That's why you don't try to break the encryption, but rather look for holes in the software, or post-it notes on the monitor
-Xyphoid
Re:Nope (Score:2)
Re:Nope (Score:4, Insightful)
Bzzt! Wrong
That would be the case if the fastest attack was brute force, in fact there are much better attacks. 1024 bit RSA is generally considered to be equivalent in strength to an 80 bit symmetric cipher. 2048 bit RSA is only equivalent to about 132 bits.
Even so, the issue has been known for some time and that is why the crypto world is in the middle of a transition to 2048 bit keys. Only it will take arround 5 years to complete the move. VeriSign has been distributing 2048 bit root keys for some time.
Parent
Re:a billion here, a billion there (Score:2)
Wow! So if I only need to crack 128-bit keys I only need to spend something like $1.93831e-258! I can't wait to get started.
Re:But what's a measily $1B for a government agenc (Score:2, Funny)
Re:RC5-64 challenge (Score:2, Informative)
Re:so.... (Score:2)
Also, I think that putting a price tag on breaking 1024 bit encryption definitely qualifies as news for nerds. Who else would want to know?
Re:Measly? (Score:2)
For instance, if a major government or other well-funded entity not averse to a little corporate espionage managed to intercept and decode information regarding, say, bids on major contracts, it could pay for itself very rapidly.
Quantum Computers aren't real yet (Score:3, Informative)
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.
Re:Then use another Public-Key Algo! (Score:3, Informative)