Posted by: Politech
August 20, 2015
Public key cryptography: What is Diffie-Hellman?
When the expansion of electronic communication was becoming foreseeable in the 1970s, researchers in both public and classified environments began to reconsider how a secure message could be sent between two people on a public channel vulnerable to eavesdroppers. Simply put, the challenge is this: encrypting and decrypting a message requires a key. If two people need to exchange encrypted messages over an insecure channel, how can they agree on a key without an eavesdropper on the network intercepting it and decrypting the messages?
One solution is the Diffie-Hellman key exchange. In 1976, researchers from Stanford released the first unclassified paper proposing a public key cryptosystem. Also known as asymmetric key cryptography, public key cryptography uses different keys to encrypt and decrypt. Each party has a public key, which anyone can use to encrypt messages and, if intercepted, does not provide an eavesdropper with any useful information. The encrypted messages are then decrypted with the corresponding secret or private key which is never sent over the network. The public and private keys are mathematically related, but only by a problem so difficult that it would take millions of years to derive the secret key from a strong public key. It later became apparent that Britain’s GCHQ had developed a similar technique one year earlier, but it remained classified until 1997.
Nowadays there are a number of different methods of public key cryptography. The mathematical problem Diffie-Hellman relies on is called the discrete logarithm. It is similar to the RSA method in that both rely on huge prime numbers, but Diffie-Hellman is unique in that it allows both parties to create the same public and private keys without an attacker being able to recreate the steps.
Despite being forty years old, the Diffie-Hellman exchange is still a cornerstone of security on the internet. Specifically, alongside a variation called Elliptic Curve Diffie-Hellman, it is used to provide “forward secrecy” – connections encrypted with a new set of keys each time, so that if the root certificate or one set of keys is stolen, the amount of communications the attacker can decipher is minimised.
The Logjam Attack
A paper by thirteen co-authors was published on 20th May, demonstrating that a significant quantity of websites using Diffie-Hellman for their secure connections are so poorly configured that a moderately resourced attacker could fully decipher intercepted traffic. The attack involves tricking the server into using a weak Diffie-Hellman key, such as of a 512- or 768-bit size. Furthermore, the paper argues that a well resourced adversary like a nation state could decrypt some Diffie-Hellman connections without forcing a downgrade simply because they are configured to use 1024-bit keys by default. Excerpts from the Snowden archive published by der Spiegel are used to show that the NSA’s 2013 budget requests and the architecture in place for cryptanalysis are both consistent with such an attack. The following table shows the frequency at which the researchers encountered the vulnerability:
It is deeply concerning that 8.4% of the most popular HTTPS sites on the internet are vulnerable to the attack. Email servers in particular are hit hard by Logjam, with a staggering 14.8% of SMTP and StartTLS servers – crucial to email privacy – being open to attackers with knowledge of cryptography.
This downgrade-based attack closely resembles March’s FREAK attack against RSA connections. Both FREAK and Logjam take advantage of a relic left over from 90s crypto regulations which outlawed distributing strong encryption outside of the United States. “Strong” is defined here as using a key of 1024-bits or greater. Therefore, “export grade” cipher suits were built into web servers that allowed SSL connections to comply with this regulation. Astoundingly, years after these cipher suits became obsolete, many web servers continued to support export grade encryption. This allowed an attacker sitting between a user and a server to trick the server into using export grade cryptography, which the attacker can then store and decrypt at their leisure.
The FREAK attack only works against the non-forward secret algorithm RSA. Logjam allows a similar downgrade attack against the forward secret Diffie-Hellman method which was thought to be much more secure. In addition to this, the discrete logarithm problem on which Diffie-Hellman is based is more difficult than the factorisation of semi-prime numbers used by RSA.
However, the Logjam attack draws on more than just small key sizes. Diffie-Hellman configurations often use groups of a specific type of prime number called “safe primes”. This means prime numbers for which the following rule is true: where p is a safe prime and q is an ordinary prime, p – 1 = 2q. The purpose of using safe primes is not to increase cryptographic strength as the name might suggest, but to make the key exchange more efficient. To ease the computational load of generating safe primes, pre-existing groups of them exist to be used by servers configured to support Diffie-Hellman. The frequent reuse of these primes allowed the researchers to perform a period of “precomputation” during which the different outcomes of connections using these known primes could be calculated to accelerate decryption in advance. The larger the key, the less feasible this precomputation becomes – hence attacks against 1024-bit keys being the preserve of nation states and 2048- and 4096-bit keys being considered secure.
Therefore, server administrators are advised to make sure export grade cipher suits are disabled and that, at an absolute minimum, Diffie-Hellman keys are set to 1024-bits, though 2048- or 4096-bit keys are preferable by far. The thirteen authors also recommend admins generate their own parameters to frustrate attackers who have precomputed the outcomes of commonly used primes. More information about securely configuring a Diffie-Hellman server can be found here.
An alternative is to use Elliptic Curve Diffie-Hellman (ECDH). In elliptic curve cryptography, smaller keys can offer a high standard of security, with a 256-bit ECDH key being roughly equivalent to a 3072-bit RSA key. This also mitigates the Logjam attack by making precomputation infeasible. However, some cryptologists like Bruce Schneier fear that elliptic curves recommended by NIST may be backdoored by the NSA and therefore favour standard Diffie-Hellman keys of a larger size. Modern web browsers have also taken steps to mitigate the attack from the client side, so make sure to visit https://weakdh.org to see if you’re safe. If you’d like to read more about Logjam without the heavy mathematics of the source paper, co-author Matthew Green has posted such a write up here.