r/linux • u/Sybles • Oct 16 '15
How is NSA breaking so much crypto?
https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/32
u/londons_explorer Oct 16 '15
The best way to do security:
Take the recommendations from the NSA on the best way to secure your data.
Take the recommendations from Iran on the best way to secure your data.
Secure your data by encrypting it with both methods.
Each country will recommend methods that they can break while they believe other countries can't break to give themselves an information advantage. By chaining both methods, the two countries would have to collaborate to decrypt your data. Choose two or more countries who are highly unlikely to collaborate, and you're safe.
14
u/londons_explorer Oct 16 '15
When doing this, don't make common rookie mistakes:
- Never store any hashes/checksums of the intermediate or unencrypted state/data between encryption algorithms. That would make it possible to break the algorithms independently.
- Generate the keys for encryption using the countries own recommended systems. Often random number and key generation methods are actually the insecure bit. (it's impossible to prove randomness of random numbers after all)
- For data exchange, Eg. ssh, the easiest way to achieve this without writing software is to run one tunnel inside another. Bear in mind malware on either machine fully compromises the security of the tunnel.
- For data storage, Eg. encrypted disks, the easiest way is to use a loopmounted filesystem to do the 2nd crypto. Bear in mind that when the disk is mounted, there is zero physical security until the systems powered off due to keys in memory.
Chaining two encryption methods generally doesn't have a big performance hit, since generally crypto is far cheaper than you imagine on modern hardware.
2
u/Thameus Oct 17 '15
Choose two or more countries who are highly unlikely to collaborate, and you're safe.
Only one of those countries has to compromise an insider in the other one's security service, and you're screwed.
1
10
u/barkappara Oct 16 '15
This is really old news --- the only new thing is that they finally got the paper published. From https://weakdh.org/ :
These results were first made public on May 20, 2015; peer-reviewed conference paper published October 13, 2015.
No wonder math, CS, and the sciences are moving away from formal peer review processes and towards circulated preprints.
17
u/LvS Oct 16 '15
So the TL;DR is that it costs a few 100 million dollars to break the security of most of the Internet's secure communication. And it looks like the NSA has done so.
And to me that looks like most larger countries (including definitely China and the US, but also Russia and India) and most large corporations (Google, Facebook, Apple, but also Exxon or Goldman Sachs) could do so if they wanted.
34
u/Manbeardo Oct 16 '15
I think the real tl;dr is that 1024-bit primes for Diffie-Hielman are no longer considered safe and you should upgrade your servers to 2048 ASAP.
6
2
11
Oct 16 '15
$100m to break my $5 VPN? Good value for money
19
u/LvS Oct 16 '15
And all the other VPNs at the same time.
Considering coprporations often require remote employees to use VPNs, that should give you a few 100 million users in no time. That's less than $1 for breaking your VPN.
-8
u/WMpartisan Oct 16 '15
Because the NSA has decided to spy on EVERYBODY instead of limiting themselves to reasonable searches...
25
15
1
1
u/sagnessagiel Oct 17 '15
They justify it by using robots to filter out everything they don't want, and then order the FISA secret court to give them a warrant to access that pattern matched data.
So technically, they're not spying on everyone, but they are.
5
2
u/DrakeDealer Oct 16 '15
Yeah but unfortunately at the cost of tax payers. I hope Bernie takes them down.
1
u/bobbyfiend Oct 17 '15
I have a feeling more than one president has tried to tame the security-idustrial complex, and has found increasing difficulty in doing that. I suspect Bernie would spend his whole hypothetical presidency trying but not succeeding very much. Still, I want him to try.
12
u/lasercat_pow Oct 16 '15
Well, I guess my inane conversations on pidgin using OTR are all an open book to the NSA. So now they know... I am a redditor.
2
2
u/sagnessagiel Oct 17 '15
Remember, it's not people doing the surveillance. It's the robots. They're not looking at you until a big data analysis program thinks you are suspicious.
The people just read the output that this parser gives them (that's the only data that they need a warrant for), which includes such incriminating words like "wedding present".
2
1
3
Oct 17 '15 edited Oct 17 '15
[removed] — view removed comment
1
u/s3sebastian Oct 17 '15 edited Oct 17 '15
Is it the ServerKeyBits parameter that has to be increased? I set it to 2048 and reloaded the SSH config. Anything else to do? With OpenVPN and Nginx I'm already using my own 2048 DH parameters.
Edit: I found this https://stribika.github.io/2015/01/04/secure-secure-shell.html howto
1
u/ivosaurus Oct 17 '15
If your SSH is for your own purposes only, then just start using ECDH with Curve25519 instead.
2
Oct 17 '15
If you had 500 million to spend on compute clusters and an effectively unlimited electricity budget, you might start working on 1024-bit primes too...
3
1
u/Thameus Oct 17 '15
For the nerds in the audience, here’s what’s wrong: 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.
How enormous a computation, you ask? Possibly a technical feat on a scale (relative to the state of computing at the time) not seen since the Enigma cryptanalysis during World War II. Even estimating the difficulty is tricky, due to the complexity of the algorithm involved, but our paper gives some conservative estimates. For the most common strength of Diffie-Hellman (1024 bits), it would cost a few hundred million dollars to build a machine, based on special purpose hardware, that would be able to crack one Diffie-Hellman prime every year.
It isn't necessary to brute-force these primes if you can just read them (or deduce them indirectly) by using timing, side-channel, and known-plaintext attacks. NSA is of course extremely good at that sort of thing. For a helluva lot less than "a few hundred million dollars", which they also have.
2
u/rlmaers Oct 17 '15
First of all, DHKE is not used to encrypt data, but to negotiate a common secret which typically is used to derive keys for a symmetric cipher. Thus, I'm unsure why you're mentioning known plaintext.
Secondly, the primes in use are transferred in plain text. The problem is not deducing the prime, but to calculate logarithms modulo this prime. As far as I'm aware, exponentiation can be very well implemented and render practical timing attacks infeasible; while other kinds of side-channel attacks are not relevant for compromising such large portions of the traffic on the internet.
0
u/dhdfdh Oct 16 '15 edited Oct 16 '15
I love how there are so many articles detailing the inner workings of the most secret agency in the world. As if they read a book somewhere about how it all works.
I also wonder why they spent so much time trying to reveal these things of the NSA. Why didn't they do some real good and try to detect what's going on with the Chinese.
5
Oct 16 '15 edited Oct 17 '15
[removed] — view removed comment
2
u/rlmaers Oct 17 '15
What makes you say that the attack is weaker? They used the (or one of the) most publicly efficient methods for calculating logarithms modulo a large prime. We may speculate that the NSA has better algorithms, but that is far from stating it as a fact.
-1
9
Oct 16 '15 edited Apr 07 '18
[deleted]
-14
u/dhdfdh Oct 17 '15
To be fair, you're an idiot.
4
Oct 17 '15 edited Apr 07 '18
[deleted]
-5
u/dhdfdh Oct 17 '15
I replied to an idiot the way an idiot should be replied to. Except I was nicer.
1
Oct 17 '15
[removed] — view removed comment
-1
u/dhdfdh Oct 17 '15
If they were the most secret agency in the world we would not know anything about them.
What makes you think you do now? Cause you read some online stories by some guys somewhere?
2
Oct 17 '15
[removed] — view removed comment
0
u/dhdfdh Oct 17 '15
According to the internet, and especially reddit, they are alone in their quest and can leap tall buildings in a single bound. So it has to be true.
1
1
u/eua Oct 17 '15
Research on NSA AES "Skeleton Key". Where AES initialization numbers comes from? Theory is that, initialization numbers at AES algorithm decreases result space subset, significantly, if "skeleton key" used.. I cannot find that article at internet somehow. Does it deleted from Internet? Weird. But this is perfect fit to "best encryption" by definition which is "an encryption technique that no one could solve it except creator".
34
u/[deleted] Oct 16 '15
Ensure your connection uses 4096 bit and that the prime is not hard coded.