Merge pull request #5726 from matrix-org/uhoreg/e2e_cross-signing2-part2

Cross-signing [3/4] -- uploading signatures edition

5 files changed, 774 insertions, 14 deletions

diff --git a/changelog.d/5726.feature b/changelog.d/5726.feature
new file mode 100644
index 0000000000..d3c669aec0
--- /dev/null
+++ b/changelog.d/5726.feature
@@ -0,0 +1 @@
+Add ability to upload cross-signing signatures.
diff --git a/synapse/handlers/e2e_keys.py b/synapse/handlers/e2e_keys.py
index be675197f1..5ea54f60be 100644
--- a/synapse/handlers/e2e_keys.py
+++ b/synapse/handlers/e2e_keys.py
@@ -19,12 +19,15 @@ import logging
 
 from six import iteritems
 
+import attr
 from canonicaljson import encode_canonical_json, json
+from signedjson.key import decode_verify_key_bytes
 from signedjson.sign import SignatureVerifyException, verify_signed_json
+from unpaddedbase64 import decode_base64
 
 from twisted.internet import defer
 
-from synapse.api.errors import CodeMessageException, Codes, SynapseError
+from synapse.api.errors import CodeMessageException, Codes, NotFoundError, SynapseError
 from synapse.logging.context import make_deferred_yieldable, run_in_background
 from synapse.logging.opentracing import log_kv, set_tag, tag_args, trace
 from synapse.types import (
@@ -602,6 +605,339 @@ class E2eKeysHandler(object):
 
         return {}
 
+    @defer.inlineCallbacks
+    def upload_signatures_for_device_keys(self, user_id, signatures):
+        """Upload device signatures for cross-signing
+
+        Args:
+            user_id (string): the user uploading the signatures
+            signatures (dict[string, dict[string, dict]]): map of users to
+                devices to signed keys. This is the submission from the user; an
+                exception will be raised if it is malformed.
+        Returns:
+            dict: response to be sent back to the client.  The response will have
+                a "failures" key, which will be a dict mapping users to devices
+                to errors for the signatures that failed.
+        Raises:
+            SynapseError: if the signatures dict is not valid.
+        """
+        failures = {}
+
+        # signatures to be stored.  Each item will be a SignatureListItem
+        signature_list = []
+
+        # split between checking signatures for own user and signatures for
+        # other users, since we verify them with different keys
+        self_signatures = signatures.get(user_id, {})
+        other_signatures = {k: v for k, v in signatures.items() if k != user_id}
+
+        self_signature_list, self_failures = yield self._process_self_signatures(
+            user_id, self_signatures
+        )
+        signature_list.extend(self_signature_list)
+        failures.update(self_failures)
+
+        other_signature_list, other_failures = yield self._process_other_signatures(
+            user_id, other_signatures
+        )
+        signature_list.extend(other_signature_list)
+        failures.update(other_failures)
+
+        # store the signature, and send the appropriate notifications for sync
+        logger.debug("upload signature failures: %r", failures)
+        yield self.store.store_e2e_cross_signing_signatures(user_id, signature_list)
+
+        self_device_ids = [item.target_device_id for item in self_signature_list]
+        if self_device_ids:
+            yield self.device_handler.notify_device_update(user_id, self_device_ids)
+        signed_users = [item.target_user_id for item in other_signature_list]
+        if signed_users:
+            yield self.device_handler.notify_user_signature_update(
+                user_id, signed_users
+            )
+
+        return {"failures": failures}
+
+    @defer.inlineCallbacks
+    def _process_self_signatures(self, user_id, signatures):
+        """Process uploaded signatures of the user's own keys.
+
+        Signatures of the user's own keys from this API come in two forms:
+        - signatures of the user's devices by the user's self-signing key,
+        - signatures of the user's master key by the user's devices.
+
+        Args:
+            user_id (string): the user uploading the keys
+            signatures (dict[string, dict]): map of devices to signed keys
+
+        Returns:
+            (list[SignatureListItem], dict[string, dict[string, dict]]):
+            a list of signatures to store, and a map of users to devices to failure
+            reasons
+
+        Raises:
+            SynapseError: if the input is malformed
+        """
+        signature_list = []
+        failures = {}
+        if not signatures:
+            return signature_list, failures
+
+        if not isinstance(signatures, dict):
+            raise SynapseError(400, "Invalid parameter", Codes.INVALID_PARAM)
+
+        try:
+            # get our self-signing key to verify the signatures
+            _, self_signing_key_id, self_signing_verify_key = yield self._get_e2e_cross_signing_verify_key(
+                user_id, "self_signing"
+            )
+
+            # get our master key, since we may have received a signature of it.
+            # We need to fetch it here so that we know what its key ID is, so
+            # that we can check if a signature that was sent is a signature of
+            # the master key or of a device
+            master_key, _, master_verify_key = yield self._get_e2e_cross_signing_verify_key(
+                user_id, "master"
+            )
+
+            # fetch our stored devices.  This is used to 1. verify
+            # signatures on the master key, and 2. to compare with what
+            # was sent if the device was signed
+            devices = yield self.store.get_e2e_device_keys([(user_id, None)])
+
+            if user_id not in devices:
+                raise NotFoundError("No device keys found")
+
+            devices = devices[user_id]
+        except SynapseError as e:
+            failure = _exception_to_failure(e)
+            failures[user_id] = {device: failure for device in signatures.keys()}
+            return signature_list, failures
+
+        for device_id, device in signatures.items():
+            # make sure submitted data is in the right form
+            if not isinstance(device, dict):
+                raise SynapseError(400, "Invalid parameter", Codes.INVALID_PARAM)
+
+            try:
+                if "signatures" not in device or user_id not in device["signatures"]:
+                    # no signature was sent
+                    raise SynapseError(
+                        400, "Invalid signature", Codes.INVALID_SIGNATURE
+                    )
+
+                if device_id == master_verify_key.version:
+                    # The signature is of the master key. This needs to be
+                    # handled differently from signatures of normal devices.
+                    master_key_signature_list = self._check_master_key_signature(
+                        user_id, device_id, device, master_key, devices
+                    )
+                    signature_list.extend(master_key_signature_list)
+                    continue
+
+                # at this point, we have a device that should be signed
+                # by the self-signing key
+                if self_signing_key_id not in device["signatures"][user_id]:
+                    # no signature was sent
+                    raise SynapseError(
+                        400, "Invalid signature", Codes.INVALID_SIGNATURE
+                    )
+
+                try:
+                    stored_device = devices[device_id]
+                except KeyError:
+                    raise NotFoundError("Unknown device")
+                if self_signing_key_id in stored_device.get("signatures", {}).get(
+                    user_id, {}
+                ):
+                    # we already have a signature on this device, so we
+                    # can skip it, since it should be exactly the same
+                    continue
+
+                _check_device_signature(
+                    user_id, self_signing_verify_key, device, stored_device
+                )
+
+                signature = device["signatures"][user_id][self_signing_key_id]
+                signature_list.append(
+                    SignatureListItem(
+                        self_signing_key_id, user_id, device_id, signature
+                    )
+                )
+            except SynapseError as e:
+                failures.setdefault(user_id, {})[device_id] = _exception_to_failure(e)
+
+        return signature_list, failures
+
+    def _check_master_key_signature(
+        self, user_id, master_key_id, signed_master_key, stored_master_key, devices
+    ):
+        """Check signatures of a user's master key made by their devices.
+
+        Args:
+            user_id (string): the user whose master key is being checked
+            master_key_id (string): the ID of the user's master key
+            signed_master_key (dict): the user's signed master key that was uploaded
+            stored_master_key (dict): our previously-stored copy of the user's master key
+            devices (iterable(dict)): the user's devices
+
+        Returns:
+            list[SignatureListItem]: a list of signatures to store
+
+        Raises:
+            SynapseError: if a signature is invalid
+        """
+        # for each device that signed the master key, check the signature.
+        master_key_signature_list = []
+        sigs = signed_master_key["signatures"]
+        for signing_key_id, signature in sigs[user_id].items():
+            _, signing_device_id = signing_key_id.split(":", 1)
+            if (
+                signing_device_id not in devices
+                or signing_key_id not in devices[signing_device_id]["keys"]
+            ):
+                # signed by an unknown device, or the
+                # device does not have the key
+                raise SynapseError(400, "Invalid signature", Codes.INVALID_SIGNATURE)
+
+            # get the key and check the signature
+            pubkey = devices[signing_device_id]["keys"][signing_key_id]
+            verify_key = decode_verify_key_bytes(signing_key_id, decode_base64(pubkey))
+            _check_device_signature(
+                user_id, verify_key, signed_master_key, stored_master_key
+            )
+
+            master_key_signature_list.append(
+                SignatureListItem(signing_key_id, user_id, master_key_id, signature)
+            )
+
+        return master_key_signature_list
+
+    @defer.inlineCallbacks
+    def _process_other_signatures(self, user_id, signatures):
+        """Process uploaded signatures of other users' keys.  These will be the
+        target user's master keys, signed by the uploading user's user-signing
+        key.
+
+        Args:
+            user_id (string): the user uploading the keys
+            signatures (dict[string, dict]): map of users to devices to signed keys
+
+        Returns:
+            (list[SignatureListItem], dict[string, dict[string, dict]]):
+            a list of signatures to store, and a map of users to devices to failure
+            reasons
+
+        Raises:
+            SynapseError: if the input is malformed
+        """
+        signature_list = []
+        failures = {}
+        if not signatures:
+            return signature_list, failures
+
+        try:
+            # get our user-signing key to verify the signatures
+            user_signing_key, user_signing_key_id, user_signing_verify_key = yield self._get_e2e_cross_signing_verify_key(
+                user_id, "user_signing"
+            )
+        except SynapseError as e:
+            failure = _exception_to_failure(e)
+            for user, devicemap in signatures.items():
+                failures[user] = {device_id: failure for device_id in devicemap.keys()}
+            return signature_list, failures
+
+        for target_user, devicemap in signatures.items():
+            # make sure submitted data is in the right form
+            if not isinstance(devicemap, dict):
+                raise SynapseError(400, "Invalid parameter", Codes.INVALID_PARAM)
+            for device in devicemap.values():
+                if not isinstance(device, dict):
+                    raise SynapseError(400, "Invalid parameter", Codes.INVALID_PARAM)
+
+            device_id = None
+            try:
+                # get the target user's master key, to make sure it matches
+                # what was sent
+                master_key, master_key_id, _ = yield self._get_e2e_cross_signing_verify_key(
+                    target_user, "master", user_id
+                )
+
+                # make sure that the target user's master key is the one that
+                # was signed (and no others)
+                device_id = master_key_id.split(":", 1)[1]
+                if device_id not in devicemap:
+                    logger.debug(
+                        "upload signature: could not find signature for device %s",
+                        device_id,
+                    )
+                    # set device to None so that the failure gets
+                    # marked on all the signatures
+                    device_id = None
+                    raise NotFoundError("Unknown device")
+                key = devicemap[device_id]
+                other_devices = [k for k in devicemap.keys() if k != device_id]
+                if other_devices:
+                    # other devices were signed -- mark those as failures
+                    logger.debug("upload signature: too many devices specified")
+                    failure = _exception_to_failure(NotFoundError("Unknown device"))
+                    failures[target_user] = {
+                        device: failure for device in other_devices
+                    }
+
+                if user_signing_key_id in master_key.get("signatures", {}).get(
+                    user_id, {}
+                ):
+                    # we already have the signature, so we can skip it
+                    continue
+
+                _check_device_signature(
+                    user_id, user_signing_verify_key, key, master_key
+                )
+
+                signature = key["signatures"][user_id][user_signing_key_id]
+                signature_list.append(
+                    SignatureListItem(
+                        user_signing_key_id, target_user, device_id, signature
+                    )
+                )
+            except SynapseError as e:
+                failure = _exception_to_failure(e)
+                if device_id is None:
+                    failures[target_user] = {
+                        device_id: failure for device_id in devicemap.keys()
+                    }
+                else:
+                    failures.setdefault(target_user, {})[device_id] = failure
+
+        return signature_list, failures
+
+    @defer.inlineCallbacks
+    def _get_e2e_cross_signing_verify_key(self, user_id, key_type, from_user_id=None):
+        """Fetch the cross-signing public key from storage and interpret it.
+
+        Args:
+            user_id (str): the user whose key should be fetched
+            key_type (str): the type of key to fetch
+            from_user_id (str): the user that we are fetching the keys for.
+                This affects what signatures are fetched.
+
+        Returns:
+            dict, str, VerifyKey: the raw key data, the key ID, and the
+                signedjson verify key
+
+        Raises:
+            NotFoundError: if the key is not found
+        """
+        key = yield self.store.get_e2e_cross_signing_key(
+            user_id, key_type, from_user_id
+        )
+        if key is None:
+            logger.debug("no %s key found for %s", key_type, user_id)
+            raise NotFoundError("No %s key found for %s" % (key_type, user_id))
+        key_id, verify_key = get_verify_key_from_cross_signing_key(key)
+        return key, key_id, verify_key
+
 
 def _check_cross_signing_key(key, user_id, key_type, signing_key=None):
     """Check a cross-signing key uploaded by a user.  Performs some basic sanity
@@ -630,7 +966,49 @@ def _check_cross_signing_key(key, user_id, key_type, signing_key=None):
             )
 
 
+def _check_device_signature(user_id, verify_key, signed_device, stored_device):
+    """Check that a signature on a device or cross-signing key is correct and
+    matches the copy of the device/key that we have stored.  Throws an
+    exception if an error is detected.
+
+    Args:
+        user_id (str): the user ID whose signature is being checked
+        verify_key (VerifyKey): the key to verify the device with
+        signed_device (dict): the uploaded signed device data
+        stored_device (dict): our previously stored copy of the device
+
+    Raises:
+        SynapseError: if the signature was invalid or the sent device is not the
+            same as the stored device
+
+    """
+
+    # make sure that the device submitted matches what we have stored
+    stripped_signed_device = {
+        k: v for k, v in signed_device.items() if k not in ["signatures", "unsigned"]
+    }
+    stripped_stored_device = {
+        k: v for k, v in stored_device.items() if k not in ["signatures", "unsigned"]
+    }
+    if stripped_signed_device != stripped_stored_device:
+        logger.debug(
+            "upload signatures: key does not match %s vs %s",
+            signed_device,
+            stored_device,
+        )
+        raise SynapseError(400, "Key does not match")
+
+    try:
+        verify_signed_json(signed_device, user_id, verify_key)
+    except SignatureVerifyException:
+        logger.debug("invalid signature on key")
+        raise SynapseError(400, "Invalid signature", Codes.INVALID_SIGNATURE)
+
+
 def _exception_to_failure(e):
+    if isinstance(e, SynapseError):
+        return {"status": e.code, "errcode": e.errcode, "message": str(e)}
+
     if isinstance(e, CodeMessageException):
         return {"status": e.code, "message": str(e)}
 
@@ -658,3 +1036,14 @@ def _one_time_keys_match(old_key_json, new_key):
     new_key_copy.pop("signatures", None)
 
     return old_key == new_key_copy
+
+
+@attr.s
+class SignatureListItem:
+    """An item in the signature list as used by upload_signatures_for_device_keys.
+    """
+
+    signing_key_id = attr.ib()
+    target_user_id = attr.ib()
+    target_device_id = attr.ib()
+    signature = attr.ib()
diff --git a/synapse/rest/client/v2_alpha/keys.py b/synapse/rest/client/v2_alpha/keys.py
index 151a70d449..341567ae21 100644
--- a/synapse/rest/client/v2_alpha/keys.py
+++ b/synapse/rest/client/v2_alpha/keys.py
@@ -274,7 +274,57 @@ class SigningKeyUploadServlet(RestServlet):
         )
 
         result = yield self.e2e_keys_handler.upload_signing_keys_for_user(user_id, body)
-        return (200, result)
+        return 200, result
+
+
+class SignaturesUploadServlet(RestServlet):
+    """
+    POST /keys/signatures/upload HTTP/1.1
+    Content-Type: application/json
+
+    {
+      "@alice:example.com": {
+        "<device_id>": {
+          "user_id": "<user_id>",
+          "device_id": "<device_id>",
+          "algorithms": [
+            "m.olm.curve25519-aes-sha256",
+            "m.megolm.v1.aes-sha"
+          ],
+          "keys": {
+            "<algorithm>:<device_id>": "<key_base64>",
+          },
+          "signatures": {
+            "<signing_user_id>": {
+              "<algorithm>:<signing_key_base64>": "<signature_base64>>"
+            }
+          }
+        }
+      }
+    }
+    """
+
+    PATTERNS = client_patterns("/keys/signatures/upload$")
+
+    def __init__(self, hs):
+        """
+        Args:
+            hs (synapse.server.HomeServer): server
+        """
+        super(SignaturesUploadServlet, self).__init__()
+        self.auth = hs.get_auth()
+        self.e2e_keys_handler = hs.get_e2e_keys_handler()
+
+    @defer.inlineCallbacks
+    def on_POST(self, request):
+        requester = yield self.auth.get_user_by_req(request, allow_guest=True)
+        user_id = requester.user.to_string()
+        body = parse_json_object_from_request(request)
+
+        result = yield self.e2e_keys_handler.upload_signatures_for_device_keys(
+            user_id, body
+        )
+        return 200, result
 
 
 def register_servlets(hs, http_server):
@@ -283,3 +333,4 @@ def register_servlets(hs, http_server):
     KeyChangesServlet(hs).register(http_server)
     OneTimeKeyServlet(hs).register(http_server)
     SigningKeyUploadServlet(hs).register(http_server)
+    SignaturesUploadServlet(hs).register(http_server)
diff --git a/synapse/storage/end_to_end_keys.py b/synapse/storage/end_to_end_keys.py
index ebcd1c9ea2..2effe08592 100644
--- a/synapse/storage/end_to_end_keys.py
+++ b/synapse/storage/end_to_end_keys.py
@@ -68,6 +68,11 @@ class EndToEndKeyWorkerStore(SQLBaseStore):
                 display_name = device_info["device_display_name"]
                 if display_name is not None:
                     r["unsigned"]["device_display_name"] = display_name
+                if "signatures" in device_info:
+                    for sig_user_id, sigs in device_info["signatures"].items():
+                        r.setdefault("signatures", {}).setdefault(
+                            sig_user_id, {}
+                        ).update(sigs)
                 rv[user_id][device_id] = r
 
         return rv
@@ -81,6 +86,8 @@ class EndToEndKeyWorkerStore(SQLBaseStore):
 
         query_clauses = []
         query_params = []
+        signature_query_clauses = []
+        signature_query_params = []
 
         if include_all_devices is False:
             include_deleted_devices = False
@@ -91,12 +98,20 @@ class EndToEndKeyWorkerStore(SQLBaseStore):
         for (user_id, device_id) in query_list:
             query_clause = "user_id = ?"
             query_params.append(user_id)
+            signature_query_clause = "target_user_id = ?"
+            signature_query_params.append(user_id)
 
             if device_id is not None:
                 query_clause += " AND device_id = ?"
                 query_params.append(device_id)
+                signature_query_clause += " AND target_device_id = ?"
+                signature_query_params.append(device_id)
+
+            signature_query_clause += " AND user_id = ?"
+            signature_query_params.append(user_id)
 
             query_clauses.append(query_clause)
+            signature_query_clauses.append(signature_query_clause)
 
         sql = (
             "SELECT user_id, device_id, "
@@ -123,6 +138,22 @@ class EndToEndKeyWorkerStore(SQLBaseStore):
             for user_id, device_id in deleted_devices:
                 result.setdefault(user_id, {})[device_id] = None
 
+        # get signatures on the device
+        signature_sql = (
+            "SELECT * " "  FROM e2e_cross_signing_signatures " " WHERE %s"
+        ) % (" OR ".join("(" + q + ")" for q in signature_query_clauses))
+
+        txn.execute(signature_sql, signature_query_params)
+        rows = self.cursor_to_dict(txn)
+
+        for row in rows:
+            target_user_id = row["target_user_id"]
+            target_device_id = row["target_device_id"]
+            if target_user_id in result and target_device_id in result[target_user_id]:
+                result[target_user_id][target_device_id].setdefault(
+                    "signatures", {}
+                ).setdefault(row["user_id"], {})[row["key_id"]] = row["signature"]
+
         log_kv(result)
         return result
 
@@ -468,24 +499,19 @@ class EndToEndKeyStore(EndToEndKeyWorkerStore, SQLBaseStore):
 
         Args:
             user_id (str): the user who made the signatures
-            signatures (iterable[(str, str, str, str)]): signatures to add - each
-                a tuple of (key_id, target_user_id, target_device_id, signature),
-                where key_id is the ID of the key (including the signature
-                algorithm) that made the signature, target_user_id and
-                target_device_id indicate the device being signed, and signature
-                is the signature of the device
+            signatures (iterable[SignatureListItem]): signatures to add
         """
         return self._simple_insert_many(
             "e2e_cross_signing_signatures",
             [
                 {
                     "user_id": user_id,
-                    "key_id": key_id,
-                    "target_user_id": target_user_id,
-                    "target_device_id": target_device_id,
-                    "signature": signature,
+                    "key_id": item.signing_key_id,
+                    "target_user_id": item.target_user_id,
+                    "target_device_id": item.target_device_id,
+                    "signature": item.signature,
                 }
-                for (key_id, target_user_id, target_device_id, signature) in signatures
+                for item in signatures
             ],
             "add_e2e_signing_key",
         )
diff --git a/tests/handlers/test_e2e_keys.py b/tests/handlers/test_e2e_keys.py
index a62c52eefa..854eb6c024 100644
--- a/tests/handlers/test_e2e_keys.py
+++ b/tests/handlers/test_e2e_keys.py
@@ -17,9 +17,11 @@
 
 import mock
 
+import signedjson.key as key
+import signedjson.sign as sign
+
 from twisted.internet import defer
 
-import synapse.api.errors
 import synapse.handlers.e2e_keys
 import synapse.storage
 from synapse.api import errors
@@ -182,6 +184,96 @@ class E2eKeysHandlerTestCase(unittest.TestCase):
         self.assertDictEqual(devices["master_keys"], {local_user: keys2["master_key"]})
 
     @defer.inlineCallbacks
+    def test_reupload_signatures(self):
+        """re-uploading a signature should not fail"""
+        local_user = "@boris:" + self.hs.hostname
+        keys1 = {
+            "master_key": {
+                # private key: HvQBbU+hc2Zr+JP1sE0XwBe1pfZZEYtJNPJLZJtS+F8
+                "user_id": local_user,
+                "usage": ["master"],
+                "keys": {
+                    "ed25519:EmkqvokUn8p+vQAGZitOk4PWjp7Ukp3txV2TbMPEiBQ": "EmkqvokUn8p+vQAGZitOk4PWjp7Ukp3txV2TbMPEiBQ"
+                },
+            },
+            "self_signing_key": {
+                # private key: 2lonYOM6xYKdEsO+6KrC766xBcHnYnim1x/4LFGF8B0
+                "user_id": local_user,
+                "usage": ["self_signing"],
+                "keys": {
+                    "ed25519:nqOvzeuGWT/sRx3h7+MHoInYj3Uk2LD/unI9kDYcHwk": "nqOvzeuGWT/sRx3h7+MHoInYj3Uk2LD/unI9kDYcHwk"
+                },
+            },
+        }
+        master_signing_key = key.decode_signing_key_base64(
+            "ed25519",
+            "EmkqvokUn8p+vQAGZitOk4PWjp7Ukp3txV2TbMPEiBQ",
+            "HvQBbU+hc2Zr+JP1sE0XwBe1pfZZEYtJNPJLZJtS+F8",
+        )
+        sign.sign_json(keys1["self_signing_key"], local_user, master_signing_key)
+        signing_key = key.decode_signing_key_base64(
+            "ed25519",
+            "nqOvzeuGWT/sRx3h7+MHoInYj3Uk2LD/unI9kDYcHwk",
+            "2lonYOM6xYKdEsO+6KrC766xBcHnYnim1x/4LFGF8B0",
+        )
+        yield self.handler.upload_signing_keys_for_user(local_user, keys1)
+
+        # upload two device keys, which will be signed later by the self-signing key
+        device_key_1 = {
+            "user_id": local_user,
+            "device_id": "abc",
+            "algorithms": ["m.olm.curve25519-aes-sha256", "m.megolm.v1.aes-sha"],
+            "keys": {
+                "ed25519:abc": "base64+ed25519+key",
+                "curve25519:abc": "base64+curve25519+key",
+            },
+            "signatures": {local_user: {"ed25519:abc": "base64+signature"}},
+        }
+        device_key_2 = {
+            "user_id": local_user,
+            "device_id": "def",
+            "algorithms": ["m.olm.curve25519-aes-sha256", "m.megolm.v1.aes-sha"],
+            "keys": {
+                "ed25519:def": "base64+ed25519+key",
+                "curve25519:def": "base64+curve25519+key",
+            },
+            "signatures": {local_user: {"ed25519:def": "base64+signature"}},
+        }
+
+        yield self.handler.upload_keys_for_user(
+            local_user, "abc", {"device_keys": device_key_1}
+        )
+        yield self.handler.upload_keys_for_user(
+            local_user, "def", {"device_keys": device_key_2}
+        )
+
+        # sign the first device key and upload it
+        del device_key_1["signatures"]
+        sign.sign_json(device_key_1, local_user, signing_key)
+        yield self.handler.upload_signatures_for_device_keys(
+            local_user, {local_user: {"abc": device_key_1}}
+        )
+
+        # sign the second device key and upload both device keys.  The server
+        # should ignore the first device key since it already has a valid
+        # signature for it
+        del device_key_2["signatures"]
+        sign.sign_json(device_key_2, local_user, signing_key)
+        yield self.handler.upload_signatures_for_device_keys(
+            local_user, {local_user: {"abc": device_key_1, "def": device_key_2}}
+        )
+
+        device_key_1["signatures"][local_user]["ed25519:abc"] = "base64+signature"
+        device_key_2["signatures"][local_user]["ed25519:def"] = "base64+signature"
+        devices = yield self.handler.query_devices(
+            {"device_keys": {local_user: []}}, 0, local_user
+        )
+        del devices["device_keys"][local_user]["abc"]["unsigned"]
+        del devices["device_keys"][local_user]["def"]["unsigned"]
+        self.assertDictEqual(devices["device_keys"][local_user]["abc"], device_key_1)
+        self.assertDictEqual(devices["device_keys"][local_user]["def"], device_key_2)
+
+    @defer.inlineCallbacks
     def test_self_signing_key_doesnt_show_up_as_device(self):
         """signing keys should be hidden when fetching a user's devices"""
         local_user = "@boris:" + self.hs.hostname
@@ -210,3 +302,204 @@ class E2eKeysHandlerTestCase(unittest.TestCase):
 
         res = yield self.handler.query_local_devices({local_user: None})
         self.assertDictEqual(res, {local_user: {}})
+
+    @defer.inlineCallbacks
+    def test_upload_signatures(self):
+        """should check signatures that are uploaded"""
+        # set up a user with cross-signing keys and a device.  This user will
+        # try uploading signatures
+        local_user = "@boris:" + self.hs.hostname
+        device_id = "xyz"
+        # private key: OMkooTr76ega06xNvXIGPbgvvxAOzmQncN8VObS7aBA
+        device_pubkey = "NnHhnqiMFQkq969szYkooLaBAXW244ZOxgukCvm2ZeY"
+        device_key = {
+            "user_id": local_user,
+            "device_id": device_id,
+            "algorithms": ["m.olm.curve25519-aes-sha256", "m.megolm.v1.aes-sha"],
+            "keys": {"curve25519:xyz": "curve25519+key", "ed25519:xyz": device_pubkey},
+            "signatures": {local_user: {"ed25519:xyz": "something"}},
+        }
+        device_signing_key = key.decode_signing_key_base64(
+            "ed25519", "xyz", "OMkooTr76ega06xNvXIGPbgvvxAOzmQncN8VObS7aBA"
+        )
+
+        yield self.handler.upload_keys_for_user(
+            local_user, device_id, {"device_keys": device_key}
+        )
+
+        # private key: 2lonYOM6xYKdEsO+6KrC766xBcHnYnim1x/4LFGF8B0
+        master_pubkey = "nqOvzeuGWT/sRx3h7+MHoInYj3Uk2LD/unI9kDYcHwk"
+        master_key = {
+            "user_id": local_user,
+            "usage": ["master"],
+            "keys": {"ed25519:" + master_pubkey: master_pubkey},
+        }
+        master_signing_key = key.decode_signing_key_base64(
+            "ed25519", master_pubkey, "2lonYOM6xYKdEsO+6KrC766xBcHnYnim1x/4LFGF8B0"
+        )
+        usersigning_pubkey = "Hq6gL+utB4ET+UvD5ci0kgAwsX6qP/zvf8v6OInU5iw"
+        usersigning_key = {
+            # private key: 4TL4AjRYwDVwD3pqQzcor+ez/euOB1/q78aTJ+czDNs
+            "user_id": local_user,
+            "usage": ["user_signing"],
+            "keys": {"ed25519:" + usersigning_pubkey: usersigning_pubkey},
+        }
+        usersigning_signing_key = key.decode_signing_key_base64(
+            "ed25519", usersigning_pubkey, "4TL4AjRYwDVwD3pqQzcor+ez/euOB1/q78aTJ+czDNs"
+        )
+        sign.sign_json(usersigning_key, local_user, master_signing_key)
+        # private key: HvQBbU+hc2Zr+JP1sE0XwBe1pfZZEYtJNPJLZJtS+F8
+        selfsigning_pubkey = "EmkqvokUn8p+vQAGZitOk4PWjp7Ukp3txV2TbMPEiBQ"
+        selfsigning_key = {
+            "user_id": local_user,
+            "usage": ["self_signing"],
+            "keys": {"ed25519:" + selfsigning_pubkey: selfsigning_pubkey},
+        }
+        selfsigning_signing_key = key.decode_signing_key_base64(
+            "ed25519", selfsigning_pubkey, "HvQBbU+hc2Zr+JP1sE0XwBe1pfZZEYtJNPJLZJtS+F8"
+        )
+        sign.sign_json(selfsigning_key, local_user, master_signing_key)
+        cross_signing_keys = {
+            "master_key": master_key,
+            "user_signing_key": usersigning_key,
+            "self_signing_key": selfsigning_key,
+        }
+        yield self.handler.upload_signing_keys_for_user(local_user, cross_signing_keys)
+
+        # set up another user with a master key.  This user will be signed by
+        # the first user
+        other_user = "@otherboris:" + self.hs.hostname
+        other_master_pubkey = "fHZ3NPiKxoLQm5OoZbKa99SYxprOjNs4TwJUKP+twCM"
+        other_master_key = {
+            # private key: oyw2ZUx0O4GifbfFYM0nQvj9CL0b8B7cyN4FprtK8OI
+            "user_id": other_user,
+            "usage": ["master"],
+            "keys": {"ed25519:" + other_master_pubkey: other_master_pubkey},
+        }
+        yield self.handler.upload_signing_keys_for_user(
+            other_user, {"master_key": other_master_key}
+        )
+
+        # test various signature failures (see below)
+        ret = yield self.handler.upload_signatures_for_device_keys(
+            local_user,
+            {
+                local_user: {
+                    # fails because the signature is invalid
+                    # should fail with INVALID_SIGNATURE
+                    device_id: {
+                        "user_id": local_user,
+                        "device_id": device_id,
+                        "algorithms": [
+                            "m.olm.curve25519-aes-sha256",
+                            "m.megolm.v1.aes-sha",
+                        ],
+                        "keys": {
+                            "curve25519:xyz": "curve25519+key",
+                            # private key: OMkooTr76ega06xNvXIGPbgvvxAOzmQncN8VObS7aBA
+                            "ed25519:xyz": device_pubkey,
+                        },
+                        "signatures": {
+                            local_user: {"ed25519:" + selfsigning_pubkey: "something"}
+                        },
+                    },
+                    # fails because device is unknown
+                    # should fail with NOT_FOUND
+                    "unknown": {
+                        "user_id": local_user,
+                        "device_id": "unknown",
+                        "signatures": {
+                            local_user: {"ed25519:" + selfsigning_pubkey: "something"}
+                        },
+                    },
+                    # fails because the signature is invalid
+                    # should fail with INVALID_SIGNATURE
+                    master_pubkey: {
+                        "user_id": local_user,
+                        "usage": ["master"],
+                        "keys": {"ed25519:" + master_pubkey: master_pubkey},
+                        "signatures": {
+                            local_user: {"ed25519:" + device_pubkey: "something"}
+                        },
+                    },
+                },
+                other_user: {
+                    # fails because the device is not the user's master-signing key
+                    # should fail with NOT_FOUND
+                    "unknown": {
+                        "user_id": other_user,
+                        "device_id": "unknown",
+                        "signatures": {
+                            local_user: {"ed25519:" + usersigning_pubkey: "something"}
+                        },
+                    },
+                    other_master_pubkey: {
+                        # fails because the key doesn't match what the server has
+                        # should fail with UNKNOWN
+                        "user_id": other_user,
+                        "usage": ["master"],
+                        "keys": {"ed25519:" + other_master_pubkey: other_master_pubkey},
+                        "something": "random",
+                        "signatures": {
+                            local_user: {"ed25519:" + usersigning_pubkey: "something"}
+                        },
+                    },
+                },
+            },
+        )
+
+        user_failures = ret["failures"][local_user]
+        self.assertEqual(
+            user_failures[device_id]["errcode"], errors.Codes.INVALID_SIGNATURE
+        )
+        self.assertEqual(
+            user_failures[master_pubkey]["errcode"], errors.Codes.INVALID_SIGNATURE
+        )
+        self.assertEqual(user_failures["unknown"]["errcode"], errors.Codes.NOT_FOUND)
+
+        other_user_failures = ret["failures"][other_user]
+        self.assertEqual(
+            other_user_failures["unknown"]["errcode"], errors.Codes.NOT_FOUND
+        )
+        self.assertEqual(
+            other_user_failures[other_master_pubkey]["errcode"], errors.Codes.UNKNOWN
+        )
+
+        # test successful signatures
+        del device_key["signatures"]
+        sign.sign_json(device_key, local_user, selfsigning_signing_key)
+        sign.sign_json(master_key, local_user, device_signing_key)
+        sign.sign_json(other_master_key, local_user, usersigning_signing_key)
+        ret = yield self.handler.upload_signatures_for_device_keys(
+            local_user,
+            {
+                local_user: {device_id: device_key, master_pubkey: master_key},
+                other_user: {other_master_pubkey: other_master_key},
+            },
+        )
+
+        self.assertEqual(ret["failures"], {})
+
+        # fetch the signed keys/devices and make sure that the signatures are there
+        ret = yield self.handler.query_devices(
+            {"device_keys": {local_user: [], other_user: []}}, 0, local_user
+        )
+
+        self.assertEqual(
+            ret["device_keys"][local_user]["xyz"]["signatures"][local_user][
+                "ed25519:" + selfsigning_pubkey
+            ],
+            device_key["signatures"][local_user]["ed25519:" + selfsigning_pubkey],
+        )
+        self.assertEqual(
+            ret["master_keys"][local_user]["signatures"][local_user][
+                "ed25519:" + device_id
+            ],
+            master_key["signatures"][local_user]["ed25519:" + device_id],
+        )
+        self.assertEqual(
+            ret["master_keys"][other_user]["signatures"][local_user][
+                "ed25519:" + usersigning_pubkey
+            ],
+            other_master_key["signatures"][local_user]["ed25519:" + usersigning_pubkey],
+        )