Kyoto Tycoon Secure Replication

by Nick Sullivan.

Kyoto Tycoon is a distributed key-value store written by FAL Labs, and it is used extensively at CloudFlare. Like many popular key-value stores, Kyoto Tycoon uses timestamp-based replication to ensure eventual consistency and guarantee ordering. Kyoto Tycoon is an open source project, and in the spirit of the holidays, we’re contributing our internal changes back to the open source project.

CC BY-ND 2.0 image by Moyan BrennCC BY-ND 2.0 image by Moyan Brenn

CloudFlare uses Kyoto Tycoon to replicate data from a Postgres Database to our 30 data centers around the world. In practice, it takes around 3 seconds for full propagation in normal conditions. This is our pipeline for distributing sensitive data like our session ticket keys and DNS data to the CloudFlare edge.

Protecting data in transit

If the Internet is not a dangerous place, it at least has dangerous neighborhoods. To move from one datacenter to another, data has to pass through the public Internet. Data could end up going though some network with a wire-tap in place, or through a network with an unscrupulous network operator.

Datacenter-to-datacenter encryption has been brought into the international spotlight since the surveillance revelations. One of the leaked slides contained the expression “SSL added and removed here”, and described how data could be read while in transit between Google’s data centers. As a reaction, Google and other Internet giants have started using strong cryptography for communication between datacenters. CloudFlare also encrypts cross-datacenter traffic, with Kyoto Tycoon playing a big part.

With Kyoto Tycoon’s original design, data was replicated across the Internet in plaintext. Now, data replication happens over a mutually-authenticated encryption tunnel. Any parties with the ability to read or modify network traffic will not be able to read or modify the data. We thought this change would be useful for others using Kyoto Tycoon, so as promised we’re releasing the source code for our changes back to the community.

TLS Mutual Authentication

In the standard HTTPS used by browsers, authentication is one-way: browsers validate the identity of the server but servers don’t validate the identity of the browser. The mechanism for this is an algorithm we’ve talked a lot about on this blog called Transport Layer Security (TLS). A website can be accessed securely using TLS and a certificate signed by a trusted Certificate Authority. When a browser loads a site, it checks to see if the certificate is valid and was issued to the proper domain name. If everything is valid, a lock icon is show to indicate encryption. Any failure to validate the certificate in the browser shows a warning that the site is not trusted.

The following diagram shows how a TLS connection is established.

There are different requirements for server-to-server communication. For one, both sides need to trust each other. This mutual trust prevents malicious computers from accessing the network of CloudFlare machines. In TLS, the feature that enables both sides to authenticate each other is called client authentication. Just as in the example above, the server has a certificate and validates its side of the connection, but in addition, the client also has a certificate. At the end of the handshake, the client signs the conversation with its certificate key. This signature proves that the client owns the certificate and that the handshake hasn’t been tampered with.

Client authentication is a simple way for servers to limit incoming connections to trusted clients. It’s sometimes used with browsers in corporate environments, and we use it in Keyless SSL to authenticate connections to the key server.

We added support for mutually authenticated replication to Kyoto Tycoon using OpenSSL. We use an internal CA to sign and validate the certificates. The code for our version of Kyoto Tycoon (and the related project Kyoto Cabinet) is available here on Github:

Happy Holidays and stay safe.

comments powered by Disqus