How Is the NSA Breaking So Much Crypto? (freedom-to-tinker.com)

schwit1 writes: There have been rumors for years that the NSA can decrypt a significant fraction of encrypted Internet traffic. In 2012, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a "computing breakthrough" that gave them "the ability to crack current public encryption." The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand.

However, the documents do not explain how these breakthroughs work, and speculation about possible backdoors or broken algorithms has been rampant in the technical community. Yesterday at ACM CCS, one of the leading security research venues, we and twelve coauthors presented a paper that we think solves this technical mystery.

If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn't just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to "crack" a particular prime, then easily break any individual connection that uses that prime.

Comments

Re:Maybe they're not

[DarkOx]

Right but if you are really concerned about opsec you'd use two or more layers anyway.

Something like HTTPs or Tor will make your traffic opaque to most parties. They are common protocols that don't attract attention of anyone who isn't already watching you specifically. So they are good choice for an outer layer. We also think if the right cipher suites are selected they are mathematically sound / secure. They should not depend on an obscurity component, aside form the negotiated key that is part of their normal operation.

I might then make up an inner layer. Lots of attacks on the outer layer protocols tend to be downgrade attacks or attacks that cause selection of ciphers the attacker knows how to break. Just using another layer of TLS inside the tunnel might be a fine idea.

Finally a third layer of something with a PSK for the symetric cipher that is a little more obscure but not known to have any problems. obscure means of course not as well testing, perhaps on of the rejected candidate algorithms for AES or a modified version of something existed. This does not have to be mathematically as good its mainly their to frustrate someone with an undisclosed ability to beach the other layers. It will make their tools not work out of the box. If they have the ability to break the other layers chances are they can break this one as well but you will make them work for it. The third level analyst with the metasploit module will some need help! This is will buy you time.

Quantum-safe encryption?

[Immerman]

So it seems to me that every time an encryption-breaking article come up lots of people mention how such-and-such algorithms are (if implemented correctly) provably safe from non-quantum attacks. Considering though that quantum computers are probably somewhere just over the horizon, and the NSA etc. will almost certainly be among the first to get them, possibly years or decades before anyone else even knows they exist, that just doesn't seem very comforting. Especially if you're encrypting something that you would prefer to remain secure indefinitely, instead of just until the Q-codebreaker chews through the recorded backlog.

So my question is, are there any common encryption algorithms capable of withstanding attack by a quantum computer? And if not, why not?