Import “altchains” support.

This change imports the following changes from upstream:

6281abc79623419eae6a64768c478272d5d3a426
dfd3322d72a2d49f597b86dab6f37a8cf0f26dbf
f34b095fab1569d093b639bfcc9a77d6020148ff
21376d8ae310cf0455ca2b73c8e9f77cafeb28dd
25efcb44ac88ab34f60047e16a96c9462fad39c1
56353962e7da7e385c3d577581ccc3015ed6d1dc
39c76ceb2d3e51eaff95e04d6e4448f685718f8d
a3d74afcae435c549de8dbaa219fcb30491c1bfb

These contain the “altchains” functionality which allows OpenSSL to
backtrack when chain building.

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

4 files changed, 437 insertions, 72 deletions

diff --git a/crypto/x509/CMakeLists.txt b/crypto/x509/CMakeLists.txt
index 8ffeaa0d..2d92bf38 100644
--- a/crypto/x509/CMakeLists.txt
+++ b/crypto/x509/CMakeLists.txt
@@ -64,5 +64,14 @@ add_executable(
   $<TARGET_OBJECTS:test_support>
 )
 
+add_executable(
+  x509_test
+
+  x509_test.cc
+
+  $<TARGET_OBJECTS:test_support>
+)
+
 target_link_libraries(pkcs7_test crypto)
