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.
Don't waste your money. I'll sell my company's secrets for a fraction of that.
If you can come up with a brute force approach to common encryption schemes, could you not stay one step ahead of something like this by utilizing multiple layers of encryption, with differing methods of encryption at each level?
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...
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.
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.
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"
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.
I can picture the scenario now:
<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>
:)
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.
The person who builds this machine may still underbid you. The machine doesn't just crack your secrets -- it's reusable. When you amortize the gigabuck over all the different people who need to be spied on, it may yet work out to be less than your minimum bribe.
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
First, it's not that the gov't is cracking encryption of bank systems so they can steal money. The cost of cracking encrypted messages from terrorists, countries they don't like, etc. using this technology would be less than the cost of other intel methods, i.e. getting someone on the inside, not to mention the intangible cost of a human life if an agent were compromised.
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.
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
~shiny
WILL HACK FOR $$$