Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice

Paper here: https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf

The paper presents interesting findings on security issues in the Diffie Hellman Key Exchange method which allows senders and receivers to generate secret keys for message encryption. It also provides forward secrecy in TLS’s ephemeral modes. The paper asserts that the Diffie Hellman Key Exchange method for 1024-bit groups or under is not as secure as they were believed to be. Around 82% of servers in total over the internet and 8.4% of the top million websites were using a single 512-bit group making them vulnerable to Logjam attack. The authors carried out the Logjam attack and ran computations for a week to come up with the statistics given above. The paper further even pulls up leaked NSA diagrams (from Snowden’s leak) and discusses how the agency might have used a similar method to decrypt VPN traffic in a passive manner. The paper concludes by strongly recommending that modern TLS servers only allow DH groups of 1024-bit or higher and Elliptic Key approach be used with Diffie-Hellman.

The authors presented that 512-bit DH groups are fairly easy to compute using discrete log algorithms. To carry out the attack, they did a week-long pre-computation and concluded that they could calculate any discrete logarithm in 512-bit groups in under a minute on two 18-core Intel Xeon E5-2699 CPUs and 128 GB of RAM machine, effectively breaking the encryption. Diffie Hellman, as claimed, is typically implemented with prime fields and large group orders. Any attacker who can find the discrete log x from y = gx mod p can easily find the shared secret. An efficient discrete log algorithm called Near Field Sieve was used to do these week-long pre-computations which had four steps: polynomial selection, sieving, matrix and logging, and finally, deducing log of the target. Computations helped reduce cryptanalysis time by an exponential percentage effectively reducing it to minutes on high-end systems. Logjam attack which allows an attacker to downgrade a TLS connection to export-grade Diffie-Hellman on any server that supported DHE_EXPORT (or by coercing to use DHE_EXPORT) was discussed since effectively downgrading a connection to use 512-bit DH groups would help an attacker then use NFS to compute variable primes and therefore, the shared secret. The observation lead the authors to believe and further theorize if the same approach could be used in groups of 768 and 1024-bits.

Before the paper rolled out, 82% of servers in total over the internet and 8.4% of the top million websites on Alexa were using single 512-bit DH groups. This presented as a shock since the better part of more than three-quarters of servers in the entire world might be vulnerable to the attack. The paper also serves as significant proof to counter the belief that 512-bit groups are infeasible to break by cryptanalysts. It also brought light to the importance of using previously ignored approaches like the Elliptic Curve Diffie-Hellman which are now being readily used by many popular companies. The attack mentioned in the paper also significantly reduces the time complexity in a similar FREAK attack which took attackers hours to downgrade a regular RSA exchange (by which there is a huge possibility server generates a fresh ephemeral key). The paper further claims that a small number of fixed or standardized groups are used by millions of servers. Thus, performing precomputation for a single 1024-bit group would allow passive eavesdropping on 18% of popular HTTPS sites, and a second group would allow decryption of traffic to 66% of IPsec VPNs and 26% of SSH servers.

Findings in the paper imply a massive threat to privacy. Cryptography exists to provide users apprehension-free internet usage. By analyzing the Snowden leak, it was brought to attention that NSA may have been decrypting internet traffic including VPNs by passively eavesdropping, rendering privacy useless since they have the resources to effortlessly downgrade even 768 and 1024-bit DH groups. By the medium of this freely accessible paper, the authors encouraged cyber awareness and encouraged corporate security teams to use better DH methods and stronger bit groups. As a result, the majority of the browsers rolled out patches for Logjam attack. Thereafter in 2017, IETF published RFC 8270 recommending that SSH’s minimum DH modulus size should be 2048 bits long.

References:

[1] https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

[2] https://en.wikipedia.org/wiki/Logjam_(computer_security)

[3] Highlights - https://jhalderm.com/pub/papers/weakdh-cacm19.pdf