Path Building and Validity Checking in X.509 Certificate Chains

The Certificate message in a TLS handshake is an unordered pile. It has a defined sequence within itself, but nothing in the protocol guarantees that the pile is a chain, that every certificate is needed, or that the order helps. Turning it into a decision is the client’s job, and the job is harder than reading fields off the first certificate. A validator must find a sequence of certificates where each one’s issuer name matches the next one’s subject name, each one’s signature verifies under the next one’s public key, every constraint along the way holds, and the last one is a trust anchor the validator already accepts. That is a graph search, and the graphs are occasionally not trees.

What one certificate asserts

A certificate is a DER-encoded structure with three top-level parts: tbsCertificate, an algorithm identifier, and a signature value. The signature covers the first part, so the fields inside it are what the issuer is vouching for. The fields that matter for path validation are few.

The subject and issuer are Name structures, sequences of attribute type and value pairs. Comparison between them is not string equality: RFC 5280 specifies a matching rule per attribute type, with case folding for the common ones and whitespace normalization, so CN=Example and CN=example chain while a byte comparison would fail. Implementations that compare DER bytes directly reject chains that a conforming validator accepts, and the failure appears only with issuers whose name encoding differs from their own.

basicConstraints is the field that decides whether a certificate may act as an issuer at all. When the CA flag is asserted, the certificate may sign others; when it is absent or false, it may not. The pathLenConstraint inside it caps how many intermediate certificates may follow it, counting only intermediates and not the end entity. A certificate with a path length of zero can issue end-entity certificates but no further intermediates.

keyUsage restricts what the key may do. For an issuer, the keyCertSign bit must be set. For an end entity in TLS, the digitalSignature bit is what matters, because the handshake’s CertificateVerify is a signature. A certificate that asserts keyCertSign on an end entity, or lacks digitalSignature, is a misissuance that a validator is expected to reject.

extKeyUsage narrows the purpose further. serverAuth marks a certificate as usable for a TLS server, clientAuth for a client. When the extension is absent the certificate is unconstrained; when it is present and the required purpose is missing, the path fails even if every signature checks out. This is the field that prevents a certificate issued for code signing from authenticating a web server.

Time is checked per certificate, not per chain

notBefore and notAfter are checked against the validator’s clock for every certificate in the path independently. A chain whose root expired last week fails even if the end entity is valid until next year, and a chain whose intermediate has not yet become valid fails the same way. The two values are UTCTime for years through 2049 and GeneralizedTime afterwards, and the encoding is not interchangeable: a parser that assumes one form will misread the other.

Clock skew is the practical complication. A validator whose clock is minutes behind can reject a certificate that the issuer considers live, so implementations typically allow a small tolerance, though the protocol specifies none. The tolerance is a local policy and different stacks pick different values, which means the same chain can validate on one host and fail on another within a window around the boundary. Correcting the clock is the only real fix; extending the tolerance converts a visible failure into an intermittent one.

Validity is also the field that makes revocation structurally difficult. A certificate is trusted for its whole window unless something else intervenes, and the something else requires either a separate fetch or a stapled response, both of which are optional in practice. The chain validation described here says nothing about whether the issuer has since withdrawn the certificate.

Constraints compose along the path

Beyond the per-certificate checks, RFC 5280 defines a set of state that the validator carries as it walks from the trust anchor down to the end entity. Name constraints, when present in a CA certificate, restrict the namespace of everything below it: a permittedSubtrees entry of .example.com allows names under that domain, and an excludedSubtrees entry blocks them. A CA that is permitted to issue only for one domain cannot escape that restriction by issuing an intermediate that claims more.

Policy identifiers compose in a similar way. A certificate may assert certificate policies, and an intermediate may require that at least one of a specified set be present in every certificate below it. Validators that do not implement policy processing ignore the extension, which is permitted, but then a chain that an issuer intended to restrict will validate anyway.

The critical bit on an extension is the escape hatch that makes unknown extensions safe. A validator that encounters a critical extension it does not understand must reject the certificate. A non-critical extension it does not understand may be ignored. This is why a new constraint can be introduced without breaking old validators only if it is marked non-critical, and why an issuer that marks a constraint critical is deliberately refusing to serve clients that cannot enforce it.

Path building is search, and the input is adversarial

A server that sends three certificates in a plausible order is the easy case. The general case has a set of candidate issuers and a set of anchors, and the validator must find a path. Intermediate certificates are frequently cross-signed: the same subject key appears in two certificates, one signed by an older root and one by a newer root, and both may be present in the pile. A validator that commits to the first candidate that appears to chain may end up in a dead end and must backtrack.

def build_path(cert, pile, anchors, depth=0, seen=frozenset()):
    # depth-first with memo of visited subjects to avoid loops
    if cert.subject in anchors:
        return [cert]
    if depth > MAX_DEPTH or cert.subject in seen:
        return None
    for cand in pile:
        if cand.subject != cert.issuer:
            continue
        if not cand.is_ca or not cand.permits(cert):
            continue
        rest = build_path(cand, pile, anchors, depth + 1, seen | {cert.subject})
        if rest is not None:
            return [cert] + rest
    return None

The permits step is where the state from the previous section applies: key usage, path length counting the depth already consumed, name constraints against the names seen so far, and policy intersection. The seen set prevents an infinite loop when two certificates issue each other, which is a shape that a hostile peer can construct deliberately.

Depth limits exist for the same reason. A validator that will search arbitrarily deep can be made to spend arbitrary time, so implementations cap the chain length, commonly at a small number far below the 2^24 byte ceiling on the message itself. A server can send a large pile of plausible-looking certificates and force a search over it; the pile is bounded by the 16 MiB message limit, and the search cost grows with the product of pile size and depth.

The hostile-input aspect is why path building is often described as the least standardized part of the process. RFC 5280 describes validation of a candidate path but leaves discovery of which path to try to the implementation, and different implementations use different heuristics: prefer anchors that appear in the local store, prefer shorter paths, prefer certificates with later expiry, cache partial results. A chain that validates in one client can fail in another purely because the search explored a different branch first, and the difference is not a bug in either.

Anchors are local, and that changes the question

The trust anchor is not part of the path being validated in the same sense as the others. It is an input the validator already holds, and the constraints on it are whatever the local policy says, not necessarily what the certificate’s own extensions claim. Some validators treat an anchor’s basicConstraints as authoritative; others ignore extensions on anchors entirely because the anchor is trusted by configuration rather than by signature. The distinction matters for a root certificate that has an expired validity window: whether that expiry blocks the chain is a local decision, and stacks differ.

Anchor sets are also curated by software rather than by protocol. A program’s root store may be the operating system’s, a language runtime’s bundle, or a vendor’s list, and the contents differ. This is why a certificate chain that works in one browser can fail in another: the intermediate is present, the signature is valid, and the anchor simply is not in the store. The fix is on the server side, by including the intermediates needed to reach an anchor the client is likely to hold, which is why servers send more than one certificate even though the protocol does not require it.

Nothing in this process authenticates the name the client intended to reach. A valid path proves that some trusted issuer vouched for some key; whether that key belongs to the host named in the URL is a separate check, performed after the path is built and covered in the identity matching rules for the subject alternative name extension. Nor does a path say anything about whether the certificate has been withdrawn since it was issued; revocation is a second, separate decision. What a valid path does establish is that the key in the end-entity certificate may be used to verify the handshake signature, which is the only thing the handshake asks of it.