Widespread DH Implementation Weakness: Conspiracy or Ignorance?

September 18, 2007 by Adam Bozanich

While developing an implementation of IKE for our platform, I noticed an astonishing behavior in the servers I was testing against: Not a single IKE implementation, which included products from the biggest names in network infrastructure, were validating the Diffie-Hellman public keys that I sent. A consequence of this is that any deployment of these servers will allow the disclosure of secret information when a peer is in collusion with a passive attacker.

The Diffie Hellman (DH) key exchange is a commonly used protocol which enables two entities to establish a shared secret key. The key is considered secret because it is computationally difficult for an observer of the communications between the two entities to calculate its value. The DH secret is typically used to generate encryption keys for symmetric cipher algorithms which encrypt traffic between the two parties.

A basic DH exchange goes as follows:

  • Party A and party B publicly agree to use parameters p and g during the exchange. P is a large prime number and g is a primitive root modulo p.
  • Party A generates a random value S_a, computes K_a = g^(S_a) mod p and sends K_a to B. Party B generates a random value S_b, computes K_b = g^(S_b) mod p and sends K_b to A.
  • Party A computes K_s = (K_b)^(S_a) mod p. Party B computes K_s = (K_a)^(S_b) mod p.

K_a and K_b are the public keys of party A and party B, and the computed shared secret is K_s. For most cases, it is difficult for an attacker to derive K_s if they only know the values (p,q,K_a,K_b).

There are, however, a number of values that a public key can have which nullify the secrecy of K_s. If one party sends a public key with a value of either zero or one, the other party will compute a value of zero or one for K_s, respectively. In other words, a passive attacker will know the value of the secret key if a public key of zero or one is observed. As will be discussed later, this property has serious negative impact on the security of the DH key exchange protocol.

This vulnerability in the Diffie Hellman key exchange can be mitigated by validating the received public key. The method of validation is explained in the NIST’s “Recommendation for Key Management”. Using the same symbols as we have above, and considering the case where party B has received party A’s public key, the NIST recommendations (section 5.6.2.4) are as follows:

  • Verify that 2 <= K_a <= p - 2
  • Verify that (K_a)^g = 1 (mod p)

Similar recommendations for validation can be found in RFC 2631, ANSI X9.42and RFC 2412

If an implementation of the DH key exchange does not validate the public key received, it is leaving itself open to a number of attacks. In the paper “Key Agreement Protocols and their Security Analysis”, Simon Blake-Wilson, Don Johnson and Alfred Menezes formalize the requirements of a secure key agreement protocol. One of the desirable attributes of a key agreement protocol is as follows:

Unknown key-share: Entity i cannot be coerced into sharing a key with entity j without i‘s knowledge, ie, when i believes the key is shared with some entity l != j.

We can see that this attribute does not hold for DH implementations which do not validate public keys. An entity can be coerced into sharing the secret key with any entity that observes the transmission of the public keys. There are a number of real-world scenarios where an unknown key-share completely undermines the legitimacy of networking infrastructure which is designed to provide high security.

IKE is a variant of ISAKMP and is used to establish security associations (SA) between two entities. The SA is a set of parameters which are used to secure IP communications (IPSec). IKE uses the DH key exchange to establish a shared secret which is then used to derive keying material for the encryption of both IKE and IPSec traffic.

IKE can use a number of methods for peer authentication during Phase1, and an exposed secret key has different ramifications for each of them. The digital signature authentication method, which is preferred over pre-shared keys, is particularly vulnerable to this attack.

When using digital signature authentication, the keying material is generated from the DH secret key and a number of other parameters, all of which are sent over the wire un-encrypted. This means that if a passive attacker knows the secret key, they will be able to recover the clear-text of all traffic which is encrypted with this keying material. This includes all encrypted IKE traffic, all IPSec ESP traffic, and the ability to spoof all IPSec AH traffic.

If an IKE implementation is controlled by a party who has the ability to observe traffic coming from and going to the server, or is in collusion with another party who can observe the traffic, all of the server’s peers are in danger of unknowingly exposing the clear-text of encrypted traffic with the observers if they do not validate the DH public key. This situation would be fairly difficult to detect, as the illegitimate IKE server would not have to transmit any traffic outside of the IKE specification.

Other problems stem from the fact that an attacker does not need to perform expensive modular exponentiation to determine the secret key. This lowers the computational power necessary to execute MitM and flooding attacks.

Considering the fact that public key verification is recommended by NIST, ANSI and the DH public key exchange RFC, and given the security implications if no verification is performed, one would expect that most if not all DH key exchange implementations validate the public keys that they receive. This, however, is not the case.

I tested both popular Open Source IKE servers, as well as a number of commercial products. Nobody is validating keys. We also tested this attack against some products with the SSH protocol, and there are vulnerabilities in these implementations as well.

These results prompted the title of this paper. How could some of the biggest names in the networking and security industry miss the boat on such a critical component of their platforms? Why is it that an open source project, such as OpenSSH, would be stripped of the validation checks when imported into a commercial product?

I don’t know the answer to these, but I’m quite alarmed by what we have found. I have created a small patch for ike-scan which will allow you to test products for this vulnerability. Hopefully as people become aware of the consequences of not validating public key values, vendors will begin to make their products more secure.

Update:

We have received a number of complaints in regards to this post. Here’s a short list of some of the feedback. If I’m missing something, please let me know.

  1. With respect to the collusion attack, there is no difference between our scenario and that of back dooring a box to use pre-computed keys.
  2. The chance that these keys will be sent by a legitimate peer is almost zero.
  3. We have overstated the impact of of the findings (some have claimed that there is absolutely nothing significant)

First off, I believe that the title of this blog post should have been much less inflammatory. It overstates the findings and causes knee-jerk reactions which are not directed at our thesis.

Now a response to the complaints listed above:

  1. The scenario we describe where a peer is in collusion with a sniffer is very similar to the use of pre-computed keys. One small difference is that sending public keys of 0 or 1 is easier to detect.
  2. A key of 0 is impossible given the mathematics of the computation. Therefore if a key of 0 is received, it should be rejected and the peer should be considered untrustworthy

The point of this post was not to expose an unknown IKE protocol attack. It was meant to expose the fact that nobody is following the recommendations for validation. IKE was used as an illustrative example for those who are not familiar with the DH exchange, and the problems which can arise when proper validation is not carried out.

When building software in general, and secure systems in particular, one should take all the precautions within reason to protect the program from unforeseen circumstances which might undermine the robustness and quality of the product. This is probably the reason why OpenSSH, OpenSSL and Tor all follow the recommendations laid out in various standards and RFCs I have described.

As I explained in the post, we have already found one product who’s implementation of SSH does not validate DH public keys. Have the security implications of invalid DH public keys in each and every protocol where the DH exchange is used been analyzed? Again I point to the lowered computational power required for of MitM and DoS attacks. Many people are saying that with respect to IKE, there’s no reason to validate the keys. My response is simple: given the simplicity of the sanity checks, why not?

Categories: Advisories, C, Research
1,873 Comments
Bookmark and Share