Validate DH public keys for RFC 5114 groups.

This is CVE-2016-0701 for OpenSSL, reported by Antonio Sanso. It is a no-op for
us as we'd long removed SSL_OP_DH_SINGLE_USE and static DH cipher suites. (We
also do not parse or generate X9.42 DH parameters.)

However, we do still have the APIs which return RFC 5114 groups, so we should
perform the necessary checks in case later consumers reuse keys.

Unlike groups we generate, RFC 5114 groups do not use "safe primes" and have
many small subgroups. In those cases, the subprime q is available. Before using
a public key, ensure its order is q by checking y^q = 1 (mod p). (q is assumed
to be prime and the existing range checks ensure y is not 1.)

(Imported from upstream's 878e2c5b13010329c203f309ed0c8f2113f85648 and
75374adf8a6ff69d6718952121875a491ed2cd29, but with some bugs fixed. See
RT4278.)

Change-Id: Ib18c3e84819002fa36a127ac12ca00ee33ea018a
Reviewed-on: https://boringssl-review.googlesource.com/7001
Reviewed-by: Adam Langley <agl@google.com>

2 files changed, 89 insertions, 11 deletions

diff --git a/crypto/dh/check.c b/crypto/dh/check.c
index 06af6f25..d27fdf15 100644
--- a/crypto/dh/check.c
+++ b/crypto/dh/check.c
@@ -62,30 +62,52 @@
 
 
 int DH_check_pub_key(const DH *dh, const BIGNUM *pub_key, int *ret) {
+  *ret = 0;
+
+  BN_CTX *ctx = BN_CTX_new();
+  if (ctx == NULL) {
+    return 0;
+  }
+  BN_CTX_start(ctx);
+
   int ok = 0;
-  BIGNUM q;
 
-  *ret = 0;
-  BN_init(&q);
-  if (!BN_set_word(&q, 1)) {
+  /* Check |pub_key| is greater than 1. */
+  BIGNUM *tmp = BN_CTX_get(ctx);
+  if (tmp == NULL ||
+      !BN_set_word(tmp, 1)) {
     goto err;
   }
-
-  if (BN_cmp(pub_key, &q) <= 0) {
+  if (BN_cmp(pub_key, tmp) <= 0) {
     *ret |= DH_CHECK_PUBKEY_TOO_SMALL;
   }
-  if (!BN_copy(&q, dh->p) ||
-      !BN_sub_word(&q, 1)) {
+
+  /* Check |pub_key| is less than |dh->p| - 1. */
+  if (!BN_copy(tmp, dh->p) ||
+      !BN_sub_word(tmp, 1)) {
     goto err;
   }
-  if (BN_cmp(pub_key, &q) >= 0) {
+  if (BN_cmp(pub_key, tmp) >= 0) {
     *ret |= DH_CHECK_PUBKEY_TOO_LARGE;
   }
 
+  if (dh->q != NULL) {
+    /* Check |pub_key|^|dh->q| is 1 mod |dh->p|. This is necessary for RFC 5114
+     * groups which are not safe primes but pick a generator on a prime-order
+     * subgroup of size |dh->q|. */
+    if (!BN_mod_exp(tmp, pub_key, dh->q, dh->p, ctx)) {
+      goto err;
+    }
+    if (!BN_is_one(tmp)) {
+      *ret |= DH_CHECK_PUBKEY_INVALID;
+    }
+  }
+
   ok = 1;
 
 err:
-  BN_free(&q);
+  BN_CTX_end(ctx);
+  BN_CTX_free(ctx);
   return ok;
 }
 
diff --git a/crypto/dh/dh_test.cc b/crypto/dh/dh_test.cc
index c117bd49..885bd32b 100644
--- a/crypto/dh/dh_test.cc
+++ b/crypto/dh/dh_test.cc
@@ -72,12 +72,14 @@
 
 static bool RunBasicTests();
 static bool RunRFC5114Tests();
+static bool TestBadY();
 
 int main(int argc, char *argv[]) {
   CRYPTO_library_init();
 
   if (!RunBasicTests() ||
-      !RunRFC5114Tests()) {
+      !RunRFC5114Tests() ||
+      !TestBadY()) {
     ERR_print_errors_fp(stderr);
     return 1;
   }
@@ -477,3 +479,57 @@ static bool RunRFC5114Tests() {
 
   return 1;
 }
+
+// kRFC5114_2048_224BadY is a bad y-coordinate for RFC 5114's 2048-bit MODP
+// Group with 224-bit Prime Order Subgroup (section 2.2).
+static const uint8_t kRFC5114_2048_224BadY[] = {
+    0x45, 0x32, 0x5f, 0x51, 0x07, 0xe5, 0xdf, 0x1c, 0xd6, 0x02, 0x82, 0xb3,
+    0x32, 0x8f, 0xa4, 0x0f, 0x87, 0xb8, 0x41, 0xfe, 0xb9, 0x35, 0xde, 0xad,
+    0xc6, 0x26, 0x85, 0xb4, 0xff, 0x94, 0x8c, 0x12, 0x4c, 0xbf, 0x5b, 0x20,
+    0xc4, 0x46, 0xa3, 0x26, 0xeb, 0xa4, 0x25, 0xb7, 0x68, 0x8e, 0xcc, 0x67,
+    0xba, 0xea, 0x58, 0xd0, 0xf2, 0xe9, 0xd2, 0x24, 0x72, 0x60, 0xda, 0x88,
+    0x18, 0x9c, 0xe0, 0x31, 0x6a, 0xad, 0x50, 0x6d, 0x94, 0x35, 0x8b, 0x83,
+    0x4a, 0x6e, 0xfa, 0x48, 0x73, 0x0f, 0x83, 0x87, 0xff, 0x6b, 0x66, 0x1f,
+    0xa8, 0x82, 0xc6, 0x01, 0xe5, 0x80, 0xb5, 0xb0, 0x52, 0xd0, 0xe9, 0xd8,
+    0x72, 0xf9, 0x7d, 0x5b, 0x8b, 0xa5, 0x4c, 0xa5, 0x25, 0x95, 0x74, 0xe2,
+    0x7a, 0x61, 0x4e, 0xa7, 0x8f, 0x12, 0xe2, 0xd2, 0x9d, 0x8c, 0x02, 0x70,
+    0x34, 0x44, 0x32, 0xc7, 0xb2, 0xf3, 0xb9, 0xfe, 0x17, 0x2b, 0xd6, 0x1f,
+    0x8b, 0x7e, 0x4a, 0xfa, 0xa3, 0xb5, 0x3e, 0x7a, 0x81, 0x9a, 0x33, 0x66,
+    0x62, 0xa4, 0x50, 0x18, 0x3e, 0xa2, 0x5f, 0x00, 0x07, 0xd8, 0x9b, 0x22,
+    0xe4, 0xec, 0x84, 0xd5, 0xeb, 0x5a, 0xf3, 0x2a, 0x31, 0x23, 0xd8, 0x44,
+    0x22, 0x2a, 0x8b, 0x37, 0x44, 0xcc, 0xc6, 0x87, 0x4b, 0xbe, 0x50, 0x9d,
+    0x4a, 0xc4, 0x8e, 0x45, 0xcf, 0x72, 0x4d, 0xc0, 0x89, 0xb3, 0x72, 0xed,
+    0x33, 0x2c, 0xbc, 0x7f, 0x16, 0x39, 0x3b, 0xeb, 0xd2, 0xdd, 0xa8, 0x01,
+    0x73, 0x84, 0x62, 0xb9, 0x29, 0xd2, 0xc9, 0x51, 0x32, 0x9e, 0x7a, 0x6a,
+    0xcf, 0xc1, 0x0a, 0xdb, 0x0e, 0xe0, 0x62, 0x77, 0x6f, 0x59, 0x62, 0x72,
+    0x5a, 0x69, 0xa6, 0x5b, 0x70, 0xca, 0x65, 0xc4, 0x95, 0x6f, 0x9a, 0xc2,
+    0xdf, 0x72, 0x6d, 0xb1, 0x1e, 0x54, 0x7b, 0x51, 0xb4, 0xef, 0x7f, 0x89,
+    0x93, 0x74, 0x89, 0x59,
+};
+
+static bool TestBadY() {
+  ScopedDH dh(DH_get_2048_224(nullptr));
+  ScopedBIGNUM pub_key(
+      BN_bin2bn(kRFC5114_2048_224BadY, sizeof(kRFC5114_2048_224BadY), nullptr));
+  if (!dh || !pub_key || !DH_generate_key(dh.get())) {
+    return false;
+  }
+
+  int flags;
+  if (!DH_check_pub_key(dh.get(), pub_key.get(), &flags)) {
+    return false;
+  }
+  if (!(flags & DH_CHECK_PUBKEY_INVALID)) {
+    fprintf(stderr, "DH_check_pub_key did not reject the key.\n");
+    return false;
+  }
+
+  std::vector<uint8_t> result(DH_size(dh.get()));
+  if (DH_compute_key(result.data(), pub_key.get(), dh.get()) >= 0) {
+    fprintf(stderr, "DH_compute_key unexpectedly succeeded.\n");
+    return false;
+  }
+  ERR_clear_error();
+
+  return true;
+}