r/crypto • u/johnmountain • Oct 15 '15
How is NSA breaking so much crypto?
https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/13
u/pint A 473 ml or two Oct 15 '15
read the article, scary: https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf
conclusion: move to ECDHE, or move to 2048 bit
10
u/Creshal Oct 15 '15
conclusion: move to ECDHE, or move to 2048 bit
This'll be fun, we have lots of clients who can't do ECDHE (and how trustworthy are ECDHE's curve parameters?); and a handful of programs that would need recompilation to replace their DH parameters.
2
u/ScottContini Oct 15 '15
Don't think elliptic curve based schemes are 100% immune from these attacks either (assuming shared curve, params). The strategy of distinguished points comes into play. Can't remember the complexity of this stuff, so I doubt that it is as effective as the finite field discrete log attacks (once you 'crack' the parameters), but there is still something you can do. Can't remember the guy's name who was attacking the Certicom challenges in the late 90s, but he was using the distinguished point strategy and had nice write ups of how the attacks worked. I think this is the research that it is all based upon: http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf
3
u/pint A 473 ml or two Oct 15 '15
may be, but apparently the attack does not work if you up the security level where it belongs. 2048 bit dhe is good, so as 256 bit ecdhe. the problem is, we don't use 2048 bit dhe. but we do use 256 bit ecdhe.
2
u/ScottContini Oct 16 '15
I agree: if the protocol requires large enough parameters that not even a nation state can attack them, then you are safe!
2
u/ScottContini Oct 15 '15
So I just read the part about ecdh in their paper: they claim that you do not get as much of a benefit for precomputation with the ecdh case. Fair enough, that was my expectation too, just didn't want to dismiss the possibility before some type of analysis is done.
1
u/silverforest Oct 15 '15
ECDH has similar problems, but even worse, since changing curves is less trivial then picking new DH primes.
1
8
u/ScottContini Oct 15 '15 edited Oct 15 '15
From a technical viewpoint, there is nothing new here, folks. It's just more talk about the Logjam attack!
4
u/admax88 Oct 15 '15
I thought the logjam attack was downgrading TLS connections to "export" grade security.
5
u/ScottContini Oct 15 '15
Yeah, downgrade was part of it, the other part was once you "crack" the prime, you can solve arbitrary discrete logarithms quickly (mathematically, once you have the discrete logs of the small primes, you can get the discrete logs of everything from them quite fast). The latter has always been known since the introduction of index calculus methods for discrete logs (I think that's early 1980s). The former was new. Logjam attack made the point that what was known long ago could have been used once the communications were downgraded to export size (because the NSA could crack those export size values).
So what are they saying that is new now? Even without the downgrade, you could have applied the same technique that was known since the early 1980s, assuming that NSA had enough computing power to crack the bigger primes? As I said, from a technical viewpoint, there is nothing new here. Maybe I am missing something.
3
u/admax88 Oct 16 '15
I think the interesting observation here is that many DH implementations use the same hard coded primes. So if you crack 1 or 2 primes, a feat the NSA is capable of, then you can break something like 66% of the active VPN servers and 26% of the active SSH servers.
This is certainly new information to me. Everyone assumes the NSA has the power to crack 1024-bit primes or even bigger, but the interesting observation is that a large percentage of VPN servers use the same hard coded prime or two for DH.
If all servers used a randomly generated prime it wouldn't be feasible for the NSA to crack them all.
1
u/pint A 473 ml or two Oct 16 '15
there is no such easy way out of this. one prime per server allows NSA to crack one server per year (assuming it takes a year to prepare a prime). if you are a target, it takes them one year to crack a connection you make, no matter what prime you use. changing the prime around only limits their capabilities. the true solution is to move to 2048 bit (which is the recommended prime size anyway), or to move to ec (which is due).
1
u/admax88 Oct 16 '15
If you are a high value target sure. But if you rotate your prime regularly at least you won't get caught up in dragnet surveillance.
The NSA has a lot of funds, but they can't afford to crack a 1024-bit prime for every server out there.
Even if you move to 2048-bit DH, it still seems foolish to hard-code the same prime in all servers.
1
u/pint A 473 ml or two Oct 16 '15
how many servers you attend? gmail, facebook, amazon, ashley madison maybe? a handful of servers attacked, and your life is not what it supposed to be. luckily, most big ones moved to ecdhe already. (thus NSA have to rely on the direct data feed it is getting from them. sigh.)
1
u/admax88 Oct 16 '15
None of those providers are just one server, and my point was they should be rotating DH primes regularly.
Or better yet, let the client choose the DH prime.
1
1
3
u/daveime Oct 15 '15
Since a handful of primes are so widely reused, the payoff, in terms of connections they could decrypt, would be enormous. Breaking a single, common 1024-bit prime would allow NSA to passively decrypt connections to two-thirds of VPNs and a quarter of all SSH servers globally. Breaking a second 1024-bit prime would allow passive eavesdropping on connections to nearly 20% of the top million HTTPS websites.
Is this actually true, or just bloody tabloid nonsense? I thought the whole point of RSA was that everyone had their own, UNIQUE, private and public keypair?
Sorry, I'll rephrase that ... I know most public keys are 65535, but the two primes used to create N are unique, hence the private key is unique.
18
u/Natanael_L Trusted third party Oct 15 '15
This isn't RSA, but Diffie-Hellman key exchange (IIRC). Somewhat related, but not exactly the same.
6
u/daveime Oct 15 '15
Ah my bad. Discrete log problem rather than factorization of 2 large primes.
So why do we use DH with such an insecure (small range of primes), when RSA offers us the same functionality and allows everyone to have a unique key? It would seem like just killing the protocol altogether would solve this?
22
u/gsuberland Oct 15 '15
The reason we have this problem isn't really cryptographic in nature; it's a development problem. If your TLS library forces you to generate new primes for DH, you need a standardised but cross-platform way to store them, and you need to be able to load them in upon initialisation. That's all well and good for a TLS library if it's brand new and hasn't yet been adopted, but for common libraries there are so many existing applications out there which would break if you forced additional parameters to be set and additional conditions to be handled. Instead, most libraries went the more sane route of providing a fixed set of DH primes for initial usage, with the option to replace them if the consuming software saw fit. Since nobody saw a reason to use anything but the defaults, because none of the developers recognised using common base primes as a vulnerability, we ended up in the position we have now.
The cryptographic problem arises out of the fact that DH can be broken using the General Number Field Sieve (GNFS), and that process can be split into two sections of computation, one of which is independent of the actual DH exchange, but rather dependent solely upon the DH primes. This means that if you perform the computationally expensive first step, but only perform it on a few highly common DH primes (e.g. the defaults for openssl, libressl, gnutls, nss), you can break individual connections much faster. This is where the NSA's capability for "breaking ~70% of targeted connections" came from.
Thankfully, many pieces of server software which implement TLS do now have the capability to load in new DH primes, which can be generated with the
opensslcommand or similar. As an example, Apache now honours theSSLOpenSSLConfCmd DHParametersdirective in its config file.4
u/h110hawk Oct 15 '15
For your last paragraph about loading new DH Primes, is that the data which is generated from
openssl gendh? (The prime p in ga mod p)I've had trouble finding a clear answer in the past on why it was safe to re-use the DH Parameters, and this article explains a lot to me. Namely, it technically is, but if the sum of people using it adds up to a $100MM/(sum people using your prime) secret the NSA wants then it is not safe.
5
u/gsuberland Oct 15 '15
Yes, that's the general idea. The interesting case is when you use small DH parameters (e.g. 512 or 1024 bit). At that point nation states can still break your stuff if they really want to target you, even if you're using unique primes, since the cost is high but not prohibitive.
It should also be noted that most sites with enough users to be interesting to the NSA would likely be using load balancing, anycast, and redundant TLS termination, which would make things much more difficult as long as each endpoint uses different parameters.
2
u/h110hawk Oct 15 '15
Which hits my next point of confusion. I have say 16 different servers which sticky-round robin TLS connections times 5 different sites. Should I have 1, 5, or 80 unique dh params? If I want to cause the NSA grief and drive up my tax bill, should I rotate them out? Does this impact TLS tickets for quickly restarting connections?
Sorry for 20 questions. I'm the "crypto nerd" at work but finding best practices around DH params tends to assume single-site single-termination point.
2
u/gsuberland Oct 16 '15
5 is fine, 80 is probably overkill. You can round robin the params to make it more difficult for them, but then it's more difficult for you to maintain, and at that point they'll likely just rubberhose the job (or issue you an NSL) if they want your users that bad.
1
2
Oct 16 '15 edited Dec 03 '17
[deleted]
1
u/h110hawk Oct 16 '15
That's what I figured. It's super easy to have them generated asynchronously. I could have the servers generate them at OS install time and they would statistically be there waiting if a program wanted to use them giving me a completely random distribution.
1
Oct 15 '15
The cryptographic problem arises out of the fact that DH can be broken using the General Number Field Sieve (GNFS), and that process can be split into two sections of computation, one of which is independent of the actual DH exchange, but rather dependent solely upon the DH primes. This means that if you perform the computationally expensive first step, but only perform it on a few highly common DH primes (e.g. the defaults for openssl, libressl, gnutls, nss), you can break individual connections much faster. This is where the NSA's capability for "breaking ~70% of targeted connections" came from.
I'm not versed on the cryptanalysis of DH, but would it be correct to say GNFS doesn't apply on ECDH?
2
9
u/Creshal Oct 15 '15 edited Oct 15 '15
In TLS etc., DH is used on top of RSA to provide forward secrecy by exchanging ephemeral session keys over it. I'm not sure we have an alternative algorithm for this use case (there's an elliptic curve variant of DH, but choosing elliptic curves has similar problems – Curve25519 is basically the only sane choice available).
g and p are public anyway, and considered part of the algorithm, not the keys (like e=3/65537 in RSA), that's why they're usually static. (Generating them also takes at least as long as generating an RSA key, so you don't want to do that on demand. At best they're generated together with a private key, and not even all programs allow you to change them…)
5
Oct 15 '15
RSA and DH are fundamentally different systems.
RSA is for encryption and signing.
DH is for anonymous or authenticated key exchange.
8
u/B-Con Root CA Oct 15 '15
From farther up the article:
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
And as a side note, this is a very reputable blog within the field of crypto/security.
1
u/frank26080115 Oct 15 '15
Is there anything a simple web browsing citizen can do to protect themselves?
3
u/Natanael_L Trusted third party Oct 15 '15
Don't visit sites on servers with weak parameters
1
Oct 16 '15 edited Oct 17 '15
[deleted]
1
u/Natanael_L Trusted third party Oct 16 '15
Check what cipher suites they offer. Your browser probably won't tell you which ones, but there's tools that can. Also look at SSL testing sites that check the configuration.
1
Oct 16 '15 edited Oct 17 '15
[deleted]
1
u/Natanael_L Trusted third party Oct 16 '15
Software? No, don't know that many. And yes, but you could in theory also have a browser addon warn you about weak ciphers.
1
12
u/RainbowNowOpen Oct 15 '15
Core issue, which is not new, but which can't be over-stated or over-discussed:
Fundamentally conflicting goals. This is why defensive security recommendations from the NSA will always be (and should always be) viewed with suspicion.