Widespread DH Implementation Weakness: Conspiracy or Ignorance?
September 18th, 2007 by Adam BozanichWhile 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.