-add_dependencies(all_tests pkcs7_test)
+target_link_libraries(x509_test crypto)
+add_dependencies(all_tests pkcs7_test x509_test)
diff --git a/crypto/x509/x509_lu.c b/crypto/x509/x509_lu.c
index 7859c943..bfe6b11b 100644
--- a/crypto/x509/x509_lu.c
+++ b/crypto/x509/x509_lu.c
@@ -219,6 +219,9 @@ X509_STORE *X509_STORE_new(void)
 
 static void cleanup(X509_OBJECT *a)
 {
+    if (a == NULL) {
+        return;
+    }
     if (a->type == X509_LU_X509) {
         X509_free(a->data.x509);
     } else if (a->type == X509_LU_CRL) {
diff --git a/crypto/x509/x509_test.cc b/crypto/x509/x509_test.cc
new file mode 100644
index 00000000..b5769ccd
--- /dev/null
+++ b/crypto/x509/x509_test.cc
@@ -0,0 +1,305 @@
+/* Copyright (c) 2016, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+#include <vector>
+
+#include <assert.h>
+#include <string.h>
+
+#include <openssl/err.h>
+#include <openssl/pem.h>
+
+#include "../test/scoped_types.h"
+
+
+static const char kCrossSigningRootPEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICcTCCAdqgAwIBAgIIagJHiPvE0MowDQYJKoZIhvcNAQELBQAwPDEaMBgGA1UE\n"
+"ChMRQm9yaW5nU1NMIFRFU1RJTkcxHjAcBgNVBAMTFUNyb3NzLXNpZ25pbmcgUm9v\n"
+"dCBDQTAgFw0xNTAxMDEwMDAwMDBaGA8yMTAwMDEwMTAwMDAwMFowPDEaMBgGA1UE\n"
+"ChMRQm9yaW5nU1NMIFRFU1RJTkcxHjAcBgNVBAMTFUNyb3NzLXNpZ25pbmcgUm9v\n"
+"dCBDQTCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEAwo3qFvSB9Zmlbpzn9wJp\n"
+"ikI75Rxkatez8VkLqyxbOhPYl2Haz8F5p1gDG96dCI6jcLGgu3AKT9uhEQyyUko5\n"
+"EKYasazSeA9CQrdyhPg0mkTYVETnPM1W/ebid1YtqQbq1CMWlq2aTDoSGAReGFKP\n"
+"RTdXAbuAXzpCfi/d8LqV13UCAwEAAaN6MHgwDgYDVR0PAQH/BAQDAgIEMB0GA1Ud\n"
+"JQQWMBQGCCsGAQUFBwMBBggrBgEFBQcDAjAPBgNVHRMBAf8EBTADAQH/MBkGA1Ud\n"
+"DgQSBBBHKHC7V3Z/3oLvEZx0RZRwMBsGA1UdIwQUMBKAEEcocLtXdn/egu8RnHRF\n"
+"lHAwDQYJKoZIhvcNAQELBQADgYEAnglibsy6mGtpIXivtlcz4zIEnHw/lNW+r/eC\n"
+"CY7evZTmOoOuC/x9SS3MF9vawt1HFUummWM6ZgErqVBOXIB4//ykrcCgf5ZbF5Hr\n"
+"+3EFprKhBqYiXdD8hpBkrBoXwn85LPYWNd2TceCrx0YtLIprE2R5MB2RIq8y4Jk3\n"
+"YFXvkME=\n"
+"-----END CERTIFICATE-----\n";
+
+static const char kRootCAPEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICVTCCAb6gAwIBAgIIAj5CwoHlWuYwDQYJKoZIhvcNAQELBQAwLjEaMBgGA1UE\n"
+"ChMRQm9yaW5nU1NMIFRFU1RJTkcxEDAOBgNVBAMTB1Jvb3QgQ0EwIBcNMTUwMTAx\n"
+"MDAwMDAwWhgPMjEwMDAxMDEwMDAwMDBaMC4xGjAYBgNVBAoTEUJvcmluZ1NTTCBU\n"
+"RVNUSU5HMRAwDgYDVQQDEwdSb290IENBMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCB\n"
+"iQKBgQDpDn8RDOZa5oaDcPZRBy4CeBH1siSSOO4mYgLHlPE+oXdqwI/VImi2XeJM\n"
+"2uCFETXCknJJjYG0iJdrt/yyRFvZTQZw+QzGj+mz36NqhGxDWb6dstB2m8PX+plZ\n"
+"w7jl81MDvUnWs8yiQ/6twgu5AbhWKZQDJKcNKCEpqa6UW0r5nwIDAQABo3oweDAO\n"
+"BgNVHQ8BAf8EBAMCAgQwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMA8G\n"
+"A1UdEwEB/wQFMAMBAf8wGQYDVR0OBBIEEEA31wH7QC+4HH5UBCeMWQEwGwYDVR0j\n"
+"BBQwEoAQQDfXAftAL7gcflQEJ4xZATANBgkqhkiG9w0BAQsFAAOBgQDXylEK77Za\n"
+"kKeY6ZerrScWyZhrjIGtHFu09qVpdJEzrk87k2G7iHHR9CAvSofCgEExKtWNS9dN\n"
+"+9WiZp/U48iHLk7qaYXdEuO07No4BYtXn+lkOykE+FUxmA4wvOF1cTd2tdj3MzX2\n"
+"kfGIBAYhzGZWhY3JbhIfTEfY1PNM1pWChQ==\n"
+"-----END CERTIFICATE-----\n";
+
+static const char kRootCrossSignedPEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICYzCCAcygAwIBAgIIAj5CwoHlWuYwDQYJKoZIhvcNAQELBQAwPDEaMBgGA1UE\n"
+"ChMRQm9yaW5nU1NMIFRFU1RJTkcxHjAcBgNVBAMTFUNyb3NzLXNpZ25pbmcgUm9v\n"
+"dCBDQTAgFw0xNTAxMDEwMDAwMDBaGA8yMTAwMDEwMTAwMDAwMFowLjEaMBgGA1UE\n"
+"ChMRQm9yaW5nU1NMIFRFU1RJTkcxEDAOBgNVBAMTB1Jvb3QgQ0EwgZ8wDQYJKoZI\n"
+"hvcNAQEBBQADgY0AMIGJAoGBAOkOfxEM5lrmhoNw9lEHLgJ4EfWyJJI47iZiAseU\n"
+"8T6hd2rAj9UiaLZd4kza4IURNcKSckmNgbSIl2u3/LJEW9lNBnD5DMaP6bPfo2qE\n"
+"bENZvp2y0Habw9f6mVnDuOXzUwO9SdazzKJD/q3CC7kBuFYplAMkpw0oISmprpRb\n"
+"SvmfAgMBAAGjejB4MA4GA1UdDwEB/wQEAwICBDAdBgNVHSUEFjAUBggrBgEFBQcD\n"
+"AQYIKwYBBQUHAwIwDwYDVR0TAQH/BAUwAwEB/zAZBgNVHQ4EEgQQQDfXAftAL7gc\n"
+"flQEJ4xZATAbBgNVHSMEFDASgBBHKHC7V3Z/3oLvEZx0RZRwMA0GCSqGSIb3DQEB\n"
+"CwUAA4GBAErTxYJ0en9HVRHAAr5OO5wuk5Iq3VMc79TMyQLCXVL8YH8Uk7KEwv+q\n"
+"9MEKZv2eR/Vfm4HlXlUuIqfgUXbwrAYC/YVVX86Wnbpy/jc73NYVCq8FEZeO+0XU\n"
+"90SWAPDdp+iL7aZdimnMtG1qlM1edmz8AKbrhN/R3IbA2CL0nCWV\n"
+"-----END CERTIFICATE-----\n";
+
+static const char kIntermediatePEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICXjCCAcegAwIBAgIJAKJMH+7rscPcMA0GCSqGSIb3DQEBCwUAMC4xGjAYBgNV\n"
+"BAoTEUJvcmluZ1NTTCBURVNUSU5HMRAwDgYDVQQDEwdSb290IENBMCAXDTE1MDEw\n"
+"MTAwMDAwMFoYDzIxMDAwMTAxMDAwMDAwWjA2MRowGAYDVQQKExFCb3JpbmdTU0wg\n"
+"VEVTVElORzEYMBYGA1UEAxMPSW50ZXJtZWRpYXRlIENBMIGfMA0GCSqGSIb3DQEB\n"
+"AQUAA4GNADCBiQKBgQC7YtI0l8ocTYJ0gKyXTtPL4iMJCNY4OcxXl48jkncVG1Hl\n"
+"blicgNUa1r9m9YFtVkxvBinb8dXiUpEGhVg4awRPDcatlsBSEBuJkiZGYbRcAmSu\n"
+"CmZYnf6u3aYQ18SU8WqVERPpE4cwVVs+6kwlzRw0+XDoZAczu8ZezVhCUc6NbQID\n"
+"AQABo3oweDAOBgNVHQ8BAf8EBAMCAgQwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsG\n"
+"AQUFBwMCMA8GA1UdEwEB/wQFMAMBAf8wGQYDVR0OBBIEEIwaaKi1dttdV3sfjRSy\n"
+"BqMwGwYDVR0jBBQwEoAQQDfXAftAL7gcflQEJ4xZATANBgkqhkiG9w0BAQsFAAOB\n"
+"gQCvnolNWEHuQS8PFVVyuLR+FKBeUUdrVbSfHSzTqNAqQGp0C9fk5oCzDq6ZgTfY\n"
+"ESXM4cJhb3IAnW0UM0NFsYSKQJ50JZL2L3z5ZLQhHdbs4RmODGoC40BVdnJ4/qgB\n"
+"aGSh09eQRvAVmbVCviDK2ipkWNegdyI19jFfNP5uIkGlYg==\n"
+"-----END CERTIFICATE-----\n";
+
+static const char kIntermediateSelfSignedPEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICZjCCAc+gAwIBAgIJAKJMH+7rscPcMA0GCSqGSIb3DQEBCwUAMDYxGjAYBgNV\n"
+"BAoTEUJvcmluZ1NTTCBURVNUSU5HMRgwFgYDVQQDEw9JbnRlcm1lZGlhdGUgQ0Ew\n"
+"IBcNMTUwMTAxMDAwMDAwWhgPMjEwMDAxMDEwMDAwMDBaMDYxGjAYBgNVBAoTEUJv\n"
+"cmluZ1NTTCBURVNUSU5HMRgwFgYDVQQDEw9JbnRlcm1lZGlhdGUgQ0EwgZ8wDQYJ\n"
+"KoZIhvcNAQEBBQADgY0AMIGJAoGBALti0jSXyhxNgnSArJdO08viIwkI1jg5zFeX\n"
+"jyOSdxUbUeVuWJyA1RrWv2b1gW1WTG8GKdvx1eJSkQaFWDhrBE8Nxq2WwFIQG4mS\n"
+"JkZhtFwCZK4KZlid/q7dphDXxJTxapURE+kThzBVWz7qTCXNHDT5cOhkBzO7xl7N\n"
+"WEJRzo1tAgMBAAGjejB4MA4GA1UdDwEB/wQEAwICBDAdBgNVHSUEFjAUBggrBgEF\n"
+"BQcDAQYIKwYBBQUHAwIwDwYDVR0TAQH/BAUwAwEB/zAZBgNVHQ4EEgQQjBpoqLV2\n"
+"211Xex+NFLIGozAbBgNVHSMEFDASgBCMGmiotXbbXVd7H40UsgajMA0GCSqGSIb3\n"
+"DQEBCwUAA4GBALcccSrAQ0/EqQBsx0ZDTUydHXXNP2DrUkpUKmAXIe8McqIVSlkT\n"
+"6H4xz7z8VRKBo9j+drjjtCw2i0CQc8aOLxRb5WJ8eVLnaW2XRlUqAzhF0CrulfVI\n"
+"E4Vs6ZLU+fra1WAuIj6qFiigRja+3YkZArG8tMA9vtlhTX/g7YBZIkqH\n"
+"-----END CERTIFICATE-----\n";
+
+static const char kLeafPEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICXjCCAcegAwIBAgIIWjO48ufpunYwDQYJKoZIhvcNAQELBQAwNjEaMBgGA1UE\n"
+"ChMRQm9yaW5nU1NMIFRFU1RJTkcxGDAWBgNVBAMTD0ludGVybWVkaWF0ZSBDQTAg\n"
+"Fw0xNTAxMDEwMDAwMDBaGA8yMTAwMDEwMTAwMDAwMFowMjEaMBgGA1UEChMRQm9y\n"
+"aW5nU1NMIFRFU1RJTkcxFDASBgNVBAMTC2V4YW1wbGUuY29tMIGfMA0GCSqGSIb3\n"
+"DQEBAQUAA4GNADCBiQKBgQDD0U0ZYgqShJ7oOjsyNKyVXEHqeafmk/bAoPqY/h1c\n"
+"oPw2E8KmeqiUSoTPjG5IXSblOxcqpbAXgnjPzo8DI3GNMhAf8SYNYsoH7gc7Uy7j\n"
+"5x8bUrisGnuTHqkqH6d4/e7ETJ7i3CpR8bvK16DggEvQTudLipz8FBHtYhFakfdh\n"
+"TwIDAQABo3cwdTAOBgNVHQ8BAf8EBAMCBaAwHQYDVR0lBBYwFAYIKwYBBQUHAwEG\n"
+"CCsGAQUFBwMCMAwGA1UdEwEB/wQCMAAwGQYDVR0OBBIEEKN5pvbur7mlXjeMEYA0\n"
+"4nUwGwYDVR0jBBQwEoAQjBpoqLV2211Xex+NFLIGozANBgkqhkiG9w0BAQsFAAOB\n"
+"gQBj/p+JChp//LnXWC1k121LM/ii7hFzQzMrt70bny406SGz9jAjaPOX4S3gt38y\n"
+"rhjpPukBlSzgQXFg66y6q5qp1nQTD1Cw6NkKBe9WuBlY3iYfmsf7WT8nhlT1CttU\n"
+"xNCwyMX9mtdXdQicOfNjIGUCD5OLV5PgHFPRKiHHioBAhg==\n"
+"-----END CERTIFICATE-----\n";
+
+static const char kLeafNoKeyUsagePEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICNTCCAZ6gAwIBAgIJAIFQGaLQ0G2mMA0GCSqGSIb3DQEBCwUAMDYxGjAYBgNV\n"
+"BAoTEUJvcmluZ1NTTCBURVNUSU5HMRgwFgYDVQQDEw9JbnRlcm1lZGlhdGUgQ0Ew\n"
+"IBcNMTUwMTAxMDAwMDAwWhgPMjEwMDAxMDEwMDAwMDBaMDcxGjAYBgNVBAoTEUJv\n"
+"cmluZ1NTTCBURVNUSU5HMRkwFwYDVQQDExBldmlsLmV4YW1wbGUuY29tMIGfMA0G\n"
+"CSqGSIb3DQEBAQUAA4GNADCBiQKBgQDOKoZe75NPz77EOaMMl4/0s3PyQw++zJvp\n"
+"ejHAxZiTPCJgMbEHLrSzNoHdopg+CLUH5bE4wTXM8w9Inv5P8OAFJt7gJuPUunmk\n"
+"j+NoU3QfzOR6BroePcz1vXX9jyVHRs087M/sLqWRHu9IR+/A+UTcBaWaFiDVUxtJ\n"
+"YOwFMwjNPQIDAQABo0gwRjAMBgNVHRMBAf8EAjAAMBkGA1UdDgQSBBBJfLEUWHq1\n"
+"27rZ1AVx2J5GMBsGA1UdIwQUMBKAEIwaaKi1dttdV3sfjRSyBqMwDQYJKoZIhvcN\n"
+"AQELBQADgYEALVKN2Y3LZJOtu6SxFIYKxbLaXhTGTdIjxipZhmbBRDFjbZjZZOTe\n"
+"6Oo+VDNPYco4rBexK7umYXJyfTqoY0E8dbiImhTcGTEj7OAB3DbBomgU1AYe+t2D\n"
+"uwBqh4Y3Eto+Zn4pMVsxGEfUpjzjZDel7bN1/oU/9KWPpDfywfUmjgk=\n"
+"-----END CERTIFICATE-----\n";
+
+static const char kForgeryPEM[] =
+"-----BEGIN CERTIFICATE-----\n"
+"MIICZzCCAdCgAwIBAgIIdTlMzQoKkeMwDQYJKoZIhvcNAQELBQAwNzEaMBgGA1UE\n"
+"ChMRQm9yaW5nU1NMIFRFU1RJTkcxGTAXBgNVBAMTEGV2aWwuZXhhbXBsZS5jb20w\n"
+"IBcNMTUwMTAxMDAwMDAwWhgPMjEwMDAxMDEwMDAwMDBaMDoxGjAYBgNVBAoTEUJv\n"
+"cmluZ1NTTCBURVNUSU5HMRwwGgYDVQQDExNmb3JnZXJ5LmV4YW1wbGUuY29tMIGf\n"
+"MA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDADTwruBQZGb7Ay6s9HiYv5d1lwtEy\n"
+"xQdA2Sy8Rn8uA20Q4KgqwVY7wzIZ+z5Butrsmwb70gdG1XU+yRaDeE7XVoW6jSpm\n"
+"0sw35/5vJbTcL4THEFbnX0OPZnvpuZDFUkvVtq5kxpDWsVyM24G8EEq7kPih3Sa3\n"
+"OMhXVXF8kso6UQIDAQABo3cwdTAOBgNVHQ8BAf8EBAMCBaAwHQYDVR0lBBYwFAYI\n"
+"KwYBBQUHAwEGCCsGAQUFBwMCMAwGA1UdEwEB/wQCMAAwGQYDVR0OBBIEEEYJ/WHM\n"
+"8p64erPWIg4/liwwGwYDVR0jBBQwEoAQSXyxFFh6tdu62dQFcdieRjANBgkqhkiG\n"
+"9w0BAQsFAAOBgQA+zH7bHPElWRWJvjxDqRexmYLn+D3Aivs8XgXQJsM94W0EzSUf\n"
+"DSLfRgaQwcb2gg2xpDFoG+W0vc6O651uF23WGt5JaFFJJxqjII05IexfCNhuPmp4\n"
+"4UZAXPttuJXpn74IY1tuouaM06B3vXKZR+/ityKmfJvSwxacmFcK+2ziAg==\n"
+"-----END CERTIFICATE-----\n";
+
+
+// CertFromPEM parses the given, NUL-terminated PEM block and returns an
+// |X509*|.
+static X509* CertFromPEM(const char *pem) {
+  ScopedBIO bio(BIO_new_mem_buf(const_cast<char*>(pem), strlen(pem)));
+  return PEM_read_bio_X509(bio.get(), nullptr, nullptr, nullptr);
+}
+
+// CertsToStack converts a vector of |X509*| to an OpenSSL STACK_OF(X509*),
+// bumping the reference counts for each certificate in question.
+static STACK_OF(X509)* CertsToStack(const std::vector<X509*> &certs) {
+  ScopedX509Stack stack(sk_X509_new_null());
+  for (auto cert : certs) {
+    if (!sk_X509_push(stack.get(), cert)) {
+      return nullptr;
+    }
+    X509_up_ref(cert);
+  }
+
+  return stack.release();
+}
+
+static bool Verify(X509 *leaf, const std::vector<X509 *> &roots,
+                   const std::vector<X509 *> &intermediates,
+                   unsigned long flags = 0) {
+  ScopedX509Stack roots_stack(CertsToStack(roots));
+  ScopedX509Stack intermediates_stack(CertsToStack(intermediates));
+  if (!roots_stack ||
+      !intermediates_stack) {
+    return false;
+  }
+
+  ScopedX509_STORE_CTX ctx(X509_STORE_CTX_new());
+  if (!ctx) {
+    return false;
+  }
+  if (!X509_STORE_CTX_init(ctx.get(), nullptr /* no X509_STORE */, leaf,
+                           intermediates_stack.get())) {
+    return false;
+  }
+
+  X509_STORE_CTX_trusted_stack(ctx.get(), roots_stack.get());
+
+  X509_VERIFY_PARAM *param = X509_VERIFY_PARAM_new();
+  if (param == nullptr) {
+    return false;
+  }
+  X509_VERIFY_PARAM_set_time(param, 1452807555 /* Jan 14th, 2016 */);
+  X509_VERIFY_PARAM_set_depth(param, 16);
+  if (flags) {
+    X509_VERIFY_PARAM_set_flags(param, flags);
+  }
+  X509_STORE_CTX_set0_param(ctx.get(), param);
+
+  ERR_clear_error();
+  return X509_verify_cert(ctx.get()) == 1;
+}
+
+int main(int argc, char **argv) {
+  ScopedX509 cross_signing_root(CertFromPEM(kCrossSigningRootPEM));
+  ScopedX509 root(CertFromPEM(kRootCAPEM));
+  ScopedX509 root_cross_signed(CertFromPEM(kRootCrossSignedPEM));
+  ScopedX509 intermediate(CertFromPEM(kIntermediatePEM));
+  ScopedX509 intermediate_self_signed(CertFromPEM(kIntermediateSelfSignedPEM));
+  ScopedX509 leaf(CertFromPEM(kLeafPEM));
+  ScopedX509 leaf_no_key_usage(CertFromPEM(kLeafNoKeyUsagePEM));
+  ScopedX509 forgery(CertFromPEM(kForgeryPEM));
+
+  if (!cross_signing_root ||
+      !root ||
+      !root_cross_signed ||
+      !intermediate ||
+      !intermediate_self_signed ||
+      !leaf ||
+      !leaf_no_key_usage ||
+      !forgery) {
+    fprintf(stderr, "Failed to parse certificates\n");
+    return 1;
+  }
+
+  if (Verify(leaf.get(), {}, {})) {
+    fprintf(stderr, "Leaf verified with no roots!\n");
+    return 1;
+  }
+
+  if (Verify(leaf.get(), {}, {intermediate.get()})) {
+    fprintf(stderr, "Leaf verified with no roots!\n");
+    return 1;
+  }
+
+  if (!Verify(leaf.get(), {root.get()}, {intermediate.get()})) {
+    ERR_print_errors_fp(stderr);
+    fprintf(stderr, "Basic chain didn't verify.\n");
+    return 1;
+  }
+
+  if (!Verify(leaf.get(), {cross_signing_root.get()},
+              {intermediate.get(), root_cross_signed.get()})) {
+    ERR_print_errors_fp(stderr);
+    fprintf(stderr, "Cross-signed chain didn't verify.\n");
+    return 1;
+  }
+
+  if (!Verify(leaf.get(), {cross_signing_root.get(), root.get()},
+              {intermediate.get(), root_cross_signed.get()})) {
+    ERR_print_errors_fp(stderr);
+    fprintf(stderr, "Cross-signed chain with root didn't verify.\n");
+    return 1;
+  }
+
+  /* This is the “altchains” test – we remove the cross-signing CA but include
+   * the cross-sign in the intermediates. */
+  if (!Verify(leaf.get(), {root.get()},
+              {intermediate.get(), root_cross_signed.get()})) {
+    ERR_print_errors_fp(stderr);
+    fprintf(stderr, "Chain with cross-sign didn't backtrack to find root.\n");
+    return 1;
+  }
+
+  if (Verify(leaf.get(), {root.get()},
+             {intermediate.get(), root_cross_signed.get()},
+             X509_V_FLAG_NO_ALT_CHAINS)) {
+    fprintf(stderr, "Altchains test still passed when disabled.\n");
+    return 1;
+  }
+
+  if (Verify(forgery.get(), {intermediate_self_signed.get()},
+             {leaf_no_key_usage.get()})) {
+    fprintf(stderr, "Basic constraints weren't checked.\n");
+    return 1;
+  }
+
+  /* Test that one cannot skip Basic Constraints checking with a contorted set
+   * of roots and intermediates. This is a regression test for CVE-2015-1793. */
+  if (Verify(forgery.get(),
+             {intermediate_self_signed.get(), root_cross_signed.get()},
+             {leaf_no_key_usage.get(), intermediate.get()})) {
+    fprintf(stderr, "Basic constraints weren't checked.\n");
+    return 1;
+  }
+
+  printf("PASS\n");
+  return 0;
+}
diff --git a/crypto/x509/x509_vfy.c b/crypto/x509/x509_vfy.c
index 98d7501d..602c8fbc 100644
--- a/crypto/x509/x509_vfy.c
+++ b/crypto/x509/x509_vfy.c
@@ -189,11 +189,11 @@ static X509 *lookup_cert_match(X509_STORE_CTX *ctx, X509 *x)
 
 int X509_verify_cert(X509_STORE_CTX *ctx)
 {
-    X509 *x, *xtmp, *chain_ss = NULL;
+    X509 *x, *xtmp, *xtmp2, *chain_ss = NULL;
     int bad_chain = 0;
     X509_VERIFY_PARAM *param = ctx->param;
     int depth, i, ok = 0;
-    int num;
+    int num, j, retry;
     int (*cb) (int xok, X509_STORE_CTX *xctx);
     STACK_OF(X509) *sktmp = NULL;
     if (ctx->cert == NULL) {
@@ -284,92 +284,129 @@ int X509_verify_cert(X509_STORE_CTX *ctx)
         break;
     }
 
+    /* Remember how many untrusted certs we have */
+    j = num;
     /*
      * at this point, chain should contain a list of untrusted certificates.
      * We now need to add at least one trusted one, if possible, otherwise we
      * complain.
      */
 
-    /*
-     * Examine last certificate in chain and see if it is self signed.
-     */
-
-    i = sk_X509_num(ctx->chain);
-    x = sk_X509_value(ctx->chain, i - 1);
-    if (cert_self_signed(x)) {
-        /* we have a self signed certificate */
-        if (sk_X509_num(ctx->chain) == 1) {
-            /*
-             * We have a single self signed certificate: see if we can find
-             * it in the store. We must have an exact match to avoid possible
-             * impersonation.
-             */
-            ok = ctx->get_issuer(&xtmp, ctx, x);
-            if ((ok <= 0) || X509_cmp(x, xtmp)) {
-                ctx->error = X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT;
-                ctx->current_cert = x;
-                ctx->error_depth = i - 1;
-                if (ok == 1)
-                    X509_free(xtmp);
-                bad_chain = 1;
-                ok = cb(0, ctx);
-                if (!ok)
-                    goto end;
+    do {
+        /*
+         * Examine last certificate in chain and see if it is self signed.
+         */
+        i = sk_X509_num(ctx->chain);
+        x = sk_X509_value(ctx->chain, i - 1);
+        if (cert_self_signed(x)) {
+            /* we have a self signed certificate */
+            if (sk_X509_num(ctx->chain) == 1) {
+                /*
+                 * We have a single self signed certificate: see if we can
+                 * find it in the store. We must have an exact match to avoid
+                 * possible impersonation.
+                 */
+                ok = ctx->get_issuer(&xtmp, ctx, x);
+                if ((ok <= 0) || X509_cmp(x, xtmp)) {
+                    ctx->error = X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT;
+                    ctx->current_cert = x;
+                    ctx->error_depth = i - 1;
+                    if (ok == 1)
+                        X509_free(xtmp);
+                    bad_chain = 1;
+                    ok = cb(0, ctx);
+                    if (!ok)
+                        goto end;
+                } else {
+                    /*
+                     * We have a match: replace certificate with store
+                     * version so we get any trust settings.
+                     */
+                    X509_free(x);
+                    x = xtmp;
+                    (void)sk_X509_set(ctx->chain, i - 1, x);
+                    ctx->last_untrusted = 0;
+                }
             } else {
                 /*
-                 * We have a match: replace certificate with store version so
-                 * we get any trust settings.
+                 * extract and save self signed certificate for later use
                  */
-                X509_free(x);
-                x = xtmp;
-                (void)sk_X509_set(ctx->chain, i - 1, x);
-                ctx->last_untrusted = 0;
+                chain_ss = sk_X509_pop(ctx->chain);
+                ctx->last_untrusted--;
+                num--;
+                j--;
+                x = sk_X509_value(ctx->chain, num - 1);
             }
-        } else {
-            /*
-             * extract and save self signed certificate for later use
-             */
-            chain_ss = sk_X509_pop(ctx->chain);
-            ctx->last_untrusted--;
-            num--;
-            x = sk_X509_value(ctx->chain, num - 1);
         }
-    }
-
-    /* We now lookup certs from the certificate store */
-    for (;;) {
-        /* If we have enough, we break */
-        if (depth < num)
-            break;
+        /* We now lookup certs from the certificate store */
+        for (;;) {
+            /* If we have enough, we break */
+            if (depth < num)
+                break;
+            /* If we are self signed, we break */
+            if (cert_self_signed(x))
+                break;
+            ok = ctx->get_issuer(&xtmp, ctx, x);
 
-        /* If we are self signed, we break */
-        if (cert_self_signed(x))
-            break;
+            if (ok < 0)
+                goto end;
+            if (ok == 0)
+                break;
+            x = xtmp;
+            if (!sk_X509_push(ctx->chain, x)) {
+                X509_free(xtmp);
+                OPENSSL_PUT_ERROR(X509, ERR_R_MALLOC_FAILURE);
+                ok = 0;
+                goto end;
+            }
+            num++;
+        }
 
-        ok = ctx->get_issuer(&xtmp, ctx, x);
+        /* we now have our chain, lets check it... */
+        i = check_trust(ctx);
 
-        if (ok < 0)
+        /* If explicitly rejected error */
+        if (i == X509_TRUST_REJECTED)
             goto end;
-        if (ok == 0)
-            break;
+        /*
+         * If it's not explicitly trusted then check if there is an alternative
+         * chain that could be used. We only do this if we haven't already
+         * checked via TRUSTED_FIRST and the user hasn't switched off alternate
+         * chain checking
+         */
+        retry = 0;
+        if (i != X509_TRUST_TRUSTED
+            && !(ctx->param->flags & X509_V_FLAG_TRUSTED_FIRST)
+            && !(ctx->param->flags & X509_V_FLAG_NO_ALT_CHAINS)) {
+            while (j-- > 1) {
+                xtmp2 = sk_X509_value(ctx->chain, j - 1);
+                ok = ctx->get_issuer(&xtmp, ctx, xtmp2);
+                if (ok < 0)
+                    goto end;
+                /* Check if we found an alternate chain */
+                if (ok > 0) {
+                    /*
+                     * Free up the found cert we'll add it again later
+                     */
+                    X509_free(xtmp);
 
-        x = xtmp;
-        if (!sk_X509_push(ctx->chain, x)) {
-            X509_free(xtmp);
-            OPENSSL_PUT_ERROR(X509, ERR_R_MALLOC_FAILURE);
-            ok = 0;
-            goto end;
+                    /*
+                     * Dump all the certs above this point - we've found an
+                     * alternate chain
+                     */
+                    while (num > j) {
+                        xtmp = sk_X509_pop(ctx->chain);
+                        X509_free(xtmp);
+                        num--;
+                    }
+                    ctx->last_untrusted = sk_X509_num(ctx->chain);
+                    retry = 1;
+                    break;
+                }
+            }
         }
-        num++;
-    }
+    } while (retry);
 
-    /* we now have our chain, lets check it... */
-
-    i = check_trust(ctx);
-
-    /* If explicitly rejected error */
-    if (i == X509_TRUST_REJECTED)
-        goto end;
     /*
      * If not explicitly trusted then indicate error unless it's a single
      * self signed certificate in which case we've indicated an error already
@@ -696,6 +733,10 @@ static int check_hosts(X509 *x, X509_VERIFY_PARAM_ID *id)
     size_t n = sk_OPENSSL_STRING_num(id->hosts);
     char *name;
 
+    if (id->peername != NULL) {
+        OPENSSL_free(id->peername);
+        id->peername = NULL;
+    }
     for (i = 0; i < n; ++i) {
         name = sk_OPENSSL_STRING_value(id->hosts, i);
         if (X509_check_host(x, name, strlen(name), id->hostflags,
@@ -2160,6 +2201,9 @@ X509_STORE_CTX *X509_STORE_CTX_new(void)
 
 void X509_STORE_CTX_free(X509_STORE_CTX *ctx)
 {
+    if (ctx == NULL) {
+        return;
+    }
     X509_STORE_CTX_cleanup(ctx);
     OPENSSL_free(ctx);
 }
@@ -2280,8 +2324,12 @@ void X509_STORE_CTX_trusted_stack(X509_STORE_CTX *ctx, STACK_OF(X509) *sk)
 
 void X509_STORE_CTX_cleanup(X509_STORE_CTX *ctx)
 {
-    if (ctx->cleanup)
+    /* We need to be idempotent because, unfortunately, |X509_STORE_CTX_free|
+     * also calls this function. */
+    if (ctx->cleanup != NULL) {
         ctx->cleanup(ctx);
+        ctx->cleanup = NULL;
+    }
     if (ctx->param != NULL) {
         if (ctx->parent == NULL)
             X509_VERIFY_PARAM_free(ctx->param);