Guard against DoS in name constraints handling.

This guards against the name constraints check consuming large amounts
of CPU time when certificates in the presented chain contain an
excessive number of names (specifically subject email names or subject
alternative DNS names) and/or name constraints.

Name constraints checking compares the names presented in a certificate
against the name constraints included in a certificate higher up in the
chain using two nested for loops.

Move the name constraints check so that it happens after signature
verification so peers cannot exploit this using a chain with invalid
signatures. Also impose a hard limit on the number of name constraints
check loop iterations to further mitigate the issue.

Thanks to NCC for finding this issue.

Change-Id: I112ba76fe75d1579c45291042e448850b830cbb7
Reviewed-on: https://boringssl-review.googlesource.com/19164
Reviewed-by: Martin Kreichgauer <martinkr@google.com>
Commit-Queue: Martin Kreichgauer <martinkr@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>

crypto/x509/x509_vfy.c

diff --git a/crypto/x509/x509_vfy.c b/crypto/x509/x509_vfy.c
index b427df6..5228d01 100644
--- a/crypto/x509/x509_vfy.c
+++ b/crypto/x509/x509_vfy.c
@@ -472,13 +472,6 @@
     if (!ok)
         goto end;
 
-    /* Check name constraints */
-
-    ok = check_name_constraints(ctx);
-
-    if (!ok)
-        goto end;
-
     ok = check_id(ctx);
 
     if (!ok)
@@ -511,6 +504,12 @@
     if (!ok)
         goto end;
 
+    /* Check name constraints */
+
+    ok = check_name_constraints(ctx);
+    if (!ok)
+        goto end;
+
     /* If we get this far evaluate policies */
     if (!bad_chain && (ctx->param->flags & X509_V_FLAG_POLICY_CHECK))
         ok = ctx->check_policy(ctx);

crypto/x509v3/v3_ncons.c

diff --git a/crypto/x509v3/v3_ncons.c b/crypto/x509v3/v3_ncons.c
index fc2843e..593a520 100644
--- a/crypto/x509v3/v3_ncons.c
+++ b/crypto/x509v3/v3_ncons.c
@@ -214,17 +214,18 @@
     return 1;
 }
 
-/*
- * Check a certificate conforms to a specified set of constraints. Return
- * values: X509_V_OK: All constraints obeyed.
- * X509_V_ERR_PERMITTED_VIOLATION: Permitted subtree violation.
- * X509_V_ERR_EXCLUDED_VIOLATION: Excluded subtree violation.
- * X509_V_ERR_SUBTREE_MINMAX: Min or max values present and matching type.
- * X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE: Unsupported constraint type.
- * X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX: bad unsupported constraint
- * syntax.  X509_V_ERR_UNSUPPORTED_NAME_SYNTAX: bad or unsupported syntax of
- * name
- *
+/*-
+ * Check a certificate conforms to a specified set of constraints.
+ * Return values:
+ *   X509_V_OK: All constraints obeyed.
+ *   X509_V_ERR_PERMITTED_VIOLATION: Permitted subtree violation.
+ *   X509_V_ERR_EXCLUDED_VIOLATION: Excluded subtree violation.
+ *   X509_V_ERR_SUBTREE_MINMAX: Min or max values present and matching type.
+ *   X509_V_ERR_UNSPECIFIED: Unspecified error.
+ *   X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE: Unsupported constraint type.
+ *   X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX: Bad or unsupported constraint
+ *     syntax.
+ *   X509_V_ERR_UNSUPPORTED_NAME_SYNTAX: Bad or unsupported syntax of name.
  */
 
 int NAME_CONSTRAINTS_check(X509 *x, NAME_CONSTRAINTS *nc)
@@ -235,6 +236,21 @@
 
     nm = X509_get_subject_name(x);
 
+    /* Guard against certificates with an excessive number of names or
+     * constraints causing a computationally expensive name constraints
+     * check. */
+    size_t name_count =
+        X509_NAME_entry_count(nm) + sk_GENERAL_NAME_num(x->altname);
+    size_t constraint_count = sk_GENERAL_SUBTREE_num(nc->permittedSubtrees) +
+                              sk_GENERAL_SUBTREE_num(nc->excludedSubtrees);
+    size_t check_count = constraint_count * name_count;
+    if (name_count < (size_t)X509_NAME_entry_count(nm) ||
+        constraint_count < sk_GENERAL_SUBTREE_num(nc->permittedSubtrees) ||
+        (constraint_count && check_count / constraint_count != name_count) ||
+        check_count > 1 << 20) {
+      return X509_V_ERR_UNSPECIFIED;
+    }
+
     if (X509_NAME_entry_count(nm) > 0) {
         GENERAL_NAME gntmp;
         gntmp.type = GEN_DIRNAME;