# What is the current security status of Diffie-Hellman key exchange?

There is a web site weakdh.org, whose name alone would certainly cause some feeling of uncertainty in using DH among people who are not experts IMHO. Could some knowledgeable person kindly say something of the current security status of DH, i.e. what are the major precautions, if any, that one has to be aware of in applications of DH today?

I'm especially interested in the minimum key size needed for use in SSL, but will appreciate additional information.

• Question is very broad. No need to worry about DH as a whole. Ask a specific question about your use case if you want a more focused response. – Neil Smithline Jan 31 '16 at 18:00
• @NeilSmithline: I suppose the most important issue is the minimum key size that is currently deemed necessary. – Mok-Kong Shen Jan 31 '16 at 18:11
• In what context? SSL? Other? – Neil Smithline Jan 31 '16 at 18:20
• @NeilSmithline: SSL. Fine, if you care also to mention other contexts. – Mok-Kong Shen Jan 31 '16 at 18:22
• It might be insecure at some point in the far future, read Post-quantum cryptography – Francisco Presencia Feb 1 '16 at 5:02

The weakdh.org Web site is about the Logjam attack. Contrary to what the Web site name may suggest to the unwary, this is not about DH being weak; it is more about doing things weakly when using DH.

Diffie-Hellman works in a multiplicative subgroup of integers modulo a given prime p. To do some DH, you use some DH parameters which are:

• p : a big prime, called the "modulus"
• q : a divisor of p-1, called the "subgroup order"
• g : an integer modulo p of order q (this means that the smallest integer k > 0 such that gk = 1 mod p is k = q)

For DH to be safe, you need the following:

• p must defeat attempt at discrete logarithm through Index Calculus. This means that p must be large enough, and also must not have any "special structure" such as being very close to a power of 2, because such structures allow for improvements in Index Calculus. It so happens that size requirements for DH are about the same as the size requirements for RSA, though the underlying reason for that is intricate and partly coincidental. So, basically, use a random p of 2048 bits, and you will be fine.

• q should be prime or have a prime divisor whose size is enough to defeat generic algorithms for discrete logarithm. If the size (in bits) of the largest prime divisor of q is z, then generic algorithms have a cost in 2z/2. For best results, arrange for q to be a prime of 256 bits or more.

• Systems that use the parameters to perform a DH key exchange must generate a random integer between 1 and q-1 uniformly, using a cryptographically strong source of randomness, of course. If q is prime and larger than 256 bits, it suffices to choose a 256-bit random value to achieve 128-bit of security. However, if q is not prime, things are more complex: if q has size r bits, and the largest prime divisor of q has size e bits, and e ≥ 256, then one may choose a random value x of size r-(e-256) bits to get the usual "128-bit security".

When p is a so-called "safe prime", then p = 2⁠r+1 for a prime r, so for any generator g that is not 1 or p-1, the order of g will be either r or 2⁠r, so it suffices to generate DH secret keys x as random 257-bit values. The "safe primes" are not actually any safer than other primes, except for that point: they tolerate the choice of relatively small DH secret keys for any generator.

• Last but not least, DH is a key exchange algorithm that does not, inherently, provide authentication or confidentiality. DH is "safe" only when used within a protocol that uses DH and other algorithms with proper integration to achieve such sought after characteristics as data confidentiality and integrity.

Speaking of which, some (many) SSL/TLS implementations did things improperly, in that they gladly accepted to do DH with weak parameters, in particular a 512-bit modulus. The protocol itself is suboptimal in its handling of DH because the `ServerKeyExchange` message allows the server to send the DH parameters p and g to the client, but not q, leaving the client a bit in the dark. Thus, the client must either "play safe" and generate its key in the full 1..p-1 range, or try to use a shorter exponent (say, 256 bits, not 2048) for a reduced computational cost, but possibly at risk of weakness in case the subgroup order q is not prime. A better design would have allowed the server to send the value of q and the size of the biggest prime divisor of q. In that respect, the ECDHE cipher suites of SSL/TLS (DH translated to elliptic curves) have a better design.

For a practical answer if you are configuring your SSL/TLS server: you should use a modulus of at least 2048-bit, and a generator g such that the order of g is a prime q of at least 256 bits; alternatively, you may use a modulus p which is a "safe prime" (the order of g will then be either a very big prime, or twice a very big prime, which is almost as good). Some people feel safer when they generate their DH parameters "themselves"(*) instead of reusing existing values; if that's what it takes to allow you to sleep at night, then do it.

(*) People never generate their DH parameters themselves; they use a computer. But we are talking psychology here anyway.

• @xdhmoore: real programmers edit inodes by hand, with a magnet. Also referenced by xkcd.com/378. – Peter Cordes Feb 1 '16 at 5:28
• Some principal questions (should also be of interest for other schemes) on recommended minimum key size: (1) Who determines what key sizes are ok? Any international institutions like ISO responsible for that issue? (2) Which are the critiria employed for such decisions, noting especially that the capacities of mighty adversaries couldn't be dependably estimated and that there are probabilities of new breakthroughs in analysis and unknown 0-days. (3) What is the "minimum value" that the minimum key size is intended to protect (i.e. e.g. for a transaction for a refrigerator or for 100 Airbus)? – Mok-Kong Shen Feb 1 '16 at 12:30
• @Mok-KongShen: see keylength.com for discussion and pointers for all your questions. – Thomas Pornin Feb 1 '16 at 13:17
• My main point is: There are recommendations by experts and government institutions. But how much trust should one have towards these in the era following revelations of Snowden and others? Also IMHO unsatisfying for the commen users is: A certain earlier recommended key size was found to be insufficient due to some discovered causes and one is told that from now on one should use another larger key size and everything would be ok. But isn't that also a solid testimony of the fact that in all the time during which the old key size was in vogue the communications of the users were insecure? – Mok-Kong Shen Feb 1 '16 at 16:20

First of all, don't panic, Diffie-Hellman's algorithm is totally fine if used right (with right set of parameters).

Let me explain some preliminaries:

1. Whats SSL/TLS Protocol?

It's the underlying protocol used in HTTPS that prevents eavesdropping and tampering of the data sent in the channel. It uses diffie-hellman protocol to exchange keys between client and server.

1. What are cipher suites?

SSL/TLS protocol was made to be extensible, it is capable of using several algorithms for encrypting and signing the data, these interchangable packages are called cipher suites, you can have TLS_RSA_WITH_RC4_128_MD5 as your cipher suite which uses RSA for key exchange, RC4 for bulk data encryption and MD5 for signature.

Whats LogJam?

Now there are some of these cipher suites called EXPORT-GRADE (e.g TLS_RSA_EXPORT_WITH_RC4_40_MD5), they are intentionally weak due to US export regulations on cryptographic algorithms. These cipher suites have short key length and can easily be broken, if someone doesn't disable them on their server and the client uses them, the shared keys can be leaked and the encryption can be broken by an attacker. There was an attack on RSA named FREAK and one on Diffie-Hellman named LogJam.

Now if the client can be forced to use EXPORT-GRADE cipher suites and if the server happens to support them, an attacker can do a MITM attack by breaking the diffie-hellman algorithm due to the use of short key length. This is what LogJam is about.

There was also another vulnerability where some web servers used default diffie-hellman parameters of length 1024 which is also broken.

Note: it's all about parameters used in the algorithms, there's nothing wrong with Diffie-Hellman algorithm itself.

What to do now?

If you use modern browsers and keep them updated, by now they already prevent this attack from happening.

If you are running a webserver make sure you're using the best practices for configuring your SSL/TLS enabled versions and the underlying cipher suites.

As for the minimum key size, 1024 bits are out of reach of normal attackers, but not nation state. 2048 bit is safe. You could also use ECDHE which is diffie-hellman over elliptic curve and basically yields you the same level of security with shorter key length.