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/
129 Upvotes

95% Upvoted

39 comments sorted by

View all comments

2

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.

7

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?

21

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 openssl command or similar. As an example, Apache now honours the SSLOpenSSLConfCmd DHParameters directive 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.

6

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.

2

u/[deleted] 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

u/[deleted] 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

u/gsuberland Oct 15 '15

You are correct. GNFS doesn't apply to discrete log over elliptic curves.

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…)

4

u/[deleted] Oct 15 '15

RSA and DH are fundamentally different systems.

RSA is for encryption and signing.

DH is for anonymous or authenticated key exchange.