Sovereign Keys – An EFF Proposal

Sovereign Keys Introduction

Secure communication over the internet depends almost exclusively on Secure Sockets Layer (SSL) and/or Transport Layer Security (TLS).  In order to understand the Electronic Frontier Foundation’s (EFF) Sovereign Keys proposal, we need to take a closer look at how public key cryptography works as well as the public key infrastructure (PKI) that is in place to manage the public/private keys that are relied on for TLS.  After discussing public key cryptography and PKI, we will discuss current implementations of SSL/TLS and the numerous components therein: Domain Name System (DNS), Certificate Authorities (CA) and client/server implementation.  Finally, we will discuss the primary weaknesses in the current implementation, the Sovereign Keys proposal and how it aims to remedy those weaknesses.

To begin, we need to understand public key cryptography, which is also known as asymmetric cryptography.  In asymmetric cryptography there must exist two keys in which to provide for the desired cryptographic functions – namely the encryption/decryption of plaintext/ciphertext or the generation/validation of a digital signature.  This differs from symmetric cryptography, which only utilizes a single key for desired cryptographic functions.  The two keys utilized in asymmetric cryptography are commonly referred to as the public and private key.  As the name implies, the public key is ultimately made public and utilized in encrypting plaintext and verifying digital signatures.  Public keys are therefore made available to be public and not protected as a private key is.  Private keys, on the other hand, are utilized to decrypt ciphertext (ciphertext is the result of running an encryption algorithm on plaintext) and to generate a digital signature. (“Introduction to Public-Key”, 2014)(“Public-key Cryptography”, 2014)

Therefore, anyone with access to a public key is able to encrypt plaintext to send to the owner of the private key.  The holder of the private key is then the only party able to decrypt the ciphertext.  In dealing with communication that needs to be secured over the internet, this provides an ideal solution.  That is, after a client is able to obtain and verify a public key for an intended recipient, the client can send secure communications without fear of compromise (interception, tampering, et cetera) (Tews, 2012)

It is worth pointing out that public keys can in fact be made public.  Since the generation of the public and private key are founded in mathematical principals, it is currently not feasible to attempt to generate a corresponding private key from a public key, allowing public keys to be freely shared.  (“Public-key Cryptography”, 2014)

Utilizing asymmetric cryptography is a straight-forward process and typically involves generating a public/private key, providing the public key to a third party and then sending/receiving ciphertext/plaintext.  The major obstacle with this model is the distribution of the public key.  While it is easy for an individual to generate their key-pair and post their public key, such as in an email signature or social media platform, it is very difficult for this to scale to websites or high-traffic platforms that which to communicate securely with a large number of individuals in which they have no direct, personal relationship.  Keep in mind, it is not enough to simply make a public key available, the consumer of that public key has to also be able to verify that public key belongs to the person/organization that claims to own it.    In order to solve this problem,the public key infrasture was created and implemented.

Public key infrastructure, or PKI, was designed to “bind public keys with respective user identities by means of a certificate authority (CA)” (“Public Key Infrastructure”, 2014).  In it’s simplest sense, PKI allows a third party to verify that a public key belongs to an individual/organization that is claiming it’s ownership.  Once the public key has been verified, the third-part can feel confident in their secure communications with the owner of the public key.  PKI does this through the issuance of a digital certificate (also called an X.509 certificate), which ultimately proves ownership of a public key.  The digital certificate will contain information such as the owner, their public key and the digital signature of the authority that is certifying that the digital certificate is valid (that is, the public key belongs to the purported individual/organization).  In the case of web-based communications, the digital signature of the authority that has validated the digital certificate is typically a Certificate Authority (CA), which is considered the signer of the digital certificate.

The digital certificate that is ultimately assigned to a host is the result of what is typically referred to as the X.509 hierarchy.  The root of this hierarchical system begins with a few root CAs.  These root CAs utilize a minimal amount of public keys to provide issuance of other certificates, which serves to bind the public key to the hosts identity.  The root CAs are also able to delegate signing privileges to other organizations, which greatly expands the ability of the PKI architecture.  This process results in a trust chain, which consists of the root’s certificate, potential intermediate certificates and finally the host’s certificate.  Clients, ie browsers, are configured with a list of root certificates.  When a browser encounters a host’s certificate, they can leverage the root certificates they are already configured to trust to determine the identify of the host.  With most modern browsers, they are configured to trust 600 or more root or intermediate certificates. (Gielesberger, 2013)

