Trust and key distribution: the Web of Trust, and what replaced it.

Every cryptographic component in the previous four articles works. The unsolved problem — the one that has limited OpenPGP's real-world deployment for thirty years — is answering "is this key actually the right key for this person?" This article covers the certification and trust primitives precisely, gives the Web of Trust's actual propagation algorithm rather than the usual hand-wave, walks through how the SKS keyserver network was destroyed by an attack that required no vulnerability in any implementation, and evaluates what replaced it: verifying keyservers, WKD, DANE, and key transparency.

1. Certification: the primitive

A certification is a signature by one key over the binding between another key and one of its User IDs. The four types express confidence in the identity verification process:

Type	Name	Intended meaning
0x10	Generic certification	No claim made about verification. The default, and the least informative.
0x11	Persona certification	No verification performed.
0x12	Casual certification	Some casual verification.
0x13	Positive certification	Substantial verification. Self-signatures are conventionally this type.

In practice these distinctions carry almost no information, because there is no shared definition of "casual" or "substantial" and tools rarely surface the difference. The genuinely load-bearing parameters live in subpackets instead.

1.1 Trust Signature: depth and amount

The Trust Signature subpacket (type 5) turns a certification into a delegation, with two fields:

• Trust amount — 0 to 255, how convinced the issuer is that the binding is correct. Values ≥120 mean fully convinced; 60 conventionally means partially (marginally) convinced.
• Trust depth — 0 means "I vouch for this binding only." 1 means "this key is a trusted introducer — I will accept bindings it certifies." 2 means "and I will accept introducers it designates," and so on.

Depth is where the Web of Trust becomes a graph problem rather than a list. Depth >1 delegates the ability to delegate, which is powerful and dangerous in exactly the way intermediate CAs are in X.509.

1.2 Regular Expression scoping

The Regular Expression subpacket (type 6) constrains a trust signature to User IDs matching a pattern — typically limiting an introducer to a single domain, e.g. <[^>]+[@.]example\.com>$. This is OpenPGP's equivalent of X.509 name constraints, and it is the mechanism that makes organizational trust roots safe: your company's CA key can be a depth-2 introducer scoped to your own domain, unable to vouch for anything else.

It is also, historically, under-implemented and inconsistently enforced. If you are relying on regex scoping for security, verify that every implementation in your deployment actually enforces it rather than parsing and ignoring it.

2. The Web of Trust algorithm

The classic GnuPG model has two knobs: --marginals-needed (default 3) and --completes-needed (default 1). A key is considered valid if:

\[ \text{valid}(K) \iff \big(n_{\text{full}} \ge \texttt{completes-needed}\big) \ \lor \ \big(n_{\text{marginal}} \ge \texttt{marginals-needed}\big) \]

where \(n_{\text{full}}\) counts certifications from fully-trusted keys and \(n_{\text{marginal}}\) counts certifications from marginally-trusted keys — subject to a maximum path length (--max-cert-depth, default 5).

Crucially, ownertrust is a local, private assignment — you decide whether you trust a key's owner to certify others, and that assignment never leaves your machine. Validity is computed; ownertrust is assigned.

2.1 The modern formulation

Sequoia's WoT implementation reframes this as an explicit network flow problem: trust amounts are capacities on edges, and a certificate is authenticated if the maximum flow from your trust roots to the target binding meets a threshold (120 for full authentication). The resolution runs as a breadth-first traversal from the ultimate keys, updating validity in topological order until a fixed point is reached or the depth limit is hit.

This formulation is strictly better for implementers: it makes the semantics of partial trust explicit rather than emergent from counter thresholds, and it composes properly with depth and regex constraints. If you are building trust evaluation today, model it as flow, not as counting.

2.2 Why the Web of Trust did not work in practice

Stating this without editorializing, because the reasons are technical:

• The social graph is a metadata disclosure. Certifications are public and describe who has met whom. The WoT publishes a social network as a side effect of doing security.
• Trust does not compose semantically. "I verified Alice's passport" and "I am willing to vouch for Alice's judgment about other people's passports" are unrelated claims, but depth ≥1 conflates them.
• Revocation propagation is unsolved, as covered in Article 2 — there is no freshness requirement, so a revoked certification may never reach a relying party.
• The graph is sparse and clustered. Research on the strong set — see Barenghi et al., "Is the Web-of-Trust Tear-Proof?" — found that connectivity depends on a small number of high-degree nodes, so removing a few keys partitions the graph badly.
• Nobody did it. Key-signing parties never scaled beyond the cryptographic community, and the fraction of real-world keys with meaningful WoT paths is small.

3. The SKS collapse

The SKS keyserver network was the original distribution infrastructure: a set of federated servers that gossiped certificates using a set-reconciliation protocol, designed on one principle — append-only, never delete. That principle was a deliberate anti-censorship measure. It was also the vulnerability.

3.1 Certificate flooding, CVE-2019-13050

In late June 2019, unknown actors attacked the certificates of Robert J. Hansen and Daniel Kahn Gillmor, two prominent OpenPGP contributors. The attack abused three properties that are all by design:

