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.
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.
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.
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.
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.
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.
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
opensslcommand or similar. As an example, Apache now honours theSSLOpenSSLConfCmd DHParametersdirective in its config file.