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.

what would you do if you had a million dollars?

[jrs 1]

if you were a government agency with $1b to invest in some kind of anti-terrorist encryption breaking scheme, would you invest it in this or would you invest it in quantum computing research?

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.

Nope

[Brigadoon]

1024 bit, of course, is 2^1024 (approx 1.797e308). If you add one more bit (2^1025), you double the possibility of the number of keys, which means you double the computation time... In theory. This assumes brute-forcing it, and that the time it takes equals the maximum theoretical time to break it.

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:previously reported

[bourne]

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!

There is something new here

[Anonymous Coward]

When it came up before, there was a significant question about whether the improvements would be seen in key sizes that we are using, or whether you needed larger numbers. The conclusion of Schneier etc was that it probably didn't affect factorization of numbers people are using, though it was good research.

What is new is that people have now gone out, implemented it, and found that it really does come up to a big factoring win in the ranges of numbers that are in use. Furthermore based on real factoring examples, 1024 bit keys are doable at costs within the reach of national security agencies.

There is a difference between theoretical improvements somewhere around a million bits, and demonstrated improvements at 512 and 1024.

Re:$1Billion

[Mr. Flibble]

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.

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:Break my crypto for $1B?

[suso]

This would be an interesting Slashdot poll. "How much do you consider your most sensitive data to be worth?"

$1
$100
$1000
$10000
$100000
$100000000
Mo re than Cowboy Neil has.

Real Issue with encryption

[lamj]

We are facing some big challenges right now. Due to the crazy growth of computing power (despite the fact that new methods of calculation - factoring large number and stuff are constant being developed) Encryption standard are being obsolete faster than we can adapt to it.

Think about how long the US government will take to adopt AES.... Same encryption are going to get weaker and weaker as times goes by, we have to adapt to the rate it fades out. But apparently, encryption standards takes time to develop and get accepted. We are very likely going to change standards every 5-10 years. Government agencies, are you coming along?

Re:Would obscurity be a solution?

[Anonymous Coward]

point is, you can still crack public-key ciphers one at the time which doesn't give you much more security. however, for secret-key stuff it's a completely different issue as you need to break all of them at once.

Re:Would this be a solution?

[mosch]

524,288Tb of resiliant storage is only $1b at current prices, and that's dropping rapidly. If historical trends continue, it'll be $1m in about a decade, and it will be included standard in the PlayStation 9.

better then encryption: invent a language

[nalfeshnee]

i thought of putting this in 'ask slashdot' to be honest, but here goes ... what kind of effort is required to invent a reasonably efficient language which of course only you and your confederates would be able to use. esperanto, es an example, required a mere *eight* years.

the advantage with this is that it requires practically no encryption, if any.

"jan? khlaz tuirt'kah dar gangan Mbou!"

any idea what it means? nope, me either. and if you want an example of how strong this kind of 'encryption' is, simply take a look at the puzzles linguistics has tried to crack over the years: Linear B, (Linear A is still a mystery), hieroglyphics, etc., etc. For an example of something which is *still in plaintext and not deciphered*, check out the Voynich Manuscript [crystalinks.com].

OK, I'm not saying that one can simply go off and invent a perfect language in a coupla weeks, but look at the pseudo-languages like Elvish, Klingon and whatnot. Ideas, criticisms, reactions??

Plus of course, if someone is holding a cattleprod to your crown jewels and you're standing in a bucket of water, it doesn't *really* matter whether u used gazillion-bit keys anyway...

nalfy