Require certificates under name constraints use SANs.

The common name fallback does not interact well with name constraints.
Until we remove this fallback, we must resolve this conflict.

Blindly applying name constraints to the common name will reject
"decorative" common names that aren't intended to be hostnames (e.g.
[0]). We need to guess based on format whether the common name is a DNS
name. It is important this same check is applied to *both* name
constraints and name matching, which means the OpenSSL version (see
5bd5dcd49605ca2aa7931599894302a3ac4b0b04,
d02d80b2e80adfdde49f76cf7c7af4e013f45005, and
55a6250f1e7336e8a7d89fb609eb23398715ff6f) is unsuitable as a
compatibility data point.

In theory we could limit this to chains with name constraints, which are
uncommon, but X509_check_host sees only the leaf. We must apply it
uniformly. That means a strict check risks problems with malformed
non-WebPKI setups like [1].

For a first pass, mirror Go's behavior. Like Go, rather than run
SAN-less DNS-like common names through name constraints, we simply
reject all such certificates. Name constraints now exclude all leaf
certificates that can trigger the common name fallback. They are rare
enough that we can hopefully hold them to a higher standard.

Note this does not make misclassified decorative common names any worse,
compared to the checking the name constraint. Such names would not have
matched the constraint anyway.

Update-Note: This can may cause two kinds of errors:

1. Leaf certificates whose chain contains a name constraint and lack
   SANs may be rejected with X509_V_ERR_NAME_CONSTRAINTS_WITHOUT_SANS.

2. Leaf certificates which use the common name fallback and verify
   against an insufficiently DNS-looking hostname may fail with
   X509_V_ERR_HOSTNAME_MISMATCH.

In both cases, the fix is to include the subjectAltName in the
certificate, rather than rely on the common name fallback. (Refining the
heuristic is also an option, but the two failure modes pull it in
opposite directions, so this is tricky.)

[0] https://github.com/golang/go/issues/24151
[1] https://github.com/GoogleCloudPlatform/cloudsql-proxy/issues/194

