November 18, 2011 | By Peter Eckersley

Sovereign Keys: A Proposal to Make HTTPS and Email More Secure

This is part 2 of a series on the security of HTTPS and TLS/SSL. [Part 1]

In a previous post, we discussed some structural insecurities in HTTPS and TLS/SSL, and how those are beginning to pose serious problems for the security of the Web.

In this post I will introduce a new proposal called "Sovereign Keys", which is intended to systematically fix these weaknesses in the way that encrypted Internet protocols perform authentication. The proposal should be considered "draft" and "experimental". It will take at least a couple of years to build and test implementations of the idea to a sufficient degree for large-scale deployment, and so even if the Sovereign Keys design is successful, we are going to need some band-aids for HTTPS insecurity in the mean time (what band-aids are available is a subject for a future post). A draft design document for the Sovereign Key project is now online; this post attempts to give a high-level and less technical summary of the design's objectives and features. We are also working on a prototype implementation, and fundraising to support the project — we will publish code as soon as it's good enough to hack on and experiment with.

The Sovereign Keys design would allow clients and servers to use cryptographic protocols without having to depend on any third parties after the moment the server creates a Sovereign Key. But the design also aims to do a couple of things that other proposals for fixing the problems with CA proliferation and domain validation do not. The biggest is to remove certificate warnings altogether, and to replace them with automatic circumvention of attacks.

What's wrong with certificate warnings? How can we abolish them?

Research has shown that human beings don't understand certificate warnings and often click through them. That's not surprising: X.509 certificates are an extremely complicated and obscure infrastructure. Usually, when we get error messages about them, the errors have innocent causes, and the rational response is to click through the warning to get to the site you're trying to visit.1 But what this means is that certificate warnings don't offer much protection when they are trying to tell people about a real, serious attack.

An example of this problem is the man-in-the-middle attack that was observed by Syrian Facebook users in May of this year. That attack was conducted with an arbitrary certificate, not one signed by a trusted CA — so every target would have seen a warning message like this one:

Screenshot of a certificate warning in IE7

However, research from the Usable Privacy and Security Lab at CMU indicates that a large proportion of those targets probably clicked through and logged into their Facebook accounts anyway. The warning would only have protected a fraction of them.

Browser developers have realized this problem exists, and have been continually changing the way certificate warnings work, to make them nastier-looking and harder to click through. That helps slightly, but is also quite absurd, because it doesn't change the underlying fact that certificate warnings most often occur for unhelpful bureaucratic reasons, and many users learn to click around them out of necessity or rational pragmatism.

In the Sovereign Key design, certificate warnings are unnecessary. For websites that chose to publish a Sovereign Key (more on how you do that below and in the design docs), the web browser or email client will never show a certificate warning. Instead, if an attempt to connect over TLS results in a session that isn't cross-signed by the Sovereign Key, the browser can automatically circumvent the attack. The strongest way to do this is to compute a hash of the Sovereign Key, and use that as the .onion address of a Tor hidden service. It is also possible to use proxies or VPNs for weaker versions of this protection (in a later post we'll talk about why it's better to use Tor hidden services for this purpose). Because these methods may be slow, the user can be shown a message along the lines of "Experiencing difficulty establishing a secure connection to this site. Give us a moment while we try harder...", with a nice friendly spinning hourglass or beachball, or better, a realtime depiction of the progress of attack circumvention process.

If, after an attempt at circumventing attacks, the browser still cannot establish a verified connection to the server, it reports an error indicating that the server is unreachable.

Technical Overview: How is a Sovereign Key created? How do clients learn about them?

In the design, Sovereign Keys are created by writing to a semi-centralized, verifiably append-only data structure. The main requirement for being able to do this is that the requesting party controls a CA-signed certificate for the relevant domain, or uses a DNSSEC-signed key to show that they control that domain.2

Master copies of the append-only data structure are kept on machines called "timeline servers". There is a small number, around 10-20, of these. The level of trust that must be placed in them is very low, because the Sovereign Key protocol is able to cryptographically verify the important functions they perform. Sovereign Keys are preserved so long as at least one server has remained good. For scalability, verification, and privacy purposes, lots of copies of the entire append-only timeline structure are stored on machines called "mirrors". The timeline data structure might grow to be hundreds of gigabytes in size, but that is presently a small portion of a $100 disk drive.

Clients learn about Sovereign Keys by sending (encrypted) queries to mirrors. Once a client knows a Sovereign Key for a domain, that fact can be cached for a very long time, with only occasional queries to check for revocations. This arrangement has some nice properties in terms of making the protocol quite robust even if mirrors are malicious, blocked, or just unreliable. Clients can keep using the protocol for long periods under very hostile network conditions (like those you might find in Syria, Iran or Burma), although eventually, if they are unable to find good mirrors for weeks at a time, they will fail safe altogether.

How Strong is the Security Provided by Sovereign Keys?

In the existing TLS authentication system, there are lots of ways for attackers to obtain certificates perfidiously. In the Sovereign Key design, the attacker needs to not only perform one of those attacks, but must also possess a time machine to travel back before the target's Sovereign Key was written into the append-only data structure.

This means that websites can choose not to depend on any third parties for the security of their encryption, if they wish to. In practice, we expect many domains to use a third-party service provider for Sovereign Key management,3 but the domain holders can choose exactly which if any such parties they wish to trust. That is in stark contrast to the present situation, where every HTTPS website is vulnerable to security incidents or malfeasance in an uncontrollably large number of places.

Steps forward

The basic Sovereign Key idea is quite simple, but the addition of real-world requirements (revocation, renewal and transfer of keys; scalability; resistance to denial-of-service attacks; good tools to make all of this simple for systems administrators) makes the project somewhat ambitious.

We are working on an experimental prototype implementation, and fundraising to support this project. We'll have more to say when there's code ready for people to play with. In the mean time, we'll follow up with more posts comparing the Sovereign Key design to other proposals for addressing the insecurities in the existing Public Key Infrastructure, including DNSSEC and Perspectives/Convergence.

  • 1. Causes of false-positive warnings about certificates include certificate expiry, certificates that cover fewer variants of a domain name than the webserver they're used on, the strange phenomenon we have been calling transvalidity, where some certificates are only valid if your browser has cached the right intermediate CA certificates before hand (the SSL Observatory found about 100,000 servers using transvalid certificates that sometimes cause these mysterious warnings), use of a CA that is trusted by some browsers but not others, and a choice by a webserver operator to use a self-signed cert rather than paying a CA for one.
  • 2. In the current draft, there are additional requirements, including that an OCSP check for the CA certificate is successful, that the domain has been redirecting all HTTP traffic to HTTPS and publishing an HSTS header with this domain for the past two weeks.
  • 3. Because Sovereign Keys are so strong, they need to be backed up redundantly and revocation and re-issuance need to be managed well. Anyone can do this, but specialized service providers will be the lowest-effort way to do it.

Deeplinks Topics

Stay in Touch

NSA Spying

EFF is leading the fight against the NSA's illegal mass surveillance program. Learn more about what the program is, how it works, and what you can do.

Follow EFF

Pls plan to call your House Rep Monday, "vote no FCC privacy repeal" If your rep is Republican, ask 5 friends too

Mar 24 @ 4:18pm

A loophole in Australia's copyright safe harbor rules will stay open, endangering local user-generated content sites

Mar 24 @ 1:37pm

In all, @agcrocker addressed the appeals court on NSLs for more than 25 minutes. Here's the full recording.

Mar 24 @ 1:09pm
JavaScript license information