The chain of trust.

A public key is a number. A number has no owner, no name and no expiration date. Cryptography guarantees that a signature was produced with the private key corresponding to a given public key, but it says nothing about whom that key belongs to. Without an answer to that question, the Diffie and Hellman exchange is exposed to a man in the middle, and a digital signature does not prove who signed.

The answer that prevailed was proposed by Loren Kohnfelder in his undergraduate thesis at MIT in 1978: a trusted third party signs a statement binding a public key to a name. He called it a certificate. Everything we now call public key infrastructure grew out of that idea, and this article traces it from the bytes of a certificate to the algorithm that decides whether a chain is valid.

Anatomy of an X.509 certificate

The dominant format was born in 1988 as part of the ITU’s X.500 series, intended for a global directory that never came to exist. Its third version added extensions, which turned out to be the most important part, and RFC 5280 defines the profile used on the internet. A certificate is described in ASN.1, a structure definition language, and encoded in DER, a canonical encoding: each structure admits exactly one byte representation. That is no minor detail, because the signature is computed over bytes, and two different encodings of the same content would produce different hashes.

A certificate, then, is a signed document like any other. Its issuer (issuer) asserts that the enclosed key belongs to the subject (subject) during the validity period, under the conditions set by the extensions. The most relevant ones for signing are these:

Why a chain and not a single link

The private key of a root authority is the most sensitive asset in the system: if it is compromised, everything that hangs from it loses its value. That is why the root usually lives offline, inside a hardware security module, and is used only in formal ceremonies, with witnesses and minutes, to sign a handful of intermediate authority certificates. It is the online intermediates that issue the signers’ certificates. If an intermediate is compromised, it is revoked without touching the root.

The root, by contrast, has nobody to sign it. Its certificate is self signed, and its signature only proves that the certificate has not been altered. Trust in it is not cryptographic but a decision: the decision to include it in a store of trust anchors. Those stores are maintained by operating systems and browsers, through their root programs; by supervisory bodies, such as the European trusted lists; and by governments, through national infrastructures with a state root.

Validating a path

RFC 5280 devotes its section 6 to a precise algorithm. It takes a certification path, from the certificate following the anchor down to the signer’s, a reference time and the acceptable policies, and processes it in order, from the top down. For each certificate it checks, among other things:

• that its signature verifies with the public key of the previous certificate;
• that its issuer matches the subject of the previous certificate;
• that the reference time falls within its validity period;
• that it is not revoked at that time;
• that, if it is an intermediate, it is an authority (cA true, keyCertSign usage) and respects the path length and name constraints;
• that the certificate’s policy is among the acceptable ones.

Before validating, the path has to be built, which is not always trivial: there may be cross certificates, several intermediates with the same name, or renewed roots. Robust implementations try several candidate paths. The lab shows validation over a three level path and what happens when something fails.

Revocation: the hardest problem

A certificate can stop deserving trust before it expires: the key was lost, the subject left the company, the data were false. The issuer must be able to announce it, and the verifier must be able to find out.

On the web, revocation never quite worked: if the service does not respond, browsers usually carry on, and an attacker able to intercept traffic can also block the query. For document signing, the problem takes a different shape. What matters is not so much whether the certificate is valid today as whether it was valid at signing time, and that requires two things: keeping the revocation information from that moment, and a timestamp from a third party that fixes the moment. This is the basis of the long term signatures covered in this blog’s first series.

When the chain breaks in practice

In 2002 it was discovered that a widely used browser did not check the basicConstraints extension: any holder of an ordinary certificate could issue certificates for any site, and the browser accepted them. It was the clearest demonstration that an incomplete validator nullifies the entire infrastructure.

In 2011 the Dutch certificate authority DigiNotar was compromised. The forensic report identified 531 fraudulent certificates, including one for all Google domains, which was used to intercept the communications of some 300,000 IP addresses, most of them in Iran. Browsers and operating systems removed DigiNotar from their trust stores, the Dutch government replaced the certificates issued under its infrastructure, and the company went bankrupt within weeks. A compromised link takes down with it everything that hangs from it.

The structural response was Certificate Transparency: public append only logs in which authorities must record every certificate they issue, so that any improper issuance is out in the open. The logs are organized as Merkle trees, a direct application of hash functions: a single 32 byte root commits to millions of certificates, and proving that one is included takes only a few intermediate hashes.

← All notes