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.
ugh...
Backdoors. thank you very much.
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.
So are they saying that encryption protocols aren't using....optimus prime numbers?
I always use 17 as my large prime for DH. I doubt they've cracked it yet.
How is this news? Sounds like they are just describing the logjam attack which was published earlier this year
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
acres.
And has done so for decades. That should go a long ways to explain their abilities. Also, not all of it is commodity hardware but includes ASICs.
Also, who's to say they don't control one or more botnets to harvest even more computing resources from the public?
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
All of your chips and transmission devices also have direct backdoors.
Yes, all of them.
-- Tigger warning: This post may contain tiggers! --
But fuck.. some part of me would love to work at the NSA doing this sort of shit (and getting paid to do it). Yeah, there's the whole "but you're undermining FREEDOM!" angle, but there's a part of me that wants to ignore that and play with amazing shit.
Then again, there's a lot of folks who scoff at the NSA doing it, but hey, if Apple, Google, or FB had done it it'd be some sort of market miracle or some bullshit. :/
If you were me, you'd be good lookin'. - six string samurai
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.
Easier to crack the companies, not the code. The CA model is broken, and the NSA is part of why.
The NSA isn't "breaking crypto".
It was pre-broke for them.
You are welcome on my lawn.
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
... the negotiation always happens and those / that part of the data is always collected by the NSA.
Now, if the negotiation happened via some other transport mechanism (think sneaker-net), yes,
that's virtually unbreakable except by brute-force..
I kinda thought everybody knew that...
Also, who's to say they don't control one or more botnets to harvest even more computing resources from the public?
So despite no evidence that it is true, you consider the fact that this speculation can not be disproven (due to its nature) as proof of it truth?
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)
You do know that the NSA has more mathematicians than any other organization on the planet.
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)
Ummm, no, I think he was just speculating. That's why he said "who's to say".
That's what speculation is, you suggest something that may be true without evidence.
It's not like he said "I'm absolutely sure that they control botnets...."
Sheesh.
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
hah. well if you have both keys in encryption, data no longer safe.
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"
if you got both keys you encryption is uselesssssssssss.
or you have asics built to crack.
simple. why such a mystery?
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
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.
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.
It seems more like overt surveillance now.
My ism, it's full of beliefs.
MacOS X uses the OpenBDS moduli file, and also containing 1023 size keys and are identical on all Macs.
/private/etc/moduli
Probably a good idea to make new self generated ones with only 4k keys.
Ye son, that and those @ oracle whom seek to plunder..
Gestalt computing
They're only breaking crypto that's already broken - which is actually quite a bit. There is still crypto they can't break, otherwise there wouldn't be calls for a ban on encryption.
Given a public key, it's said "impossible" to discover the associated private key.
But if we generate *all* the pairs (private, public) keys, then we could index reversely. That all.
With a lot of work of computation (NS* has a big cluster of computers) we could calculate such index with public and private keys with size =N (typic N=1024).
Think of that,
they know what they're doing too well?
/. -- the Free Republic of technology.
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.
First, you all need to realize this is a complete lie. It's a trick to get you into compliance, by making you think they are more capable than they really are. The nazi's used the same tactics.
Second, those items that were decrypted were done so by other means. Successful Dictionary attacks, key logging, etc.
Finally, you need to encrypt EVERYTHING and it needs to be a high number of bits; I suggest you go big or go home, say 8192 bits. And it not only needs to be the data that is encrypted, the practice of how it's implemented needs to be cryptic and secure as well, so key logging and dictionary attacks won't work.
I'm sure somebody will say 8192 is too much. But I remember not long ago they said 56 bit was enough and would take millions of years to decrypt, yet today it's referenced as weak.
... is simply not credible. It only has 12 authors.
How can we be sure that the NSA doesn't have quantum computing? And even if they don't, they will be the FIRST to implement it on a massive scale once it is available.
Won't quantum computing render most of our current encryption algorythm suite obsolete?
I have it on good authority that the Chinese government was able to read GMail and Microsoft mail (both encrypted) certainly at the start of this year; for some reason they seemed to have trouble with mail from one or two other sources, but imagine that this is now resolved. as well.
Apologize for posting anonymously.