1. An OpenPGP certificate can carry an unlimited number of third-party certifications.
2. Anyone can append a certification to anyone's certificate — no authorization is required, since a certification is an assertion by the signer, not a modification by the key owner.
3. There is no way to distinguish a legitimate certification from garbage without checking every signature against keys you may not have.

The attackers appended roughly 150,000 signatures to the targeted certificates. Because the network is append-only and gossips aggressively, the poisoned certificates propagated to every server and cannot be removed. Any GnuPG client that fetched one would attempt to process every signature and effectively hang — a persistent denial of service against the local keyring, which in some configurations broke the user's GnuPG installation until manual intervention.

The practical fallout: distributions warned users away from the SKS pool, GnuPG added import limits and eventually began ignoring third-party certifications on import by default, and the network was effectively abandoned as a general-purpose distribution mechanism. The state of the keyservers has been one of managed decline since.

3.2 What implementations do now

Mitigation	Effect
Cap certifications processed per certificate on import	Bounds the DoS; may silently drop legitimate certifications
Ignore third-party certifications by default (GnuPG's self-sigs-only import behavior)	Immunizes the client; effectively abandons the WoT
Cap total certificate size	Blunt but effective
Only accept certifications from keys already in the local keyring	Preserves useful WoT edges while dropping unknown noise

4. What replaced it

4.1 Verifying keyservers (keys.openpgp.org)

keys.openpgp.org, running the Rust Hagrid software, makes different tradeoffs than SKS on every axis:

• Email verification required. A key becomes discoverable by an address only after the uploader proves control of it via a confirmation email. This makes the address-to-key mapping meaningful rather than merely asserted.
• Third-party certifications are stripped. The server distributes the key with its self-signatures only. This structurally prevents certificate flooding — the flooding vector simply does not exist.
• Deletion is supported. An address can be removed by its owner, which is a privacy requirement (GDPR, among other things) that append-only design cannot satisfy.

The tradeoff is explicit and worth naming: this design gives up the Web of Trust entirely in exchange for a distribution channel that works. It answers "here is a key that someone who controls this email address uploaded," which is a weaker claim than the WoT aspired to and a far stronger one than SKS actually delivered.

4.2 Web Key Directory

WKD (draft-koch-openpgp-webkey-service) removes the third party. The key is published on the domain that owns the email address, fetched over HTTPS:

# Advanced method (preferred)
https://openpgpkey.example.org/.well-known/openpgpkey/example.org/hu/<hashed-local>?l=alice

# Direct method (fallback)
https://example.org/.well-known/openpgpkey/hu/<hashed-local>?l=alice

# hashed-local = Z-Base-32( SHA-1( lowercase(local-part) ) )
# Response: binary (not armored) transferable public key.

Two design points that regularly confuse implementers:

• SHA-1 here is not a security claim. It is a mapping function producing a fixed-length filename, chosen to avoid exposing the raw local-part in a URL. Its collision weakness is irrelevant to this use, because an attacker who could produce a colliding local-part would still need control of the domain to publish anything.
• The security root is TLS and DNS. WKD's trust reduces to the Web PKI plus domain control — the same root as the rest of the web. That is a meaningful downgrade from the WoT's aspirations and a large upgrade over its reality.

WKD is now the practical default for automatic key discovery: GnuPG queries it via --auto-key-locate, and it works without any user action for organizations that publish correctly.

4.3 DANE OPENPGPKEY

RFC 7929 defines an OPENPGPKEY DNS record type, placing the key in DNS with DNSSEC as the integrity mechanism. Conceptually clean — it moves the trust root from the Web PKI to DNSSEC — but deployment is thin because DNSSEC deployment is thin, and because keys are large enough that DNS record size becomes awkward. Worth knowing, rarely worth deploying in 2026 unless you already have a DNSSEC-everywhere posture.

4.4 Key transparency

The structural gap all of the above share: you must trust that the server gave you the same key it gives everyone else. A compromised or coerced WKD host can serve an attacker's key to one targeted user and the real key to everyone else, and nothing detects it.

Key transparency addresses this with the Certificate Transparency pattern: publish all key bindings in an append-only, cryptographically verifiable log (a Merkle tree), so that any equivocation — showing different bindings to different parties — is detectable by auditors. The IETF KEYTRANS working group is developing the general architecture, and the OpenPGP working group charter states an intent to integrate its output.

5. Comparing the distribution mechanisms

Mechanism	Trust root	Answers	Flooding-resistant	Detects equivocation
Manual fingerprint exchange	Your own verification	Exactly the right question	n/a	Yes (you saw it yourself)
Web of Trust	Your certification graph	Identity binding, transitively	No	No
SKS keyservers	None	"Someone uploaded this"	No — fatally	No
keys.openpgp.org	Server + email control	"An address-controller uploaded this"	Yes (strips certs)	No
WKD	TLS + domain control	"The domain publishes this for this address"	Yes	No
DANE OPENPGPKEY	DNSSEC	Same as WKD, different root	Yes	No
Key transparency	Log + auditors	Same, plus consistency	Yes	Yes (the point)

6. User IDs as an attack surface

A User ID is unstructured UTF-8 (Article 1). Everything displayed from it is attacker-controlled:

• Homoglyphs. аlice@example.org with a Cyrillic а renders identically to the Latin form. Any UI that matches identities visually is defeated.
• Bidirectional override characters can reorder displayed text so that the rendered address differs from the stored bytes.
• Embedded newlines and control characters feed directly into the SigSpoof-class injection problem from Article 4 — a User ID containing a newline plus a fake status line is the same bug in a different field.
• The comment field — Name (comment) <email> — is free text that some tools display prominently and some hide, which is precisely the inconsistency an attacker wants.

User Attribute packets (tag 17), typically JPEG images, are worse: they hand an attacker-controlled image to an image decoder, adding an entire memory-corruption surface for a feature almost nobody uses. Reject or ignore them unless you have a specific need.

7. Operational guidance

Rule	Prevents
Cap certification count and total size on certificate import	Certificate flooding DoS
Only process certifications from keys already known locally	Unbounded verification work from unknown signers
Enforce regex scoping on trust signatures, or refuse to honor depth >0	Over-broad delegation
Never render User IDs without normalization and control-character stripping	Homoglyph and bidi spoofing, status-line injection
Treat User Attribute packets as untrusted binary; ignore by default	Image-decoder memory corruption
Cache observed key bindings and surface changes to the user	Silent key substitution by a distribution point
Prefer WKD over keyserver lookup; require TLS validation	Unauthenticated key sourcing
Re-check revocation state on every use, not just at import	Acting on a key revoked after you imported it

FAQ

Is the Web of Trust dead?

As a global, internet-scale identity system, yes — the graph is too sparse, the metadata leak is unacceptable to most users, and the SKS collapse removed its distribution layer. As a bounded mechanism inside an organization, with a scoped introducer key and regex constraints, it works and is genuinely useful. The failure was of the global aspiration, not of the primitive.

Can poisoned certificates be cleaned up?

Not from the SKS network — it is append-only by design and there is no delete operation. The mitigation was entirely client-side: import limits and ignoring third-party certifications. The affected certificates remain poisoned on those servers permanently, which is exactly why the network was abandoned rather than repaired.

Why does WKD use SHA-1 if SHA-1 is broken?

Because it is not being used as a security primitive. It maps a local-part to a fixed-length filename. Forging a collision would let an attacker occupy the same URL path — but publishing at that path requires control of the domain, which is the actual security boundary. Collision resistance is not load-bearing here.

Should I still publish my key to keyservers?

To keys.openpgp.org, yes — it is verified, strips flooding vectors, and supports deletion. To the SKS pool, no. And publish via WKD on your own domain if you control one; that is the mechanism with the best combination of automatic discovery and meaningful trust root available today.

Takeaways

• Ownertrust is assigned locally; validity is computed from the graph. Conflating the two is the most common conceptual error in WoT discussions.
• Model trust as network flow, not as threshold counting — it composes correctly with depth and scoping, which counters do not.
• SKS was destroyed without any implementation vulnerability. Append-only + unauthenticated writes + unbounded size is a DoS primitive in any system.
• Modern distribution trades the WoT for something that works: WKD's trust root is TLS and domain control, which is weaker in theory and far stronger in practice than an unreachable social graph.
• Nothing deployed today detects a distribution point equivocating — that is precisely the gap key transparency exists to close, and it is not closed yet.
• User IDs are attacker-controlled display strings. Every rendering path needs normalization and control-character handling.

Next in this series

Article 6 — Post-quantum OpenPGP and the LibrePGP schism: RFC 9980's composite ML-KEM and ML-DSA constructions, SLH-DSA, why the working group chose hybrid over pure PQC, the technical substance of the OpenPGP/LibrePGP split, and a comparison of the major implementations.

References

• Robert J. Hansen — SKS Keyserver Network Under Attack — the primary first-hand account of the 2019 flooding attack, by one of its targets.
• CVE-2019-13050 — certificate spamming against SKS and GnuPG — vendor analysis of the persistent DoS.
• Sequoia — Certificate Flooding, SKS and GnuPG Issues — implementer's perspective on mitigations.
• Sequoia — OpenPGP Web of Trust — the network-flow formulation of trust propagation, with worked examples.
• draft-koch-openpgp-webkey-service — OpenPGP Web Key Directory — normative WKD specification, direct and advanced methods.
• RFC 7929 — DNS-Based Authentication of Named Entities (DANE) for OpenPGP
• keys.openpgp.org — design and policy — why it verifies addresses and strips third-party certifications.
• draft-ietf-keytrans-architecture — Key Transparency Architecture — the general design the OpenPGP WG intends to build on.
• Barenghi et al. — Is the Web-of-Trust Tear-Proof? — graph-theoretic analysis of strong-set connectivity and its fragility.
• The State of the Keyservers — survey of what actually still runs.