Merge pull request #8 from matrix-org/server2server_signing

Server2server signing

20 files changed, 540 insertions, 440 deletions

diff --git a/synapse/api/errors.py b/synapse/api/errors.py
index 88175602c4..6d7d499fea 100644
--- a/synapse/api/errors.py
+++ b/synapse/api/errors.py
@@ -19,6 +19,7 @@ import logging
 
 
 class Codes(object):
+    UNAUTHORIZED = "M_UNAUTHORIZED"
     FORBIDDEN = "M_FORBIDDEN"
     BAD_JSON = "M_BAD_JSON"
     NOT_JSON = "M_NOT_JSON"
diff --git a/synapse/api/urls.py b/synapse/api/urls.py
index 6314f31f7a..6dc19305b7 100644
--- a/synapse/api/urls.py
+++ b/synapse/api/urls.py
@@ -18,4 +18,5 @@
 CLIENT_PREFIX = "/_matrix/client/api/v1"
 FEDERATION_PREFIX = "/_matrix/federation/v1"
 WEB_CLIENT_PREFIX = "/_matrix/client"
-CONTENT_REPO_PREFIX = "/_matrix/content"
\ No newline at end of file
+CONTENT_REPO_PREFIX = "/_matrix/content"
+SERVER_KEY_PREFIX = "/_matrix/key/v1"
diff --git a/synapse/app/homeserver.py b/synapse/app/homeserver.py
index 61d574a00f..6394bc27d1 100755
--- a/synapse/app/homeserver.py
+++ b/synapse/app/homeserver.py
@@ -25,9 +25,11 @@ from twisted.web.static import File
 from twisted.web.server import Site
 from synapse.http.server import JsonResource, RootRedirect
 from synapse.http.content_repository import ContentRepoResource
+from synapse.http.server_key_resource import LocalKey
 from synapse.http.client import MatrixHttpClient
 from synapse.api.urls import (
-    CLIENT_PREFIX, FEDERATION_PREFIX, WEB_CLIENT_PREFIX, CONTENT_REPO_PREFIX
+    CLIENT_PREFIX, FEDERATION_PREFIX, WEB_CLIENT_PREFIX, CONTENT_REPO_PREFIX,
+    SERVER_KEY_PREFIX,
 )
 from synapse.config.homeserver import HomeServerConfig
 from synapse.crypto import context_factory
@@ -63,6 +65,9 @@ class SynapseHomeServer(HomeServer):
             self, self.upload_dir, self.auth, self.content_addr
         )
 
+    def build_resource_for_server_key(self):
+        return LocalKey(self)
+
     def build_db_pool(self):
         return adbapi.ConnectionPool(
             "sqlite3", self.get_db_name(),
@@ -88,7 +93,8 @@ class SynapseHomeServer(HomeServer):
         desired_tree = [
             (CLIENT_PREFIX, self.get_resource_for_client()),
             (FEDERATION_PREFIX, self.get_resource_for_federation()),
-            (CONTENT_REPO_PREFIX, self.get_resource_for_content_repo())
+            (CONTENT_REPO_PREFIX, self.get_resource_for_content_repo()),
+            (SERVER_KEY_PREFIX, self.get_resource_for_server_key()),
         ]
         if web_client:
             logger.info("Adding the web client.")
diff --git a/synapse/config/server.py b/synapse/config/server.py
index 516e4cf882..d9d8d0e14e 100644
--- a/synapse/config/server.py
+++ b/synapse/config/server.py
@@ -13,10 +13,9 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-import nacl.signing
 import os
-from ._base import Config
-from syutil.base64util import encode_base64, decode_base64
+from ._base import Config, ConfigError
+import syutil.crypto.signing_key
 
 
 class ServerConfig(Config):
@@ -70,9 +69,16 @@ class ServerConfig(Config):
                                   "content repository")
 
     def read_signing_key(self, signing_key_path):
-        signing_key_base64 = self.read_file(signing_key_path, "signing_key")
-        signing_key_bytes = decode_base64(signing_key_base64)
-        return nacl.signing.SigningKey(signing_key_bytes)
+        signing_keys = self.read_file(signing_key_path, "signing_key")
+        try:
+            return syutil.crypto.signing_key.read_signing_keys(
+                signing_keys.splitlines(True)
+            )
+        except Exception as e:
+            raise ConfigError(
+                "Error reading signing_key."
+                " Try running again with --generate-config"
+            )
 
     @classmethod
     def generate_config(cls, args, config_dir_path):
@@ -86,6 +92,21 @@ class ServerConfig(Config):
 
         if not os.path.exists(args.signing_key_path):
             with open(args.signing_key_path, "w") as signing_key_file:
-                key = nacl.signing.SigningKey.generate()
-                signing_key_file.write(encode_base64(key.encode()))
-
+                syutil.crypto.signing_key.write_signing_keys(
+                    signing_key_file,
+                    (syutil.crypto.SigningKey.generate("auto"),),
+                )
+        else:
+            signing_keys = cls.read_file(args.signing_key_path, "signing_key")
+            if len(signing_keys.split("\n")[0].split()) == 1:
+                # handle keys in the old format.
+                key = syutil.crypto.signing_key.decode_signing_key_base64(
+                    syutil.crypto.signing_key.NACL_ED25519,
+                    "auto",
+                    signing_keys.split("\n")[0]
+                )
+                with open(args.signing_key_path, "w") as signing_key_file:
+                    syutil.crypto.signing_key.write_signing_keys(
+                        signing_key_file,
+                        (key,),
+                    )
diff --git a/synapse/crypto/keyclient.py b/synapse/crypto/keyclient.py
index c11df5c529..5949ea0573 100644
--- a/synapse/crypto/keyclient.py
+++ b/synapse/crypto/keyclient.py
@@ -15,9 +15,10 @@
 
 
 from twisted.web.http import HTTPClient
+from twisted.internet.protocol import Factory
 from twisted.internet import defer, reactor
-from twisted.internet.protocol import ClientFactory
-from twisted.names.srvconnect import SRVConnector
+from twisted.internet.endpoints import connectProtocol
+from synapse.http.endpoint import matrix_endpoint
 import json
 import logging
 
@@ -30,15 +31,19 @@ def fetch_server_key(server_name, ssl_context_factory):
     """Fetch the keys for a remote server."""
 
     factory = SynapseKeyClientFactory()
