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.
Just what I was thinking....
and all that....
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.
"...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."
While there are a few alternatives to RSA (though they share some mathematical similarity) i'm not aware of any non-quantum replacement for DH. That obviously makes it a natural candidate for any kind of focussed attack.
I honestly had no idea that most implementations fixed p. It seems obvious in retrospect that this could lead to the creation of a giant LUT
This is the original logjam attack from May this year.
Even the PDF points to the same site:
https://weakdh.org/
New things are always on the horizon
You are wrong. Precalculating the primes is not simple and it wouldn't help.
The authors of the paper are pre-calculating the number field sieve for the prime group. This allows them to efficiently compute discrete logs over the group.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
How is this news? Sounds like they are just describing the logjam attack which was published earlier this year
They are estimating the computation effort to build a number field seive to efficiently compute logs over the 1024 bit prime groups in common use for plain old Diffie Hellman.
They recommend elliptic curves and not the NIST curves. From TFP:
"Transition to elliptic curves. Transitioning to elliptic
curve Diffie-Hellman (ECDH) key exchange with appropriate
parameters avoids all known feasible cryptanalytic
attacks. Current elliptic curve discrete log algorithms for
strong curves do not gain as much of an advantage from
precomputation. In addition, ECDH keys are shorter than
in “mod p” Diffie-Hellman, and shared-secret computations
are faster. Unfortunately, the most widely supported ECDH
parameters, those specified by NIST, are now viewed with
suspicion due to NSA influence on their design, despite no
known or suspected weaknesses. These curves are undergoing
scrutiny, and new curves, such as Curve25519, are
being standardized by the IRTF for use in Internet protocols.
We recommend transitioning to elliptic curves where
possible; this is the most effective long-term solution to the
vulnerabilities described in this paper."
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
All of your chips and transmission devices also have direct backdoors.
Yes, all of them.
-- Tigger warning: This post may contain tiggers! --
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.
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.
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.
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.
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.
Backdoors. thank you very much.
Nope. They mention that in the paper and then proceed to show how it can be done without them.
Just because it can be done without backdoors, doesn't mean the NSA isn't going the easy route. That the NSA is tapping large datacenters before encryption and has access to the private keys of major companies is known now. Schneier says:
The new Snowden revelations are explosive. Basically, the NSA is able to decrypt most of the Internet. They're doing it primarily by cheating, not by mathematics.
NB: The message above might reflect my opinion right now, but not necessarily tomorrow or next year.
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.
Yes but with Moor's law we'll beat that eventually, just as athletes running faster and faster will eventually exceed the speed of light. ;-)
Yes but with Moor's law we'll beat that eventually, just as athletes running faster and faster will eventually exceed the speed of light. ;-)
No, they will eventually slow down time itself, causing the people watching them to live forever even with their diet of chips and bud light, and lifestyle of a couch potato.
But by that time the American spectators will be so heavy that they form a black hole, meaning not even the athletes can get away.