Change-Id: If25557de428768292a14ba3bdeeffbd74e3a3bf8
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/35665
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/x509/make_many_constraints.go b/crypto/x509/make_many_constraints.go
index e507403..578618d 100644
--- a/crypto/x509/make_many_constraints.go
+++ b/crypto/x509/make_many_constraints.go
@@ -137,10 +137,10 @@
 	}{
 		{"many_names1.pem", 513, 513},
 		{"many_names2.pem", 1025, 0},
-		{"many_names3.pem", 0, 1025},
+		{"many_names3.pem", 1, 1025},
 		{"some_names1.pem", 256, 256},
 		{"some_names2.pem", 513, 0},
-		{"some_names3.pem", 0, 513},
+		{"some_names3.pem", 1, 513},
 	}
 	for i, leaf := range leaves {
 		leafTemplate := x509.Certificate{
diff --git a/crypto/x509/many_names3.pem b/crypto/x509/many_names3.pem
index dbfa042..f15638f 100644
--- a/crypto/x509/many_names3.pem
+++ b/crypto/x509/many_names3.pem
@@ -1,5 +1,5 @@
 -----BEGIN CERTIFICATE-----
-MIJqmDCCaYCgAwIBAgIBBDANBgkqhkiG9w0BAQsFADANMQswCQYDVQQDEwJDQTAg
+MIJqrDCCaZSgAwIBAgIBBDANBgkqhkiG9w0BAQsFADANMQswCQYDVQQDEwJDQTAg
 Fw0wMDAxMDEwMDAwMDBaGA8yMTAwMDEwMTAwMDAwMFowgmfXMRAwDgYDVQQDEwd0
 MC50ZXN0MRYwFAYJKoZIhvcNAQkBFgd0MEB0ZXN0MRYwFAYJKoZIhvcNAQkBFgd0
 MUB0ZXN0MRYwFAYJKoZIhvcNAQkBFgd0MkB0ZXN0MRYwFAYJKoZIhvcNAQkBFgd0
@@ -560,12 +560,12 @@
 oiXCzepBrhtp5UQSjHD4D4hKtgdMgVxX+LRtwgW3mnu/vBu7rzpr/DS8io99p3lq
 Z1Aky+aNlcMj6MYy8U+YFEevb/V0lRY9oqwmW7BHnXikm/vi6sjIS350U8zb/mRz
 YeIs2R65LUduTL50+UMgat9ocewI2dv8aO9Dph+8NdGtg8LFYyTTHcUxJoMr1PTO
-gnmET19WJH4PrFwk7ZE1QJQQ1L4iKmPeQistuQIDAQABozUwMzAOBgNVHQ8BAf8E
-BAMCBaAwEwYDVR0lBAwwCgYIKwYBBQUHAwEwDAYDVR0TAQH/BAIwADANBgkqhkiG
-9w0BAQsFAAOCAQEAtMIpnGzOBkJXEBmCsRVbTrg9QgYRlGPG48+cXT2QbIutAmbj
-miF+OYg/bRsQtuqcKjnJYog+x6UCU3d34jaMEfEXfHSwF7xPQrqJm45MXhG3so4E
-+el5GMAS+SKFQK3w8NPoGhGwn82sz4XV6HMG+ANUxMlCrOcx2jh5UW+7ITjdRwJd
-ReJ/JaMpneJdwGFSU9Vn+t7PFb51/pOYqO/PuEANzphovjMVcFZ6mtAQwYDkQZBJ
-Vy1/7bPoNmbKD0GAS6HpS+xaJ/DnjjD6Kal2T7GMyvRMogj5BeZ/uEkXCEhvoaBT
-os1gaqqnGpZ6JSEDctzjgpCtEPR40yiz1wv1CA==
+gnmET19WJH4PrFwk7ZE1QJQQ1L4iKmPeQistuQIDAQABo0kwRzAOBgNVHQ8BAf8E
+BAMCBaAwEwYDVR0lBAwwCgYIKwYBBQUHAwEwDAYDVR0TAQH/BAIwADASBgNVHREE
+CzAJggd0MC50ZXN0MA0GCSqGSIb3DQEBCwUAA4IBAQAi7LIMyX5Ec514hvjROZ8b
+7i4UR3xd5IbniVSej+PKZhG2inN6aX9bksdda0ddYZeRSHAkNJuoabeankQJ/x5x
+sxBntWSVLCxz6S8NRrLAPKKPBvFb/W5ns57LP9SrLIij9l/NSd+K/CQNTlfcdorg
+4ltPVNwSMp/XXjH6rQYJSbo9MhDoxeqPpv73e4jY0DfGn1a8uwyCXalLjh4EkUyS
+Ye0N7MoUKV0IucrXKdgj2sHgBFqNKJ/GVQ422xZRbYqsyIJ0bPD6Fc8VcqfVrvYg
+lCYJfu7Xij5n3mjQaSYcbVxH71X8fYhhNq1tk+WtQOXirz2EkSuh1rNGU/LT8Q6r
 -----END CERTIFICATE-----
diff --git a/crypto/x509/some_names3.pem b/crypto/x509/some_names3.pem
index a6d3ee7..7b38bf3 100644
--- a/crypto/x509/some_names3.pem
+++ b/crypto/x509/some_names3.pem
@@ -1,5 +1,5 @@
 -----BEGIN CERTIFICATE-----
-MII2fzCCNWegAwIBAgIBBzANBgkqhkiG9w0BAQsFADANMQswCQYDVQQDEwJDQTAg
+MII2kzCCNXugAwIBAgIBBzANBgkqhkiG9w0BAQsFADANMQswCQYDVQQDEwJDQTAg
 Fw0wMDAxMDEwMDAwMDBaGA8yMTAwMDEwMTAwMDAwMFowgjO+MRAwDgYDVQQDEwd0
 MC50ZXN0MRYwFAYJKoZIhvcNAQkBFgd0MEB0ZXN0MRYwFAYJKoZIhvcNAQkBFgd0
 MUB0ZXN0MRYwFAYJKoZIhvcNAQkBFgd0MkB0ZXN0MRYwFAYJKoZIhvcNAQkBFgd0
@@ -282,12 +282,13 @@
 BEiEhBxIsaIlws3qQa4baeVEEoxw+A+ISrYHTIFcV/i0bcIFt5p7v7wbu686a/w0
 vIqPfad5amdQJMvmjZXDI+jGMvFPmBRHr2/1dJUWPaKsJluwR514pJv74urIyEt+
 dFPM2/5kc2HiLNkeuS1Hbky+dPlDIGrfaHHsCNnb/GjvQ6YfvDXRrYPCxWMk0x3F
-MSaDK9T0zoJ5hE9fViR+D6xcJO2RNUCUENS+Iipj3kIrLbkCAwEAAaM1MDMwDgYD
+MSaDK9T0zoJ5hE9fViR+D6xcJO2RNUCUENS+Iipj3kIrLbkCAwEAAaNJMEcwDgYD
 VR0PAQH/BAQDAgWgMBMGA1UdJQQMMAoGCCsGAQUFBwMBMAwGA1UdEwEB/wQCMAAw
-DQYJKoZIhvcNAQELBQADggEBAH6ad2kFE0qGDe3ErMdwTGjbBz3T12dDvAUVhGHQ
-uZShOdPsXMHD2mUqFgLE0iJFeXB7jOSAKtzmKHNmxZ4W0UZ7eMPPogkgIbG3d3yR
-8zBO21CUyOQWChywpKcAou9ji3Kq6pb4+mqq0a5TGIYyGJKSUTv09KI+iHgwteCX
-DHzzhuTs8AhodmNO5K/F9YFWJWvQ1NrwyUmOFEw8/UcljyKxFrP2VEov0fWeiTRB
-Ps6VaFBW7SEEi8fAM9W5kfsl+iWRvwFcFdXGQt1HbeywCu58DLI4uceHCFb+3MMO
-Xv7wJ5UhQODuzwuq7CuZvlxR2tiFoPP+s5fPH0L8MBP5z6w=
+EgYDVR0RBAswCYIHdDAudGVzdDANBgkqhkiG9w0BAQsFAAOCAQEAQA/0vvY1gLA2
+0jrPkBVWte7OHzWVkwq7mqgQPR4L9qLLu7Vhelp4dW8n95s1wCbca5j5SJEGv4Uv
+0fI1OOK7XQeYdNlHBmvMVW47GoBSo6tuYNPI/y4xnM6ypEZiPKkdj9Ar9qNgURfV
+z3s1czip915dyTWgwBy7CTxOlG8NW0uiFgEc9iiDDfQsPwVXiVtxOPtjhPeI3F0J
+jh3wctFxBnAvLV9SsDxpWujM1dd/1SSQ25jKQhbKNtiDAC8v+Q043r8ZGHjRdxe8
+W2tVWH/iz9c+ze0P0ao7LKv8eGzoIsrBqICS86X4Zv5lGeTGaD2osF1oNvmmoSlh
+536yFa415g==
 -----END CERTIFICATE-----
diff --git a/crypto/x509/x509_test.cc b/crypto/x509/x509_test.cc
index 517635e..c0ac170 100644
--- a/crypto/x509/x509_test.cc
+++ b/crypto/x509/x509_test.cc
@@ -32,6 +32,7 @@
 
 #include "../internal.h"
 #include "../test/test_util.h"
+#include "../x509v3/internal.h"
 
 
 std::string GetTestData(const char *path);
@@ -727,6 +728,95 @@
     "D0+O6KI=\n"
     "-----END CERTIFICATE-----\n";
 
+// kConstrainedIntermediate is an intermediate signed by kSANTypesRoot, with
+// permitted DNS names of permitted1.test and foo.permitted2.test and an
+// excluded DNS name of excluded.permitted1.test. Its private key is:
+//
+// -----BEGIN PRIVATE KEY-----
+// MIGHAgEAMBMGByqGSM49AgEGCCqGSM49AwEHBG0wawIBAQQgTXUM4tJWM7OzATty
+// JhNOfIv/d8heWFBeKOfMR+RfaROhRANCAASbbbWYiN6mn+BCpg4XNpibOH0D/DN4
+// kZ5C/Ml2YVomC9T83OKk2CzB8fPAabPb4P4Vv+fIabpEfjWS5nzKLY1y
+// -----END PRIVATE KEY-----
+static const char kConstrainedIntermediate[] =
+    "-----BEGIN CERTIFICATE-----\n"
+    "MIICDjCCAXegAwIBAgIBAjANBgkqhkiG9w0BAQsFADArMRcwFQYDVQQKEw5Cb3Jp\n"
+    "bmdTU0wgVGVzdDEQMA4GA1UEAxMHUm9vdCBDQTAgFw0wMDAxMDEwMDAwMDBaGA8y\n"
+    "MDk5MDEwMTAwMDAwMFowKDEmMCQGA1UEAxMdTmFtZSBDb25zdHJhaW50cyBJbnRl\n"
+    "cm1lZGlhdGUwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAASbbbWYiN6mn+BCpg4X\n"
+    "NpibOH0D/DN4kZ5C/Ml2YVomC9T83OKk2CzB8fPAabPb4P4Vv+fIabpEfjWS5nzK\n"
+    "LY1yo4GJMIGGMA8GA1UdEwEB/wQFMAMBAf8wGwYDVR0jBBQwEoAQQDfXAftAL7gc\n"
+    "flQEJ4xZATBWBgNVHR4BAf8ETDBKoCowEYIPcGVybWl0dGVkMS50ZXN0MBWCE2Zv\n"
+    "by5wZXJtaXR0ZWQyLnRlc3ShHDAaghhleGNsdWRlZC5wZXJtaXR0ZWQxLnRlc3Qw\n"
+    "DQYJKoZIhvcNAQELBQADgYEAFq1Ka05hiKREwRpSceQPzIIH4B5a5IVBg5/EvmQI\n"
+    "9V0fXyAE1GmahPt70sIBxIgzNTEaY8P/IoOuCdlZWe0msmyEO3S6YSAzOWR5Van6\n"
+    "cXmFM1uMd95TlkxUMRdV+jKJTvG6R/BM2zltaV7Xt662k5HtzT5Svw0rZlFaggZz\n"
+    "UyM=\n"
+    "-----END CERTIFICATE-----\n";
+
+// kCommonNamePermittedLeaf is a leaf certificate signed by
+// kConstrainedIntermediate. Its common name is permitted by the name
+// constraints.
+static const char kCommonNamePermittedLeaf[] =
+    "-----BEGIN CERTIFICATE-----\n"
+    "MIIBaDCCAQ2gAwIBAgIBAzAKBggqhkjOPQQDAjAoMSYwJAYDVQQDEx1OYW1lIENv\n"
+    "bnN0cmFpbnRzIEludGVybWVkaWF0ZTAgFw0wMDAxMDEwMDAwMDBaGA8yMDk5MDEw\n"
+    "MTAwMDAwMFowPjEeMBwGA1UEChMVQ29tbW9uIG5hbWUgcGVybWl0dGVkMRwwGgYD\n"
+    "VQQDExNmb28ucGVybWl0dGVkMS50ZXN0MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcD\n"
+    "QgAENX5Ycs8q8MRzPYUz6DqLHhJR3wcmniFRgkiEa7MxE/mRe00y0VGwH7xi7Aoc\n"
+    "emXPrtD4JwN5bssbcxWGAKYYzaMQMA4wDAYDVR0TAQH/BAIwADAKBggqhkjOPQQD\n"
+    "AgNJADBGAiEAtsnWuRQXtw2xbieC78Y8SVEtTjcZUx8uZyQe1GPLfGICIQDR4fNY\n"
+    "yg3PC94ydPNQZVsFxAne32CbonWWsokalTFpUQ==\n"
+    "-----END CERTIFICATE-----\n";
+static const char kCommonNamePermitted[] = "foo.permitted1.test";
+
+// kCommonNameNotPermittedLeaf is a leaf certificate signed by
+// kConstrainedIntermediate. Its common name is not permitted by the name
+// constraints.
+static const char kCommonNameNotPermittedLeaf[] =
+    "-----BEGIN CERTIFICATE-----\n"
+    "MIIBazCCARCgAwIBAgIBBDAKBggqhkjOPQQDAjAoMSYwJAYDVQQDEx1OYW1lIENv\n"
+    "bnN0cmFpbnRzIEludGVybWVkaWF0ZTAgFw0wMDAxMDEwMDAwMDBaGA8yMDk5MDEw\n"
+    "MTAwMDAwMFowQTEiMCAGA1UEChMZQ29tbW9uIG5hbWUgbm90IHBlcm1pdHRlZDEb\n"
+    "MBkGA1UEAxMSbm90LXBlcm1pdHRlZC50ZXN0MFkwEwYHKoZIzj0CAQYIKoZIzj0D\n"
+    "AQcDQgAEzfghKuWf0JoXb0Drp09C3yXMSQQ1byt+AUaymvsHOWsxQ9v1Q+vkF/IM\n"
+    "HRqGTk2TyxrB2iClVEn/Uu+YtYox1KMQMA4wDAYDVR0TAQH/BAIwADAKBggqhkjO\n"
+    "PQQDAgNJADBGAiEAxaUslxmoWL1tIvnDz7gDkto/HcmdU0jHVuUQLXcCG8wCIQCN\n"
+    "5xZjitlCQU8UB5qSu9wH4B+0JcVO3Ss4Az76HEJWMw==\n"
+    "-----END CERTIFICATE-----\n";
+static const char kCommonNameNotPermitted[] = "not-permitted.test";
+
+// kCommonNameNotPermittedWithSANsLeaf is a leaf certificate signed by
+// kConstrainedIntermediate. Its common name is not permitted by the name
+// constraints but it has a SAN list.
+static const char kCommonNameNotPermittedWithSANsLeaf[] =
+    "-----BEGIN CERTIFICATE-----\n"
+    "MIIBqTCCAU+gAwIBAgIBBjAKBggqhkjOPQQDAjAoMSYwJAYDVQQDEx1OYW1lIENv\n"
+    "bnN0cmFpbnRzIEludGVybWVkaWF0ZTAgFw0wMDAxMDEwMDAwMDBaGA8yMDk5MDEw\n"
+    "MTAwMDAwMFowSzEsMCoGA1UEChMjQ29tbW9uIG5hbWUgbm90IHBlcm1pdHRlZCB3\n"
+    "aXRoIFNBTlMxGzAZBgNVBAMTEm5vdC1wZXJtaXR0ZWQudGVzdDBZMBMGByqGSM49\n"
+    "AgEGCCqGSM49AwEHA0IABKsn9wOApXFHrqhLdQgbFSeaSoAIbxgO0zVSRZUb5naR\n"
+    "93zoL3MFOvZEF8xiEqh7le+l3XuUig0fwqpcsZzRNJajRTBDMAwGA1UdEwEB/wQC\n"
+    "MAAwMwYDVR0RBCwwKoITZm9vLnBlcm1pdHRlZDEudGVzdIITZm9vLnBlcm1pdHRl\n"
+    "ZDIudGVzdDAKBggqhkjOPQQDAgNIADBFAiACk+1f184KkKAXuntmrz+Ygcq8MiZl\n"
+    "4delx44FtcNaegIhAIA5nYfzxNcTXxDo3U+x1vSLH6Y7faLvHiFySp7O//q+\n"
+    "-----END CERTIFICATE-----\n";
+static const char kCommonNameNotPermittedWithSANs[] = "not-permitted.test";
+
+// kCommonNameNotDNSLeaf is a leaf certificate signed by
+// kConstrainedIntermediate. Its common name is not a DNS name.
+static const char kCommonNameNotDNSLeaf[] =
+    "-----BEGIN CERTIFICATE-----\n"
+    "MIIBYTCCAQagAwIBAgIBCDAKBggqhkjOPQQDAjAoMSYwJAYDVQQDEx1OYW1lIENv\n"
+    "bnN0cmFpbnRzIEludGVybWVkaWF0ZTAgFw0wMDAxMDEwMDAwMDBaGA8yMDk5MDEw\n"
+    "MTAwMDAwMFowNzEcMBoGA1UEChMTQ29tbW9uIG5hbWUgbm90IEROUzEXMBUGA1UE\n"
+    "AxMOTm90IGEgRE5TIG5hbWUwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAASnueyc\n"
+    "Zxtnw5ke2J2T0/LwAK37auQP/RSFd9mem+BJVbgviawtAlignJmafp7Zw4/GdYEJ\n"
+    "Vm8qlriOJtluvXGcoxAwDjAMBgNVHRMBAf8EAjAAMAoGCCqGSM49BAMCA0kAMEYC\n"
+    "IQChUAmVNI39VHe0zemRE09VDcSEgOxr1nTvjLcg/Q8pVQIhAJYZnJI0YZAi05QH\n"
+    "RHNlAkTK2TnUaVn3fGSylaLiFS1r\n"
+    "-----END CERTIFICATE-----\n";
+static const char kCommonNameNotDNS[] = "Not a DNS name";
+
 // CertFromPEM parses the given, NUL-terminated pem block and returns an
 // |X509*|.
 static bssl::UniquePtr<X509> CertFromPEM(const char *pem) {
@@ -790,7 +880,8 @@
                   const std::vector<X509 *> &intermediates,
                   const std::vector<X509_CRL *> &crls, unsigned long flags,
                   bool use_additional_untrusted,
-                  std::function<void(X509_VERIFY_PARAM *)> configure_callback) {
+                  std::function<void(X509_VERIFY_PARAM *)> configure_callback,
+                  int (*verify_callback)(int, X509_STORE_CTX *) = nullptr) {
   bssl::UniquePtr<STACK_OF(X509)> roots_stack(CertsToStack(roots));
   bssl::UniquePtr<STACK_OF(X509)> intermediates_stack(
       CertsToStack(intermediates));
@@ -1888,3 +1979,95 @@
             verify_cert(with_ip.get(), X509_CHECK_FLAG_NEVER_CHECK_SUBJECT,
                         "foo.host1.test"));
 }
+
+TEST(X509Test, LooksLikeDNSName) {
+    static const char *kValid[] = {
+        "example.com",
+        "eXample123-.com",
+        "*.example.com",
+        "exa_mple.com",
+        "example.com.",
+        "project-dev:us-central1:main",
+    };
+    static const char *kInvalid[] = {
+        "-eXample123-.com",
+        "",
+        ".",
+        "*",
+        "*.",
+        "example..com",
+        ".example.com",
+        "example.com..",
+        "*foo.example.com",
+        "foo.*.example.com",
+        "foo,bar",
+    };
+
+    for (const char *str : kValid) {
+      SCOPED_TRACE(str);
+      EXPECT_TRUE(x509v3_looks_like_dns_name(
+          reinterpret_cast<const uint8_t *>(str), strlen(str)));
+    }
+    for (const char *str : kInvalid) {
+      SCOPED_TRACE(str);
+      EXPECT_FALSE(x509v3_looks_like_dns_name(
+          reinterpret_cast<const uint8_t *>(str), strlen(str)));
+    }
+}
+
+TEST(X509Test, CommonNameAndNameConstraints) {
+  bssl::UniquePtr<X509> root = CertFromPEM(kSANTypesRoot);
+  ASSERT_TRUE(root);
+  bssl::UniquePtr<X509> intermediate = CertFromPEM(kConstrainedIntermediate);
+  ASSERT_TRUE(intermediate);
+  bssl::UniquePtr<X509> permitted = CertFromPEM(kCommonNamePermittedLeaf);
+  ASSERT_TRUE(permitted);
+  bssl::UniquePtr<X509> not_permitted =
+      CertFromPEM(kCommonNameNotPermittedLeaf);
+  ASSERT_TRUE(not_permitted);
+  bssl::UniquePtr<X509> not_permitted_with_sans =
+      CertFromPEM(kCommonNameNotPermittedWithSANsLeaf);
+  ASSERT_TRUE(not_permitted_with_sans);
+  bssl::UniquePtr<X509> not_dns = CertFromPEM(kCommonNameNotDNSLeaf);
+  ASSERT_TRUE(not_dns);
+
+  auto verify_cert = [&](X509 *leaf, unsigned flags, const char *host) {
+    return Verify(
+        leaf, {root.get()}, {intermediate.get()}, {}, 0, false,
+        [&](X509_VERIFY_PARAM *param) {
+          ASSERT_TRUE(X509_VERIFY_PARAM_set1_host(param, host, strlen(host)));
+          X509_VERIFY_PARAM_set_hostflags(param, flags);
+        });
+  };
+
+  // Certificates which would otherwise trigger the common name fallback are
+  // rejected whenever there are name constraints. We do this whether or not
+  // the common name matches the constraints.
+  EXPECT_EQ(
+      X509_V_ERR_NAME_CONSTRAINTS_WITHOUT_SANS,
+      verify_cert(permitted.get(), 0 /* no flags */, kCommonNamePermitted));
+  EXPECT_EQ(X509_V_ERR_NAME_CONSTRAINTS_WITHOUT_SANS,
+            verify_cert(not_permitted.get(), 0 /* no flags */,
+                        kCommonNameNotPermitted));
+
+  // This occurs even if the built-in name checks aren't used. The caller may
+  // separately call |X509_check_host|.
+  EXPECT_EQ(X509_V_ERR_NAME_CONSTRAINTS_WITHOUT_SANS,
+            Verify(not_permitted.get(), {root.get()}, {intermediate.get()}, {},
+                   0 /* no flags */, false, nullptr));
+
+  // If the leaf certificate has SANs, the common name fallback is always
+  // disabled, so the name constraints do not apply.
+  EXPECT_EQ(X509_V_OK, Verify(not_permitted_with_sans.get(), {root.get()},
+                              {intermediate.get()}, {}, 0, false, nullptr));
+  EXPECT_EQ(X509_V_ERR_HOSTNAME_MISMATCH,
+            verify_cert(not_permitted_with_sans.get(), 0 /* no flags */,
+                        kCommonNameNotPermittedWithSANs));
+
+  // If the common name does not look like a DNS name, we apply neither name
+  // constraints nor common name fallback.
+  EXPECT_EQ(X509_V_OK, Verify(not_dns.get(), {root.get()}, {intermediate.get()},
+                              {}, 0, false, nullptr));
+  EXPECT_EQ(X509_V_ERR_HOSTNAME_MISMATCH,
+            verify_cert(not_dns.get(), 0 /* no flags */, kCommonNameNotDNS));
+}
diff --git a/crypto/x509/x509_txt.c b/crypto/x509/x509_txt.c
index 99f83c6..8e6ac27 100644
--- a/crypto/x509/x509_txt.c
+++ b/crypto/x509/x509_txt.c
@@ -195,6 +195,9 @@
     case X509_V_ERR_STORE_LOOKUP:
         return ("Issuer certificate lookup error");
 
+    case X509_V_ERR_NAME_CONSTRAINTS_WITHOUT_SANS:
+        return "Issuer has name constraints but leaf has no SANs";
+
     default:
         return "unknown certificate verification error";
     }
