Weak keys and prime reuse make Diffie-Hellman implementations vulnerable

Posted by   Virus Bulletin on   May 20, 2015

'Logjam' attack possibly used by the NSA to decrypt VPN traffic.

A group of researchers have discovered a number of vulnerabilities in the way the Diffie-Hellman key exchange protocol is deployed and have demonstrated an attack (dubbed 'Logjam') that exploits these vulnerabilities.

Diffie-Hellman is used by two entities (typically referred to as Alice and Bob) to agree on a secret key over a public channel. This key can then be used to encrypt and decrypt data using a much faster symmetric key algorithm, such as AES, 3DES or the now obsolete RC4. The protocol is widely used, for instance in SSL/TLS.

To use the protocol, Alice and Bob agree on a (large) prime number, p, and a 'base', g, which is a number taken modulo p and which satisfies certain conditions.

Alice and Bob choose secret numbers, a and b, respectively. Alice computes ga, while Bob computes gb; these results are then exchanged over a public channel. Alice then uses her secret key a to compute (gb)a, and likewise, Bob computes (ga)b. Both numbers are equal to gab, which is used as a secret key.

If p is large enough and satisfies some extra conditions (which, incidentally, the paper shows aren't always met), it is impossible for an adversary to compute a (or b) given ga (or gb). This is because there is no efficient way to solve the discrete logarithm problem.

One of the problems is that many clients and servers still support Diffie-Hellman using prime numbers that aren't large enough and it is possible for someone with a man-in-the-middle position to force the connection to downgrade to these keys. In particular, they support 512-bit 'export-grade' keys. The use of export-grade cipher suites dates back to the 1990s, when the US government tried to prevent the export of strong encryption technology. Earlier this year, the FREAK vulnerability showed how such suites had come back to haunt us.

On top of this, many of these servers use one of only two fixed primes for 512-bit Diffie-Hellman. In their paper (pdf), the researchers demonstrate how they can use this to perform a larger number of 'precomputations' on those primes. These precomputations then help them to solve the discrete logarithms in real time.

The median time of 90 seconds to break keys is enough to effectively break TLS connections that use 512-bit Diffie-Hellman for the key exchange, thus breaking both confidentiality and the integrity of the connection. As a proof-of-concept it was used against www.fbi.gov (which has since been patched).

Attacking 768- and 1024-bit keys

The paper then looks at Diffie-Hellman implementations that use 768- or 1024-bit keys. The authors estimate that, using Logjam, breaking 768-bit keys is feasible with academic power, while breaking 1024-bit keys is not beyond the reach of the budgets of nation states.

Again, it is crucial for the attacker that the same prime is used by many implementations: this means that the attack scales orders of magnitude better, and might make it more interesting than the much cheaper FREAK attack.

Of course, there is always the million-dollar question: did the NSA know about the attack? Depending on your view of the agency, the answer suggested in the paper is either worrying or reassuring: they probably did.

Based on documents leaked by Edward Snowden and published by Der Spiegel last year, it is believed that the agency and its Five Eyes allies can decrypt IPsec connections on a large scale and subsequently read VPN traffic. IPsec uses Diffie-Hellman for the key exchange.

Indeed, an Internet-wide scan showed that around two-thirds of the VPN servers that use IPsec use one particular 1024-bit prime to exchange keys. Moreover, the technical details explained by the NSA in one of its classified slides match those of Logjam.

If the NSA did indeed know about Logjam, there is some historic irony: the Diffie-Hellman protocol was invented independently by GCHQ a year before Whitfield Diffie and Martin Hellman published their 'New Directions in Cryptography' paper (pdf) in 1976.

Other vulnerable servers

Apart from web and VPN servers, the researchers also found a significant number of mail servers (using STARTTLS, POP3S and/or IMAPS) that were supporting export-grade Diffie-Hellman keys. Moreover, more than one in four SSH servers use a single 1024-bit prime for the Diffie-Hellman key exchange.

The developers of many of the pieces of client and server software that were vulnerable were notified of the vulnerability prior to publication of the research. As a result, patches have already been or will soon be rolled out.

For those who determine the choice of cipher suites in software or hardware, the paper comes with three recommendations: avoid fixed prime numbers; disable support for export-grade ciphers; and transition to the elliptic curve Diffie-Hellman (ECDH) key exchange algorithm.

As it happens, I will be giving a presentation on elliptic curve cryptography in general, and ECDH in particular, at BSides London on 3 June. The talk is aimed at security researchers but doesn't require any mathematical background.



Posted on 20 May 2015 by Martijn Grooten
twitter.png
fb.png
linkedin.png
hackernews.png
reddit.png

 

Latest posts:

VB2018 paper: The modality of mortality in domain names

Domains play a crucial role in most cyber attacks, from the very advanced to the very mundane. Today, we publish a VB2018 paper by Paul Vixie (Farsight Security) who undertook the first systematic study into the lifetimes of newly registered domains.…

VB2018 paper: Analysing compiled binaries using logic

Constraint programming is a lesser-known technique that is becoming increasingly popular among malware analysts. In a paper presented at VB2018 Thaís Moreira Hamasaki presented an overview of the technique and explained how it can be applied to the…

Virus Bulletin encourages experienced speakers and newcomers alike to submit proposals for VB2019

With a little less than a month before the deadline of the call for papers for VB2019, Virus Bulletin encourages submissions from experienced speakers and newcomers alike.

VB2018 paper: Internet balkanization: why are we raising borders online?

At VB2018 in Montreal, Ixia researcher Stefan Tanase presented a thought-provoking paper on the current state of the Internet and the worrying tendency towards raising borders and restricting the flow of information. Today we publish both his paper…

The malspam security products miss: banking and email phishing, Emotet and Bushaloader

The set-up of the VBSpam test lab gives us a unique insight into the kinds of emails that are more likely to bypass email filters. This week we look at the malspam that was missed: banking and email phishing, Emotet and Bushaloader.

We have placed cookies on your device in order to improve the functionality of this site, as outlined in our cookies policy. However, you may delete and block all cookies from this site and your use of the site will be unaffected. By continuing to browse this site, you are agreeing to Virus Bulletin's use of data as outlined in our privacy policy.