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.

Re:not surprising...

[monkeydo]

Lotus Notes, Microsoft Exchange

Most large companies use one or the other for messaging. Both make it fairly easy to encrypt all of your traffic, but neither has good support for third party encryption. Your best hope right now would be some third party plugin on the client, but that makes it less likely to be used. It also make administration in a large environment very difficult.

We aren't just talking about changing algorithms here. If this "discovery" is all they are claiming it could very well mean that all public key crypto is insecure. Companies like Cisco, Verisign, and MS have encouraged enterprise customers to spend a lot of money on PKI as an enabling technology for everything from secure email to remote access. That may be down the drain if in fact, "Everything you know about public key cryptography is wrong."

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?

[Steve B]

No data security is really secure against a government focused on you -- if they can't break the crypto, they'll Trojan the machine, plant a spy camera to capture the passphrase, or squeeze the information out of you and/or your correspondents.

The realistic target is making it cost too much to target you. (Note that cost != money -- the usual government policy in that regard is "spend all you want; we'll tax more". Real costs to governments are man-hours of specially trained personnel, risk of exposure and embarassment, or risk of exposure and loss of ability to use the same trick again.)

Re:Were they even secure yesterday?

[Anonymous Coward]

Security doesn't equal encryption.
Your stuff may be easily available even if it was protected by 4096-bit keys - and taking advantage of this is where they are even better at (than in breaking the laws of physics or something).

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?

[baka_boy]

I think that government agencies are more interested in having the potential to know whay any single person or group is doing, rather than literally needing to know what everyone is doing, all of the time.

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. As you say, individuals can (and do) protect their privacy in dealings with each other, with or without the threat of government intervention. Massive corporations, OTOH, are effectively immune to any power less than the largest national governments.

Re:Were they even secure yesterday?

[marphod]

This is not, however, a 'break' in RSA. There is neither a theoretical flaw in RSA (or other factoring-based encryption methods), nor has factoring been shown to be an P problem.

This is an increase in algorithmic speed. Its a jump on moore's law, but this is hardly unexpected.

In order for there to be a break of RSA or another factoring-based algorithm, the there needs to be a flaw shown in the algorithm, that makes solving it easier than factoring large primes, or factoring primes needs to be shown to be a low-cost non-hard problem.

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:Just wait...

[GSV NegotiableEthics]

If you're relying on crypto for normal purposes, don't get worried because even Dan Bernstein doesn't know if cracking your private key is feasible, yet.

If you're really worried that someone could crack your crypto and do great harm, you should probably switch to a more secure form, such as one-time pad if this is practicable in your environment. The main attractions of public key crypto are the ease of use and the readily available implementations. It isn't the only game in town.

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.

NSA, et. al.

[jacobcaz]

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.

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

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

Sure I use a 2048bit key (soon to be 4096bit I guess), but will that really stop them from making me give up the goods if faced with jail when they come asking for my data?

Nope, because I have nothing really to hide. Maybe I keep my cache of pr0n encrypted so my fiancee doesn't discover it, but I will sure-as-shooting give that information up to keep me out of jail.

I'm to pretty for jail!

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:NSA, et. al.

[Anonymous Coward]

For now. Isn't it the case in Britain that you can be legally required to divulge keys, or that there are motions to make it so? Isn't it also the case that in many countries the fear is not jail, but torture or death?

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.

1.5 bits lost?

[nagora]

If this new method speeds the calculation by a factor of three, and each extra bit in the keys doubles the amount of time needed then surely this "breakthough" amounts to everyone losing less than 1.5 bits of security, doen't it?

The poster seems to think speeding the calculation by 3x means reducing the strength of 300bits to that of 100bits. I know this is plain wrong but I'm not sure of the correct value.

TWW

Get a grip, people!

[coyote-san]

I've seen a lot of comments about how this means that all SSL and PGP encryption is transparent, etc.

Please, get a grip.

Most "transient" connections still use 512 bit keys. If this effectively reduces the key size by 3, that's still 170 bits. That's far larger than the RSA key that took years to crack a few years back.

Technology improves, algorithms improve, and the TLAs can certainly afford to build cracking engines, but it will probably still take a substantial amount of time to crack a key. (Substantial = days.) Well worth the effort if you're looking at suspected terrorists or double agents inside of the FBI, but hardly worth it for anyone reading this comment.

What we *do* need to worry about is the effect on long-term keys. E.g., root CA keys often have 20-year lifetimes, something that now seems foolish with 1k bit keys.

One word: Asymptotics.

[DontUThinkImPretty]

Bernstein's results are asymptotic. That is, he states that a key of length n is about a secure on his special hardware as a key of length 3n on standard hardware. But this is an approximation for very large n. It is completely possible that for n near the length commonly used, his hardware could actually take longer than other equiptment.

Bernstein's result isn't the RSA killer you hotheads are making it out to be. It's a very cool result, but it's not the biggest and the baddest in the last decade.

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

Re:There are alternatives

[chongo]

Sorry for the confusion! Allow me to clarify:

A common mistake that some people make is to assume that one only needs to count CPU cycles. The so-called "MIPS years" measurements.

Consider two keys that require the same number of CPU cycles to crack, one Elliptic Curve (EC) and one RSA. The EC key crack requires only a modest amount of memory, even for large EC keys. The RSA key (by factoring) requires a larger and larger working sets as the key size increases.

Consider the cracking a 256 bit EC key and the cracking of a 1620 bit RSA key by factoring:

Both efforts require about the same number of CPU operations.

The EC crack requires only a modest amount of memory (a handful of Megabytes) and can be performed in parallel over many machines with nil communication between them.

The RSA crack requires a working set of about 120 TBytes (120*1024 GBytes)! On a single machine, you will need ~2^47 bytes of ram in order to not to swap to death. Worse yet, you are evaluating a Matrix. You could try and split it over many machines but them the communication between them (as you perform row/col matrix ops) will kill you.

So when I said two equivalently hard keys I should had said: two keys that require the same number of CPU operations to crack.

Two keys can require the same number of CPU ops to crack. However, a 256 bit EC key needs only a modest amount of memory and can be cracked on many machines running in parallel. A 1620 bit RSA requires a HUGE 120 TByte matrix sitting in a single address space where swapping and/or inter-processor communication become a major problem.

Re:There are alternatives

[chongo]

So you are saying EC is vulnerable due to that it requires "only" 2^128 ops to crack and it can even be parallelized?

No, that is not what I am saying. EC is more vulerable than RSA for a given key size where the CPU ops to perform the best known cracking algorithm are the same.

CPU-op equivalent EC searches require only a modest amount of memory and can be run in parallel with nil communcation requirements. CPU-op equivalent RSA searches require large working sets with matrix operations that do not lend themselves to parallel operations once the initial sieve is performed.

Even if you deploy a TWINKLE device in an RSA key crack that reduces the initial loading of the matrix to nil, the working set size of the matrix, the swap and/or system communication requirements become non-trivial for an CPU-op equivalent RSA key.