diff --git a/crypto/x509/x509_vfy.c b/crypto/x509/x509_vfy.c
index 5af3fb3..fff97fa 100644
--- a/crypto/x509/x509_vfy.c
+++ b/crypto/x509/x509_vfy.c
@@ -70,6 +70,7 @@
 
 #include "vpm_int.h"
 #include "../internal.h"
+#include "../x509v3/internal.h"
 
 static CRYPTO_EX_DATA_CLASS g_ex_data_class =
     CRYPTO_EX_DATA_CLASS_INIT_WITH_APP_DATA;
@@ -710,13 +711,40 @@
     return ok;
 }
 
+static int reject_dns_name_in_common_name(X509 *x509)
+{
+    X509_NAME *name = X509_get_subject_name(x509);
+    int i = -1;
+    for (;;) {
+        i = X509_NAME_get_index_by_NID(name, NID_commonName, i);
+        if (i == -1) {
+            return X509_V_OK;
+        }
+
+        X509_NAME_ENTRY *entry = X509_NAME_get_entry(name, i);
+        ASN1_STRING *common_name = X509_NAME_ENTRY_get_data(entry);
+        unsigned char *idval;
+        int idlen = ASN1_STRING_to_UTF8(&idval, common_name);
+        if (idlen < 0) {
+            return X509_V_ERR_OUT_OF_MEM;
+        }
+        /* Only process attributes that look like host names. Note it is
+         * important that this check be mirrored in |X509_check_host|. */
+        int looks_like_dns = x509v3_looks_like_dns_name(idval, (size_t)idlen);
+        OPENSSL_free(idval);
+        if (looks_like_dns) {
+            return X509_V_ERR_NAME_CONSTRAINTS_WITHOUT_SANS;
+        }
+    }
+}
+
 static int check_name_constraints(X509_STORE_CTX *ctx)
 {
-    X509 *x;
     int i, j, rv;
+    int has_name_constraints = 0;
     /* Check name constraints for all certificates */
     for (i = sk_X509_num(ctx->chain) - 1; i >= 0; i--) {
-        x = sk_X509_value(ctx->chain, i);
+        X509 *x = sk_X509_value(ctx->chain, i);
         /* Ignore self issued certs unless last in chain */
         if (i && (x->ex_flags & EXFLAG_SI))
             continue;
@@ -729,6 +757,7 @@
         for (j = sk_X509_num(ctx->chain) - 1; j > i; j--) {
             NAME_CONSTRAINTS *nc = sk_X509_value(ctx->chain, j)->nc;
             if (nc) {
+                has_name_constraints = 1;
                 rv = NAME_CONSTRAINTS_check(x, nc);
                 switch (rv) {
                 case X509_V_OK:
@@ -747,6 +776,36 @@
             }
         }
     }
+
+    /* Name constraints do not match against the common name, but
+     * |X509_check_host| still implements the legacy behavior where, on
+     * certificates lacking a SAN list, DNS-like names in the common name are
+     * checked instead.
+     *
+     * While we could apply the name constraints to the common name, name
+     * constraints are rare enough that can hold such certificates to a higher
+     * standard. Note this does not make "DNS-like" heuristic failures any
+     * worse. A decorative common-name misidentified as a DNS name would fail
+     * the name constraint anyway. */
+    X509 *leaf = sk_X509_value(ctx->chain, 0);
+    if (has_name_constraints && leaf->altname == NULL) {
+        rv = reject_dns_name_in_common_name(leaf);
+        switch (rv) {
+        case X509_V_OK:
+            break;
+        case X509_V_ERR_OUT_OF_MEM:
+            ctx->error = rv;
+            return 0;
+        default:
+            ctx->error = rv;
+            ctx->error_depth = i;
+            ctx->current_cert = leaf;
+            if (!ctx->verify_cb(0, ctx))
+                return 0;
+            break;
+        }
+    }
+
     return 1;
 }
 
diff --git a/crypto/x509v3/internal.h b/crypto/x509v3/internal.h
index e6be684..c143d73 100644
--- a/crypto/x509v3/internal.h
+++ b/crypto/x509v3/internal.h
@@ -43,6 +43,11 @@
 // followed by '.'. Otherwise, it returns a non-zero number.
 int x509v3_name_cmp(const char *name, const char *cmp);
 
+// x509v3_looks_like_dns_name returns one if |in| looks like a DNS name and zero
+// otherwise.
+OPENSSL_EXPORT int x509v3_looks_like_dns_name(const unsigned char *in,
+                                              size_t len);
+
 
 #if defined(__cplusplus)
 }  /* extern C */
