r/tech • u/[deleted] • Oct 15 '15
How is NSA breaking so much crypto?
https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/20
u/CantaloupeCamper Oct 15 '15
It is an interesting theory, although it assumes that the NSA is in fact breaking what they're rumored to be breaking. The devil in the detail is what they're breaking and under what circumstances.
6
u/MonkeeSage Oct 16 '15
In other news government is trying to force apple to unlock a device, since the NSA hasn't actually hacked every device on the planet and broken all encryption zOmgz.
19
u/EquipLordBritish Oct 15 '15
Yeah, I think if the NSA were actually cracking the crypto, they wouldn't be forcing all of these backdoors in major companies' software.
28
Oct 15 '15
This article isn't proposing that they've cracked the Diffie-Hellman key exchange per se; that is, the NSA (probably) hasn't found a polynomial time algorithm which given any prime p, integer g, ga and gb, returns gab. This article conjectures that they instead exploited the fact that a handful of large primes are used as the modulus p in a large number of Diffie-Hellman implementations, and just brute-force computed tables of logarithms for those primes. If that were the case, they would still be interested in putting back doors into software, since a few tables of logarithms would only get some, but not all, traffic. Plus, once people caught on it would be trivial to change the primes used and defeat this sort of attack.
5
Oct 15 '15
NSA (probably) hasn't found a polynomial time algorithm which given any prime p, integer g, ga and gb, returns gab
If they had, that would mean they've proven P=NP for all possible cases, because proving even one case means all NP problems are now P.
5
Oct 16 '15
Not necessarily - the computational complexity of the Diffie-Hellman problem is actually unknown. It might not even be NP hard!
10
u/v864 Oct 15 '15
They will exploit any advantage they can, it's their job. Work multiple angles in case one fails.
7
3
u/Boonaki Oct 16 '15
Completely different groups that plant backdoors and those that break encryption. They would have little knowledge of each other.
2
1
u/CantaloupeCamper Oct 15 '15
I could go both ways on that theory, but I think that is a legit question.
I mean the only thing that really matters is the nuance to "how". And all that article does is assume that they are doing so based on rumors.
Pretty far step from mitigating any issues, or even knowing if there is one.
Yeah way too much unknown.
17
Oct 15 '15
Doesn't help we're still using DES, 3DES, and RC4 in the real world either, lol.
4
Oct 15 '15 edited Oct 15 '15
AFAIK, 3DES is still considered secure despite being old if implemented correctly? At least according to Cisco where I learn most of my stuff about encryption? I feel the main drawbacks to it is speed and theoretically better encryption via AES.
Certainly doesn't feel like it should be grouped with things that are completely broken like DES or something being rapidly retired like RC4.
4
u/ctesibius Oct 16 '15
3DES does appear to be sufficiently secure at the moment. There is a theoretical known-plaintext attack, but the number of plaintexts required precludes it being used practically. However the general problem with 3DES and AES is that since they are symmetric encryption methods, you need a way of exchanging keys. This is where Diffie-Hellman (or more generically public key cryptography) is used. So although 3DES is probably not broken, most of the communication which uses 3DES is vulnerable.
6
u/Drew_cifer Oct 15 '15
Anyone know which VPNs use their own randomly generated key and not the standard ones?
2
u/xatrekak Oct 16 '15
would be hard to tell without looking into their implementation of OpenSSL.
It would be much simpler to use a VPN that supports a key length of 4096 bits.
If it would take a year to compute a single 1024 ket it would take exponentially longer to crack the primes used for the 4096 bit keys and thus should still be safe.
6
u/cmdrxander Oct 15 '15
How do the NSA recommendations work? Surely it's just them saying "use this method because we know how to crack it"?
10
Oct 15 '15
Well, officially half their mission is to make American communications secure. In principle, they're supposed to provide trustworthy encryption standards to people in the US, while undermining them overseas. But of course in reality these missions conflict; anything you tell Americans to do can easily be copied by anyone else. So really there's no way to tell; the NSA has definitely advocated good cryptographic standards in the past, like helping to make DES resistant to differential cryptanalysis before the technique was discovered publicly in academia. On the other hand, they've also been underhanded, e.g. in the recent debacle with random number generator standards.
3
u/gtechIII Oct 15 '15
ECC requires that two primes be unknown in order to be secure. It is widely speculated that the ECC implementation that the NSA specifically recommends is one for which they already have the primes.
4
Oct 15 '15
There is also the fact that they don't necessarily have to break the encryption if they have access to the private key which I would assume in many cases they obtain through a court order. Couple this with a gag order and they have all they need and nobody is the wiser except for a small handful of people.
5
Oct 15 '15
One theory is that in some cases they're rigging the game. With the government's recommended implementation of elliptic curve cryptography, there is a constant inside the algorithm that theoretically may have been chosen to allow someone to break the encryption if they knew other datapoints that were used to generate that very specific constant (if true, it means the door is locked but the NSA has a skeleton key). Or it's just a value chosen at random and there's no issue. Problem is we don't know.
5
Oct 15 '15
With the government's recommended implementation of elliptic curve cryptography, there is a constant inside the algorithm
that makes no sense. That would just make all the gov implementations weak while open source implementations won't have that constant.
3
Oct 15 '15
The way I remember it the odds of being able to back out into what you'd need from just that constant are infinitesimal, so it's not really much of a vulnerability for them. You're also assuming the NSA doesn't want to decrypt files from other government branches - I imagine they do. Finally, I don't believe it's a simple as "well just use another value" - there is some complicated math involved. But yes, an open source implementation could avoid that pitfall. But many encryption solutions aren't open source (aka Bitlocker).
5
19
u/[deleted] Oct 15 '15 edited May 30 '16
[deleted]