Certificates and the Trust Chain

The previous lesson showed that setup produces a shared secret and counted how many rounds that secret costs. What was produced was named a secret; it was not identity. The client took the other side’s public value, arrived at a shared number with it, and closed the body with that number — but nothing said the other end was the measurement station. The side that sent the public value could be station.example, or some other endpoint using that name.

This lesson’s question is how a name binds to a public key, and how many times the client asks a question while verifying that bond. Its second half is the course’s axis: chain verification is a decision taken with no extra round trip, true even as the chain grows longer.

What the Certificate Declares

A certificate is a statement that binds a name to a public key and puts someone else’s signature under that bond. Its fields say:

certificate
  subject      : station.example           <- whose name
  public key   : <the subject's public key>   <- which key speaks with that name
  issuer       : intermediate-1.test       <- who approved the bond
  validity     : start .. end              <- the time range the bond holds in
  signature    : produced with the issuer's private key

This listing is not run; it shows what the fields declare. The body that issues the certificate is called a certificate authority.

The intermediary’s position is familiar here: it is still looking at what the message says. The difference is one field — here, something verifies what the message says: the signature. When the rest of the course says “the intermediary believes what it is told,” it means the absence of this verification.

What the Signature Proves

The signature mechanism below is modeled within the lesson. It is not a real signature scheme and carries no security property: the modulus is shrunk, the digest function is a toy, and in this model the private key can be recovered from the public key. The security justification for real schemes belongs to the Identity, Access and Cryptography course. The only thing taken from the model here is which fields the signature stands on.

from math import gcd

SEED = 20260809
PRIME = 2147483647          # modulus shrunk for the lesson


def generator(seed: int):
    d = seed % 2147483646 + 1

    def r(n: int) -> int:
        nonlocal d
        d = (d * 48271) % PRIME
        return d % n
    return r


def digest(text: str) -> int:
    h = 2166136261
    for b in text.encode():
        h = (h * 16777619 + b) % PRIME
    return h


def key_pair(r) -> tuple[int, int]:
    while True:
        private = 3 + r(PRIME - 4)
        if gcd(private, PRIME - 1) == 1:
            return private, pow(private, -1, PRIME - 1)


def sign(subject: str, public: int, issuer: str, issuer_private: int, valid: bool) -> dict:
    s = {"subject": subject, "public": public, "issuer": issuer, "valid": valid}
    s["signature"] = pow(digest(f"{subject}|{public}|{issuer}|{valid}"), issuer_private, PRIME)
    return s


def signature_valid(s: dict, issuer_public: int) -> bool:
    return pow(s["signature"], issuer_public, PRIME) == digest(
        f"{s['subject']}|{s['public']}|{s['issuer']}|{s['valid']}")


r = generator(SEED)
anchor_private, anchor_public = key_pair(r)
leaf_private, leaf_public = key_pair(r)
leaf = sign("station.example", leaf_public, "anchor.test", anchor_private, True)

print(f"subject {leaf['subject']}, issuer {leaf['issuer']}")
print(f"signature valid: {signature_valid(leaf, anchor_public)}")
print(f"copy with altered subject: {signature_valid(dict(leaf, subject='other.test'), anchor_public)}")
print(f"copy with altered key: {signature_valid(dict(leaf, public=7), anchor_public)}")

subject station.example, issuer anchor.test
signature valid: True
copy with altered subject: False
copy with altered key: False

The signature stands on the subject, the public key, the issuer, and the validity field; if any field changes, verification falls. The result is subtle but important: the signature does not make the certificate unchangeable, it makes a change show.

The signature stands not directly on the document but on the document’s digest. This fixes the length of what is signed and makes the signing work independent of the document’s size — the same division of labor as the previous lesson, the asymmetric role again touching a fixed-size number. In return a new condition is born: two different documents must not fall onto the same digest. Which assumption satisfies this condition belongs to the Identity, Access and Cryptography course.

What the signature does not prove must also be listed. It shows the issuer approved this bond; it does not show the issuer was authorized to approve it, that the subject still exists at that moment, or that the subject’s private key has not fallen into someone else’s hands. All of these happen outside the certificate and cannot be written into a signed document afterward.

