Insecure Diffie Hellman key exchange parameters validation in Mbed TLS (former PolarSSL)

Discovered on:
2009-09-06
Reported on:
2011-02-01
Remediated on:
2011-02-11
Published on:
2011-02-11
Severity:
CVE:
CVE-2011-1923
Class:
CWE-310

Summary

Mbed TLS (then PolarSSL) is a widely used cryptographic library originally written by Christopher Devine (as XySSL, released under the BSD 3-clause license) which has seen a significant amount of acceptance in embedded applications, owing to its lightweight origins, and was acquired by ARM.

During the course of internal research, a specialist from Subreption identified a severe vulnerability in the library’s implementation of the Diffie-Hellman key exchange, consisting of a lack of validation for the public parameters, a well known “man in the middle” attack against DH where a malicious third-party can manipulate the public parameters of the exchange and force a weak or predictable secret to be generated by the targeted parties.

This results in complete compromise of the integrity and confidentiality of the key material and every communication thereafter.

Technical details

The nature of the vulnerability, manifested in the implementation for Diffie-Hellman in Mbed TLS, is actually a well documented cryptographic weakness or attack against DH that was described in-depth in the now historical paper “Minding your p’s and q’s” by Ross Anderson and Serge Vaudenay.

Anderson and Vaudenay describe the attack against Diffie-Hellman as follows:

  1. Diffie Hellman-like protocols

In the original Diffie Hellman Protocol, everything works modulo a fixed prime p. Two participants Alice and Bob first agree on this prime and a generator g of Z∗p ; then Alice picks a random a and sends ga mod p to Bob, who picks a random b and sends gb mod p to Alice. They then compute a shared private key as gab mod p.

3.1 The middleperson attack

The traditional countermeasure is a key confirmation protocol in which Alice and Bob authenticate either the key they think they have just agreed, or the components they think they exchanged in order to agree it. We shall now show that these two countermeasures are not in fact equivalent; there are attacks in which Charlie forces Alice and Bob to share a key that he can calculate. If a careless implementation does not check the received values, then Charlie can simply intercept both ga and gb and replace them with 0 or 1. Alice and Bob end up sharing a ‘secret’ that Charlie knows too. Assuming as before that p − 1 = qw with w smooth, a more sophisticated attack is for Charlie to replace the numbers ga with gaq and gb with gbq . In this way, the exchange is forced into the smooth subgroup of Z∗ p ; he can then compute the discrete logarithm of gaq mod p to the base gq and apply it to gbq mod p, getting the shared key gabq . This attack was discovered by van Oorschot and Wiener [32]; for more discussion on key agreement protocols, see Just and Vaudenay [18]

Summarizing the paper, the vulnerability requires the ability to influence the parameters that both parties use during the exchange. This is trivially done with close access or compromised network equipment, or provider-level capabilities. At that point, Alice and Bob will settle on using a shared secret that the adversary knows or can compute in near real-time, effectively compromising the entire scheme.

While the Mbed TLS mantainer described the issue as “possible”, Subreption developed both a unit test and a network-driven proof of concept that successfully targeted the exchange resulting in compromise of the shared secret. Therefore, our recommendation presently is to be wary of Mbed TLS, involving a qualified third-party to audit and supervise its deployment and use. Other issues have been identified in the library over the years and most of them are related to the fact that the library has not been thoroughly audited nor developed by world-class cryptographers.

This vulnerability was long present in Mbed TLS despite literature existing since 1996 warning of the problem.

Patch or remediation

The maintainer of the library was unable to devise a proper fix for the problem, therefore Subreption provided a verified patch to the source code of the Mbed TLS library, which was merged by its maintainer (although no credit or copyright information was included into the modified source file of the software distribution). Subreption makes no implicit nor explicit guarantee for this patch beyond fixing the issue as manifested at the time of disclosure.

The contents of the original patch are as follows:

 1Index: dhm.c
 2===================================================================
 3--- dhm.c       (revision 950)
 4+++ dhm.c       (working copy)
 5@@ -63,6 +63,35 @@
 6 }
 7
 8 /*
 9+ * Verify sanity of public parameter with regards to P
10+ *
11+ * Public parameter should be: 2 <= public_param <= P - 2
12+ *
13+ * For more information on the attack, see:
14+ *  http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
15+ *  http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
16+ */
17+static int dhm_check_range( const mpi *public_param, const mpi *P )
18+{
19+    mpi L, U;
20+    int ret = POLARSSL_ERR_DHM_BAD_INPUT_DATA;
21+
22+    mpi_init( &L, &U, NULL );
23+    mpi_lset( &L, 2 );
24+    mpi_sub_int( &U, P, 2 );
25+
26+    if( mpi_cmp_mpi( public_param, &L ) >= 0 &&
27+        mpi_cmp_mpi( public_param, &U ) <= 0 )
28+    {
29+        ret = 0;
30+    }
31+
32+    mpi_free( &L, &U, NULL );
33+
34+    return( ret );
35+}
36+
37+/*
38  * Parse the ServerKeyExchange parameters
39  */
40 int dhm_read_params( dhm_context *ctx,
41@@ -78,6 +107,9 @@
42         ( ret = dhm_read_bignum( &ctx->GY, p, end ) ) != 0 )
43         return( ret );
44
45+    if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
46+        return( ret );
47+
48     ctx->len = mpi_size( &ctx->P );
49
50     if( end - *p < 2 )
51@@ -122,6 +154,9 @@
52     MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
53                           &ctx->P , &ctx->RP ) );
54
55+    if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
56+        return( ret );
57+
58     /*
59      * export P, G, GX
60      */
61@@ -199,6 +233,9 @@
62     MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
63                           &ctx->P , &ctx->RP ) );
64
65+    if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
66+        return( ret );
67+
68     MPI_CHK( mpi_write_binary( &ctx->GX, output, olen ) );
69
70 cleanup:
71@@ -223,6 +260,9 @@
72     MPI_CHK( mpi_exp_mod( &ctx->K, &ctx->GY, &ctx->X,
73                           &ctx->P, &ctx->RP ) );
74
75+    if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
76+        return( ret );
77+
78     *olen = mpi_size( &ctx->K );
79
80     MPI_CHK( mpi_write_binary( &ctx->K, output, *olen ) );

References

The following references are relevant to this advisory: