Digital signatures are free-range rows

A digital signature is a database row that has exited its database. Don’t believe me? Let’s walk through some examples.

When you visit my website, it sends you a certificate that reads “Google Trust Services asserts that the public key for josnyder.com is 02 18ed213a b9c5e95c e13e3a4d d196044b e4b4d88c 88e36874 bf25a36f 38801770”. Your browser trusts Google Trust Services, so it is happy to encrypt information to that public key when it is intending to communicate with josnyder.com. Does it have to be this way? Not at all. Your browser could maintain a database of the public keys for every website that it wants to communicate with, like some sort of massive Internet-wide phonebook. Some protocols do this: they use public keys directly as identities. Tor onion services come to mind, as do cryptocurrency wallet IDs. Under such protocols, constructing a map of meaningful identities to public keys is purely the user’s job. But on the web, certificate authorities help endpoints maintain the database.

Off the web and onto software artifacts: a signed software artifact is a statement of provenance. Bad signatures just encode set membership: each one says something like “X key endorses the existence of some piece of software with SHA256 hash Y”. Better ones are maps: they encode “the expected hash of the artifact known as terraform_1.10.1_linux_amd64.zip is d49d4d08 ed092a8d ec335f1f e3e127d1 a285f160 557323dd 5a84ddc0 c8472e1a”. Certainly no public key cryptography is required here: you could instead have a trusted courier bring you a compendium containing the hashes of all the software that Hashicorp has released (or just the software itself). For a long time this was pretty much how all software was transferred: someone you trusted brought you some software. There may have been a checksum involved, but if so its only purpose was to ensure that their floppy disk hadn’t corrupted the bits in transit.

Digital signatures answer three questions:

1. What happens if I don’t trust my courier?
2. What happens if the database is too big to keep around?
3. What happens if my database changes too fast?

Very obviously, a digital signature means that you no longer have to trust your courier. You just trust the originator of the database, and the elliptic curve math ensures that the courier hasn’t tampered with anything in transit.

If your database is too big to keep around: no worries! Digital signatures allow people to detach single rows from the DB and send them to you on a just-in-time basis. Your browser didn’t know the public key for josnyder.com before you came here, and it will quickly forget it once you leave. But in the meantime, my webserver was more than happy to send a single integrity-protected row, which originally was part of Google Trust Services’s DB, down to your browser for it to work with. That’s what a domain validation certificate is.

The same mechanism allows signatures to abstract away the problem of keeping local database replicas up to date. A newly issued certificate can be immediately sent (via untrusted courier) to any interested party. There’s no need to wait for database replication to start using a new signature: you just send it to the intended recipient and they know to trust it, because of math. You also don’t need to worry about placing load on the database: Google Trust Services was only involved once, at the inception of the certificate, and they don’t need to be involved at any later point.

The Catch

Obviously there’s a catch: two, in fact. Databases synthesized from digital signatures are append-only and non-scannable.

Append-only

Once a signature is issued, the math that makes it valid will remain true until the end of time. Designers of PKI systems recognized this, and incorporated external information—in the form of wall clock time—into the database’s semantics. Each signature has an expiration date, comparable to rows in a database where each one has an associated TTL. In this sense the DB is like memcached, but slower¹.

This becomes a major problem when the rows in a database lose their truthfulness halfway through the lifetime of a certificate. The public key for josnyder.com might have been 02 18ed213a... when Google Trust Services got involved, but who knows whether the associated private key will remain appropriately confidential for the whole lifetime of the certificate? If it doesn’t, then we’d very much like to delete the associated row from the database, but we can’t!

Designers of PKI systems recognized that, and so they built CRLs², which are…plain old databases of the non-cryptographic sort. At the end of the day, web PKI is a combination of: (1) a cryptographically represented database of issued certificates and (2) a classically represented database of revoked certificates.

The whole situation is even worse with software artifacts, which usually have neither (a) expiry information nor (b) revocation. Assuming nobody leaks their keys, it’s probably best to think of any given software artifact signature as “a product of its time”: it represents some state that a CI platform knew at a given moment, but it doesn’t encode any information about whether we learned later-on that the CI machine which built the artifact had been compromised.

Non-scannable

Databases born of cryptographic signatures cannot disprove the existence of a row. If my friend says that they validated the signature for terraform_1.10.1_linux_amd64.zip before executing it, did they end up running the same binary that I have on my system? We don’t know. An attacker could have issued a second—completely valid—certificate identifying a different artifact. If the database were scannable, we’d be able to find every row matching the artifact in question, and provably say “yep, there’s only one row here”. But with cryptography, we can’t!

There’s no way for anyone to make strong assertions about the signatures that have been issued (or will be issued) by a given public key over its lifetime. Keys can leak. Enclaves can be subverted. Random number generators can be broken ab initio. None of the math behind public key cryptography necessarily produces a visible audit log.

The upshot: an attacker could have issued a signature for their own Terraform 1.10.1 long before Hashicorp issued theirs. Or long after. Or right at the same time. Nobody can say for sure: at best we speak in terms of probabilities of a key being compromised.

Faced with this reality, our best countermeasure is simply to monitor the valid signatures seen in the wild. The Certificate Transparency (CT) system is the means by which publicly trusted certificate authorities are held accountable. The idea (one hopes) is that each CA enqueues the certificates they issue into a public log. If anyone finds a validly signed certificate that hasn’t been logged, it implies that either the CA is doing something nasty, or they have lost control of their keys to someone who is doing something nasty. CA’s would prefer to not get caught in such positions, because (we hope) it would represent a threat to their business continuity.

Among other shortcomings, CT means that all certificate issuance is public: you can’t hide the fact that a certificate was issued for your domain name, even if you wanted to.

Conclusion

Cryptography converts information security problems into key management problems

— Whitfield Diffie, apocryphally

I see digital signatures as a welcome addition to the solution-space of “how do I make databases scalable?” Relative to classical databases they offer significantly better performance on certain axes: storage size³, portability, and read/write rate. But they also introduce significant new headaches to solve or engineer around. One of the biggest is simply that they’re hard to understand: put a sqlite3 shell in front of a typical software engineer, and they can get the hang of it rather quickly. But with cryptography you can study it for years and there’ll still always be some new surprise lurking around the corner.