+    endpoint = matrix_endpoint(
+        reactor, server_name, ssl_context_factory, timeout=30
+    )
 
-    SRVConnector(
-        reactor, "matrix", server_name, factory,
-        protocol="tcp", connectFuncName="connectSSL", defaultPort=443,
-        connectFuncKwArgs=dict(contextFactory=ssl_context_factory)).connect()
-
-    server_key, server_certificate = yield factory.remote_key
-
-    defer.returnValue((server_key, server_certificate))
+    for i in range(5):
+        try:
+            protocol = yield endpoint.connect(factory)
+            server_response, server_certificate = yield protocol.remote_key
+            defer.returnValue((server_response, server_certificate))
+            return
+        except Exception as e:
+            logger.exception(e)
+    raise IOError("Cannot get key for %s" % server_name)
 
 
 class SynapseKeyClientError(Exception):
@@ -51,69 +56,47 @@ class SynapseKeyClientProtocol(HTTPClient):
     the server and extracts the X.509 certificate for the remote peer from the
     SSL connection."""
 
+    timeout = 30
+
+    def __init__(self):
+        self.remote_key = defer.Deferred()
+
     def connectionMade(self):
         logger.debug("Connected to %s", self.transport.getHost())
-        self.sendCommand(b"GET", b"/key")
+        self.sendCommand(b"GET", b"/_matrix/key/v1/")
         self.endHeaders()
         self.timer = reactor.callLater(
-            self.factory.timeout_seconds,
+            self.timeout,
             self.on_timeout
         )
 
     def handleStatus(self, version, status, message):
         if status != b"200":
-            logger.info("Non-200 response from %s: %s %s",
-                        self.transport.getHost(), status, message)
+            #logger.info("Non-200 response from %s: %s %s",
+            #            self.transport.getHost(), status, message)
             self.transport.abortConnection()
 
     def handleResponse(self, response_body_bytes):
         try:
             json_response = json.loads(response_body_bytes)
         except ValueError:
-            logger.info("Invalid JSON response from %s",
-                        self.transport.getHost())
+            #logger.info("Invalid JSON response from %s",
+            #            self.transport.getHost())
             self.transport.abortConnection()
             return
 
         certificate = self.transport.getPeerCertificate()
-        self.factory.on_remote_key((json_response, certificate))
+        self.remote_key.callback((json_response, certificate))
         self.transport.abortConnection()
         self.timer.cancel()
 
     def on_timeout(self):
         logger.debug("Timeout waiting for response from %s",
                      self.transport.getHost())
+        self.remote_key.errback(IOError("Timeout waiting for response"))
         self.transport.abortConnection()
 
 
-class SynapseKeyClientFactory(ClientFactory):
+class SynapseKeyClientFactory(Factory):
     protocol = SynapseKeyClientProtocol
-    max_retries = 5
-    timeout_seconds = 30
-
-    def __init__(self):
-        self.succeeded = False
-        self.retries = 0
-        self.remote_key = defer.Deferred()
 
-    def on_remote_key(self, key):
-        self.succeeded = True
-        self.remote_key.callback(key)
-
-    def retry_connection(self, connector):
-        self.retries += 1
-        if self.retries < self.max_retries:
-            connector.connector = None
-            connector.connect()
-        else:
-            self.remote_key.errback(
-                SynapseKeyClientError("Max retries exceeded"))
-
-    def clientConnectionFailed(self, connector, reason):
-        logger.info("Connection failed %s", reason)
-        self.retry_connection(connector)
-
-    def clientConnectionLost(self, connector, reason):
-        logger.info("Connection lost %s", reason)
-        if not self.succeeded:
-            self.retry_connection(connector)
diff --git a/synapse/crypto/keyring.py b/synapse/crypto/keyring.py
new file mode 100644
index 0000000000..015f76ebe3
--- /dev/null
+++ b/synapse/crypto/keyring.py
@@ -0,0 +1,154 @@
+# -*- coding: utf-8 -*-
+# Copyright 2014 OpenMarket Ltd
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from synapse.crypto.keyclient import fetch_server_key
+from twisted.internet import defer
+from syutil.crypto.jsonsign import verify_signed_json, signature_ids
+from syutil.crypto.signing_key import (
+    is_signing_algorithm_supported, decode_verify_key_bytes
+)
+from syutil.base64util import decode_base64, encode_base64
+from synapse.api.errors import SynapseError, Codes
+
+from OpenSSL import crypto
+
+import logging
+
+
+logger = logging.getLogger(__name__)
+
+
+class Keyring(object):
+    def __init__(self, hs):
+        self.store = hs.get_datastore()
+        self.clock = hs.get_clock()
+        self.hs = hs
+
+    @defer.inlineCallbacks
+    def verify_json_for_server(self, server_name, json_object):
+        key_ids = signature_ids(json_object, server_name)
+        if not key_ids:
+            raise SynapseError(
+                400,
+                "Not signed with a supported algorithm",
+                 Codes.UNAUTHORIZED,
+            )
+        try:
+            verify_key = yield self.get_server_verify_key(server_name, key_ids)
+        except IOError:
+            raise SynapseError(
+                502,
+                "Error downloading keys for %s" % (server_name,),
+                Codes.UNAUTHORIZED,
+            )
+        except:
+            raise SynapseError(
+                401,
+                "No key for %s with id %s" % (server_name, key_ids),
+                Codes.UNAUTHORIZED,
+            )
+        try:
+            verify_signed_json(json_object, server_name, verify_key)
+        except:
+            raise SynapseError(
+                401,
+                "Invalid signature for server %s with key %s:%s" % (
+                    server_name, verify_key.alg, verify_key.version
+                ),
+                Codes.UNAUTHORIZED,
+            )
+
+    @defer.inlineCallbacks
+    def get_server_verify_key(self, server_name, key_ids):
+        """Finds a verification key for the server with one of the key ids.
+        Args:
+            server_name (str): The name of the server to fetch a key for.
+            keys_ids (list of str): The key_ids to check for.
+        """
+
+        # Check the datastore to see if we have one cached.
+        cached = yield self.store.get_server_verify_keys(server_name, key_ids)
+
+        if cached:
+            defer.returnValue(cached[0])
+            return
+
+        # Try to fetch the key from the remote server.
+        # TODO(markjh): Ratelimit requests to a given server.
+
+        (response, tls_certificate) = yield fetch_server_key(
+            server_name, self.hs.tls_context_factory
+        )
+
+        # Check the response.
+
+        x509_certificate_bytes = crypto.dump_certificate(
+            crypto.FILETYPE_ASN1, tls_certificate
+        )
+
+        if ("signatures" not in response
+            or server_name not in response["signatures"]):
+            raise ValueError("Key response not signed by remote server")
+
+        if "tls_certificate" not in response:
+            raise ValueError("Key response missing TLS certificate")
+
+        tls_certificate_b64 = response["tls_certificate"]
+
+        if encode_base64(x509_certificate_bytes) != tls_certificate_b64:
+            raise ValueError("TLS certificate doesn't match")
+
+        verify_keys = {}
+        for key_id, key_base64 in response["verify_keys"].items():
+            if is_signing_algorithm_supported(key_id):
+                key_bytes = decode_base64(key_base64)
+                verify_key = decode_verify_key_bytes(key_id, key_bytes)
+                verify_keys[key_id] = verify_key
+
+        for key_id in response["signatures"][server_name]:
+            if key_id not in response["verify_keys"]:
+                raise ValueError(
+                    "Key response must include verification keys for all"
+                    " signatures"
+                )
+            if key_id in verify_keys:
+                verify_signed_json(
+                    response,
+                    server_name,
+                    verify_keys[key_id]
+                )
+
+        # Cache the result in the datastore.
+
+        time_now_ms = self.clock.time_msec()
+
+        self.store.store_server_certificate(
+            server_name,
+            server_name,
+            time_now_ms,
+            tls_certificate,
+        )
+
+        for key_id, key in verify_keys.items():
+            self.store.store_server_verify_key(
+                server_name, server_name, time_now_ms, key
+            )
+
+        for key_id in key_ids:
+            if key_id in verify_keys:
+                defer.returnValue(verify_keys[key_id])
+                return
+
+        raise ValueError("No verification key found for given key ids")
diff --git a/synapse/crypto/keyserver.py b/synapse/crypto/keyserver.py
deleted file mode 100644
index a23484dbae..0000000000
--- a/synapse/crypto/keyserver.py
+++ /dev/null
@@ -1,111 +0,0 @@
-# -*- coding: utf-8 -*-
-# Copyright 2014 OpenMarket Ltd
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
-# you may not use this file except in compliance with the License.
-# You may obtain a copy of the License at
-#
-#     http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-
-
-from twisted.internet import reactor, ssl
-from twisted.web import server
-from twisted.web.resource import Resource
-from twisted.python.log import PythonLoggingObserver
-
-from synapse.crypto.resource.key import LocalKey
-from synapse.crypto.config import load_config
-
-from syutil.base64util import decode_base64
-
-from OpenSSL import crypto, SSL
-
-import logging
-import nacl.signing
-import sys
-
-
-class KeyServerSSLContextFactory(ssl.ContextFactory):
-    """Factory for PyOpenSSL SSL contexts that are used to handle incoming
-    connections and to make connections to remote servers."""
-
-    def __init__(self, key_server):
-        self._context = SSL.Context(SSL.SSLv23_METHOD)
-        self.configure_context(self._context, key_server)
-
-    @staticmethod
-    def configure_context(context, key_server):
-        context.set_options(SSL.OP_NO_SSLv2 | SSL.OP_NO_SSLv3)
-        context.use_certificate(key_server.tls_certificate)
-        context.use_privatekey(key_server.tls_private_key)
-        context.load_tmp_dh(key_server.tls_dh_params_path)
-        context.set_cipher_list("!ADH:HIGH+kEDH:!AECDH:HIGH+kEECDH")
-
-    def getContext(self):
-        return self._context
-
-
-class KeyServer(object):
-    """An HTTPS server serving LocalKey and RemoteKey resources."""
-
-    def __init__(self, server_name, tls_certificate_path, tls_private_key_path,
-                 tls_dh_params_path, signing_key_path, bind_host, bind_port):
-        self.server_name = server_name
-        self.tls_certificate = self.read_tls_certificate(tls_certificate_path)
-        self.tls_private_key = self.read_tls_private_key(tls_private_key_path)
-        self.tls_dh_params_path = tls_dh_params_path
-        self.signing_key = self.read_signing_key(signing_key_path)
-        self.bind_host = bind_host
-        self.bind_port = int(bind_port)
-        self.ssl_context_factory = KeyServerSSLContextFactory(self)
-
-    @staticmethod
-    def read_tls_certificate(cert_path):
-        with open(cert_path) as cert_file:
-            cert_pem = cert_file.read()
-            return crypto.load_certificate(crypto.FILETYPE_PEM, cert_pem)
-
-    @staticmethod
-    def read_tls_private_key(private_key_path):
-        with open(private_key_path) as private_key_file:
-            private_key_pem = private_key_file.read()
-            return crypto.load_privatekey(crypto.FILETYPE_PEM, private_key_pem)
-
-    @staticmethod
-    def read_signing_key(signing_key_path):
-        with open(signing_key_path) as signing_key_file:
-            signing_key_b64 = signing_key_file.read()
-            signing_key_bytes = decode_base64(signing_key_b64)
-            return nacl.signing.SigningKey(signing_key_bytes)
-
-    def run(self):
-        root = Resource()
-        root.putChild("key", LocalKey(self))
-        site = server.Site(root)
-        reactor.listenSSL(
-            self.bind_port,
-            site,
-            self.ssl_context_factory,
-            interface=self.bind_host
-        )
-
-        logging.basicConfig(level=logging.DEBUG)
-        observer = PythonLoggingObserver()
-        observer.start()
-
-        reactor.run()
-
-
-def main():
-    key_server = KeyServer(**load_config(__doc__, sys.argv[1:]))
-    key_server.run()
-
-
-if __name__ == "__main__":
-    main()
diff --git a/synapse/crypto/resource/__init__.py b/synapse/crypto/resource/__init__.py
deleted file mode 100644
index 9bff9ec169..0000000000
--- a/synapse/crypto/resource/__init__.py
+++ /dev/null
@@ -1,15 +0,0 @@
-# -*- coding: utf-8 -*-
-# Copyright 2014 OpenMarket Ltd
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
-# you may not use this file except in compliance with the License.
-# You may obtain a copy of the License at
-#
-#     http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-
diff --git a/synapse/crypto/resource/key.py b/synapse/crypto/resource/key.py
deleted file mode 100644
index 48d14b9f4a..0000000000
--- a/synapse/crypto/resource/key.py
+++ /dev/null
@@ -1,161 +0,0 @@
-# -*- coding: utf-8 -*-
-# Copyright 2014 OpenMarket Ltd
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
-# you may not use this file except in compliance with the License.
-# You may obtain a copy of the License at
-#
-#     http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-
-
-from twisted.web.resource import Resource
-from twisted.web.server import NOT_DONE_YET
-from twisted.internet import defer
-from synapse.http.server import respond_with_json_bytes
-from synapse.crypto.keyclient import fetch_server_key
-from syutil.crypto.jsonsign import sign_json, verify_signed_json
-from syutil.base64util import encode_base64, decode_base64
-from syutil.jsonutil import encode_canonical_json
-from OpenSSL import crypto
-from nacl.signing import VerifyKey
-import logging
-
-
-logger = logging.getLogger(__name__)
-
-
-class LocalKey(Resource):
-    """HTTP resource containing encoding the TLS X.509 certificate and NACL
-    signature verification keys for this server::
-
-        GET /key HTTP/1.1
-
-        HTTP/1.1 200 OK
-        Content-Type: application/json
-        {
-            "server_name": "this.server.example.com"
-            "signature_verify_key": # base64 encoded NACL verification key.
-            "tls_certificate": # base64 ASN.1 DER encoded X.509 tls cert.
-            "signatures": {
-                "this.server.example.com": # NACL signature for this server.
-            }
-        }
-    """
-
-    def __init__(self, key_server):
-        self.key_server = key_server
-        self.response_body = encode_canonical_json(
-            self.response_json_object(key_server)
-        )
-        Resource.__init__(self)
-
-    @staticmethod
-    def response_json_object(key_server):
-        verify_key_bytes = key_server.signing_key.verify_key.encode()
-        x509_certificate_bytes = crypto.dump_certificate(
-            crypto.FILETYPE_ASN1,
-            key_server.tls_certificate
-        )
-        json_object = {
-            u"server_name": key_server.server_name,
-            u"signature_verify_key": encode_base64(verify_key_bytes),
-            u"tls_certificate": encode_base64(x509_certificate_bytes)
-        }
-        signed_json = sign_json(
-            json_object,
-            key_server.server_name,
-            key_server.signing_key
-        )
-        return signed_json
-
-    def getChild(self, name, request):
-        logger.info("getChild %s %s", name, request)
-        if name == '':
-            return self
-        else:
-            return RemoteKey(name, self.key_server)
-
-    def render_GET(self, request):
-        return respond_with_json_bytes(request, 200, self.response_body)
-
-
-class RemoteKey(Resource):
-    """HTTP resource for retreiving the TLS certificate and NACL signature
-    verification keys for a another server. Checks that the reported X.509 TLS
-    certificate matches the one used in the HTTPS connection. Checks that the
-    NACL signature for the remote server is valid. Returns JSON signed by both
-    the remote server and by this server.
-
-    GET /key/remote.server.example.com HTTP/1.1
-
-    HTTP/1.1 200 OK
-    Content-Type: application/json
-    {
-        "server_name": "remote.server.example.com"
-        "signature_verify_key": # base64 encoded NACL verification key.
-        "tls_certificate": # base64 ASN.1 DER encoded X.509 tls cert.
-        "signatures": {
-            "remote.server.example.com": # NACL signature for remote server.
-            "this.server.example.com": # NACL signature for this server.
-        }
-    }
-    """
-
-    isLeaf = True
-
-    def __init__(self, server_name, key_server):
-        self.server_name = server_name
-        self.key_server = key_server
-        Resource.__init__(self)
-
-    def render_GET(self, request):
-        self._async_render_GET(request)
-        return NOT_DONE_YET
-
-    @defer.inlineCallbacks
-    def _async_render_GET(self, request):
-        try:
-            server_keys, certificate = yield fetch_server_key(
-                self.server_name,
-                self.key_server.ssl_context_factory
-            )
-
-            resp_server_name = server_keys[u"server_name"]
-            verify_key_b64 = server_keys[u"signature_verify_key"]
-            tls_certificate_b64 = server_keys[u"tls_certificate"]
-            verify_key = VerifyKey(decode_base64(verify_key_b64))
-
-            if resp_server_name != self.server_name:
-                raise ValueError("Wrong server name '%s' != '%s'" %
-                                 (resp_server_name, self.server_name))
-
-            x509_certificate_bytes = crypto.dump_certificate(
-                crypto.FILETYPE_ASN1,
-                certificate
-            )
-
-            if encode_base64(x509_certificate_bytes) != tls_certificate_b64:
-                raise ValueError("TLS certificate doesn't match")
-
-            verify_signed_json(server_keys, self.server_name, verify_key)
-
-            signed_json = sign_json(
-                server_keys,
-                self.key_server.server_name,
-                self.key_server.signing_key
-            )
-
-            json_bytes = encode_canonical_json(signed_json)
-            respond_with_json_bytes(request, 200, json_bytes)
-
-        except Exception as e:
-            json_bytes = encode_canonical_json({
-                u"error": {u"code": 502, u"message": e.message}
-            })
-            respond_with_json_bytes(request, 502, json_bytes)
diff --git a/synapse/federation/__init__.py b/synapse/federation/__init__.py
index 1351b68fd6..0112588656 100644
--- a/synapse/federation/__init__.py
+++ b/synapse/federation/__init__.py
@@ -22,6 +22,7 @@ from .transport import TransportLayer
 
 def initialize_http_replication(homeserver):
     transport = TransportLayer(
+        homeserver,
         homeserver.hostname,
         server=homeserver.get_resource_for_federation(),
         client=homeserver.get_http_client()
diff --git a/synapse/federation/replication.py b/synapse/federation/replication.py
index 5f96f79998..2346d55045 100644
--- a/synapse/federation/replication.py
+++ b/synapse/federation/replication.py
@@ -492,7 +492,6 @@ class _TransactionQueue(object):
     """
 
     def __init__(self, hs, transaction_actions, transport_layer):
