PolarSSL is now part of ARM Official announcement and rebranded as mbed TLS.

Diffie-Hellman backdoors

Diffie-Hellman backdoors

Several recent academic papers studied the possibility of backdoored Diffie-Hellman parameters and their occurance in the wild. This article gives a quick overview about this threat.

Diffie-Hellman key agreement

The Diffie-Hellman (DH) key agreement is the first asymmetric cryptographic primitive. It is part of the TLS protocol; the ephemeral variant (DHE) even provides forward secrecy in the ciphersuites that use it. The security of the DH key agreement relates to the discrete logarithm problem over an algebraic group. The TLS protocol uses two main types of groups with the DH key agreement: subgroups of finite fields (prime fields) and subgroups of elliptic curves. In both cases, the participants should validate the cryptographic parameters before accepting and using the peer's group and public key.

In the case of elliptic curve Diffie-Hellman (ECDHE), this validation can be done during a TLS handshake, and Mbed TLS does it automatically. Therefore, the remainder of the article only discusses the finite field version of the DH key agreement (FFDHE).

The finite field is defined by the prime p (in other words, all the computations are performed modulo p), the subgroup by the generator g (the members of the group are of the form g^x for some integer x). The private key k is an integer, and the public key X=g^k is sent to the peer. Both parties calculate the secret s=Y^k using their own private key k and their peer's public key Y.

If the group is too small (g^q=1 holds for some small integer q) or if it is of composite order (the smallest nontrivial q for which g^q=1 holds is not a prime), then an adversary who knows the public parameters can learn the secret. If the private key k is too short or the field (i.e. the prime p) is too small, then again, the key agreement based on them is weak. You can prevent all of these problems by choosing the parameters carefully.

Parameter validation

In a TLS connection, the server decides about the group used during the key agreement. Therefore, if the server uses weak parameters, the adversary can decrypt the whole session. If the client detects that the parameters are weak, it can terminate the connection.

To fully validate the parameters, check whether:

  • The field is a field (p is prime).
  • The field is large enough (p is at least 2048 bits long NIST).
  • The order of the subgroup is valid (p-1 is divisible by q).
  • The subgroup is large enough (q is at least 224 bits long NIST).
  • The subgroup is of prime order (q is prime).
  • The generator is a member of the subgroup ( 1 < g < p-1 and g^q = 1).
  • The peer's public key is a member of the subgroup ( 1 < Y < p-1 and Y^q = 1).

However, checking all of these is expensive computationally and not practical. In addition, in TLS versions prior to 1.3, there is no way for the client to know about q and thus to fully validate the requirements unless p is a safe prime. (In case p is a safe prime, then q can be deduced if p is known: q = (p-1)/2).

Even if the client could validate the parameters fully, there is an issue with the Special Number Field Sieve algorithm. The prime can be intentionally constructed so that the SNFS is applicable to it. The more suitable the prime is for the SNFS, the easier it is to detect this backdoor. It is possible to find a balance where detecting the backdoor is as hard as breaking a safe prime of the same size, but the SNFS attack is still feasible for certain modulus sizes.

Why would a server use weak parameters?

In the best scenario, using weak parameters can be just a mistake. However, it can also be the result of a sabotage or an arrangement with a third party. (Governments love to demand backdoors on products and services in the name of national security.) There are numerous examples in the wild for non-safe prime moduli or for moduli that are not even prime, and nobody seems to know why and how those values got there.

What can we do?

As explained above, there are backdoors that can't possibly be detected on the client side in TLS protocol versions prior to 1.3 and any effort to do so is computationally expensive. Therefore, Mbed TLS clients assume that the modulus is a safe prime and perform only the validation necessary for this case. If a Diffie-Hellman backdoor on the server side is part of your threat model, consider disabling FFDHE key exchange on the client side for TLS protocol versions prior to 1.3.

On the server, use safe prime moduli to avoid weaknesses (especially if your application is re-using Diffie-Hellman exponents for short periods of time to increase performance). If you use public moduli, make sure that they are random and whoever generated them didn’t construct them with a backdoor. You can only verify this if: - Their seeds are published. - They are generated with the digits of some well known constant (for example e or pi).

References

  • Dorey, Kristen, Nicholas Chang-Fong and Aleksander Essex. “Indiscreet Logs: Persistent Diffie-Hellman Backdoors in TLS.” IACR Cryptology ePrint Archive 2016 (2016): 999.
  • Valenta, Luke, David Adrian, Antonio Sanso, Shaanan Cohney, Joshua Fried, Marcella Hastings, J. Alex Halderman, and Nadia Heninger. "Measuring Small Subgroup Attacks against Diffie-Hellman." Proceedings 2017 Network and Distributed System Security Symposium, 2017. doi:10.14722/ndss.2017.23171.
  • Fried, Joshua, Pierrick Gaudry, Nadia Heninger, and Emmanuel Thomé. "A Kilobit Hidden SNFS Discrete Logarithm Computation." Lecture Notes in Computer Science Advances in Cryptology – EUROCRYPT 2017, 2017, 202-31. doi:10.1007/978-3-319-56620-7_8.
  • Wong, David. "How to Backdoor Diffie-Hellman." IACR Cryptology ePrint Archive 2016 (2016): 644.

Like this?

Section:
Blog

Author:


Published:


Last updated:
Oct 5, 2018

Sharing:


Want to stay up to date?

To sign up for Mbed TLS news, log in to or create an Mbed account and update your marketing preferences.