diff --git a/crypto/x509v3/v3_utl.c b/crypto/x509v3/v3_utl.c
index 51db478..86c4940 100644
--- a/crypto/x509v3/v3_utl.c
+++ b/crypto/x509v3/v3_utl.c
@@ -909,6 +909,53 @@
                           subject, subject_len, flags);
 }
 
+int x509v3_looks_like_dns_name(const unsigned char *in, size_t len) {
+    /* This function is used as a heuristic for whether a common name is a
+     * hostname to be matched, or merely a decorative name to describe the
+     * subject. This heuristic must be applied to both name constraints and the
+     * common name fallback, so it must be loose enough to accept hostname
+     * common names, and tight enough to reject decorative common names. */
+
+    if (len > 0 && in[len - 1] == '.') {
+        len--;
+    }
+
+    /* Wildcards are allowed in front. */
+    if (len >= 2 && in[0] == '*' && in[1] == '.') {
+        in += 2;
+        len -= 2;
+    }
+
+    if (len == 0) {
+        return 0;
+    }
+
+    size_t label_start = 0;
+    for (size_t i = 0; i < len; i++) {
+        unsigned char c = in[i];
+        if ((c >= 'a' && c <= 'z') ||
+            (c >= '0' && c <= '9') ||
+            (c >= 'A' && c <= 'Z') ||
+            (c == '-' && i > label_start) ||
+            /* These are not valid characters in hostnames, but commonly found
+             * in deployments outside the Web PKI. */
+            c == '_' ||
+            c == ':') {
+            continue;
+        }
+
+        /* Labels must not be empty. */
+        if (c == '.' && i > label_start && i < len - 1) {
+            label_start = i + 1;
+            continue;
+        }
+
+        return 0;
+    }
+
+    return 1;
+}
+
 /*
  * Compare an ASN1_STRING to a supplied string. If they match return 1. If
  * cmp_type > 0 only compare if string matches the type, otherwise convert it
@@ -916,8 +963,8 @@
  */
 
 static int do_check_string(ASN1_STRING *a, int cmp_type, equal_fn equal,
-                           unsigned int flags, const char *b, size_t blen,
-                           char **peername)
+                           unsigned int flags, int check_type, const char *b,
+                           size_t blen, char **peername)
 {
     int rv = 0;
 
@@ -938,7 +985,17 @@
         astrlen = ASN1_STRING_to_UTF8(&astr, a);
         if (astrlen < 0)
             return -1;
-        rv = equal(astr, astrlen, (unsigned char *)b, blen, flags);
+        /*
+         * We check the common name against DNS name constraints if it passes
+         * |x509v3_looks_like_dns_name|. Thus we must not consider common names
+         * for DNS fallbacks if they fail this check.
+         */
+        if (check_type == GEN_DNS &&
+            !x509v3_looks_like_dns_name(astr, astrlen)) {
+            rv = 0;
+        } else {
+            rv = equal(astr, astrlen, (unsigned char *)b, blen, flags);
+        }
         if (rv > 0 && peername)
             *peername = BUF_strndup((char *)astr, astrlen);
         OPENSSL_free(astr);
@@ -994,7 +1051,7 @@
             else
                 cstr = gen->d.iPAddress;
             /* Positive on success, negative on error! */
-            if ((rv = do_check_string(cstr, alt_type, equal, flags,
+            if ((rv = do_check_string(cstr, alt_type, equal, flags, check_type,
                                       chk, chklen, peername)) != 0)
                 break;
         }
@@ -1014,7 +1071,7 @@
         ne = X509_NAME_get_entry(name, j);
         str = X509_NAME_ENTRY_get_data(ne);
         /* Positive on success, negative on error! */
-        if ((rv = do_check_string(str, -1, equal, flags,
+        if ((rv = do_check_string(str, -1, equal, flags, check_type,
                                   chk, chklen, peername)) != 0)
             return rv;
     }
diff --git a/crypto/x509v3/v3name_test.cc b/crypto/x509v3/v3name_test.cc
index 0736120..c1da9c8 100644
--- a/crypto/x509v3/v3name_test.cc
+++ b/crypto/x509v3/v3name_test.cc
@@ -65,6 +65,7 @@
 #include <openssl/x509v3.h>
 
 #include "../internal.h"
+#include "internal.h"
 
 
 static const char *const names[] = {
@@ -344,7 +345,7 @@
         ret = X509_check_host(crt, name, namelen, 0, NULL);
         match = -1;
         if (ret < 0) {
-            fprintf(stderr, "internal error in X509_check_host");
+            fprintf(stderr, "internal error in X509_check_host\n");
             ++errors;
         } else if (fn->host) {
             if (ret == 1 && !samename)
@@ -359,7 +360,7 @@
                               X509_CHECK_FLAG_NO_WILDCARDS, NULL);
         match = -1;
         if (ret < 0) {
-            fprintf(stderr, "internal error in X509_check_host");
+            fprintf(stderr, "internal error in X509_check_host\n");
             ++errors;
         } else if (fn->host) {
             if (ret == 1 && !samename)
@@ -391,6 +392,15 @@
     while (pfn->name) {
         const char *const *pname = names;
         while (*pname) {
+            // The common name fallback requires the name look sufficiently
+            // DNS-like.
+            if (strcmp(pfn->name, "set CN") == 0 &&
+                !x509v3_looks_like_dns_name(
+                    reinterpret_cast<const unsigned char*>(*pname),
+                    strlen(*pname))) {
+                ++pname;
+                continue;
+            }
             bssl::UniquePtr<X509> crt(make_cert());
             ASSERT_TRUE(crt);
             ASSERT_TRUE(pfn->fn(crt.get(), *pname));
diff --git a/include/openssl/x509_vfy.h b/include/openssl/x509_vfy.h
index 86aa546..f262334 100644
--- a/include/openssl/x509_vfy.h
+++ b/include/openssl/x509_vfy.h
@@ -370,6 +370,8 @@
 /* Issuer lookup error */
 #define		X509_V_ERR_STORE_LOOKUP				66
 
+#define		X509_V_ERR_NAME_CONSTRAINTS_WITHOUT_SANS	67
+
 /* Certificate verify flags */
 
 /* Send issuer+subject checks to verify_cb */