Chain and Trust Anchor

Verifying the signature needs the issuer’s public key. What says that key belongs to the issuer? Another certificate. This question repeats itself and the certificate chain is born: at the bottom the leaf certificate carrying the subject, above it one or more intermediate certificates, at the top the point where the chain stops.

The chain has to stop somewhere, and where it stops is decided not by a signature but by a placement. The certificate already in the client’s hand, verified against nothing else, is called the trust anchor. The anchor can be self-signed, and usually is, but what makes it trustworthy is not its own signature — its own signature says nothing — but that it is in the client’s hand.

This distinction ties into the course’s axis. The anchor sits with the client, not at the network’s edge. So even for the chain’s topmost rung, no one is asked a question.

The answer to who carries the chain also decides the round budget. The server sends the leaf and intermediate certificates; the client holds the anchor. The client needs no separate request to collect the chain, because it already arrives inside the presentation. The server sending incomplete intermediate certificates, on the other hand, does not push the client to spend a round — it pushes straight to rejection: if the pieces in its hand do not reach the anchor, the client decides.

Matching the Name

Even if the chain is consistent, the decision depends on one more match: the name the client wants to reach must satisfy one of the names the certificate declares. X.509 certificates carry these names in the subject alternative name field; a single certificate can declare more than one name, and a wildcard form (like *.station.example) satisfies a single level.

Two properties of the match tie into the course’s axis. First, the match is also local: the client compares the name in its hand against the list in its hand, asking no one. Second and more subtle, the two ends of the comparison must come from separate sources: the requested name from the client’s own request, the declared name from the certificate. If the name is read from the certificate and compared back against the same certificate, the check always passes and measures nothing — its meaning lies in the independence of its two ends.

Chain Verification Needs No Round Trip

Forty certificate submissions are measured. Chain lengths vary from one to five; submissions may have a rung with a broken signature, a chain that does not reach the client’s anchors, a leaf subject that does not satisfy the requested name, or a closed validity field. The oracle — the truth known because we produced the scenario — states for each submission whether acceptance was correct. Each submission carries one decision, so the set is 40 decisions and its resolution is 1/40 = 0.025.

Assumptions of the measurement:

• GT7 — The signature scheme is modeled within the lesson: the modulus is shrunk, the digest function is a toy, and in this model the private key can be recovered from the public key. What is measured is not the strength of the signature but where verification is done.
• GT8 — Forty submissions are produced from a single seed; chain length is drawn between one and five and each submission is given at most one flaw: broken signature, a chain that does not reach the anchor, a subject that does not satisfy the requested name, a closed validity field, or revocation.
• GT9 — The oracle is known because we produced the scenario: a submission’s acceptance is correct only if it has no flaw. The revocation flaw is not written into the chain — those chains are consistent start to finish and verification cannot see revocation.
• GT10 — The server sends the leaf and intermediate certificates, the client holds the trust anchor; collecting the chain needs no separate request. The anchor set is singular.
• GT11 — Three regimes are compared: walking with a local anchor, asking each rung’s issuer (one round trip per rung), never verifying at all. The walk exits early: it stops at a broken rung, so the signature-check count does not equal the rung count.
• GT12 — The decision measured belongs not to the intermediary but to the client; the intermediary does not enter this table. What is measured is not a duration but a verification step and a round trip.

from math import gcd

SEED = 20260809
PRIME = 2147483647
FLAWS = ("none", "none", "none", "none", "none", "none", "none",
         "signature", "anchor", "name", "validity", "revoked", "revoked")


def generator(seed: int):
    d = seed % 2147483646 + 1

    def r(n: int) -> int:
        nonlocal d
        d = (d * 48271) % PRIME
        return d % n
    return r


def digest(text: str) -> int:
    h = 2166136261
    for b in text.encode():
        h = (h * 16777619 + b) % PRIME
    return h


def key_pair(r) -> tuple[int, int]:
    while True:
        private = 3 + r(PRIME - 4)
        if gcd(private, PRIME - 1) == 1:
            return private, pow(private, -1, PRIME - 1)


