Slashdot Mirror
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.
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.
We've long past the point where we knew RSA, simple Diffie Hellman, Sha-1 and NIST curves need to go in the bin. This is one more nail in the coffin.
The standards I'm working in have gone Ed25519, Curve25519 ECDH, Shake128, AES, etc. 128 bits, sane curves, modern hashes. Rearranging the TLS deck chairs won't help.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
When the NSA leaks happened, investigates this and promoted this as a possible attack vector.
NOTE - You can generate a new set of moduli like so:
# ssh-keygen -G moduli-2048.candidates -b 2048
# ssh-keygen -T moduli-2048 -f moduli-2048.candidates
Put the results in /etc/ssh/moduli
WARNING: This takes forever. Also, according to man ssh-keygen:
It is important that this file contains moduli of a range of bit lengths and that both ends of a connection share common moduli.
It's not possible to regenerate and share many moduli quickly - hence the reuse of moduli. SSH has support for x25519 algorithms - this definitely means I'll be moving away from pre-computed DH moduli also.
I said no... but I missed and it came out yes.
Scott Aaronson has an excellent summary of this research on his blog: http://www.scottaaronson.com/b... One point that Scott makes that is easy to lose track of is how much working this out required people on both the theoretical crypto end and the practical crypto end to work together. This is a combination of multiple vulnerabilities and some clever number theory.
How Is the NSA Breaking So Much Crypto?
Maybe they're not. They're hardly going to tell you what they can't crack.
systemd is Roko's Basilisk.
So, in short, they're not breaking crypto, they are breaking shitty implementations of crypto.
So basically, like using a one-time pad multiple times.
Well, I guess it's time to start sorting the wheat from the chaff and start ditching fixed-prime implementations wholesale.
-SS "Teach the ignorant, care for the dumb, and punish the stupid."
Backdoors. thank you very much.
Nope. They mention that in the paper and then proceed to show how it can be done without them. But nice try.
The biggest surprise for me in the paper is the revelation that all major browsers would not accept a prime less than 512 bits with one exception- Safari. Safari was found to accept primes as small as 16 bits, essentially rendering it completely vulnerable to real-time attack by almost anybody.
IE, Firefox, and Chrome are already transitioning to support stronger mechanisms which would not be vulnerable. Time to take a hard look at your choice of browser, Apple fanboys.
Apparently you have no clue how many ages of the universe it would take to enumerate the 256-bit primes.
We are nerds here, so lets calculate it. The number of primes less than N is approx ln(N), so the number of primes less than 2^256 = (2^256/256) = 2^248 = 4.5e74. If you computed one prime per plank time, it would take this long: 4.5e77 * 5.4e-44 secs/planckTime / (1.38e10 years/universe * 3600 * 24 * 365) = 2.3e12, or about 2 trillion times the age of the universe. 512 bit primes would take considerably longer.
Once you calculate the list of primes, you need to figure out where to store it. Storing 4.5e74 numbers is problematic, since that is about a quintillion times the number of atoms in the sun.
We can be fairly certain that the NSA is not just relying on a lookup table.
Here I was about to give you grief on your math ( ln ( 2^512 ) ~= 354 ), and then realized the problem was simply that you mis-typed the initial theorem.
For anyone else thrown off, the correct rule is that there's approximately N / log( N ) primes less than N.
--- Most topics have many sides worth arguing, allow me to take one opposite you.
For anyone else thrown off, the correct rule is that there's approximately N / log( N ) primes less than N.
Sorry about that. But the math is still wrong. It is supposed to be ln (log base e) and I did the calculations with log2. So the number of primes less than 2^256 should be (2^256/177) = 6.5e74, not 4.5e74.
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?
--- Most topics have many sides worth arguing, allow me to take one opposite you.