Unexpected Security Flaws in the use of Diffie-Hellman

The miraculous Diffie-Hellman key exchange

Published in 1976, the Diffie-Hellman key exchange demonstrated a method for two parties to generate a shared secret key across a public network where anyone eavesdropping on the entire exchange will have trouble learning the shared secret. The whole exchange can be achieved in 3 messages. The diagram below shows what variables are sent over the public domain, meaning an eavesdropper will know the public variables.

Breaking Diffie-Hellman will require the attacker to compute gab given g, p and ga/gb. An attacker can do the last step that one of sides performs if they can find the secret a or b. However, the key exchange is secure due to the difficulty in reversing the calculation that is done to combine g and a/b (g^a mod p). In mathematics, reversing the calculation is known as solving the discrete logarithm problem. The amount of difficulty in breaking this security is closely related to be the size of the prime number p. The common sizes of primes are 512 bit, 768 bit, 1024 bit and 2048 bit (as larger primes have a disproportional cost of performance to security gain). The problem that the paper and this blog will discuss is how 512, 768 and potentially 1024 bit key exchanges could be broken on the fly given a substantial (and expensive) but plausible amount of pre-calculation on designated prime numbers.

Export grade Diffie-Hellman instead of 'Military Weapons Grade' (Why we use 512 bit)

Around 1990s, the US government declared the intellectual property of some strong encryption methods to be 'military weapons grade', which included Diffie-Hellman key exchanges that used more than 512 bits. As a result, if an algorithm or code was published and reached outside the US, the authors would be committing the crime of 'exporting military grade weapons'. From this, 512 bit Diffie-Hellman is known as DHE-EXPORT as it can be export. These restrictions no longer apply, but the 512 bit system is in use in some cases for the purpose of backwards compatibility.

Breaking Diffie-Hellman (through pre-computation)

As the design of Diffie-Hellman is based around the difficulty of solving the discrete log problem (reversing the calculation that each side makes), the best method of attack for an eavesdropper is to do just that. One of the most efficient algorithms to perform this calculation is known as the number field sieve (NFS) algorithm. It takes a very long time to compute this algorithm for the large prime that are used today, meaning it is impossible to use it in real time. What the researchers have shown is that they are able to pre-compute using a specific prime number p, and after 3 steps, create a logarithm database that stores the results of the computations and allows a 4th step to take the input of a shared key in the Diffie-Hellman exchange (gb/ga) and find the solution in around a minute by looking through the database. This means that not only is it possible to break new key exchanges in effectively real-time, but the pre-computation can be transferred, kept or sold.

This method of pre-computation to create a database for a single prime number is still a very long process. Researchers with 'academic-level' computational resources managed to solve for a 512 bit prime within a week back in 2015, and with modern hardware and improved software, they can compute a prime in just 2 days. Their 2015 system was made up of 2000-3000 microprocessor cores. The size of this would be beyond an individual but well within the range of larger academic teams and certainly nation states. Beyond 512 bits, the researchers also determined that 768 bit primes could be broken by academic teams with even more time for each prime, and they concluded that given millions in funding, nation states could break a single 1024 bit prime every year. There is evidence from the leaks on the NSA, that they had cracked 1024 bit Diffie-Hellman allowing them to decrypt some VPN traffic.

Just use a different prime...

The pre-computations take a long time and only give you a database for a single prime number, but the widespread implications of this are severe when you begin to look at how most servers implement Diffie-Hellman in practice. In a 2015 scan of 529,000 HTTPS sites, 68.3% were found to use Diffie-Hellman, and 8.4% used 512 bit (DHE-EXPORT). Of these sites that use 512 bit primes, 82% used the same prime, and another 10% used a second prime. They are the default for Apache and 'mod_ssl' respectively. This means that an attacker could perform pre-calculation on just 2 primes, and be able to attack around 92% of websites that use 512 bit Diffie-Hellman.

Safe primes are important in order to maintain security, which is defined as a prime where (p-1) / 2 is also a prime. Finding safe primes that are of the size required can be computationally difficult, which is why most implementations use a publicly known safe prime, such as those in the Oakley groups. As a result, most implementations of Diffie-Hellman have ended up using the same primes meaning that this pre-computation attack, although initially computationally expensive, can have widespread use in the many servers that use the most common primes.

For efficiently, servers typically use the same secret value for all their key exchanges in order to avoid time calculating based on new private parameters. This should not have a significant effect of security as the client still uses a new secret value every time (however this can be used as discussed later). This use of at least on new secret value every time is call being 'ephemeral', and enables forward secrecy. Some servers such as Microsoft change this value every 2 hours, but multiple key exchanges are still done using the same server-held secret value.

Downgrading higher bit implementations back to 512 bit

In Transport Layer Security (TLS), a handshake occurs between the client and the server to decide which cryptographic system will be used i.e. regular DHE or DHE-EXPORT. A client sends their list of supported methods which allows for a Man in the Middle attack (MITM) to downgrade their connection to use DHE-EXPORT (which is 512bit) every time. This is done by hijacking the client's message to ask for DHE-EXPORT to be used instead of DHE, and then simply eavesdropping on the parameters (g, p and gb) which the sever sends to the client for the key exchange. Given the p which the attacker has used in the pre-computation, and the g and gb values, it is possible to find the value of b within a minute or so. The researchers were able to perform this within an average of 70 seconds (ranging from 34 - 206 seconds). When b is known, the attacker can block the server, or continue to passively eavesdrop and wait for the client to send ga, and then find the secret private key gba that is used for encryption/decryption of messages for the rest of the session.

Some systems have time-outs that require the MITM do the computation quickly and potentially in under the minute that is possible with the pre-computation method. In this case, the fact that some servers use the same secret value b for multiple different handshakes, an attack can hijack one handshake to calculate b, and then use b for future handshakes. However, many systems have a workaround such as Firefox's alerts that reset the timer, and some systems have a long or non-existent time-out for responses.

For attacks on 768 bit, and potentially 1024 bit, where pre-computation has been done (with a larger cost of time and resources), the resulting lookup of the database that is create will take even longer than a database for a 512 bit prime. So utilising the method of cracking the server's private key in one handshake that will time-out, and then using the private key to crack a new handshake in real-time is important.

Summary of the Attack

Step 1: Pre-compute a given prime number that the target server uses, for 512 bit primes, this can be done in just a few days using academic level resources. For 1024 bit primes, a nation state could reasonably crack one prime in a year. The result of this pre-computation is a logarithm database for the given prime.

Step 2: Start a Man in the Middle attack in order to hijack the clients request to use regular DHE, and change it to request 512 bit DHE-EXPORT if possible.

Step 3: Read the server's response that includes the values g, large prime p, and server public key gb.

Step 4: Use values g and gb to lookup the pre-computed database and find the corresponding server secret value b. This takes around a minute for 512 bit primes when using academic level resources and may time-out a connection.

Step 4.5: If the MITM attack failed due to a time-out, use the now calculated b value in a new handshake.

Step 5: Read the clients calculated ga values and combine it with the known b value to find the secret key gab that was exchanged. Now you can decrypt messages until the session ends.

References

Subject Research Paper: "https://doi.org/10.1145/2810103.2813707",

Computerphile youtube:
https://www.youtube.com/watch?v=NmM9HA2MQGI&
https://www.youtube.com/watch?v=Yjrfm_oRO0w

Textbook: "Network Security, Private Communication in a Public World" p.g. 166-167, Second Edition, Charlie Kaufman, Radia Perlman, Mike Speciner

https://tls.mbed.org/kb/cryptography/ephemeral-diffie-hellman