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....
I was ridiculed for suggesting that you simply pre-calculate every possible prime in that bitspace and that's it.
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.
Influence the outcome.
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
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! --
When you have the ability to create your own money by entering into a computer you have the resources to do it relatively quickly.
I love Jesus, except for his foreign policy.
The NSA isn't "breaking crypto".
It was pre-broke for them.
You are welcome on my lawn.
You must've seen a pre-published description of Logjam, since this is the paper that first presented it. The second sentence even starts with, "First, we present Logjam [...]". So yeah...
It's a complete lie. Trust the math.
Anytime they have cracked something, they already had some information or used a keylogger or something similar. In a situation where they had to perform a complete crack, they are mostly out of luck.
Strong indications are that Snowden is a government plant, and that his mission was to convince the public and rest of the world that the NSA was more capable than they actually are.
I've worked in computer forensics for almost 10 years and worked with countless government agencies around the world. Years ago I watched one of the 3-letter agencies crack BitLocker in under 30 seconds. It's funny how many insist there is no way and dismiss the idea without a second thought. Now new evidence is showing that they certainly have the technology to do so. Maybe it's time to not be so quick to dismiss such thoughts.
This will separate the wheat from chaff. People who know security and take it seriously will make sure they spend the resources to find a couple of large primes and base their keys on them. The equivalent of script kiddies who just download some binaries with security hashing algorithms who use it without understanding them will get cracked. Not just by NSA. Anyone with a budget and determination will. All the governments.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
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.
17 isn't prime....
CAP == 'disallow'
Anybody else seeing the headline as:
???
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
If it has the keys (i.e. is one of the SSL endpoints), SURE. A random SSL connection between two nodes... not a fucking chance. (null certificate + man-in-the-middle don't count as that makes the firewall an endpoint)
Bullshit yes, 'tis what you spout. If any of those had found a way to break encryption as the NSA had, I would expect a paper on it much like this and a push to deprecate whatever was broken. Particularly given their businesses are built upon secure communications. Instead, the NSA breaks it and uses it to spy on everyone.
They can MITM anyone they want and they almost certainly have the ability to mint any certificate they wish....
My eyes reflect the stars and a smile lights up my face.
I read about how DH works years ago and this was the first thing that came to mind. It's there. Just go read.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion. -- Spazmania (174582)
I'm certain you've got codebreakers breaking codes. If you're able to do this, and you'd like to establish a shred of good will, would you kindly package it into simple-to-use applications that will allow users to decrypt files held ransom by Cryptowall? You'd be strengthening your image while simultaneously hurting the economy of the sketchy side of the internet.
Warm regards,
Voyager529
Worst office Christmas party ever.
You forgot 1 from your list, and 17/1 has no remainder.
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.
The ability to create, shape, sell, and attack weak international crypto would be the easy key to decades of "the ability to crack current public encryption". :)
A "computing breakthrough" could just be in cheap storage, fast sorting that allows a collect it all ability after getting plain text.
Nothing much has really changed from the ideas of the 1950's. Set weak junk encryption, get the majority of users accepting a weak standard and then collect it all.
It worked for diplomatic hardware in the 1950-90's. Just keep pushing the easy to break standards and really smart nations line up to buy and install junk crypto globally.
How did it work? Nations only tested for man in the middle attacks or trying to force the crypto. The West had the design, trap door, keys so getting back plain text was not an issue
In the past words and important messages had to be kept or sorted in real time. Now the 1970's-90's breakthrough is collect it all.
Low prices, created in neutral nations, great marketing, seeing fake reports about other advanced nations trusting the same systems are the most easy tricks to sell bad crypto.
The other magic was to buy up or create crypto front companies with endless gov funding if a really private sector secure product ever emerged ever generation or so.
Other more simple and direct methods also stopped development of advanced independent domestic crypto.
The clues to how the NSA works on all emerging crypto are in the crypto history books.
How did the UK break the Soviet embassy codes in the 1930's? They hired the person who worked to on them.
Ernst Fetterlein https://en.wikipedia.org/wiki/...
Weak codes, finding the correct staff, ensuring other nations never create good crypto or buy into junk standards.
Domestic spying is now "Benign Information Gathering"
The journal article cited addresses Diffie-Hellman (DH) certificates with 1024 bits. For browsers, such certificates are being deprecated. Certification authorities are not supposed to issue intermediate certificates or sign subscriber certificates that have less than 2048 bits, and Mozilla reserves the right to require even larger certificates.
Furthermore, the OpenPGP format allows even larger DH parts of the DH/DSS encryption keys. My own DH/DSS key is 4096/1024. The 4096 is the size of the DH part. The 1024 is the size of the one-time, temporary DSS key used to encrypt my files; that temporary key is then itself encrypted with my DH key and appended to the encrypted file. Since a new DSS key is generated each time I encrypt a file -- even for the same file -- the smaller size does not bother me.
Ummm, no, I think he was just speculating. That's why he said "who's to say".
But he said it in the same conspiracy theorist manner as do nut jobs who "speculate" that Obama is a shape-shifting humanoid reptilian from Planet Nibiru.
"I don't know, therefore Aliens" Wafflebox1
No true fanboy would use Safari!
I hate printers.
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.
Actually most of the mathematicians I have known have been pretty fun people to hang out with. Maybe you're thinking of accountants?
--- Most topics have many sides worth arguing, allow me to take one opposite you.
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.
This is more of a front door with a bicycle lock.
Seven puppies were harmed during the making of this post.
It seems more like overt surveillance now.
My ism, it's full of beliefs.
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.
As in coming in the front door and hitting someone with a bicycle lock?
The hard core are still using CyberDog!
I always use 17 as my large prime for DH. I doubt they've cracked it yet.
Everybody else uses odd primes, so I always use an even prime.
Intron: the portion of DNA which expresses nothing useful.
ECDH is possibly backdoored by the NSA. From what we know, DH is mathematically sound, provided you generate your own, large enough (2048b or larger) prime.
ECDH in TLS only uses curves proposed by NIST. Some cryptographers believe that constants used to pre-compute the curves are in fact backdoored, which would explain how they decrypt most of the traffic. Curve 25519 and a few others are very likely safe, but not available in TLS1.2. ALL available ECDH curves in TLS were proposed by NIST.
I believe that between precomputed ECDH curves and Logjam, the NSA is able to decrypt nearly https traffic.
https://www.schneier.com/blog/...
"I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry." - Bruce Schneier on ECDHE curves in TLS
I trust Bruce.
Ideally, the standards body would introduce curve 25519 to TLS1.2. Until then, server operators need to take this advice, configure their servers to prefer DHE (not EC) with 2k+ keys, and turn off older ciphers including EC*.
Oh, and get firefox to fix this bug: https://bugzilla.mozilla.org/s...
-=Lothsahn=-
You realize that the ssl cert provider isn't the one doing the attacking, don't you?
they know what they're doing too well?
/. -- the Free Republic of technology.
You thought we were gonna think 2, but I know ur secret is 0. 0 goes an integer number of times into any other number! It also goes a non integer number of times into any other number, but I doubt that disqualifies it in the eyes of the Lord.
Wasn't this the plot of Sneakers?
In November this year, a new encryption protocol (Perpetual Encryption) will become available to the public
Alright I guess we'll see in a month and half.
And N/2 is >= sqrt(N) for N>=4 (and since we take the integer floor of the result works for the 4 natural numbers that missed anyway), and thus provides a perfectly valid upper bound - not optimal but there was no claim that it was.
We could, if we had a couple trillion trillion trillion trillion universes at our disposal.
A successful API design takes a mixture of software design and pedagogy.
Sorry if this is a dumb question, but I use openssl dhparam to generate a 4096-bit DH parameter file. Does that make a difference?
It would help mitigate that attack by increasing the workload to build the number field sieve. But it would increase the load at both ends. Switching to Curve25519 ECDH or Goldilocks or some other good elliptic curve would reduce the load at both ends and prevent the logjam attack.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
Yep. Get Curve25519 ECDH deployed. It's a good option for O(2**128) bit security bounds. And yes, the short term TLS solution is to move to bigger prime fields for DH.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.