CVE-2026-69249: Exponential Backtracking Denial of Service in python-cryptography X.509 Verification Engine

The python-cryptography library utilizes a Rust-based path validation module, cryptography-x509-verification, to construct and validate certificate paths from an end-entity leaf certificate back to a trusted anchor.

This engine exposes a critical attack surface on any server, application, or gateway that accepts client certificates, validates S/MIME signatures, or performs custom X.509 validations on untrusted user-supplied certificate inputs.

The vulnerability is classified under CWE-400: Uncontrolled Resource Consumption. Under adversarial conditions, the verification engine is susceptible to algorithmic complexity exploitation, wherein a relatively short, maliciously structured validation chain triggers high CPU usage and complete system unavailability.

The path building process in ChainBuilder::potential_issuers functions by mapping subject names to find candidate parents from the trust store and the untrusted intermediate certificate pool.

Prior to version 49.0.0, when the pool of untrusted intermediates contained multiple identical or structurally identical copies of a self-signed certificate, the potential_issuers method retrieved and processed each duplicate independently.

Because the recursive function build_chain_inner failed to deduplicate these candidate issuers or bound the number of cryptographic signature operations, the resolver entered a recursive backtracking search. For $k$ duplicate intermediate certificates and a maximum path search depth $d$, the engine performs up to $k^d$ recursive states and corresponding signature validations. This combinatorial explosion quickly saturates the host CPU.

The vulnerability was resolved in commit 4a12cf49675a184e47f912b00b04f3a629283582 by implementing two complementary mitigation policies within the Rust engine.

First, a global signature validation budget of 128 check operations is introduced. Every signature verification decrements this budget, preventing unbound verification cycles. Second, candidate parent certificates are sorted and prioritized based on matching authority and subject key identifiers (AKI/SKI), pushing unlikely or duplicate name-colliding certificates to the bottom of the evaluation list.

Below is the structured representation of the path traversal workflow showing how validation flow has been bounded:

Let us review the key differences in src/rust/cryptography-x509-verification/src/lib.rs:

struct Budget {
    name_constraint_checks: usize,
+   signature_checks: usize,
}
 
impl Budget {
+   const DEFAULT_SIGNATURE_CHECK_LIMIT: usize = 1 << 7; // Max 128 checks
 
+   fn signature_check<'chain, B: CryptoOps>(&mut self) -> ValidationResult<'chain, (), B> {
+       self.signature_checks = self.signature_checks.checked_sub(1).ok_or_else(|| {
+           ValidationError::new(ValidationErrorKind::FatalError(
+               "Exceeded maximum signature check limit",
+           ))
+       })?;
+       Ok(())
+   }
}

The implementation of potential_issuers now performs a stable sort to group the most viable candidate issuers first, using AKI-to-SKI matching:

-   fn potential_issuers(
-       &self,
-       cert: &'a VerificationCertificate<'chain, B>,
-   ) -> impl Iterator<Item = &'a VerificationCertificate<'chain, B>> + '_ {
+   fn potential_issuers(
+       &self,
+       cert: &'a VerificationCertificate<'chain, B>,
+       cert_extensions: &Extensions<'chain>,
+   ) -> Vec<&'a VerificationCertificate<'chain, B>> {
+       let mut candidates: Vec<&'a VerificationCertificate<'chain, B>> = self
+           .store
+           .get_by_subject(&cert.certificate().tbs_cert.issuer)
+           .iter()
+           .chain(self.intermediates.iter().filter(|&candidate| {
+               candidate.certificate().subject() == cert.certificate().issuer()
+           }))
+           .collect();
+
+       let want_kid: Option<&[u8]> = cert_extensions
+           .get_extension(&AUTHORITY_KEY_IDENTIFIER_OID)
+           .and_then(|ext| ext.value::<AuthorityKeyIdentifier<'_, Asn1Read>>().ok())
+           .and_then(|aki| aki.key_identifier);
+
+       candidates.sort_by_key(|candidate| {
+           let have_kid: Option<&[u8]> = 
+               candidate.certificate().extensions().ok().and_then(|exts| {
+                   exts.get_extension(&SUBJECT_KEY_IDENTIFIER_OID)
+                       .and_then(|ext| ext.value::<&[u8]>().ok())
+               });
+
+           match (want_kid, have_kid) {
+               (Some(want), Some(have)) if want == have => 0, // Match (high priority)
+               (Some(_), Some(_)) => 2, // Mismatch (low priority)
+               _ => 1u8, // Missing ID (medium priority)
+           }
+       });
+       candidates
+   }

Exploitation does not require authentication or elevated privileges. An attacker simply submits a structured certificate chain containing several duplicates of a self-signed certificate.

Because the path validation engine explores all possible path combinations recursively, the CPU time increases exponentially relative to the number of duplicates. If the target server uses the unpatched verification engine, this process will block the executing thread indefinitely or until it hits a global worker timeout.

To demonstrate the vulnerability, the following performance table measures the validation duration of the unpatched vs. the patched library configuration:

Although the patch addresses the exponential explosion of cryptographic signature verification, some architectural edge cases remain.

First, potential_issuers continues to load and copy all matching intermediate certificates into a heap-allocated Vec before sorting. An attacker who uploads a chain with thousands of candidates can still force the server to allocate memory and perform $O(N \log N)$ operations. However, this is significantly less intensive than cryptographic signature operations.

Second, the name constraint budget of $2^{20}$ checks remains large. In highly complex, nested name constraint topologies, verification tasks could still introduce non-trivial latency overhead, though not sufficient to trigger a prolonged Denial of Service.