Sovereign Keys for certificate verification

The certificate-authority (CA)-based approach to identity-checking on the web is under heavy fire these days. In theory, when a client like a web browser initiates a secure connection to a remote server, it relies on a chain of trusted cryptographic signatures presented by the server to verify that the public-key encryption certificate belongs to who the browser is expecting. But as the Electronic Frontier Foundation (EFF) has pointed out numerous times in public, the CA system is too-easily circumvented by fake CAs or attackers intercepting and replacing credentials during the handshake.

The problem affects SSL/TLS, SMTPS, and other secure protocols. There are plenty of proposals for replacing the CA portion of system, including Convergence, MonkeySphere, and Public Key Pinning. EFF's chief technologist Peter Eckersley has proposed a new framework called Sovereign Keys that is intended to securely verify associations between domain names and cryptographic keys in a way that is more robust than the CA system in use today, but can piggyback on it.

The Sovereign Key system allows clients to verify the validity of a server's X.509 certificate by referencing a persistent, append-only database mirrored around the world. The Sovereign Key service is designed to prevent man-in-the-middle and server-impersonation attacks — even those where an attacker has compromised a CA — and provides a safe workaround when an attack on SSL/TLS would trigger one of those certificate warning messages that users have grown accustomed to ignoring. Although in theory it could be used to replace the CA system outright, the proposal instead presents it as a way to augment existing techniques, which maximizes compatibility with existing HTTPS and SSL/TLS infrastructure.

A November 18 blog post outlines the Sovereign Keys proposal at a high level, including the weaknesses in the current CA model and links to research showing the ineffectiveness of certificate warnings in modern web browsers. The proposal itself is hosted in the EFF Git repository, although Eckersley warns that it is in draft form only, and not a complete specification. In particular, it does not detail protocol encodings and numerical parameters that would be required before undertaking a real-world implementation.

There is also a set of "issues" with the current design that are also hosted in the repository. Currently five in number, they outline possible attack vectors and transitional or pragmatic hurdles in the way of possible adoption. Eckersley said that the EFF is working toward a real-world test, but that because of the scope involved, it is still too soon to announce.

The design

As the proposal outlines it, there are two chief problems with the CA system in use today. First, it is vulnerable to variety of attacks, including a compromised CA itself, a CA pressured by a government into maliciously replacing a certificate, a compromised router near either the client or the CA, or even a compromised DNS server in between the client and CA. Second, the default way for browsers to warn users about potential attacks is with a certificate warning message. But research has shown that the majority of certificate warnings are generated by "bureaucratic" non-attack incidents like mismatches and self-signed certificates, which has trained users to ignore the warnings.

The first goal of the Sovereign Keys design is to allow clients to check the validity of a server's certificate without relying on any third-party that could be compromised like the CA system can. The second is to provide an alternate method for clients to securely connect to the correct server in case the validity check fails (meaning the server the client actually wants to connect to, even if the server originally seen is an impostor).

In the Sovereign Keys system, a definitive "sovereign key" key-pair exists for each service on the Internet. There is a public, master database of all of the (public key) sovereign keys, and any client could use it to check the signature on a particular server's SSL/TLS certificate. The certificate could be changed, but as long as the verified sovereign key signs the new one, the clients would consider it valid. What makes the Sovereign Keys database more trustworthy than a chain of CA-signatures is that it is verifiably read-append-only — meaning that all clients can query it, but that the database server can only append new records, not modify old ones — and replicated by a set of global mirrors.

Because it can be appended to but not changed, the database is a "timeline" that includes a complete record of new sovereign key registrations, revocations, and other incidents. In the event that a timeline server experiences a fault (such as two events being recorded out-of-sequence), any client can recognize it, flag it as renegade, and stop trusting it. The timeline is a bit like the distributed, public transaction record used by Bitcoin — its authenticity is designed to be verifiable by clients and mirrors. Each entry includes a strictly-incrementing serial number and a monotonically-increasing timestamp, and the entries are cryptographically signed.

The other half of the design is what a client is meant to do if a server's certificate fails the sovereign key-verification test. Rather than allow the user to continue to connect (which may be a man-in-the-middle attack, but even if it is not, reinforces the behavior that continuing to connect is acceptable), the client takes the sovereign key found in the timeline for the service, computes an SHA1 hash of the key, and attempts to connect to that hash value as a hidden .onion service via Tor. If the service does not accept connections on the .onion address, the client is to stop, and not connect at all. In other words, it may ultimately fail to connect, but that is better than making an unsafe connection.

Of course, the use of Tor as an alternate method for connecting to a service introduces its own set of additional requirements. The client must be running Tor and have a proxy set up to properly redirect requests using the .onion pseudo-domain. The server must also be configured to run the hidden service, because the system uses Tor routing rather than DNS or IP addressing to route traffic.

Multiple timelines?

The integrity of the timeline is paramount to making the Sovereign Keys system work. Although, technically speaking, there are multiple trusted timelines, one for each timeline server. The timeline servers inform each other of events, but in keeping with the append-only nature of the timeline, each timeline server has its own timestamp. There are separate record types to distinguish between events that happen on the timeline server and those that are relayed from a peer.

