--- a/security/pkix/lib/pkixbuild.cpp
+++ b/security/pkix/lib/pkixbuild.cpp
@@ -31,41 +31,44 @@ namespace mozilla { namespace pkix {
 
 static Result BuildForward(TrustDomain& trustDomain,
                            const BackCert& subject,
                            Time time,
                            KeyUsage requiredKeyUsageIfPresent,
                            KeyPurposeId requiredEKUIfPresent,
                            const CertPolicyId& requiredPolicy,
                            /*optional*/ const Input* stapledOCSPResponse,
-                           unsigned int subCACount);
+                           unsigned int subCACount,
+                           unsigned int& buildForwardCallBudget);
 
 TrustDomain::IssuerChecker::IssuerChecker() { }
 TrustDomain::IssuerChecker::~IssuerChecker() { }
 
 // The implementation of TrustDomain::IssuerTracker is in a subclass only to
 // hide the implementation from external users.
 class PathBuildingStep final : public TrustDomain::IssuerChecker
 {
 public:
   PathBuildingStep(TrustDomain& aTrustDomain, const BackCert& aSubject,
                    Time aTime, KeyPurposeId aRequiredEKUIfPresent,
                    const CertPolicyId& aRequiredPolicy,
                    /*optional*/ const Input* aStapledOCSPResponse,
-                   unsigned int aSubCACount, Result aDeferredSubjectError)
+                   unsigned int aSubCACount, Result aDeferredSubjectError,
+                   unsigned int& aBuildForwardCallBudget)
     : trustDomain(aTrustDomain)
     , subject(aSubject)
     , time(aTime)
     , requiredEKUIfPresent(aRequiredEKUIfPresent)
     , requiredPolicy(aRequiredPolicy)
     , stapledOCSPResponse(aStapledOCSPResponse)
     , subCACount(aSubCACount)
     , deferredSubjectError(aDeferredSubjectError)
     , result(Result::FATAL_ERROR_LIBRARY_FAILURE)
     , resultWasSet(false)
+    , buildForwardCallBudget(aBuildForwardCallBudget)
   {
   }
 
   Result Check(Input potentialIssuerDER,
                /*optional*/ const Input* additionalNameConstraints,
                /*out*/ bool& keepGoing) override;
 
   Result CheckResult() const;
@@ -83,16 +86,17 @@ private:
   // Initialized lazily.
   uint8_t subjectSignatureDigestBuf[MAX_DIGEST_SIZE_IN_BYTES];
   der::PublicKeyAlgorithm subjectSignaturePublicKeyAlg;
   SignedDigest subjectSignature;
 
   Result RecordResult(Result currentResult, /*out*/ bool& keepGoing);
   Result result;
   bool resultWasSet;
+  unsigned int& buildForwardCallBudget;
 
   PathBuildingStep(const PathBuildingStep&) = delete;
   void operator=(const PathBuildingStep&) = delete;
 };
 
 Result
 PathBuildingStep::RecordResult(Result newResult, /*out*/ bool& keepGoing)
 {
@@ -187,21 +191,30 @@ PathBuildingStep::Check(Input potentialI
     }
   }
 
   rv = CheckTLSFeatures(subject, potentialIssuer);
   if (rv != Success) {
     return RecordResult(rv, keepGoing);
   }
 
+  // If we've ran out of budget, stop searching.
+  if (buildForwardCallBudget == 0) {
+    Result savedRv = RecordResult(Result::ERROR_UNKNOWN_ISSUER, keepGoing);
+    keepGoing = false;
+    return savedRv;
+  }
+  buildForwardCallBudget--;
+
   // RFC 5280, Section 4.2.1.3: "If the keyUsage extension is present, then the
   // subject public key MUST NOT be used to verify signatures on certificates
   // or CRLs unless the corresponding keyCertSign or cRLSign bit is set."
   rv = BuildForward(trustDomain, potentialIssuer, time, KeyUsage::keyCertSign,
-                    requiredEKUIfPresent, requiredPolicy, nullptr, subCACount);
+                    requiredEKUIfPresent, requiredPolicy, nullptr, subCACount,
+                    buildForwardCallBudget);
   if (rv != Success) {
     return RecordResult(rv, keepGoing);
   }
 
   // Calculate the digest of the subject's signed data if we haven't already
   // done so. We do this lazily to avoid doing it at all if we backtrack before
   // getting to this point. We cache the result to avoid recalculating it if we
   // backtrack after getting to this point.