With the invention of the CA, the ability to verify public keys can scale to the level needed to support TLS-based communication over the internet.  As long as the reputation of the CA is good, then they can trust any digital certificate signed by that CA, which implicitly means they are trusting the public key with the intended third party (owner of the public key) without every verifying true ownership directly.  While this appears to be an acceptable solution, problems arise when one can not trust the CA.  Cases in which trust is lost in a CA are when they are compromised and an attacker can issue fraudulent digital certificates that are genuinely signed by the CA. Anyone that trusts that CA will also trust the fraudulent certificate based on the stolen digital certificate.  The DigiNor story mentioned early in this document is an excellent example of the breakdown of the PKI system.  Essentially, a CA is able to issue a valid, trusted certificate for a host without the consent of the host.  (Gielesberger, 2013)   This leads to one of the primary issues with the current architecture, since a browser will inherently trust a large number root and intermediate CAs, if a CA is compromised the attacker is able to issue fraudulent certificates without the host ever knowing.  Once this has occurred, certificate revocation has to take place and in it’s current form is highly ineffective and disorganized, as well as largely ignored by browsers and/or users.

With the infrastructure in place, TLS was able to be implemented to provide end-to-end encryption over the internet.  In a typical scenario, when a user wishes to connect to a web server a session is established.  During the setup of the session, the web server will respond with it’s public key.  The browser can then verify the public key through the use of the digital certificate issued by a CA (and the inherent trust chain).  If the public-keys match, then the browser trusts that public key and can proceed in using secure communications with the server.  If the key is not verified, the browser typically displays a certificate error to the user.  Currently, there is no widely-accepted and implemented standard for the client to determine the validity of the public key sent; it simply checks if the certificate was legitimately signed.  If a CA is compromised, then attackers can generate fraudulent “valid” certificates and masquerade as legitimate organizations, acting on their behalf for nefarious purposes.  When a certificate is identified as no longer valid, especially when it is fraudulent or has been compromised, clients need to know to immediately stop trusting that certificate.  Due to the limitations of the structure of the CA, there is no effective way of communicating this to the clients.  (Tews, 2012)(McKinley, 2012)  The most common solution is for the browser to display a certificate error warning, indicating to the user that they can not trust communication with the server and should not proceed.  However, the user is typically allowed the opportunity to accept the certificate warning and proceed in establishing a secure connection with the site, using a potentially invalid public key.  In this scenario, the client is potentially communicating sensitive information with an untrusted server.  It is with this problem that EFF proposed Sovereign Keys aims to address.

As previously stated, Sovereign Keys is a proposal and no current implementation exists.  As such, we can discuss the technical validity of the proposal and determine how it helps in addressing the verification of a public-key.  The overall goal of Sovereign Keys is to assist the consumer of a public-key in determining the validity of the public key they received from a server (or third party).  This becomes especially important when the end-user can not efficiently determine when they can no longer trust the CA or a specific certificate issued by a CA.  In order to provide an additional element of security, one outside of the direct trust relationship with the CA, Sovereign Keys proposes an independent infrasture that utilizes additional hardware, cooperation with website owners/operators and browser vendors.  Sovereign Keys is a transparency-based system. (Gielesberger, 2013)  The proposal includes, at it’s core, timeline servers, mirrors and clients.  A timeline server, which will contain an append-only data structure is used to record the sovereign key.  This sovereign key is generated by a site owner (or owner of a public key) after receiving a valid digital certificate from a CA.  In order to generate a sovereign key, the website must be able to prove domain ownership via the digital certificate signed by a CA.  Once the sovereign key is generated, it is submitted to a timeline server.  The timeline server appends this information, the key and the certificate, to it’s append-only data structure.  The timeline servers are managed, when a key and certificate are submitted for addition to a timeline server, they can be checked for validity utilizing the digital certificate.  If the submitted key is verified, the operator of the timeline server will add them to the database along with the domain name the sovereign key is valid for. (Tews, 2012)(Eckersley, 2011)  With a Soveriegn Key in place, when a client receives a host certificate, they are now able to check for a cross-signature in the X509 certificate (see figure 1).

Chain of trust

Figure 1: X509 Certificate Signing (Gielesberger, 2013)