def sign(subject: str, public: int, issuer: str, issuer_private: int, valid: bool) -> dict:
    s = {"subject": subject, "public": public, "issuer": issuer, "valid": valid}
    s["signature"] = pow(digest(f"{subject}|{public}|{issuer}|{valid}"), issuer_private, PRIME)
    return s


def signature_valid(s: dict, issuer_public: int) -> bool:
    return pow(s["signature"], issuer_public, PRIME) == digest(
        f"{s['subject']}|{s['public']}|{s['issuer']}|{s['valid']}")


def build_chain(length: int, name: str, r, anchor_private: int, valid: bool) -> list[dict]:
    top_private, top_name, chain = anchor_private, "anchor.test", []
    for rung in range(length, 0, -1):
        private, public = key_pair(r)
        subject = name if rung == 1 else f"intermediate-{rung - 1}.test"
        chain.append(sign(subject, public, top_name, top_private, valid or rung > 1))
        top_private, top_name = private, subject
    return chain


def verify_chain(chain: list[dict], name: str, anchors: dict, counter: dict) -> bool:
    top_public = anchors.get(chain[0]["issuer"])
    if top_public is None:
        return False
    for s in chain:
        counter["signature"] += 1
        if not signature_valid(s, top_public) or not s["valid"]:
            return False
        top_public = s["public"]
    return chain[-1]["subject"] == name


r = generator(SEED)
anchor_private, anchor_public = key_pair(r)
ANCHORS = {"anchor.test": anchor_public}

submissions = []
for no in range(40):
    length, flaw = 1 + r(5), FLAWS[r(13)]
    name = "other.test" if flaw == "name" else "station.example"
    chain = build_chain(length, name, r, anchor_private, flaw != "validity")
    if flaw == "signature":
        chain[-1] = dict(chain[-1], signature=(chain[-1]["signature"] + 1) % PRIME)
    elif flaw == "anchor":
        chain[0] = dict(chain[0], issuer="unknown.test")
    submissions.append({"length": length, "flaw": flaw, "chain": chain})


def measure(submissions, per_round, verify=True):
    counter, correct, wrong, rounds = {"signature": 0}, 0, 0, 0
    for s in submissions:
        given = (verify_chain(s["chain"], "station.example", ANCHORS, counter)
                  if verify else True)
        correct += given == (s["flaw"] == "none")
        wrong += given != (s["flaw"] == "none")
        rounds += per_round * s["length"]
    return correct, wrong, rounds, counter["signature"]


print(f"{'regime':<26s} {'correct':>7s} {'wrong':>7s} {'round trips':>12s} "
      f"{'signature checks':>17s}")
for regime_name, per_round, do_verify in (("local anchor", 0, True),
                                           ("ask each rung remotely", 1, True),
                                           ("skip verification", 0, False)):
    c, w, t, i = measure(submissions, per_round, do_verify)
    print(f"{regime_name:<26s} {c:7d} {w:7d} {t:12d} {i:17d}")

print()
print(f"{'chain length':>13s} {'submissions':>12s} {'signature checks':>17s} "
      f"{'round trips':>12s}")
for length in range(1, 6):
    matches = [s for s in submissions if s["length"] == length]
    print(f"{length:13d} {len(matches):12d} {measure(matches, 0)[3]:17d} {0:12d}")

print()
flaws = {k: sum(s["flaw"] == k for s in submissions) for k in
         ("none", "signature", "anchor", "name", "validity", "revoked")}
print(f"submissions {len(submissions)}, decisions {len(submissions)}, "
      f"rungs {sum(s['length'] for s in submissions)}, flaws {flaws}")

regime                     correct   wrong  round trips  signature checks
local anchor                    33       7            0                98
ask each rung remotely          33       7          111                98
skip verification               17      23            0                 0

 chain length  submissions  signature checks  round trips
            1            9                 9            0
            2           10                18            0
            3           10                24            0
            4            3                12            0
            5            8                35            0