@@ -280,17 +293,18 @@ PathBuildingStep::Check(Input potentialI
 static Result
 BuildForward(TrustDomain& trustDomain,
              const BackCert& subject,
              Time time,
              KeyUsage requiredKeyUsageIfPresent,
              KeyPurposeId requiredEKUIfPresent,
              const CertPolicyId& requiredPolicy,
              /*optional*/ const Input* stapledOCSPResponse,
-             unsigned int subCACount)
+             unsigned int subCACount,
+             unsigned int& buildForwardCallBudget)
 {
   Result rv;
 
   TrustLevel trustLevel;
   // If this is an end-entity and not a trust anchor, we defer reporting
   // any error found here until after attempting to find a valid chain.
   // See the explanation of error prioritization in pkix.h.
   rv = CheckIssuerIndependentProperties(trustDomain, subject, time,
@@ -338,17 +352,17 @@ BuildForward(TrustDomain& trustDomain,
     assert(subCACount == 0);
   }
 
   // Find a trusted issuer.
 
   PathBuildingStep pathBuilder(trustDomain, subject, time,
                                requiredEKUIfPresent, requiredPolicy,
                                stapledOCSPResponse, subCACount,
-                               deferredEndEntityError);
+                               deferredEndEntityError, buildForwardCallBudget);
 
   // TODO(bug 965136): Add SKI/AKI matching optimizations
   rv = trustDomain.FindIssuer(subject.GetIssuer(), pathBuilder, time);
   if (rv != Success) {
     return rv;
   }
 
   rv = pathBuilder.CheckResult();
@@ -377,14 +391,27 @@ BuildCertChain(TrustDomain& trustDomain,
   // XXX: Support the legacy use of the subject CN field for indicating the
   // domain name the certificate is valid for.
   BackCert cert(certDER, endEntityOrCA, nullptr);
   Result rv = cert.Init();
   if (rv != Success) {
     return rv;
   }
 
+  // See bug 1056341 for context. If mozilla::pkix is being used in an
+  // environment where there are many certificates that all have the same
+  // distinguished name as their subject and issuer (but different SPKIs - see
+  // the loop prevention as per RFC4158 Section 5.2 in PathBuildingStep::Check),
+  // the space to search becomes exponential. Because it would be prohibitively
+  // expensive to explore the entire space, we introduce a budget here that,
+  // when exhausted, terminates the search with the result
+  // Result::ERROR_UNKNOWN_ISSUER. Essentially, we limit the total number of
+  // times `BuildForward` can be called. The current value appears to be a good
+  // balance between finding a path when one exists (when the space isn't too
+  // large) and timing out quickly enough when the space is too large or there
+  // is no valid path to a trust anchor.
+  unsigned int buildForwardCallBudget = 200000;
   return BuildForward(trustDomain, cert, time, requiredKeyUsageIfPresent,
                       requiredEKUIfPresent, requiredPolicy, stapledOCSPResponse,
-                      0/*subCACount*/);
+                      0/*subCACount*/, buildForwardCallBudget);
 }
 
 } } // namespace mozilla::pkix

