--- a/security/certverifier/moz.build
+++ b/security/certverifier/moz.build
@@ -1,15 +1,17 @@
 # -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
 # vim: set filetype=python:
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 UNIFIED_SOURCES += [
+    '../insanity/lib/pkixbuild.cpp',
+    '../insanity/lib/pkixcheck.cpp',
     '../insanity/lib/pkixder.cpp',
     '../insanity/lib/pkixkey.cpp',
     'CertVerifier.cpp',
     'NSSCertDBTrustDomain.cpp',
 ]
 
 if not CONFIG['NSS_NO_LIBPKIX']:
     UNIFIED_SOURCES += [

--- a/security/insanity/include/insanity/pkix.h
+++ b/security/insanity/include/insanity/pkix.h
@@ -13,21 +13,26 @@
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 #ifndef insanity_pkix__pkix_h
 #define insanity_pkix__pkix_h
 
-#include "certt.h"
-#include "seccomon.h"
+#include "pkixtypes.h"
+#include "prtime.h"
 
 namespace insanity { namespace pkix {
 
+SECStatus BuildCertChain(TrustDomain& trustDomain,
+                         CERTCertificate* cert,
+                         PRTime time,
+                 /*out*/ ScopedCERTCertList& results);
+
 // Verify the given signed data using the public key of the given certificate.
 // (EC)DSA parameter inheritance is not supported.
 SECStatus VerifySignedData(const CERTSignedData* sd,
                            const CERTCertificate* cert,
                            void* pkcs11PinArg);
 
 } } // namespace insanity::pkix
 

new file mode 100644
--- /dev/null
+++ b/security/insanity/lib/pkixbuild.cpp
@@ -0,0 +1,288 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* Copyright 2013 Mozilla Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "insanity/pkix.h"
+
+#include <limits>
+
+#include "pkixcheck.h"
+#include "pkixder.h"
+
+namespace insanity { namespace pkix {
+
+// We assume ext has been zero-initialized by its constructor and otherwise
+// not modified.
+//
+// TODO(perf): This sorting of extensions should be be moved into the
+// certificate decoder so that the results are cached with the certificate, so
+// that the decoding doesn't have to happen more than once per cert.
+Result
+BackCert::Init()
+{
+  const CERTCertExtension* const* exts = nssCert->extensions;
+  if (!exts) {
+    return Success;
+  }
+
+  const SECItem* dummyEncodedSubjectKeyIdentifier = nullptr;
+  const SECItem* dummyEncodedAuthorityKeyIdentifier = nullptr;
+  const SECItem* dummyEncodedAuthorityInfoAccess = nullptr;
+
+  for (const CERTCertExtension* ext = *exts; ext; ext = *++exts) {
+    const SECItem** out = nullptr;
+
+    if (ext->id.len == 3 &&
+        ext->id.data[0] == 0x55 && ext->id.data[1] == 0x1d) {
+      // { id-ce x }
+      switch (ext->id.data[2]) {
+        case 14: out = &dummyEncodedSubjectKeyIdentifier; break; // bug 965136
+        case 35: out = &dummyEncodedAuthorityKeyIdentifier; break; // bug 965136
+      }
+    } else if (ext->id.len == 9 &&
+               ext->id.data[0] == 0x2b && ext->id.data[1] == 0x06 &&
+               ext->id.data[2] == 0x06 && ext->id.data[3] == 0x01 &&
+               ext->id.data[4] == 0x05 && ext->id.data[5] == 0x05 &&
+               ext->id.data[6] == 0x07 && ext->id.data[7] == 0x01) {
+      // { id-pe x }
+      switch (ext->id.data[8]) {
+        // We should remember the value of the encoded AIA extension here, but
+        // since our TrustDomain implementations get the OCSP URI using
+        // CERT_GetOCSPAuthorityInfoAccessLocation, we currently don't need to.
+        case 1: out = &dummyEncodedAuthorityInfoAccess; break;
+      }
+    } else if (ext->critical.data && ext->critical.len > 0) {
+      // The only valid explicit value of the critical flag is TRUE because
+      // it is defined as BOOLEAN DEFAULT FALSE, so we just assume it is true.
+      return Fail(RecoverableError, SEC_ERROR_UNKNOWN_CRITICAL_EXTENSION);
+    }
+
+    if (out) {
+      // This is an extension we understand. Save it in results unless we've
+      // already found the extension previously.
+      if (*out) {
+        // Duplicate extension
+        return Fail(RecoverableError, SEC_ERROR_EXTENSION_VALUE_INVALID);
+      }
+      *out = &ext->value;
+    }
+  }
+
+  return Success;
+}
+
+static Result BuildForward(TrustDomain& trustDomain,
+                           BackCert& subject,
+                           PRTime time,
+                           EndEntityOrCA endEntityOrCA,
+                           unsigned int subCACount,
+                           /*out*/ ScopedCERTCertList& results);
+
+// The code that executes in the inner loop of BuildForward
+static Result
+BuildForwardInner(TrustDomain& trustDomain,
+                  BackCert& subject,
+                  PRTime time,
+                  EndEntityOrCA endEntityOrCA,
+                  CERTCertificate* potentialIssuerCertToDup,
+                  unsigned int subCACount,
+                  ScopedCERTCertList& results)
+{
+  PORT_Assert(potentialIssuerCertToDup);
+
+  BackCert potentialIssuer(potentialIssuerCertToDup, &subject);
+  Result rv = potentialIssuer.Init();
+  if (rv != Success) {
+    return rv;
+  }
+
+  // RFC5280 4.2.1.1. Authority Key Identifier
+  // RFC5280 4.2.1.2. Subject Key Identifier
+
+  // Loop prevention, done as recommended by RFC4158 Section 5.2
+  // TODO: this doesn't account for subjectAltNames!
+  // TODO(perf): This probably can and should be optimized in some way.
+  bool loopDetected = false;
+  for (BackCert* prev = potentialIssuer.childCert;
+       !loopDetected && prev != nullptr; prev = prev->childCert) {
+    if (SECITEM_ItemsAreEqual(&potentialIssuer.GetNSSCert()->derPublicKey,
+                              &prev->GetNSSCert()->derPublicKey) &&
+        SECITEM_ItemsAreEqual(&potentialIssuer.GetNSSCert()->derSubject,
+                              &prev->GetNSSCert()->derSubject)) {
+      return Fail(RecoverableError, SEC_ERROR_UNKNOWN_ISSUER); // XXX: error code
+    }
+  }
+
+  rv = CheckTimes(potentialIssuer.GetNSSCert(), time);
+  if (rv != Success) {
+    return rv;
+  }
+
+  unsigned int newSubCACount = subCACount;
+  if (endEntityOrCA == MustBeCA) {
+    newSubCACount = subCACount + 1;
+  } else {
+    PR_ASSERT(newSubCACount == 0);
+  }
+
+  rv = BuildForward(trustDomain, potentialIssuer, time, MustBeCA,
+                    newSubCACount, results);
+  if (rv != Success) {
+    return rv;
+  }
+
+  if (trustDomain.VerifySignedData(&subject.GetNSSCert()->signatureWrap,
+                                   potentialIssuer.GetNSSCert()) != SECSuccess) {
+    return MapSECStatus(SECFailure);
+  }
+
+  return Success;
+}
+
+// Caller must check for expiration before calling this function
+static Result
+BuildForward(TrustDomain& trustDomain,
+             BackCert& subject,
+             PRTime time,
+             EndEntityOrCA endEntityOrCA,
+             unsigned int subCACount,
+             /*out*/ ScopedCERTCertList& results)
+{
+  // Avoid stack overflows and poor performance by limiting cert length.
+  // XXX: 6 is not enough for chains.sh anypolicywithlevel.cfg tests
+  static const size_t MAX_DEPTH = 8;
+  if (subCACount >= MAX_DEPTH - 1) {
+    return RecoverableError;
+  }
+
+  TrustDomain::TrustLevel trustLevel;
+  Result rv = MapSECStatus(trustDomain.GetCertTrust(endEntityOrCA,
+                                                    subject.GetNSSCert(),
+                                                    &trustLevel));
+  if (rv != Success) {
+    return rv;
+  }
+  if (trustLevel == TrustDomain::ActivelyDistrusted) {
+    return Fail(RecoverableError, SEC_ERROR_UNTRUSTED_CERT);
+  }
+  if (trustLevel != TrustDomain::TrustAnchor &&
+      trustLevel != TrustDomain::InheritsTrust) {
+    // The TrustDomain returned a trust level that we weren't expecting.
+    return Fail(FatalError, PR_INVALID_STATE_ERROR);
+  }
+
+  if (trustLevel == TrustDomain::TrustAnchor) {
+    // End of the recursion. Create the result list and add the trust anchor to
+    // it.
+    results = CERT_NewCertList();
+    if (!results) {
+      return FatalError;
+    }
+    rv = subject.PrependNSSCertToList(results.get());
+    return rv;
+  }
+
+  // Find a trusted issuer.
+  // TODO(bug 965136): Add SKI/AKI matching optimizations
+  ScopedCERTCertList candidates;
+  if (trustDomain.FindPotentialIssuers(&subject.GetNSSCert()->derIssuer, time,
+                                       candidates) != SECSuccess) {
+    return MapSECStatus(SECFailure);
+  }
+  PORT_Assert(candidates.get());
+  if (!candidates) {
+    return Fail(RecoverableError, SEC_ERROR_UNKNOWN_ISSUER);
+  }
+
+  for (CERTCertListNode* n = CERT_LIST_HEAD(candidates);
+       !CERT_LIST_END(n, candidates); n = CERT_LIST_NEXT(n)) {
+    rv = BuildForwardInner(trustDomain, subject, time, endEntityOrCA,
+                           n->cert, subCACount, results);
+    if (rv == Success) {
+      // We found a trusted issuer. At this point, we know the cert is valid
+      return subject.PrependNSSCertToList(results.get());
+    }
+    if (rv != RecoverableError) {
+      return rv;
+    }
+  }
+
+  return Fail(RecoverableError, SEC_ERROR_UNKNOWN_ISSUER);
+}
+
+SECStatus
+BuildCertChain(TrustDomain& trustDomain,
+               CERTCertificate* certToDup,
+               PRTime time,
+               /*out*/ ScopedCERTCertList& results)
+{
+  PORT_Assert(certToDup);
+
+  if (!certToDup) {
+    PR_SetError(SEC_ERROR_INVALID_ARGS, 0);
+    return SECFailure;
+  }
+
+  // The only non-const operation on the cert we are allowed to do is
+  // CERT_DupCertificate.
+
+  BackCert ee(certToDup, nullptr);
+  Result rv = ee.Init();
+  if (rv != Success) {
+    return SECFailure;
+  }
+
+  rv = BuildForward(trustDomain, ee, time, MustBeEndEntity,
+                    0, results);
+  if (rv != Success) {
+    results = nullptr;
+    return SECFailure;
+  }
+
+  // Build the cert chain even if the cert is expired, because we would
+  // rather report the untrusted issuer error than the expired error.
+  if (CheckTimes(ee.GetNSSCert(), time) != Success) {
+    PR_SetError(SEC_ERROR_EXPIRED_CERTIFICATE, 0);
+    return SECFailure;
+  }
+
+  return SECSuccess;
+}
+
+PLArenaPool*
+BackCert::GetArena()
+{
+  if (!arena) {
+    arena = PORT_NewArena(DER_DEFAULT_CHUNKSIZE);
+  }
+  return arena.get();
+}
+
+Result
+BackCert::PrependNSSCertToList(CERTCertList* results)
+{
+  PORT_Assert(results);
+
+  CERTCertificate* dup = CERT_DupCertificate(nssCert);
+  if (CERT_AddCertToListHead(results, dup) != SECSuccess) { // takes ownership
+    CERT_DestroyCertificate(dup);
+    return FatalError;
+  }
+
+  return Success;
+}
+
+} } // namespace insanity::pkix

new file mode 100644
--- /dev/null
+++ b/security/insanity/lib/pkixcheck.cpp
@@ -0,0 +1,37 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* Copyright 2013 Mozilla Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "insanity/pkix.h"
+#include "pkixcheck.h"
+#include "pkixutil.h"
+
+namespace insanity { namespace pkix {
+
+Result
+CheckTimes(const CERTCertificate* cert, PRTime time)
+{
+  PR_ASSERT(cert);
+
+  SECCertTimeValidity validity = CERT_CheckCertValidTimes(cert, time, false);
+  if (validity != secCertTimeValid) {
+    return Fail(RecoverableError, SEC_ERROR_EXPIRED_CERTIFICATE);
+  }
+
+  return Success;
+}
+
+} } // namespace insanity::pkix

new file mode 100644
--- /dev/null
+++ b/security/insanity/lib/pkixcheck.h
@@ -0,0 +1,30 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* Copyright 2013 Mozilla Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef insanity__pkixcheck_h
+#define insanity__pkixcheck_h
+
+#include "pkixutil.h"
+#include "certt.h"
+
+namespace insanity { namespace pkix {
+
+Result CheckTimes(const CERTCertificate* cert, PRTime time);
+
+} } // namespace insanity::pkix
+
+#endif // insanity__pkixcheck_h

--- a/security/insanity/lib/pkixkey.cpp
+++ b/security/insanity/lib/pkixkey.cpp
@@ -11,17 +11,16 @@
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 #include "insanity/pkix.h"
-#include "insanity/pkixtypes.h"
 
 #include <limits>
 #include <stdint.h>
 
 #include "cert.h"
 #include "cryptohi.h"
 #include "prerror.h"
 #include "secerr.h"

--- a/security/insanity/lib/pkixutil.h
+++ b/security/insanity/lib/pkixutil.h
@@ -54,19 +54,61 @@ MapSECStatus(SECStatus srv)
     return Success;
   }
 
   PRErrorCode error = PORT_GetError();
   switch (error) {
     case SEC_ERROR_EXTENSION_NOT_FOUND:
       return RecoverableError;
 
+    case PR_INVALID_STATE_ERROR:
     case SEC_ERROR_LIBRARY_FAILURE:
     case SEC_ERROR_NO_MEMORY:
       return FatalError;
   }
 
   // TODO: PORT_Assert(false); // we haven't classified the error yet
   return RecoverableError;
 }