-
         self.server_name = hs.hostname
         self.transaction_actions = transaction_actions
         self.transport_layer = transport_layer
@@ -591,7 +590,7 @@ class _TransactionQueue(object):
 
             transaction = Transaction.create_new(
                 ts=self._clock.time_msec(),
-                transaction_id=self._next_txn_id,
+                transaction_id=str(self._next_txn_id),
                 origin=self.server_name,
                 destination=destination,
                 pdus=pdus,
@@ -609,18 +608,17 @@ class _TransactionQueue(object):
 
             # FIXME (erikj): This is a bit of a hack to make the Pdu age
             # keys work
-            def cb(transaction):
+            def json_data_cb():
+                data = transaction.get_dict()
                 now = int(self._clock.time_msec())
-                if "pdus" in transaction:
-                    for p in transaction["pdus"]:
+                if "pdus" in data:
+                    for p in data["pdus"]:
                         if "age_ts" in p:
                             p["age"] = now - int(p["age_ts"])
-
-                return transaction
+                return data
 
             code, response = yield self.transport_layer.send_transaction(
-                transaction,
-                on_send_callback=cb,
+                transaction, json_data_cb
             )
 
             logger.debug("TX [%s] Sent transaction", destination)
diff --git a/synapse/federation/transport.py b/synapse/federation/transport.py
index 93296af204..755eee8cf6 100644
--- a/synapse/federation/transport.py
+++ b/synapse/federation/transport.py
@@ -24,6 +24,7 @@ over a different (albeit still reliable) protocol.
 from twisted.internet import defer
 
 from synapse.api.urls import FEDERATION_PREFIX as PREFIX
+from synapse.api.errors import Codes, SynapseError
 from synapse.util.logutils import log_function
 
 import logging
@@ -54,7 +55,7 @@ class TransportLayer(object):
             we receive data.
     """
 
-    def __init__(self, server_name, server, client):
+    def __init__(self, homeserver, server_name, server, client):
         """
         Args:
             server_name (str): Local home server host
@@ -63,6 +64,7 @@ class TransportLayer(object):
             client (synapse.protocol.http.HttpClient): the http client used to
                 send requests
         """
+        self.keyring = homeserver.get_keyring()
         self.server_name = server_name
         self.server = server
         self.client = client
@@ -144,7 +146,7 @@ class TransportLayer(object):
 
     @defer.inlineCallbacks
     @log_function
-    def send_transaction(self, transaction, on_send_callback=None):
+    def send_transaction(self, transaction, json_data_callback=None):
         """ Sends the given Transaction to it's destination
 
         Args:
@@ -163,25 +165,15 @@ class TransportLayer(object):
         if transaction.destination == self.server_name:
             raise RuntimeError("Transport layer cannot send to itself!")
 
-        data = transaction.get_dict()
-
-        # FIXME (erikj): This is a bit of a hack to make the Pdu age
-        # keys work
-        def cb(destination, method, path_bytes, producer):
-            if not on_send_callback:
-                return
-
-            transaction = json.loads(producer.body)
-
-            new_transaction = on_send_callback(transaction)
-
-            producer.reset(new_transaction)
+        # FIXME: This is only used by the tests. The actual json sent is
+        # generated by the json_data_callback.
+        json_data = transaction.get_dict()
 
         code, response = yield self.client.put_json(
             transaction.destination,
             path=PREFIX + "/send/%s/" % transaction.transaction_id,
-            data=data,
-            on_send_callback=cb,
+            data=json_data,
+            json_data_callback=json_data_callback,
         )
 
         logger.debug(
@@ -205,6 +197,72 @@ class TransportLayer(object):
 
         defer.returnValue(response)
 
+    @defer.inlineCallbacks
+    def _authenticate_request(self, request):
+        json_request = {
+            "method": request.method,
+            "uri": request.uri,
+            "destination": self.server_name,
+            "signatures": {},
+        }
+
+        content = None
+        origin = None
+
+        if request.method == "PUT":
+            #TODO: Handle other method types? other content types?
+            try:
+                content_bytes = request.content.read()
+                content = json.loads(content_bytes)
+                json_request["content"] = content
+            except:
+                raise SynapseError(400, "Unable to parse JSON", Codes.BAD_JSON)
+
+        def parse_auth_header(header_str):
+            try:
+                params = auth.split(" ")[1].split(",")
+                param_dict = dict(kv.split("=") for kv in params)
+                def strip_quotes(value):
+                    if value.startswith("\""):
+                        return value[1:-1]
+                    else:
+                        return value
+                origin = strip_quotes(param_dict["origin"])
+                key = strip_quotes(param_dict["key"])
+                sig = strip_quotes(param_dict["sig"])
+                return (origin, key, sig)
+            except:
+                raise SynapseError(
+                    400, "Malformed Authorization header", Codes.UNAUTHORIZED
+                )
+
+        auth_headers = request.requestHeaders.getRawHeaders(b"Authorization")
+
+        for auth in auth_headers:
+            if auth.startswith("X-Matrix"):
+                (origin, key, sig) = parse_auth_header(auth)
+                json_request["origin"] = origin
+                json_request["signatures"].setdefault(origin,{})[key] = sig
+
+        if not json_request["signatures"]:
+            raise SynapseError(
+                401, "Missing Authorization headers", Codes.UNAUTHORIZED,
+            )
+
+        yield self.keyring.verify_json_for_server(origin, json_request)
+
+        defer.returnValue((origin, content))
+
+    def _with_authentication(self, handler):
+        @defer.inlineCallbacks
+        def new_handler(request, *args, **kwargs):
+            (origin, content) = yield self._authenticate_request(request)
+            response = yield handler(
+                origin, content, request.args, *args, **kwargs
+            )
+            defer.returnValue(response)
+        return new_handler
+
     @log_function
     def register_received_handler(self, handler):
         """ Register a handler that will be fired when we receive data.
@@ -218,7 +276,7 @@ class TransportLayer(object):
         self.server.register_path(
             "PUT",
             re.compile("^" + PREFIX + "/send/([^/]*)/$"),
-            self._on_send_request
+            self._with_authentication(self._on_send_request)
         )
 
     @log_function
@@ -236,9 +294,9 @@ class TransportLayer(object):
         self.server.register_path(
             "GET",
             re.compile("^" + PREFIX + "/pull/$"),
-            lambda request: handler.on_pull_request(
-                request.args["origin"][0],
-                request.args["v"]
+            self._with_authentication(
+                lambda origin, content, query:
+                handler.on_pull_request(query["origin"][0], query["v"])
             )
         )
 
@@ -247,8 +305,9 @@ class TransportLayer(object):
         self.server.register_path(
             "GET",
             re.compile("^" + PREFIX + "/pdu/([^/]*)/([^/]*)/$"),
-            lambda request, pdu_origin, pdu_id: handler.on_pdu_request(
-                pdu_origin, pdu_id
+            self._with_authentication(
+                lambda origin, content, query, pdu_origin, pdu_id:
+                handler.on_pdu_request(pdu_origin, pdu_id)
             )
         )
 
@@ -256,38 +315,47 @@ class TransportLayer(object):
         self.server.register_path(
             "GET",
             re.compile("^" + PREFIX + "/state/([^/]*)/$"),
-            lambda request, context: handler.on_context_state_request(
-                context
+            self._with_authentication(
+                lambda origin, content, query, context:
+                handler.on_context_state_request(context)
             )
         )
 
         self.server.register_path(
             "GET",
             re.compile("^" + PREFIX + "/backfill/([^/]*)/$"),
-            lambda request, context: self._on_backfill_request(
-                context, request.args["v"],
-                request.args["limit"]
+            self._with_authentication(
+                lambda origin, content, query, context:
+                self._on_backfill_request(
+                    context, query["v"], query["limit"]
+                )
             )
         )
 
         self.server.register_path(
             "GET",
             re.compile("^" + PREFIX + "/context/([^/]*)/$"),
-            lambda request, context: handler.on_context_pdus_request(context)
+            self._with_authentication(
+                lambda origin, content, query, context:
+                handler.on_context_pdus_request(context)
+            )
         )
 
         # This is when we receive a server-server Query
         self.server.register_path(
             "GET",
             re.compile("^" + PREFIX + "/query/([^/]*)$"),
-            lambda request, query_type: handler.on_query_request(
-                query_type, {k: v[0] for k, v in request.args.items()}
+            self._with_authentication(
+                lambda origin, content, query, query_type:
+                handler.on_query_request(
+                    query_type, {k: v[0] for k, v in query.items()}
+                )
             )
         )
 
     @defer.inlineCallbacks
     @log_function
-    def _on_send_request(self, request, transaction_id):
+    def _on_send_request(self, origin, content, query, transaction_id):
         """ Called on PUT /send/<transaction_id>/
 
         Args:
@@ -302,12 +370,7 @@ class TransportLayer(object):
         """
         # Parse the request
         try:
-            data = request.content.read()
-
-            l = data[:20].encode("string_escape")
-            logger.debug("Got data: \"%s\"", l)
-
-            transaction_data = json.loads(data)
+            transaction_data = content
 
             logger.debug(
                 "Decoded %s: %s",
diff --git a/synapse/federation/units.py b/synapse/federation/units.py
index 622fe66a8f..ecca35ac43 100644
--- a/synapse/federation/units.py
+++ b/synapse/federation/units.py
@@ -186,6 +186,8 @@ class Transaction(JsonEncodedObject):
         "previous_ids",
         "pdus",
         "edus",
+        "transaction_id",
+        "destination",
     ]
 
     internal_keys = [
diff --git a/synapse/http/client.py b/synapse/http/client.py
index 0e8fa2eb25..9f54b74e3a 100644
--- a/synapse/http/client.py
+++ b/synapse/http/client.py
@@ -26,6 +26,8 @@ from syutil.jsonutil import encode_canonical_json
 
 from synapse.api.errors import CodeMessageException, SynapseError
 
+from syutil.crypto.jsonsign import sign_json
+
 from StringIO import StringIO
 
 import json
@@ -147,7 +149,7 @@ class BaseHttpClient(object):
 
 
 class MatrixHttpClient(BaseHttpClient):
-    """ Wrapper around the twisted HTTP client api. Implements 
+    """ Wrapper around the twisted HTTP client api. Implements
 
     Attributes:
         agent (twisted.web.client.Agent): The twisted Agent used to send the
@@ -156,8 +158,42 @@ class MatrixHttpClient(BaseHttpClient):
 
     RETRY_DNS_LOOKUP_FAILURES = "__retry_dns"
 
+    def __init__(self, hs):
+        self.signing_key = hs.config.signing_key[0]
+        self.server_name = hs.hostname
+        BaseHttpClient.__init__(self, hs)
+
+    def sign_request(self, destination, method, url_bytes, headers_dict,
+                     content=None):
+        request = {
+            "method": method,
+            "uri": url_bytes,
+            "origin": self.server_name,
+            "destination": destination,
+        }
+
+        if content is not None:
+            request["content"] = content
+
+        request = sign_json(request, self.server_name, self.signing_key)
+
+        from syutil.jsonutil import encode_canonical_json
+        logger.debug("Signing " + " " * 11 + "%s %s",
+            self.server_name, encode_canonical_json(request))
+
+        auth_headers = []
+
+        for key,sig in request["signatures"][self.server_name].items():
+            auth_headers.append(bytes(
+                "X-Matrix origin=%s,key=\"%s\",sig=\"%s\"" % (
+                    self.server_name, key, sig,
+                )
+            ))
+
+        headers_dict[b"Authorization"] = auth_headers
+
     @defer.inlineCallbacks
-    def put_json(self, destination, path, data, on_send_callback=None):
+    def put_json(self, destination, path, data={}, json_data_callback=None):
         """ Sends the specifed json data using PUT
 
         Args:
@@ -166,6 +202,8 @@ class MatrixHttpClient(BaseHttpClient):
             path (str): The HTTP path.
             data (dict): A dict containing the data that will be used as
                 the request body. This will be encoded as JSON.
+            json_data_callback (callable): A callable returning the dict to
+                use as the request body.
 
         Returns:
             Deferred: Succeeds when we get a 2xx HTTP response. The result
@@ -173,13 +211,16 @@ class MatrixHttpClient(BaseHttpClient):
             CodeMessageException is raised.
         """
 
-        if not on_send_callback:
-            def on_send_callback(destination, method, path_bytes, producer):
-                pass
+        if not json_data_callback:
+            def json_data_callback():
+                return data
 
         def body_callback(method, url_bytes, headers_dict):
-            producer = _JsonProducer(data)
-            on_send_callback(destination, method, path, producer)
+            json_data = json_data_callback()
+            self.sign_request(
+                destination, method, url_bytes, headers_dict, json_data
+            )
+            producer = _JsonProducer(json_data)
             return producer
 
         response = yield self._create_request(
@@ -221,6 +262,7 @@ class MatrixHttpClient(BaseHttpClient):
         logger.debug("Query bytes: %s Retry DNS: %s", args, retry_on_dns_fail)
 
         def body_callback(method, url_bytes, headers_dict):
+            self.sign_request(destination, method, url_bytes, headers_dict)
             return None
 
         response = yield self._create_request(
diff --git a/synapse/http/server_key_resource.py b/synapse/http/server_key_resource.py
new file mode 100644
index 0000000000..b30ecead27
--- /dev/null
+++ b/synapse/http/server_key_resource.py
@@ -0,0 +1,89 @@
+# -*- coding: utf-8 -*-
+# Copyright 2014 OpenMarket Ltd
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+
+from twisted.web.resource import Resource
+from synapse.http.server import respond_with_json_bytes
+from syutil.crypto.jsonsign import sign_json
+from syutil.base64util import encode_base64
+from syutil.jsonutil import encode_canonical_json
+from OpenSSL import crypto
+import logging
+
+
+logger = logging.getLogger(__name__)
+
+
+class LocalKey(Resource):
+    """HTTP resource containing encoding the TLS X.509 certificate and NACL
+    signature verification keys for this server::
+
+        GET /key HTTP/1.1
+
+        HTTP/1.1 200 OK
+        Content-Type: application/json
+        {
+            "server_name": "this.server.example.com"
+            "verify_keys": {
+                "algorithm:version": # base64 encoded NACL verification key.
+            },
+            "tls_certificate": # base64 ASN.1 DER encoded X.509 tls cert.
+            "signatures": {
+                "this.server.example.com": {
+                   "algorithm:version": # NACL signature for this server.
+                }
+            }
+        }
+    """
+
+    def __init__(self, hs):
+        self.hs = hs
+        self.response_body = encode_canonical_json(
+            self.response_json_object(hs.config)
+        )
+        Resource.__init__(self)
+
+    @staticmethod
+    def response_json_object(server_config):
+        verify_keys = {}
+        for key in server_config.signing_key:
+            verify_key_bytes = key.verify_key.encode()
+            key_id = "%s:%s" % (key.alg, key.version)
+            verify_keys[key_id] = encode_base64(verify_key_bytes)
+
+        x509_certificate_bytes = crypto.dump_certificate(
+            crypto.FILETYPE_ASN1,
+            server_config.tls_certificate
+        )
+        json_object = {
+            u"server_name": server_config.server_name,
+            u"verify_keys": verify_keys,
+            u"tls_certificate": encode_base64(x509_certificate_bytes)
+        }
+        for key in server_config.signing_key:
+            json_object = sign_json(
+                json_object,
+                server_config.server_name,
+                key,
+            )
+
+        return json_object
+
+    def render_GET(self, request):
+        return respond_with_json_bytes(request, 200, self.response_body)
+
+    def getChild(self, name, request):
+        if name == '':
+            return self
diff --git a/synapse/server.py b/synapse/server.py
index e5b048ede0..a4d2d4aba5 100644
--- a/synapse/server.py
+++ b/synapse/server.py
@@ -34,6 +34,7 @@ from synapse.util.distributor import Distributor
 from synapse.util.lockutils import LockManager
 from synapse.streams.events import EventSources
 from synapse.api.ratelimiting import Ratelimiter
+from synapse.crypto.keyring import Keyring
 
 
 class BaseHomeServer(object):
@@ -75,8 +76,10 @@ class BaseHomeServer(object):
         'resource_for_federation',
         'resource_for_web_client',
         'resource_for_content_repo',
+        'resource_for_server_key',
         'event_sources',
         'ratelimiter',
+        'keyring',
     ]
 
     def __init__(self, hostname, **kwargs):
@@ -212,6 +215,9 @@ class HomeServer(BaseHomeServer):
     def build_ratelimiter(self):
         return Ratelimiter()
 
+    def build_keyring(self):
+        return Keyring(self)
+
     def register_servlets(self):
         """ Register all servlets associated with this HomeServer.
         """
diff --git a/synapse/storage/__init__.py b/synapse/storage/__init__.py
index 32d9c1392b..6dadeb8cce 100644
--- a/synapse/storage/__init__.py
+++ b/synapse/storage/__init__.py
@@ -57,6 +57,7 @@ SCHEMAS = [
     "presence",
     "im",
     "room_aliases",
+    "keys",
     "redactions",
 ]
 
diff --git a/synapse/storage/_base.py b/synapse/storage/_base.py
index 889de2bedc..dba50f1213 100644
--- a/synapse/storage/_base.py
+++ b/synapse/storage/_base.py
@@ -121,7 +121,7 @@ class SQLBaseStore(object):
     # "Simple" SQL API methods that operate on a single table with no JOINs,
     # no complex WHERE clauses, just a dict of values for columns.
 
-    def _simple_insert(self, table, values, or_replace=False):
+    def _simple_insert(self, table, values, or_replace=False, or_ignore=False):
         """Executes an INSERT query on the named table.
 
         Args:
@@ -130,13 +130,16 @@ class SQLBaseStore(object):
             or_replace : bool; if True performs an INSERT OR REPLACE
         """
         return self.runInteraction(
-            self._simple_insert_txn, table, values, or_replace=or_replace
+            self._simple_insert_txn, table, values, or_replace=or_replace,
+            or_ignore=or_ignore,
         )
 
     @log_function
-    def _simple_insert_txn(self, txn, table, values, or_replace=False):
+    def _simple_insert_txn(self, txn, table, values, or_replace=False,
+                           or_ignore=False):
         sql = "%s INTO %s (%s) VALUES(%s)" % (
-            ("INSERT OR REPLACE" if or_replace else "INSERT"),
+            ("INSERT OR REPLACE" if or_replace else
+             "INSERT OR IGNORE" if or_ignore else "INSERT"),
             table,
             ", ".join(k for k in values),
             ", ".join("?" for k in values)
diff --git a/synapse/storage/keys.py b/synapse/storage/keys.py
index 5a38c3e8f2..8189e071a3 100644
--- a/synapse/storage/keys.py
+++ b/synapse/storage/keys.py
@@ -18,7 +18,8 @@ from _base import SQLBaseStore
 from twisted.internet import defer
 
 import OpenSSL
-import nacl.signing
+from  syutil.crypto.signing_key import decode_verify_key_bytes
+import hashlib
 
 class KeyStore(SQLBaseStore):
     """Persistence for signature verification keys and tls X.509 certificates
@@ -42,62 +43,76 @@ class KeyStore(SQLBaseStore):
         )
         defer.returnValue(tls_certificate)
 
-    def store_server_certificate(self, server_name, key_server, ts_now_ms,
+    def store_server_certificate(self, server_name, from_server, time_now_ms,
                                  tls_certificate):
         """Stores the TLS X.509 certificate for the given server
         Args:
-            server_name (bytes): The name of the server.
-            key_server (bytes): Where the certificate was looked up
-            ts_now_ms (int): The time now in milliseconds
+            server_name (str): The name of the server.
+            from_server (str): Where the certificate was looked up
+            time_now_ms (int): The time now in milliseconds
             tls_certificate (OpenSSL.crypto.X509): The X.509 certificate.
         """
         tls_certificate_bytes = OpenSSL.crypto.dump_certificate(
             OpenSSL.crypto.FILETYPE_ASN1, tls_certificate
         )
+        fingerprint = hashlib.sha256(tls_certificate_bytes).hexdigest()
         return self._simple_insert(
             table="server_tls_certificates",
-            keyvalues={
+            values={
                 "server_name": server_name,
-                "key_server": key_server,
-                "ts_added_ms": ts_now_ms,
-                "tls_certificate": tls_certificate_bytes,
+                "fingerprint": fingerprint,
+                "from_server": from_server,
+                "ts_added_ms": time_now_ms,
+                "tls_certificate": buffer(tls_certificate_bytes),
             },
+            or_ignore=True,
         )
 
     @defer.inlineCallbacks
-    def get_server_verification_key(self, server_name):
-        """Retrieve the NACL verification key for a given server
+    def get_server_verify_keys(self, server_name, key_ids):
+        """Retrieve the NACL verification key for a given server for the given
+        key_ids
         Args:
-            server_name (bytes): The name of the server.
+            server_name (str): The name of the server.
+            key_ids (list of str): List of key_ids to try and look up.
         Returns:
-            (nacl.signing.VerifyKey): The verification key.
+            (list of VerifyKey): The verification keys.
         """
-        verification_key_bytes, = yield self._simple_select_one(
-            table="server_signature_keys",
-            key_values={"server_name": server_name},
-            retcols=("tls_certificate",),
+        sql = (
+            "SELECT key_id, verify_key FROM server_signature_keys"
+            " WHERE server_name = ?"
+            " AND key_id in (" + ",".join("?" for key_id in key_ids) + ")"
         )
-        verification_key = nacl.signing.VerifyKey(verification_key_bytes)
-        defer.returnValue(verification_key)
 
-    def store_server_verification_key(self, server_name, key_version,
-                                      key_server, ts_now_ms, verification_key):
+        rows = yield self._execute_and_decode(sql, server_name, *key_ids)
+
+        keys = []
+        for row in rows:
+            key_id = row["key_id"]
+            key_bytes = row["verify_key"]
+            key = decode_verify_key_bytes(key_id, str(key_bytes))
+            keys.append(key)
+        defer.returnValue(keys)
+
+    def store_server_verify_key(self, server_name, from_server, time_now_ms,
+                                verify_key):
         """Stores a NACL verification key for the given server.
         Args:
-            server_name (bytes): The name of the server.
-            key_version (bytes): The version of the key for the server.
-            key_server (bytes): Where the verification key was looked up
+            server_name (str): The name of the server.
+            key_id (str): The version of the key for the server.
+            from_server (str): Where the verification key was looked up
             ts_now_ms (int): The time now in milliseconds
-            verification_key (nacl.signing.VerifyKey): The NACL verify key.
+            verification_key (VerifyKey): The NACL verify key.
         """
-        verification_key_bytes = verification_key.encode()
+        verify_key_bytes = verify_key.encode()
         return self._simple_insert(
             table="server_signature_keys",
-            key_values={
+            values={
                 "server_name": server_name,
-                "key_version": key_version,
-                "key_server": key_server,
-                "ts_added_ms": ts_now_ms,
-                "verification_key": verification_key_bytes,
+                "key_id": "%s:%s" % (verify_key.alg, verify_key.version),
+                "from_server": from_server,
+                "ts_added_ms": time_now_ms,
+                "verify_key": buffer(verify_key.encode()),
             },
+            or_ignore=True,
         )
diff --git a/synapse/storage/schema/keys.sql b/synapse/storage/schema/keys.sql
index 706a1a03ff..9bf2068d84 100644
--- a/synapse/storage/schema/keys.sql
+++ b/synapse/storage/schema/keys.sql
@@ -14,17 +14,18 @@
  */
 CREATE TABLE IF NOT EXISTS server_tls_certificates(
   server_name TEXT, -- Server name.
-  key_server TEXT, -- Which key server the certificate was fetched from.
+  fingerprint TEXT, -- Certificate fingerprint.
+  from_server TEXT, -- Which key server the certificate was fetched from.
   ts_added_ms INTEGER, -- When the certifcate was added.
   tls_certificate BLOB, -- DER encoded x509 certificate.
-  CONSTRAINT uniqueness UNIQUE (server_name)
+  CONSTRAINT uniqueness UNIQUE (server_name, fingerprint)
 );
 
 CREATE TABLE IF NOT EXISTS server_signature_keys(
   server_name TEXT, -- Server name.
-  key_version TEXT, -- Key version.
-  key_server TEXT, -- Which key server the key was fetched form.
+  key_id TEXT, -- Key version.
+  from_server TEXT, -- Which key server the key was fetched form.
   ts_added_ms INTEGER, -- When the key was added.
-  verification_key BLOB, -- NACL verification key.
-  CONSTRAINT uniqueness UNIQUE (server_name, key_version)
+  verify_key BLOB, -- NACL verification key.
+  CONSTRAINT uniqueness UNIQUE (server_name, key_id)
 );