--- a/security/pkix/test/gtest/pkixbuild_tests.cpp
+++ b/security/pkix/test/gtest/pkixbuild_tests.cpp
@@ -44,17 +44,19 @@ using namespace mozilla::pkix;
 using namespace mozilla::pkix::test;
 
 static ByteString
 CreateCert(const char* issuerCN, // null means "empty name"
            const char* subjectCN, // null means "empty name"
            EndEntityOrCA endEntityOrCA,
            /*optional modified*/ std::map<ByteString, ByteString>*
              subjectDERToCertDER = nullptr,
-           /*optional*/ const ByteString* extension = nullptr)
+           /*optional*/ const ByteString* extension = nullptr,
+           /*optional*/ const TestKeyPair* issuerKeyPair = nullptr,
+           /*optional*/ const TestKeyPair* subjectKeyPair = nullptr)
 {
   static long serialNumberValue = 0;
   ++serialNumberValue;
   ByteString serialNumber(CreateEncodedSerialNumber(serialNumberValue));
   EXPECT_FALSE(ENCODING_FAILED(serialNumber));
 
   ByteString issuerDER(issuerCN ? CNToDERName(issuerCN) : Name(ByteString()));
   ByteString subjectDER(subjectCN ? CNToDERName(subjectCN) : Name(ByteString()));
@@ -70,17 +72,19 @@ CreateCert(const char* issuerCN, // null
     extensions.push_back(*extension);
   }
   extensions.push_back(ByteString()); // marks the end of the list
 
   ScopedTestKeyPair reusedKey(CloneReusedKeyPair());
   ByteString certDER(CreateEncodedCertificate(
                        v3, sha256WithRSAEncryption(), serialNumber, issuerDER,
                        oneDayBeforeNow, oneDayAfterNow, subjectDER,
-                       *reusedKey, extensions.data(), *reusedKey,
+                       subjectKeyPair ? *subjectKeyPair : *reusedKey,
+                       extensions.data(),
+                       issuerKeyPair ? *issuerKeyPair : *reusedKey,
                        sha256WithRSAEncryption()));
   EXPECT_FALSE(ENCODING_FAILED(certDER));
 
   if (subjectDERToCertDER) {
     (*subjectDERToCertDER)[subjectDER] = certDER;
   }
 
   return certDER;
@@ -740,8 +744,150 @@ TEST_F(pkixbuild, RevokedEndEntityWithMu
   ASSERT_EQ(Result::ERROR_REVOKED_CERTIFICATE,
             BuildCertChain(trustDomain, certDERInput, Now(),
                            EndEntityOrCA::MustBeEndEntity,
                            KeyUsage::noParticularKeyUsageRequired,
                            KeyPurposeId::id_kp_serverAuth,
                            CertPolicyId::anyPolicy,
                            nullptr/*stapledOCSPResponse*/));
 }
+
+// This represents a collection of different certificates that all have the same
+// subject and issuer distinguished name.
+class SelfIssuedCertificatesTrustDomain final : public DefaultCryptoTrustDomain
+{
+public:
+  void SetUpCerts(size_t totalCerts)
+  {
+    ASSERT_TRUE(totalCerts > 0);
+    // First we generate a trust anchor.
+    ScopedTestKeyPair rootKeyPair(GenerateKeyPair());
+    rootCACertDER = CreateCert("DN", "DN", EndEntityOrCA::MustBeCA, nullptr,
+                               nullptr, rootKeyPair.get(), rootKeyPair.get());
+    ASSERT_FALSE(ENCODING_FAILED(rootCACertDER));
+    certs.push_back(rootCACertDER);
+    ScopedTestKeyPair issuerKeyPair(rootKeyPair.release());
+    size_t subCAsGenerated;
+    // Then we generate 6 sub-CAs (given that we were requested to generate at
+    // least that many).
+    for (subCAsGenerated = 0;
+         subCAsGenerated < totalCerts - 1 && subCAsGenerated < 6;
+         subCAsGenerated++) {
+      // Each certificate has to have a unique SPKI (mozilla::pkix does loop
+      // detection and stops searching if it encounters two certificates in a
+      // path with the same subject and SPKI).
+      ScopedTestKeyPair keyPair(GenerateKeyPair());
+      ByteString cert(CreateCert("DN", "DN", EndEntityOrCA::MustBeCA, nullptr,
+                                 nullptr, issuerKeyPair.get(), keyPair.get()));
+      ASSERT_FALSE(ENCODING_FAILED(cert));
+      certs.push_back(cert);
+      issuerKeyPair.reset(keyPair.release());
+    }
+    // We set firstIssuerKey here because we can't end up with a path that has
+    // more than 7 CAs in it (because mozilla::pkix limits the path length).
+    firstIssuerKey.reset(issuerKeyPair.release());
+    // For any more sub CAs we generate, it doesn't matter what their keys are
+    // as long as they're different.
+    for (; subCAsGenerated < totalCerts - 1; subCAsGenerated++) {
+      ScopedTestKeyPair keyPair(GenerateKeyPair());
+      ByteString cert(CreateCert("DN", "DN", EndEntityOrCA::MustBeCA, nullptr,
+                                 nullptr, keyPair.get(), keyPair.get()));
+      ASSERT_FALSE(ENCODING_FAILED(cert));
+      certs.insert(certs.begin(), cert);
+    }
+  }
+
+  const TestKeyPair* GetFirstIssuerKey()
+  {
+    return firstIssuerKey.get();
+  }
+
+private:
+  Result GetCertTrust(EndEntityOrCA, const CertPolicyId&, Input candidateCert,
+                      /*out*/ TrustLevel& trustLevel) override
+  {
+    trustLevel = InputEqualsByteString(candidateCert, rootCACertDER)
+               ? TrustLevel::TrustAnchor
+               : TrustLevel::InheritsTrust;
+    return Success;
+  }
+
+  Result FindIssuer(Input, IssuerChecker& checker, Time) override
+  {
+    bool keepGoing;
+    for (auto& cert: certs) {
+      Input certInput;
+      Result rv = certInput.Init(cert.data(), cert.length());
+      if (rv != Success) {
+        return rv;
+      }
+      rv = checker.Check(certInput, nullptr, keepGoing);
+      if (rv != Success || !keepGoing) {
+        return rv;
+      }
+    }
+    return Success;
+  }
+
+  Result CheckRevocation(EndEntityOrCA, const CertID&, Time, Duration,
+                         /*optional*/ const Input*, /*optional*/ const Input*)
+                         override
+  {
+    return Success;
+  }
+
+  Result IsChainValid(const DERArray&, Time, const CertPolicyId&) override
+  {
+    return Success;
+  }
+
+  std::vector<ByteString> certs;
+  ByteString rootCACertDER;
+  ScopedTestKeyPair firstIssuerKey;
+};
+
+TEST_F(pkixbuild, AvoidUnboundedPathSearchingFailure)
+{
+  SelfIssuedCertificatesTrustDomain trustDomain;
+  // This creates a few hundred million potential paths of length 8 (end entity
+  // + 6 sub-CAs + root). It would be prohibitively expensive to enumerate all
+  // of these, so we give mozilla::pkix a budget that is spent when searching
+  // paths. If the budget is exhausted, it simply returns an unknown issuer
+  // error. In the future it might be nice to return a specific error that would
+  // give the front-end a hint that maybe it shouldn't have so many certificates
+  // that all have the same subject and issuer DN but different SPKIs.
+  trustDomain.SetUpCerts(18);
+  ByteString certDER(CreateCert("DN", "DN", EndEntityOrCA::MustBeEndEntity,
+                                nullptr, nullptr,
+                                trustDomain.GetFirstIssuerKey()));
+  ASSERT_FALSE(ENCODING_FAILED(certDER));
+  Input certDERInput;
+  ASSERT_EQ(Success, certDERInput.Init(certDER.data(), certDER.length()));
+  ASSERT_EQ(Result::ERROR_UNKNOWN_ISSUER,
+            BuildCertChain(trustDomain, certDERInput, Now(),
+                           EndEntityOrCA::MustBeEndEntity,
+                           KeyUsage::noParticularKeyUsageRequired,
+                           KeyPurposeId::id_kp_serverAuth,
+                           CertPolicyId::anyPolicy,
+                           nullptr/*stapledOCSPResponse*/));
+}
+
+TEST_F(pkixbuild, AvoidUnboundedPathSearchingSuccess)
+{
+  SelfIssuedCertificatesTrustDomain trustDomain;
+  // This creates a few hundred thousand possible potential paths of length 8
+  // (end entity + 6 sub-CAs + root). This will nearly exhaust mozilla::pkix's
+  // search budget, so this should succeed.
+  trustDomain.SetUpCerts(10);
+  ByteString certDER(CreateCert("DN", "DN", EndEntityOrCA::MustBeEndEntity,
+                                nullptr, nullptr,
+                                trustDomain.GetFirstIssuerKey()));
+  ASSERT_FALSE(ENCODING_FAILED(certDER));
+  Input certDERInput;
+  ASSERT_EQ(Success, certDERInput.Init(certDER.data(), certDER.length()));
+  ASSERT_EQ(Success,
+            BuildCertChain(trustDomain, certDERInput, Now(),
+                           EndEntityOrCA::MustBeEndEntity,
+                           KeyUsage::noParticularKeyUsageRequired,
+                           KeyPurposeId::id_kp_serverAuth,
+                           CertPolicyId::anyPolicy,
+                           nullptr/*stapledOCSPResponse*/));
+}