+
+// During path building and verification, we build a linked list of BackCerts
+// from the current cert toward the end-entity certificate. The linked list
+// is used to verify properties that aren't local to the current certificate
+// and/or the direct link between the current certificate and its issuer,
+// such as name constraints.
+//
+// Each BackCert contains pointers to all the given certificate's extensions
+// so that we can parse the extension block once and then process the
+// extensions in an order that may be different than they appear in the cert.
+class BackCert
+{
+public:
+  // nssCert and childCert must be valid for the lifetime of BackCert
+  BackCert(CERTCertificate* nssCert, BackCert* childCert)
+    : childCert(childCert)
+    , nssCert(nssCert)
+  {
+  }
+
+  Result Init();
+
+  BackCert* const childCert;
+
+  const CERTCertificate* GetNSSCert() const { return nssCert; }
+
+  // This is the only place where we should be dealing with non-const
+  // CERTCertificates.
+  Result PrependNSSCertToList(CERTCertList* results);
+
+  PLArenaPool* GetArena();
+
+private:
+  CERTCertificate* nssCert;
+
+  ScopedPLArenaPool arena;
+
+  BackCert(const BackCert&) /* = delete */;
+  void operator=(const BackCert&); /* = delete */;
+};
+
 } } // namespace insanity::pkix
 
 #endif // insanity_pkix__pkixutil_h