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.

Would this be a solution?

[SClitheroe]

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...

Pay attention. Security = risk management.

[mib]

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.

Re:$1Billion

[Mittermeyer]

When carrier battle groups, air wings, army divisions and the fate of nations are on the line, $1 billion for total SIGINT access is cheap indeed.

Break out those one-time key pads and pigeons, boys, the government will own your electronic crytposouls before you know it.

Re:Nope

[Zeinfeld]

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.

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.

Re:Would this be a solution?

[frinsore]

Using multiple encryption on one message may not increase the difficulty and may even lower it. Encryption algorithms are mathmatical formula so this example will suffice even though it may be simplistic. Say you have two encryption algorithms F(x)=8x and G(x)=x*x*x. You may think that by combining the two would make it more difficult to find x but F(G(x))=(2x)*(2x)*(2x) or 2x cubed which is as difficult as G(x) by itself. But say instead of G(x) you used H(x)=x/8 which would simply decrypt x to it's original value. In short to be able to combine encryption algorithms you have to know what they do and even then there is no garuntee that you're not introducing new holes.

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.

Maybe I'm not clear on this but...

[ZiZ]

Doesn't this fall under circumventing encryption, therefore making it illegal to think about under the DMCA? Or is it ok when it's expensive to break things, but not when it's cheap?

Not so fast..

[Sloppy]

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.

Re:Maybe I'm missing something...

[nathanm]

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.

a slightly-less-Amerocentric thought...

[Simon Garlick]

How many tyrants and dictators around the world would think NOTHING of squeezing their own countries $1B harder in order to crack the communications of dissidents, opposing political parties, and oppressed ethnic minorities?

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?

Re:2048 bit

[prakashj79]

A brute force decryption attempt would take roughly twice as much time for every extra bit in the key. No naive decryption scheme will work even if the key size is as low as 128 bits.

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.

Re:Would this be a solution?

[0x0d0a]

I doubt that using multiple encryption on one message would lower the strength. I'm not a cryptographer, but if that were the case, the very first thing any attacker would do is encrypt the message again with the same encryption scheme and a random key, which is a relatively cheap operation.

1024-bit RSA is in no danger. Not yet, anyway.

[swillden]

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.

Re:The US government has something like this

[aziraphale]

The non-conspiracy argument that I've heard makes a lot of sense to me, at least. US government believes that E-Commerce is going to be big. US Government notes that US retailers can export lots of goods to other countries if e-commerce is enabled. US Government notes, exports==good. US Government realises, people outside the US need to be able to communicate securely with companies inside the states in order to perform such transactions. US Government allows export of strong crypto, giving US a world lead in e-commerce market.

Money is almost always a better explanation for the actions of Americans than malice.