The process starts when the owner of a domain registers a sovereign key for a new service (officially, this registration calls for both a protocol — say, HTTPS or SMTPS — and a domain) with a nearby timeline server. According to the proposal, the registrant must present evidence that he or she controls the domain at the time of the registration. The evidence can be either "a CA-signed DER-encoded X.509 certificate associating the name with the Sovereign Key, or DANE DNSSEC evidence associating the name with the Sovereign Key, if that is available for this TLD [top-level domain]." The timeline server must verify the evidence. The evidence is logged in the timeline entry along with other pertinent data: the timeline's serial number and timestamp, the sovereign key itself, the domain name and protocol(s) registered for it, an optional expiration date, and two auxiliary fields, "wildcard" and "inheriting name(s)."

The proposal estimates that the space required to store such timeline entries for all of the 200 million domains currently in existence is around 300GB (although no estimate is made for how quickly this set of domains is growing, which could also prove relevant). The wildcard field is set by the registrant; if 0 then the sovereign key applies only the exact domain name listed; if 1 then the sovereign key is considered valid for matching subdomains as well. The "inheriting name(s)" are an optional list of other sovereign keys that are granted the right to register a new sovereign key for this domain if and when this current sovereign key is later revoked. Only self-signed revocations are accepted, so, in theory, designating "heirs" at the time of registration prevents later hijacking.

Apart from new sovereign key registrations, the timeline contains three types of entries: registrations-by-reference (registrations that were initiated at other timeline servers), revocations, and reissuances (which might change parameters like the protocols accepted). These entries are shorter, consisting of (in the registration-by-reference example) the original timeline server's id, serial number, and timestamp data, plus the serial number and timestamp that the reference was logged at in this timeline.

The design calls for a set number of timeline servers (10-30); having multiple root timeline servers should increase performance and make the network more reliable, particularly if they are located in different geographic and network regions. The proposal does not address how they are bootstrapped, but they seem to require a priori knowledge of each other in order to propagate registrations-by-reference and other important timeline events. Mirrors, on the other hand, also increase availability and performance from the clients' perspective, but mirrors do not record any new events to the timeline, they only synchronize with the authoritative timeline servers.

Conflicts, mirrors, and sharing

Space in the proposal is dedicated to what happens when one timeline server seems to violate the rules, such as storing two entries in its timeline with the same or out-of-order serial numbers, recording a lower timestamp than a previous entry, or registering a new sovereign key without verifiable credentials. Because clients are expected to query the mirror servers and not the root timeline servers directly, mirrors are expected to catch the misbehavior first. They then record the incident (including the problematic timeline entries), stop trusting the timeline server, and propagate the incident to clients that ask. Mirrors are also supposed to propagate this "renegation" information to each other; presumably the managers of the root timeline servers would be notified as well.

A longer discussion is devoted to the mirroring and mirror-querying protocol. Clients are supposed to trust the oldest sovereign key found for a domain in all of the valid timelines — plus whatever revocations and renewals follow it — so replicating the entire timeline could be important to verifying any particular transaction. How long clients and mirrors should cache information is both a performance and security consideration. The proposal recommends a series of trust stages from 24 hours to two weeks in length.

It also discusses how Sovereign Keys could be implemented in parallel with the existing SSL/TLS CA system. Because clients can do sovereign key verification by checking one signature on the certificate presented by a server, the CA system is not needed at all, but Eckersley recommends implementing it at first with sovereign key signatures added-on to existing CA-signed (or self-signed) server certificates.

Issues

The issues/ directory in the Git repository discusses technical and practical problems with the proposal, including concerns with such a CA/Sovereign Keys transitional system. The first is that an attacker who compromises a victim's DNS or web server can generate fraudulent sovereign key registrations complete with the DANE or CA-backed credentials the system is supposed to trust. The authors recommend that domain owners combat this potential attack by preemptively creating a sovereign key with no associated protocols, and outline a series of steps that root timeline server administrators could take to protect against rogue registrations.

There are several potential problems with timeline management discussed as well, including attackers compromising a timeline server (which is particularly troublesome since the timeline servers trust each other unless a renegation is spotted), false alarms caused by system time adjustments, and clock synchronization problems. A separate issue addresses the assumption that the set of authoritative timeline servers is small and well-known. This assumption has implications for renegation tracking and synchronization, but it also limits the decentralization of the Sovereign Keys framework, and in a real sense places critical (if not ultimate) trust in the timeline overseers.

Two attack vectors are considered: denial of service by flooding the timeline servers with registrations or the timeline servers and mirrors with queries, and a Sybil attack against a client by overloading its list of Sovereign Keys mirrors with compromised servers.

Of the vulnerabilities discussed, the false registrations created by breaking the existing CA or DANE DNSSEC system clearly has the largest attack surface. After all, the Internet could not be "switched over" to Sovereign Keys instantaneously even if every server and CA decided to do so. In the meantime, as EFF's other publications regularly show, there are enough attacks on (and security holes in) the CA system now that the Sovereign Keys proposal's reliance on CA as the trust authority for new sovereign key registrations sounds almost illogical. The proposal details ideas for bootstrapping mirror servers in a secure way, but creating verifiable sovereign keys for the 200 million domains is a much larger problem to solve.

It is clear that the current CA system is seriously flawed, and it is clear that browser certificate warnings are an ineffective tool to prevent users from falling victim to attackers. Some parts of the draft Sovereign Keys proposal are intriguing (such as the verifiable, public timeline record), but in other ways to most end users it may sound like replacing one remote authority with another. Falling back on Tor might be good from a technical perspective, but will be a challenge to implement. On either of the two goals of the project, then, its future will depend on how it is received by those outside of the EFF.