diff --git a/lib/client.js b/lib/client.js
index <HASH>..<HASH> 100644
--- a/lib/client.js
+++ b/lib/client.js
@@ -349,12 +349,12 @@ function _uploadDeviceKeys(client) {
         device_id: deviceId,
         keys: client._deviceKeys,
         user_id: userId,
-        signatures: {},
     };
 
+    var sig = client._olmDevice.sign(anotherjson.stringify(deviceKeys));
+    deviceKeys.signatures = {};
     deviceKeys.signatures[userId] = {};
-    deviceKeys.signatures[userId]["ed25519:" + deviceId] =
-        client._olmDevice.sign(anotherjson.stringify(deviceKeys));
+    deviceKeys.signatures[userId]["ed25519:" + deviceId] = sig;
 
     return client.uploadKeysRequest({
         device_keys: deviceKeys,
Fix device key signing

Calculate the signature *before* we add the `signatures` key.