Home » Articles » Cryptanalytic Breakthrough: What Are Diffie-Hellman and the Logjam Attack?
Click Here To Hide Tor

Cryptanalytic Breakthrough: What Are Diffie-Hellman and the Logjam Attack?

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:

logjam

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.

3 comments

  1. Given the totality of empirical evidence available, as well as the effective absence of any credible alternative explanations for the many ways in which selection of NIST curves vary from well-established, credibly robust methods for curve generation and validation, it is both reasonable and accurate to state that the NIST curves are backdoored.

    Whether that feature is being utilised to enable current, in-the-wild attacks on ECC cryptosystems making use of the NIST curves remains an open question – as does the identity of any attackers doing so. There are assumptions, and some potentially dispositive data points, to be found but none are enough to support a strong statement of conclusion in these matters.

    This is not the case, to repeat, when it comes to the question of the reliability of the NIST curves when faced with attacks made possible via the (highly secretive, and lacking in any non-malicious explanation worth considering as anything other than a form of dark humour) process used to generate their fundamental operational parameters.

    Put another way, NIST ECC is backdoored. This is a fact, with ample empirical data supporting its factual status. ECC systems using NIST curves are, therefore, themselves backdoored and cannot be considered secure in production deployments.

    It might be true, as a result of some strange confluence of prior conditions and circumstantial coincidences, that these backdoors aren’t being used – or are being used sparingly, or only by certain attackers against a well-defined subset of targets. Occam argues otherwise, and until evidence exists to contradict the lest-complex explanation (viz, the backdoors were placed there in order to allow access for the NSA and thus the NSA is now using those carefully-engineered capabilities to enable broad-scale cryptanalytic successes in the wild against such systems) it is logically reasonable to avoid using these specific examples of ECC technology in systems that require genuine security confidence.

    Note that this has nothing to do with any claims of macro-class flaws in ECC as a general cryptographic class of primitives. Indeed, curve families such as Brainpool – and, even more so, individual curves such as c25519 – are widely regarded as both robust against any such “magic parameter” trickery inherent in their ontological parameters, and more than credible alternatives to non-ECC systems for asymmetric key generation & real-life usage in production systems architectures.

    There is a point at which treating datum with overwhelming empirical support and broad subject-matter expert consensus as mere allegations or matters of personal opinion is, itself, a form of mendacity. This may be intentional – as in cases where false “controversy” is created in order to blur otherwise-settled matters of factual consensus – or it may (as is almost certainly the case in the article above) simply reflect the difficulty inherent in attempting to digest a specialised field sufficiently to be able to distinguish between substantive matters of ongoing debate, and settled questions.

    Either way, the underlying facts remain facts; in this case, NIST curves are backdoored whether we state this fact bluntly as such, or whether this fact becomes obscured by layers of unnecessary – and inaccurate – hedging, doubt-expression, and prevarication.

    Cheers,

    ~ cryptostorm private network

  2. Even the highest level encryption currently used 4096 bit has been cracked by Daniel Genkin &Adi Shamir (who co-invented RSA)using a side channel attack with a microphone by listening to cpu frequency during decryption. For more info check this link out:
    http://www.extremetech.com/extreme/173108-researchers-crack-the-worlds-toughest-encryption-by-listening-to-the-tiny-sounds-made-by-your-computers-cpu

  3. pattern_juggled

    Given the totality of empirical evidence available, as well as the effective absence of any credible alternative explanations for the many ways in which selection of NIST curves vary from well-established, credibly robust methods for curve generation and validation, it is both reasonable and accurate to state that the NIST curves are backdoored.

    Whether that feature is being utilised to enable current, in-the-wild attacks on ECC cryptosystems making use of the NIST curves remains an open question – as does the identity of any attackers doing so. There are assumptions, and some potentially dispositive data points, to be found but none are enough to support a strong statement of conclusion in these matters.

    This is not the case, to repeat, when it comes to the question of the reliability of the NIST curves when faced with attacks made possible via the (highly secretive, and lacking in any non-malicious explanation worth considering as anything other than a form of dark humour) process used to generate their fundamental operational parameters.

    Put another way, NIST ECC is backdoored. This is a fact, with ample empirical data supporting its factual status. ECC systems using NIST curves are, therefore, themselves backdoored and cannot be considered secure in production deployments.

    It might be true, as a result of some strange confluence of prior conditions and circumstantial coincidences, that these backdoors aren’t being used – or are being used sparingly, or only by certain attackers against a well-defined subset of targets. Occam argues otherwise, and until evidence exists to contradict the lest-complex explanation (viz, the backdoors were placed there in order to allow access for the NSA and thus the NSA is now using those carefully-engineered capabilities to enable broad-scale cryptanalytic successes in the wild against such systems) it is logically reasonable to avoid using these specific examples of ECC technology in systems that require genuine security confidence.

    Note that this has nothing to do with any claims of macro-class flaws in ECC as a general cryptographic class of primitives. Indeed, curve families such as Brainpool – and, even more so, individual curves such as c25519 – are widely regarded as both robust against any such “magic parameter” trickery inherent in their ontological parameters, and more than credible alternatives to non-ECC systems for asymmetric key generation & real-life usage in production systems architectures.

    There is a point at which treating datum with overwhelming empirical support and broad subject-matter expert consensus as mere allegations or matters of personal opinion is, itself, a form of mendacity. This may be intentional – as in cases where false “controversy” is created in order to blur otherwise-settled matters of factual consensus – or it may (as is almost certainly the case in the article above) simply reflect the difficulty inherent in attempting to digest a specialised field sufficiently to be able to distinguish between substantive matters of ongoing debate, and settled questions.

    Either way, the underlying facts remain facts; in this case, NIST curves are backdoored whether we state this fact bluntly as such, or whether this fact becomes obscured by layers of unnecessary – and inaccurate – hedging, doubt-expression, and prevarication.

    Cheers,

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Captcha: *