The append-only data structure is a critical component in the proposed infrastructure.  When a sovereign key is initially claimed for a domain name, it is recorded via the timeline server’s records.  These records can no longer be altered, which prevents a subsequent claimant from attempting to alter the original claim even if they had successfully been able to compromise a CA – since a claim is partially based on a valid digital certificate.  The append-only data structure is guaranteed by utilizing an incrementing serial number and a monotonically increasing timestamp, which become a part of each entry into the timeline.  In the proposal, if any entry violates these two properties then a client will immediately stop trusting that timeline server.  When a client requests a sovereign key, the client will trust the oldest claim to that key. (Eckersley, 2014) This aspect of the design also provides for the transparency of the system.  Since the Sovereign Keys are made publicly available on the timeline server, a client is thus able to verify the cross-signature which allows them to determine the validity of the certificate they were presented with.  The timeline server is the core of the system because they hold the mapping between the host and it’s corresponding Sovereign Key.  (Gielesberger, 2013)

The process in which a client registers a Sovereign Key is worth paying particular attention.  The request generates a write event to the timeline server, in which other timeline servers and mirrors are updated to the change.  The process of associating a Sovereign Key to a host is called binding.  The host will send a bind message to a timeline server with proof of domain ownership, which can include a valid CA-signed certificate or a key that utilizes DNSSEC via DANE.  (Gielesberger, 2013)  The timeline server will record the bind message and will be utilized by clients to determine the authenticity of the Sovereign Key.  This is a critical step, as it produces the claim of trust from the host certificate to the root certificate.  This trust is assumed, and discussed, later when a client verifies a domain by it’s Sovereign Key.

In the proposal, there is not a single timeline server.  Multiple timeline servers are proposed that are geographically disperse, diversely operated and exhibit various security mechanisms.  According to the draft proposal, about 10 – 30 timeline servers would be sufficient to implement the core infrastructure.  However, clients would not be sending their queries directly to a timeline server but rather a mirror.  In the proposal, there will be M mirrors, where there are more mirrors than timeline servers, would be added to the infrastructure to provide for accessibility and scalability, with the mirror containing a read-only copy of the entire append-only data structure.  This would also allow for verification of sovereign keys, as a client would be able to utilize the mirrors to verify the information they received. (Eckersley, 2011)  Mirrors will be kept in-synchronization with the timeline servers to ensure accuracy and reliability.  Mirrors will have a complete picture of the timeline data-structure, which allows them to detect rogue mirrors and remove them from the list of trusted mirrors. (Gielesberger, 2013)

The final component in the proposal is the client.  When a client receives an X.509 certificate it will not need to perform the usual certificate chain check, as this process will be guaranteed by the timeline server and the Sovereign Key.  Instead, the client will contact a mirror to obtain the host’s sovereign key and check that the certificate has been signed by that key.  In order to cross-sign a certificate with a Sovereign Key, the proposal relies on an extension to the X509 data format.  This extension allows for a certificate to be signed by more than one key, which is not supported without the extension.  Clients that do not support this extension will ignore it and there will be no impact on their ability to handle the certificate as it normally would. (Gielesberger, 2013)

When a client queries a mirror for a Sovereign Key, it receives a chronological listing of messages for that domain.  The client then uses the key that signed the first bind message in order to verify the remaining messages as well as to connect to any defined services with the host.  A host can submit an Unbind message, in which case the Sovereign Key is disassociated with the domain.  If a client encounters an Unbind message, it evaluate the messages for a Rebind message.  If a Rebind message is located than that key is used.  If no Rebind is found then there is no valid Sovereign Key for that domain. (Gielesberger, 2013)

In a typical scenario using sovereign keys, a client would attempt to connect to a website via it’s domain name.  The client wishes to establish secure communications and the server supports HTTPS using SSL/TLS.   The domain name system (DNS) is utilized to resolve a domain name into an internet protocol (IP) address.  The client then contacts the server via the IP address and attempts to establish a secure connection.  The client’s browser needs to be aware of sovereign keys and the server has to have a published sovereign key.   Assuming the server published a sovereign key and the client is aware to check, the client will make a request to a mirror while establishing the secure connection to the website.  The client is then able to verify that the public key provided by the server has been cross-signed by a sovereign key.  If this can not be verified, the client can not send data to the server and may display an appropriate warning/error to the user.  If verification is successful, the client is able to establish secure communications with the server. (Eckersley, 2014)

End User Experience

When looking at the implementation of Sovereign Keys, there are primarily two actors that we need to be concerned with: browser vendors and the site owners/operators.  It is these two parties that will be largely responsible for the successful adoption of the proposal – assuming adequate infrastructure is built and in place.  For the browser vendors, the most significant hurdle will be in creating products that are Sovereign Keys aware.  This burden will largely fall on the browser vendors, as it is assumed that the typical user will not want to configure additional security.  That is, the end user of a browser assumes that all the security they need for SSL/TLS communication is built directly into the browser and works without additional configuration.  It is therefore up to the browser vendors to implement the Sovereign Keys protocol in the browser and provide an appropriate response when verification fails (as the proposal defines, the client can not send data but may notify the user or leverage an alternate route).

