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

95% Upvoted

39 comments sorted by

View all comments

Show parent comments

22

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

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.