submissions 40, decisions 40, rungs 111, flaws {'none': 17, 'signature': 3, 'anchor': 4, 'name': 5, 'validity': 4, 'revoked': 7}

The first two rows alone pay off the course’s axis. The client walking with a local anchor got 33 decisions right, 7 wrong, with zero round trips. The client asking each rung’s issuer spent 111 round trips and arrived at the same table: 33 correct, 7 wrong. Asking changed not a single decision; it only added 111 rounds.

In the second table, the round-trip column is zero start to finish. Whether the chain is one rung or five, the client asks no one; the only thing that grows is local work — signature checks climb from 9 to 35. This is the difference between local work and rounds: one is paid on the client’s processor, the other on the network, and the two cannot be converted into the same unit.

Total signature checks are 98, rung count is 111. The gap is not an inconsistency but the walk itself: in the four chains that never reach the anchor, no signature is checked at all — the client sees at the first step that it has no anchor in hand — and when a broken rung is hit, the walk stops. Chain verification is an operation that exits early.

What the Chain Does Not Say

All 7 wrong decisions come from the same flaw, and its name is written in the table’s last row: revoked 7. In these seven submissions the chain is consistent start to finish — signatures hold, the name is the one requested, the validity field is open — but the certificate is no longer counted valid.

The distinction is this: chain verification measures the document’s internal consistency, and everything it measures is written inside the document — which is why it can run locally and needs no round trip. Revocation, on the other hand, reports something happening outside the document and cannot be written into the document afterward, because the document freezes the moment it is signed. The chain verifies without asking; revocation cannot be known without asking.

Configuration Flaws and Narrowings

The table’s third row is the cost of a flaw. A client that never runs chain verification gets away with zero round trips and zero signature checks; what it pays is correct decisions dropping from 33 to 17. This is what is wrong — the work gained is local and cheap, what is lost is the decision itself. How this is done is not this course’s subject.

The parts of verification must also be counted separately, each with its narrowing written next to it:

• Name check. In the measurement, 5 submissions were rejected for this check alone: their chains were flawless, their subjects did not satisfy the requested name. Narrowing: if the name check is built as an inseparable step of the verification path rather than a setting that can be turned on and off, it cannot be disabled.
• Validity check. In the measurement, 4 submissions were rejected for this alone. Narrowing: if validity ranges are kept short, the window a wrong clock opens is also shortened.
• Width of the anchor set. Every anchor in the client’s hand makes every chain descending from that anchor acceptable. Narrowing: if the anchor set is narrowed to endpoints actually used, the set of acceptable chains narrows by the same proportion.
• The chain’s intermediate rungs. In the measurement, 4 submissions never reached the anchor and were rejected for that; the server sending incomplete intermediate certificates produces the same result. Narrowing: a missing rung is closed on the server’s configuration, not on the client — not by widening the client’s anchor set.

The last item also explains a habit: most situations that look like a “certificate error” are not an attack, they are a configuration flaw. Where the flaw sits is separated by looking at which check fell.

Summary

• A certificate binds a name to a public key and puts the issuer’s signature under that bond; the signature stands on the subject, key, issuer, and validity fields.
• The signature does not make the document unchangeable, it makes a change show; it does not show the issuer was authorized, the subject still exists, or the key stayed in hand.
• The chain stops at the trust anchor; what makes the anchor trustworthy is not its own signature but that it is in the client’s hand.
• Across forty submissions, the client walking with a local anchor took 33 correct and 7 wrong decisions with 0 round trips; the client asking each rung spent 111 round trips and arrived at the same table.
• As chain length went from 1 to 5, local signature checks climbed from 9 to 35, round trips stayed at 0 on every row.
• All 7 wrong decisions come from revocation: the chain measures the document’s inside, revocation is what happens outside the document.

Next Step

Chain verification asked for no round at all, but it does not run in a vacuum: it happens inside a specific connection, at a specific moment, and the certificate reaches the client only after an exchange begins. That exchange has its own budget — how many messages go back and forth, at which round the certificate arrives, after which round the body starts being carried. The next lesson counts this budget and measures what happens to the intermediary’s decision table once the budget closes.