Factoring Breakthrough?

An anonymous reader sent in: "In this post to the Cryptography Mailing List, someone who knows more about math than I do claimed "effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were." Apparently Dan Bernstein of qmail fame figured out how to factor integers faster on the same cost hardware. Should we be revoking our keys and creating larger ones? Is this "the biggest news in crypto in the last decade," as the original poster claims, or only ginger-scale big?"

Comments

not surprising...

[lyapunov]

Cryptography is going to be a perpetual game of "measure, counter-measure" as computing power increases and people develop more clever ways of doing things.

Does anybody have good sources about this? Ones based on historical encryption and decryption that lead into modern times would be ideal.

Were they even secure yesterday?

[Carmody]

The NSA factors numbers, and their work is top-secret. When I read stories like this, I wonder if people are just discovering things that the NSA has known about for years. If the NSA could factor 2 Kbit keys, would they tell people? Probably not.

So when you ask "Are our keys secure" the logical follow-up question is, "From who?"

From me? Yes. I probably couldn't factor a 1000 digit number.

From your boss? Yes. You could use rot-13 and your boss would probably be baffeled.

From your boss' lawyers? From the police? Here is where we get into the gray area; where the article becomes relevant

From the government? I think you were kidding yourself when you thought it was secure in the first place. I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race.

Re:Were they even secure yesterday?

[gweihir]

Wait, I don't understand that. Is this good or bad?

It supposedly improved DES. But it also implies that the NSA might have knowen about differential cryptoanalysis 20 years before public research discoverd it. The implication is that they might know a lot of other things that are not yet knowen in the public crypto research community. On the other hand, they might only have had a hunch, or there might have been other weaknesses in the old design (they changed the s-boxes, as far as I remember), that they could find and the effect on differential cryptoanalysis is accidental.

But there is also another limiting factor: If they can break, e.g. AES or RSA far easier than the public suspects, they don't want the public to know! After all when it is knowen a cipher is insecure, people will stop using it or improce its security. This is analog to not exposing a highly placed intelligence source.

If you plan a major terrorist attack and use email for the related communication, you might have to worry. Otherwise, as long as you use cipthers that are belived to be secure for the near future by current published research, you should not need to worry.

Re:Were they even secure yesterday?

[rho]

What worries me is the possibility that corporations could have effectively the same amount of power, with none of the public scrutiny, accountability, or mission to "protect" (at least in theory) those they watch.

What public scrutiny? Do you know what the NSA is doing? Do you thing your drunk, philandering senator knows? Or even cares?

This is a dangerous attitude--whereas a corporation could learn all about you, the worst they'll do with the information is use it to sell you more bric-a-brac, and if you discover that they're invading your privacy, you can at least sue them.

If the government is gathering this data, it can use it to take, with force, everything you own because you smoked a joint in 1963. Plus, if you find out the government is invading your privacy, you can only... well... you can only grease up your sphincter to help with the penetration. And, depending on how you find out what the government is doing, they can shoot you.

Corporations do bad things, but the worst things are done by governments, not corporations. Even the worst things done by corporations are done by the government at the corporations' behest (vis. DMCA).

Re:AES?

[Hizonner]

The Rijndael/AES cryptosystem does not depend on the difficulty of factoring. This is a big deal mostly for RSA.

Just wait...

[JohnBE]

Shouldn't we all hang on until crypto experts validate this? Is it theoretical? How much does the attack cost? etc. etc.

I wouldn't start sending those revocation certificates just yet.

Re:No wonder NSA was okay with 128 bit encryption.

[fremen]

Using 128 bits is fine for symmetric key algorithms like IDEAS and Blowfish. It's not ok for public/private key algorithms like RSA. You're comparing Apples to Oranges.

Re:it's a cool method

[Ed Avis]

Only a threefold increase in speed? That would make hardly any difference, you'd get a threefold speed increase just by waiting a few years for Moore's law to deliver.

My understanding is that keys of three times the length can be cracked in about the same time - which is an _exponential_ increase in speed.

Re:NSA, et. al.

[Tackhead]

> I find it funny and interesting that because the NSA and other TLA agengies are *so* tight lipped we assume their skills and abilities are far ahead of current "joe-sixpack" tech.

For the past 50 years, that's been the case.

> I suppose this very well could be the case, but it sure lends itself to great conspiracy theories.

For the past 50 years, that's also been the case ;-)

Most of us older /.ers grew up believing that the mods to the S-boxes in DES were probably backdoors. Turns out they were to secure the algorithm against differential cryptanalysis, which didn't get discovered outside of NSA until recently.

NSA is still reputed to be the largest employer of mathematicians on the planet. They're reputed to have more supercomputing power than any organization on the planet. Both allegations are reasonably well-substantiated.

> I suppose the TLA agencies don't really need strong crypto to invade on my privacy. They just need a court order.

Correct. NSA's got two missions - secure American computing and communications, and 0wn every one else's ;-)

Not only is it easier to get a court order to make you give up your keys (or to eavesdrop/keylog you while you enter them), it's a hell of a lot safer.

The funniest part of Cryptonomicon is where the Brits are busy sending bombers to "see" German shipping but not bomb it. (If they just bombed the Germans, the Germans would realize that their crypto had been broken.) One of the protagonist's jobs, as an information theorist, was to figure out just how often they could get away with "just bombing them" and how often they had to make it look like they "got lucky" with a chance overflight or other observation.

The hardest part of crypto isn't breaking your opponent's codes, nor is it securing your own secrets. It's securing the big secret, namely not acting in a way that proves you've broken your opponent's codes.

Knowing your enemy's "A" team plans to attack tomorrow at dawn is good, but if you take out the "A" team 5 minutes before dawn, you run the risk of losing your ability to monitor the "B" team.

Re:it's a cool method

[gweihir]

In terms of big-Oh, it went from O(x^N) to O(x^(N/3)).

Exactly. That means we have to make N three times as large as we thought we had to. This is not a catastrophe, except in high-security applications. But these should use something like "make absolute sure its enough bits and then quadruple the number" anyway...