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.
"...many applications tend to use standardized or hard-coded primes."
If the suggested theory of static primes holds true, during application design, what part of of the definition of random did we not quite understand?
Given the impact, this stands as the golden example of what not to do Ever again.
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."
Say you can crack it, even if you can't. Security researchers around the world will try to figure out how you did it, and in the end, show you what to do.
Sort of like Reagan-era Star Wars. Drove the Russians crazy (and broke) trying to replicate non-existent technology because they took our word for it, that we had done it.
So rise up, all ye lost ones, as one, we'll claw the clouds.
In the hacking/spy drama movie Sneakers, there is a scene where Robert Redford's character is confronted with an office door protected by a keypad lock, which cannot be picked. But he needs to get into that office. The lock looks impenetrable. Surely the mission is about to fail.
So he asks his support team for help with the lock. What they tell him is never shown on screen, only Redford mumbling and agreeing to try it.
He takes a couple steps back and KICKS IN THE DOOR. The lock was completely irrelevant, in the end.
The lesson from that scene is extremely powerful when you understand the same lesson applies to ANY problem. When you are faced with a heavily secured door, or an encryption standard, the attack vector is often going to be something other than going through the face of the door or the front end of the encryption. What you'd do is KICK IN THE DOOR. And the TLAs know this and do exactly that. Their people have always kicked in doors while normal people look at the locks and shrug and walk away.
Sig for hire.