The other burden fails on the site operators, as it is up to them to submit a sovereign key to a timeline server for inclusion in the infrastructure.  Additionally, the site operator must submit any self-signed changes to the infrastructure.  These changes may include certificate revocations and renewals. (Eckersley, 2014)

This leaves us with the end-user and how they fit into the infrastructure.  In a typical browsing scenario, when verification fails the protocol states that the client can not send data to the server and may inform the user of the problem.  EFF’s research has shown that most users will ignore any client-side certificate validation errors in order to proceed with their task at hand.  In order to provide the user a seamless and secure connection to the legitimate server, the proposal includes automated circumvention of attacks.  When a server operator/owner submits their sovereign key, they can additionally provide preferred, alternate routing paths.  This alternate routing may be implemented in lieu of client-side warning messages and be triggered automatically, making it transparent to the end user. The alternative is to decline the connection and inform the user that their request can not be completed.  (Eckersley, 2014)

There are still significant problems that Sovereign Keys will face when dealing with the end-user.  The primary problem is that the user will have to be using a browser that supports Sovereign Keys as well as connecting to a site that utilizes it.  This additionally security needs to be transparent to the end-user, which means that all major browsers will need to support it as well as a significant number of site operators in order for it to achieve any level of effectiveness, preventing the user from performing additional configuration in their browser of choice or having to perform research in order to determine which sites support Sovereign Keys.

 Market Usage

At the time of this writing, no support by browser vendors or large-scale site operators has been noted.  The proposal is still in draft form, prototype code is available at (“Alternatives to X.509”, 2014).  However, the code appears to be incomplete and, according to commit logs, work stopped in August of 2012.

 

Sources

“Introduction to Public-Key Cryptography.” Mozilla Developer Network. Mozilla, n.d. Web. 28 Nov. 2014.
<https://developer.mozilla.org/en-US/docs/Introduction_to_Public-Key_Cryptography>.

“Public-key Cryptography.” Wikipedia. Wikimedia Foundation, 27 Nov. 2014. Web. 28 Nov. 2014. <https://en.wikipedia.org/wiki/Public-key_cryptography>.

Tews, Erik. “Sovereign Keys – A Proposal for Fixing Attacks on CAs and DNSSEC.” Cryptanalysis Breaking News. N.p., 28 Jan. 2012. Web. 28 Nov. 2014. <https://cryptanalysis.eu/blog/2012/01/18/sovereign-keys-a-proposal-for-fixing-attacks-on-cas-and-dnssec/>.

“Public Key Infrastructure.” Wikipedia. Wikimedia Foundation, 28 Nov. 2014. Web. 28 Nov. 2014. <https://en.wikipedia.org/wiki/Public_key_infrastructure>.

“Public Key Certificate.” Wikipedia. Wikimedia Foundation, 26 Nov. 2014. Web. 28 Nov. 2014. <https://en.wikipedia.org/wiki/Public_key_certificate>.

McKinley, Holly L. “SSL and TLS: A Beginners Guide.” SANS Institute InfoSec Reading Room (2012): 1-15. Web. 28 Nov. 2014.

Eckersley, Peter. “Sovereign Keys: A Proposal to Make HTTPS and Email More Secure.” Electronic Frontier Foundation. N.p., 18 Nov. 2011. Web. 28 Nov. 2014. <https://www.eff.org/deeplinks/2011/11/sovereign-keys-proposal-make-https-and-email-more-secure>.

Eckersley, Peter. “Git.eff.org Git – Sovereign-keys.git/blob – Sovereign-key-design.txt.” Git.eff.org Git – Sovereign-keys.git/blob – Sovereign-key-design.txt. Electronic Frontier Foundation, n.d. Web. 28 Nov. 2014. <https://git.eff.org/?p=sovereign-keys.git;a=blob;f=sovereign-key-design.txt;hb=master>.

“Git.eff.org Git – Sovereign-keys.git/tree.” Git.eff.org Git – Sovereign-keys.git/tree. Electronic Frontier Foundation, n.d. Web. 28 Nov. 2014. <https://git.eff.org/?p=sovereign-keys.git;a=tree>.

Gielesberger, Michael. “Alternatives to X.509.” Alternatives to X.509 (n.d.): n. pag. Web. <http://www.net.in.tum.de/fileadmin/TUM/NET/NET-2013-02-1/NET-2013-02-1_07.pdf>.

 

Leave a Reply