--- a/toolkit/components/extensions/ExtensionStorageSync.jsm
+++ b/toolkit/components/extensions/ExtensionStorageSync.jsm
@@ -21,16 +21,17 @@ Cu.import("resource://gre/modules/AppCon
 const KINTO_PROD_SERVER_URL = "https://webextensions.settings.services.mozilla.com/v1";
 const KINTO_DEFAULT_SERVER_URL = KINTO_PROD_SERVER_URL;
 
 const STORAGE_SYNC_ENABLED_PREF = "webextensions.storage.sync.enabled";
 const STORAGE_SYNC_SERVER_URL_PREF = "webextensions.storage.sync.serverURL";
 const STORAGE_SYNC_SCOPE = "sync:addon_storage";
 const STORAGE_SYNC_CRYPTO_COLLECTION_NAME = "storage-sync-crypto";
 const STORAGE_SYNC_CRYPTO_KEYRING_RECORD_ID = "keys";
+const STORAGE_SYNC_CRYPTO_SALT_LENGTH_BYTES = 32;
 const FXA_OAUTH_OPTIONS = {
   scope: STORAGE_SYNC_SCOPE,
 };
 // Default is 5sec, which seems a bit aggressive on the open internet
 const KINTO_REQUEST_TIMEOUT = 30000;
 
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 const {
@@ -190,21 +191,41 @@ if (AppConstants.platform != "android") 
       const {kinto} = yield storageSyncInit;
       return kinto.collection(STORAGE_SYNC_CRYPTO_COLLECTION_NAME, {
         idSchema: cryptoCollectionIdSchema,
         remoteTransformers: [new KeyRingEncryptionRemoteTransformer()],
       });
     }),
 
     /**
+     * Generate a new salt for use in hashing extension and record
+     * IDs.
+     *
+     * @returns {string} A base64-encoded string of the salt
+     */
+    getNewSalt() {
+      return btoa(CryptoUtils.generateRandomBytes(STORAGE_SYNC_CRYPTO_SALT_LENGTH_BYTES));
+    },
+
+    /**
      * Retrieve the keyring record from the crypto collection.
      *
      * You can use this if you want to check metadata on the keyring
      * record rather than use the keyring itself.
      *
+     * The keyring record, if present, should have the structure:
+     *
+     * - kbHash: a hash of the user's kB. When this changes, we will
+     *   try to sync the collection.
+     * - uuid: a record identifier. This will only change when we wipe
+     *   the collection (due to kB getting reset).
+     * - keys: a "WBO" form of a CollectionKeyManager.
+     * - salts: a normal JS Object with keys being collection IDs and
+     *   values being base64-encoded salts to use when hashing IDs
+     *   for that collection.
      * @returns {Promise<Object>}
      */
     getKeyRingRecord: Task.async(function* () {
       const collection = yield this.getCollection();
       const cryptoKeyRecord = yield collection.getAny(STORAGE_SYNC_CRYPTO_KEYRING_RECORD_ID);
 
       let data = cryptoKeyRecord.data;
       if (!data) {
@@ -213,16 +234,21 @@ if (AppConstants.platform != "android") 
         // reupload everything.
         const uuidgen = Cc["@mozilla.org/uuid-generator;1"].getService(Ci.nsIUUIDGenerator);
         const uuid = uuidgen.generateUUID().toString();
         data = {uuid};
       }
       return data;
     }),
 
+    getSalts: Task.async(function* () {
+      const cryptoKeyRecord = yield this.getKeyRingRecord();
+      return cryptoKeyRecord && cryptoKeyRecord.salts;
+    }),
+
     /**
      * Retrieve the actual keyring from the crypto collection.
      *
      * @returns {Promise<CollectionKeyManager>}
      */
     getKeyRing: Task.async(function* () {
       const cryptoKeyRecord = yield this.getKeyRingRecord();
       const collectionKeys = new CollectionKeyManager();
@@ -370,17 +396,17 @@ function extensionIdToCollectionId(user,
 }
 
 /**
  * Verify that we were built on not-Android. Call this as a sanity
  * check before using cryptoCollection.
  */
 function ensureCryptoCollection() {
   if (!cryptoCollection) {
-    throw new Error("Call to ensureKeysFor, but no sync code; are you on Android?");
+    throw new Error("Call to ensureCanSync, but no sync code; are you on Android?");
   }
 }
 
 // FIXME: This is kind of ugly. Probably we should have
 // ExtensionStorageSync not be a singleton, but a constructed object,
 // and this should be a constructor argument.
 let _fxaService = null;
 if (AppConstants.platform != "android") {
@@ -394,17 +420,17 @@ this.ExtensionStorageSync = {
   syncAll: Task.async(function* () {
     const extensions = extensionContexts.keys();
     const extIds = Array.from(extensions, extension => extension.id);
     log.debug(`Syncing extension settings for ${JSON.stringify(extIds)}`);
     if (extIds.length == 0) {
       // No extensions to sync. Get out.
       return;
     }
-    yield this.ensureKeysFor(extIds);
+    yield this.ensureCanSync(extIds);
     yield this.checkSyncKeyRing();
     const promises = Array.from(extensionContexts.keys(), extension => {
       return openCollection(extension).then(coll => {
         return this.sync(extension, coll);
       });
     });
     yield Promise.all(promises);
   }),
@@ -519,49 +545,88 @@ this.ExtensionStorageSync = {
       const kintoHttp = new KintoHttpClient(prefStorageSyncServerURL, {
         headers: headers,
         timeout: KINTO_REQUEST_TIMEOUT,
       });
       return yield kintoHttp.deleteBucket("default");
     });
   }),
 
+  ensureSaltsFor: Task.async(function* (keysRecord, extIds) {
+    const newSalts = Object.assign({}, keysRecord.salts);
+    for (let collectionId of extIds) {
+      if (newSalts[collectionId]) {
+        continue;
+      }
+
+      newSalts[collectionId] = cryptoCollection.getNewSalt();
+    }
+
+    return newSalts;
+  }),
+
+  /**
+   * Check whether the keys record (provided) already has salts for
+   * all the extensions given in extIds.
+   *
+   * @param {Object} keysRecord A previously-retrieved keys record.
+   * @param {Array<string>} extIds The IDs of the extensions which
+   *                need salts.
+   * @returns {boolean}
+   */
+  hasSaltsFor(keysRecord, extIds) {
+    if (!keysRecord.salts) {
+      return false;
+    }
+
+    for (let collectionId of extIds) {
+      if (!keysRecord.salts[collectionId]) {
+        return false;
+      }
+    }
+
+    return true;
+  },
+
   /**
    * Recursive promise that terminates when our local collectionKeys,
    * as well as that on the server, have keys for all the extensions
    * in extIds.
    *
    * @param {Array<string>} extIds
    *                        The IDs of the extensions which need keys.
    * @returns {Promise<CollectionKeyManager>}
    */
-  ensureKeysFor: Task.async(function* (extIds) {
+  ensureCanSync: Task.async(function* (extIds) {
     ensureCryptoCollection();
 
+    const keysRecord = yield cryptoCollection.getKeyRingRecord();
     const collectionKeys = yield cryptoCollection.getKeyRing();
-    if (collectionKeys.hasKeysFor(extIds)) {
+    if (collectionKeys.hasKeysFor(extIds) && this.hasSaltsFor(keysRecord, extIds)) {
       return collectionKeys;
     }
 
     const kbHash = yield this.getKBHash();
     const newKeys = yield collectionKeys.ensureKeysFor(extIds);
+    const newSalts = yield this.ensureSaltsFor(keysRecord, extIds);
     const newRecord = {
       id: STORAGE_SYNC_CRYPTO_KEYRING_RECORD_ID,
       keys: newKeys.asWBO().cleartext,
+      salts: newSalts,
       uuid: collectionKeys.uuid,
       // Add a field for the current kB hash.
       kbHash: kbHash,
     };
     yield cryptoCollection.upsert(newRecord);
     const result = yield this._syncKeyRing(newRecord);
     if (result.resolved.length != 0) {
       // We had a conflict which was automatically resolved. We now
       // have a new keyring which might have keys for the
       // collections. Recurse.
-      return yield this.ensureKeysFor(extIds);
+      return yield this.ensureCanSync(extIds);
     }
 
     // No conflicts. We're good.
     return newKeys;
   }),
 
   /**
    * Get the current user's hashed kB.

--- a/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
+++ b/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
@@ -2,16 +2,17 @@
  * http://creativecommons.org/publicdomain/zero/1.0/ */
 
 "use strict";
 
 do_get_profile();   // so we can use FxAccounts
 
 Cu.import("resource://testing-common/httpd.js");
 Cu.import("resource://services-common/utils.js");
+Cu.import("resource://services-crypto/utils.js");
 Cu.import("resource://gre/modules/ExtensionStorageSync.jsm");
 const {
   CollectionKeyEncryptionRemoteTransformer,
   cryptoCollection,
   idToKey,
   extensionIdToCollectionId,
   keyToId,
 } = Cu.import("resource://gre/modules/ExtensionStorageSync.jsm", {});
@@ -257,21 +258,22 @@ class KintoServer {
           last_modified: 1475161309026,
           id: "b09f1618-d789-302d-696e-74ec53ee18a8", // FIXME
         },
       }));
     });
   }
 
   // Utility function to install a keyring at the start of a test.
-  installKeyRing(keysData, etag, {conflict = false} = {}) {
+  installKeyRing(keysData, salts, etag, {conflict = false} = {}) {
     this.installCollection("storage-sync-crypto");
     const keysRecord = {
       "id": "keys",
       "keys": keysData,
+      "salts": salts,
       "last_modified": etag,
     };
     this.etag = etag;
     const methodName = conflict ? "encryptAndAddRecordWithConflict" : "encryptAndAddRecord";
     this[methodName](new KeyRingEncryptionRemoteTransformer(),
                      "storage-sync-crypto", keysRecord);
   }
 
@@ -409,16 +411,17 @@ function assertPostedUpdatedRecord(post,
 // Assert that this post was an encrypted keyring, and produce the
 // decrypted body. Sanity check the body while we're here.
 const assertPostedEncryptedKeys = Task.async(function* (post) {
   equal(post.path, collectionRecordsPath("storage-sync-crypto") + "/keys");
 
   let body = yield new KeyRingEncryptionRemoteTransformer().decode(post.body.data);
   ok(body.keys, `keys object should be present in decoded body`);
   ok(body.keys.default, `keys object should have a default key`);
+  ok(body.salts, `salts object should be present in decoded body`);
   return body;
 });
 
 // assertEqual, but for keyring[extensionId] == key.
 function assertKeyRingKey(keyRing, extensionId, expectedKey, message) {
   if (!message) {
     message = `expected keyring's key for ${extensionId} to match ${expectedKey.keyPairB64}`;
   }
@@ -484,127 +487,183 @@ add_task(function* test_extension_id_to_
   equal(extensionIdToCollectionId(loggedInUser, extensionId),
         "abf4e257dad0c89027f8f25bd196d4d69c100df375655a0c49f4cea7b791ea7d");
   equal(extensionIdToCollectionId(loggedInUser, extensionId),
         extensionIdToCollectionId(newKBUser, extensionId));
   equal(extensionIdToCollectionId(loggedInUser, extensionId2),
         "6584b0153336fb274912b31a3225c15a92b703cdc3adfe1917c1aa43122a52b8");
 });
 
-add_task(function* ensureKeysFor_posts_new_keys() {
+add_task(function* ensureCanSync_posts_new_keys() {
   const extensionId = uuid();
   yield* withContextAndServer(function* (context, server) {
     yield* withSignedInUser(loggedInUser, function* () {
       server.installCollection("storage-sync-crypto");
       server.etag = 1000;
 
-      let newKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId]);
+      let newKeys = yield ExtensionStorageSync.ensureCanSync([extensionId]);
       ok(newKeys.hasKeysFor([extensionId]), `key isn't present for ${extensionId}`);
 
       let posts = server.getPosts();
       equal(posts.length, 1);
       const post = posts[0];
       assertPostedNewRecord(post);
       const body = yield assertPostedEncryptedKeys(post);
+      const oldSalt = body.salts[extensionId];
       ok(body.keys.collections[extensionId], `keys object should have a key for ${extensionId}`);
+      ok(oldSalt, `salts object should have a salt for ${extensionId}`);
 
       // Try adding another key to make sure that the first post was
       // OK, even on a new profile.
       yield cryptoCollection._clear();
       server.clearPosts();
       // Restore the first posted keyring, but add a last_modified date
       const firstPostedKeyring = Object.assign({}, post.body.data, {last_modified: server.etag});
       server.addRecordInPast("storage-sync-crypto", firstPostedKeyring);
       const extensionId2 = uuid();
-      newKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId2]);
+      newKeys = yield ExtensionStorageSync.ensureCanSync([extensionId2]);
       ok(newKeys.hasKeysFor([extensionId]), `didn't forget key for ${extensionId}`);
       ok(newKeys.hasKeysFor([extensionId2]), `new key generated for ${extensionId2}`);
 
       posts = server.getPosts();
       equal(posts.length, 1);
       const newPost = posts[posts.length - 1];
       const newBody = yield assertPostedEncryptedKeys(newPost);
       ok(newBody.keys.collections[extensionId], `keys object should have a key for ${extensionId}`);
       ok(newBody.keys.collections[extensionId2], `keys object should have a key for ${extensionId2}`);
+      ok(newBody.salts[extensionId], `salts object should have a key for ${extensionId}`);
+      ok(newBody.salts[extensionId2], `salts object should have a key for ${extensionId2}`);
+      equal(oldSalt, newBody.salts[extensionId], `old salt should be preserved in post`);
     });
   });
 });
 
-add_task(function* ensureKeysFor_pulls_key() {
-  // ensureKeysFor is implemented by adding a key to our local record
+add_task(function* ensureCanSync_pulls_key() {
+  // ensureCanSync is implemented by adding a key to our local record
   // and doing a sync. This means that if the same key exists
   // remotely, we get a "conflict". Ensure that we handle this
   // correctly -- we keep the server key (since presumably it's
   // already been used to encrypt records) and we don't wipe out other
   // collections' keys.
   const extensionId = uuid();
   const extensionId2 = uuid();
+  const extensionOnlyKey = uuid();
+  const extensionOnlySalt = uuid();
   const DEFAULT_KEY = new BulkKeyBundle("[default]");
   DEFAULT_KEY.generateRandom();
   const RANDOM_KEY = new BulkKeyBundle(extensionId);
   RANDOM_KEY.generateRandom();
+  const RANDOM_SALT = cryptoCollection.getNewSalt();
   yield* withContextAndServer(function* (context, server) {
     yield* withSignedInUser(loggedInUser, function* () {
       const keysData = {
         "default": DEFAULT_KEY.keyPairB64,
         "collections": {
           [extensionId]: RANDOM_KEY.keyPairB64,
         },
       };
-      server.installKeyRing(keysData, 999);
+      const saltData = {
+        [extensionId]: RANDOM_SALT,
+      };
+      server.installKeyRing(keysData, saltData, 999);
 
-      let collectionKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId]);
+      let collectionKeys = yield ExtensionStorageSync.ensureCanSync([extensionId]);
       assertKeyRingKey(collectionKeys, extensionId, RANDOM_KEY);
 
       let posts = server.getPosts();
       equal(posts.length, 0,
-            "ensureKeysFor shouldn't push when the server keyring has the right key");
+            "ensureCanSync shouldn't push when the server keyring has the right key");
 
       // Another client generates a key for extensionId2
       const newKey = new BulkKeyBundle(extensionId2);
       newKey.generateRandom();
       keysData.collections[extensionId2] = newKey.keyPairB64;
+      saltData[extensionId2] = cryptoCollection.getNewSalt();
       server.clearCollection("storage-sync-crypto");
-      server.installKeyRing(keysData, 1000);
+      server.installKeyRing(keysData, saltData, 1000);
 
-      let newCollectionKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId, extensionId2]);
+      let newCollectionKeys = yield ExtensionStorageSync.ensureCanSync([extensionId, extensionId2]);
       assertKeyRingKey(newCollectionKeys, extensionId2, newKey);
       assertKeyRingKey(newCollectionKeys, extensionId, RANDOM_KEY,
-                       `ensureKeysFor shouldn't lose the old key for ${extensionId}`);
+                       `ensureCanSync shouldn't lose the old key for ${extensionId}`);
+
+      posts = server.getPosts();
+      equal(posts.length, 0, "ensureCanSync shouldn't push when updating keys");
+
+      // Another client generates a key, but not a salt, for extensionOnlyKey
+      const onlyKey = new BulkKeyBundle(extensionOnlyKey);
+      onlyKey.generateRandom();
+      keysData.collections[extensionOnlyKey] = onlyKey.keyPairB64;
+      server.clearCollection("storage-sync-crypto");
+      server.installKeyRing(keysData, saltData, 1001);
+
+      let withNewKey = yield ExtensionStorageSync.ensureCanSync([extensionId, extensionOnlyKey]);
+      dump(`got ${JSON.stringify(withNewKey.asWBO().cleartext)}\n`);
+      assertKeyRingKey(withNewKey, extensionOnlyKey, onlyKey);
+      assertKeyRingKey(withNewKey, extensionId, RANDOM_KEY,
+                       `ensureCanSync shouldn't lose the old key for ${extensionId}`);
 
       posts = server.getPosts();
-      equal(posts.length, 0, "ensureKeysFor shouldn't push when updating keys");
+      equal(posts.length, 1, "ensureCanSync should push when generating a new salt");
+      const withNewKeyRecord = yield assertPostedEncryptedKeys(posts[0]);
+      // We don't a priori know what the new salt is
+      dump(`${JSON.stringify(withNewKeyRecord)}\n`);
+      ok(withNewKeyRecord.salts[extensionOnlyKey],
+         `ensureCanSync should generate a salt for an extension that only had a key`);
+
+      // Another client generates a key, but not a salt, for extensionOnlyKey
+      const newSalt = cryptoCollection.getNewSalt();
+      saltData[extensionOnlySalt] = newSalt;
+      server.clearCollection("storage-sync-crypto");
+      server.installKeyRing(keysData, saltData, 1002);
+
+      let withOnlySaltKey = yield ExtensionStorageSync.ensureCanSync([extensionId, extensionOnlySalt]);
+      assertKeyRingKey(withOnlySaltKey, extensionId, RANDOM_KEY,
+                       `ensureCanSync shouldn't lose the old key for ${extensionId}`);
+      // We don't a priori know what the new key is
+      ok(withOnlySaltKey.hasKeysFor([extensionOnlySalt]),
+         `ensureCanSync generated a key for an extension that only had a salt`);
+
+      posts = server.getPosts();
+      equal(posts.length, 2, "ensureCanSync should push when generating a new key");
+      const withNewSaltRecord = yield assertPostedEncryptedKeys(posts[1]);
+      equal(withNewSaltRecord.salts[extensionOnlySalt], newSalt,
+            "ensureCanSync should keep the existing salt when generating only a key");
     });
   });
 });
 
-add_task(function* ensureKeysFor_handles_conflicts() {
+add_task(function* ensureCanSync_handles_conflicts() {
   // Syncing is done through a pull followed by a push of any merged
   // changes. Accordingly, the only way to have a "true" conflict --
   // i.e. with the server rejecting a change -- is if
   // someone pushes changes between our pull and our push. Ensure that
   // if this happens, we still behave sensibly (keep the remote key).
   const extensionId = uuid();
   const DEFAULT_KEY = new BulkKeyBundle("[default]");
   DEFAULT_KEY.generateRandom();
   const RANDOM_KEY = new BulkKeyBundle(extensionId);
   RANDOM_KEY.generateRandom();
+  const RANDOM_SALT = cryptoCollection.getNewSalt();
   yield* withContextAndServer(function* (context, server) {
     yield* withSignedInUser(loggedInUser, function* () {
       const keysData = {
         "default": DEFAULT_KEY.keyPairB64,
         "collections": {
           [extensionId]: RANDOM_KEY.keyPairB64,
         },
       };
-      server.installKeyRing(keysData, 765, {conflict: true});
+      const saltData = {
+        [extensionId]: RANDOM_SALT,
+      };
+      server.installKeyRing(keysData, saltData, 765, {conflict: true});
 
       yield cryptoCollection._clear();
 
-      let collectionKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId]);
+      let collectionKeys = yield ExtensionStorageSync.ensureCanSync([extensionId]);
       assertKeyRingKey(collectionKeys, extensionId, RANDOM_KEY,
                        `syncing keyring should keep the server key for ${extensionId}`);
 
       let posts = server.getPosts();
       equal(posts.length, 1,
             "syncing keyring should have tried to post a keyring");
       const failedPost = posts[0];
       assertPostedNewRecord(failedPost);
@@ -618,31 +677,33 @@ add_task(function* ensureKeysFor_handles
     });
   });
 });
 
 add_task(function* checkSyncKeyRing_reuploads_keys() {
   // Verify that when keys are present, they are reuploaded with the
   // new kB when we call touchKeys().
   const extensionId = uuid();
-  let extensionKey;
+  let extensionKey, extensionSalt;
   yield* withContextAndServer(function* (context, server) {
     yield* withSignedInUser(loggedInUser, function* () {
       server.installCollection("storage-sync-crypto");
       server.etag = 765;
 
       yield cryptoCollection._clear();
 
-      // Do an `ensureKeysFor` to generate some keys.
-      let collectionKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId]);
+      // Do an `ensureCanSync` to generate some keys.
+      let collectionKeys = yield ExtensionStorageSync.ensureCanSync([extensionId]);
       ok(collectionKeys.hasKeysFor([extensionId]),
-         `ensureKeysFor should return a keyring that has a key for ${extensionId}`);
+         `ensureCanSync should return a keyring that has a key for ${extensionId}`);
       extensionKey = collectionKeys.keyForCollection(extensionId).keyPairB64;
       equal(server.getPosts().length, 1,
             "generating a key that doesn't exist on the server should post it");
+      const body = yield assertPostedEncryptedKeys(server.getPosts()[0]);
+      extensionSalt = body.salts[extensionId];
     });
 
     // The user changes their password. This is their new kB, with
     // the last f changed to an e.
     const NOVEL_KB = "0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdee";
     const newUser = Object.assign({}, loggedInUser, {kB: NOVEL_KB});
     let postedKeys;
     yield* withSignedInUser(newUser, function* () {
@@ -652,16 +713,18 @@ add_task(function* checkSyncKeyRing_reup
       equal(posts.length, 2,
             "when kB changes, checkSyncKeyRing should post the keyring reencrypted with the new kB");
       postedKeys = posts[1];
       assertPostedUpdatedRecord(postedKeys, 765);
 
       let body = yield assertPostedEncryptedKeys(postedKeys);
       deepEqual(body.keys.collections[extensionId], extensionKey,
                 `the posted keyring should have the same key for ${extensionId} as the old one`);
+      deepEqual(body.salts[extensionId], extensionSalt,
+                `the posted keyring should have the same salt for ${extensionId} as the old one`);
     });
 
     // Verify that with the old kB, we can't decrypt the record.
     yield* withSignedInUser(loggedInUser, function* () {
       let error;
       try {
         yield new KeyRingEncryptionRemoteTransformer().decode(postedKeys.body.data);
       } catch (e) {
@@ -689,32 +752,33 @@ add_task(function* checkSyncKeyRing_over
       const oldUser = Object.assign({}, loggedInUser, {kB: NOVEL_KB});
       server.installCollection("storage-sync-crypto");
       server.installDeleteBucket();
       server.etag = 765;
       yield* withSignedInUser(oldUser, function* () {
         const FAKE_KEYRING = {
           id: "keys",
           keys: {},
+          salts: {},
           uuid: "abcd",
           kbHash: "abcd",
         };
         yield server.encryptAndAddRecord(transformer, "storage-sync-crypto", FAKE_KEYRING);
       });
 
       // Now we have this new user with a different kB.
       yield* withSignedInUser(loggedInUser, function* () {
         yield cryptoCollection._clear();
 
-        // Do an `ensureKeysFor` to generate some keys.
+        // Do an `ensureCanSync` to generate some keys.
         // This will try to sync, notice that the record is
         // undecryptable, and clear the server.
-        let collectionKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId]);
+        let collectionKeys = yield ExtensionStorageSync.ensureCanSync([extensionId]);
         ok(collectionKeys.hasKeysFor([extensionId]),
-           `ensureKeysFor should always return a keyring with a key for ${extensionId}`);
+           `ensureCanSync should always return a keyring with a key for ${extensionId}`);
         extensionKey = collectionKeys.keyForCollection(extensionId).keyPairB64;
 
         deepEqual(server.getDeletedBuckets(), ["default"],
                   "Kinto server should have been wiped when keyring was thrown away");
 
         let posts = server.getPosts();
         equal(posts.length, 1,
              "new keyring should have been uploaded");
@@ -732,17 +796,17 @@ add_task(function* checkSyncKeyRing_over
         equal(typeof body.uuid, "string", "keyring UUIDs should be strings");
         notEqual(body.uuid, "abcd",
                  "new keyring should not have the same UUID as previous keyring");
         ok(body.keys,
            "new keyring should have a keys attribute");
         ok(body.keys.default, "new keyring should have a default key");
         // We should keep the extension key that was in our uploaded version.
         deepEqual(extensionKey, body.keys.collections[extensionId],
-                  "ensureKeysFor should have returned keyring with the same key that was uploaded");
+                  "ensureCanSync should have returned keyring with the same key that was uploaded");
 
         // This should be a no-op; the keys were uploaded as part of ensurekeysfor
         yield ExtensionStorageSync.checkSyncKeyRing();
         equal(server.getPosts().length, 1,
               "checkSyncKeyRing should not need to post keys after they were reuploaded");
       });
     });
   });
@@ -759,20 +823,20 @@ add_task(function* checkSyncKeyRing_flus
   yield* withSyncContext(function* (context) {
     yield* withServer(function* (server) {
       server.installCollection("storage-sync-crypto");
       server.installCollection(collectionId);
       server.installDeleteBucket();
       yield* withSignedInUser(loggedInUser, function* () {
         yield cryptoCollection._clear();
 
-        // Do an `ensureKeysFor` to get access to keys.
-        let collectionKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId]);
+        // Do an `ensureCanSync` to get access to keys.
+        let collectionKeys = yield ExtensionStorageSync.ensureCanSync([extensionId]);
         ok(collectionKeys.hasKeysFor([extensionId]),
-           `ensureKeysFor should always return a keyring that has a key for ${extensionId}`);
+           `ensureCanSync should always return a keyring that has a key for ${extensionId}`);
         const extensionKey = collectionKeys.keyForCollection(extensionId).keyPairB64;
 
         // Set something to make sure that it gets re-uploaded when
         // uuid changes.
         yield ExtensionStorageSync.set(extension, {"my-key": 5}, context);
         yield ExtensionStorageSync.syncAll();
 
         let posts = server.getPosts();
@@ -784,16 +848,19 @@ add_task(function* checkSyncKeyRing_flus
 
         let body = yield transformer.decode(postedKeys.body.data);
         ok(body.uuid,
            "keyring should have a UUID");
         ok(body.keys,
            "keyring should have a keys attribute");
         ok(body.keys.default,
            "keyring should have a default key");
+        ok(body.salts[extensionId],
+           `keyring should have a salt for ${extensionId}`);
+        const extensionSalt = body.salts[extensionId];
         deepEqual(extensionKey, body.keys.collections[extensionId],
                   "new keyring should have the same key that we uploaded");
 
         // Another client comes along and replaces the UUID.
         // In real life, this would mean changing the keys too, but
         // this test verifies that just changing the UUID is enough.
         const newKeyRingData = Object.assign({}, body, {
           uuid: "abcd",
@@ -804,38 +871,40 @@ add_task(function* checkSyncKeyRing_flus
         });
         server.clearCollection("storage-sync-crypto");
         server.etag = 765;
         yield server.encryptAndAddRecordOnlyOnce(transformer, "storage-sync-crypto", newKeyRingData);
 
         // Fake adding another extension just so that the keyring will
         // really get synced.
         const newExtension = uuid();
-        const newKeyRing = yield ExtensionStorageSync.ensureKeysFor([newExtension]);
+        const newKeyRing = yield ExtensionStorageSync.ensureCanSync([newExtension]);
 
         // This should have detected the UUID change and flushed everything.
         // The keyring should, however, be the same, since we just
         // changed the UUID of the previously POSTed one.
         deepEqual(newKeyRing.keyForCollection(extensionId).keyPairB64, extensionKey,
-                  "ensureKeysFor should have pulled down a new keyring with the same keys");
+                  "ensureCanSync should have pulled down a new keyring with the same keys");
 
         // Syncing should reupload the data for the extension.
         yield ExtensionStorageSync.syncAll();
         posts = server.getPosts();
         equal(posts.length, 4,
               "should have posted keyring for new extension and reuploaded extension data");
 
         const finalKeyRingPost = posts[2];
         const reuploadedPost = posts[3];
 
         equal(finalKeyRingPost.path, collectionRecordsPath("storage-sync-crypto") + "/keys",
               "keyring for new extension should have been posted to /keys");
         let finalKeyRing = yield transformer.decode(finalKeyRingPost.body.data);
         equal(finalKeyRing.uuid, "abcd",
               "newly uploaded keyring should preserve UUID from replacement keyring");
+        deepEqual(finalKeyRing.salts[extensionId], extensionSalt,
+                  "newly uploaded keyring should preserve salts from existing salts");
 
         // Confirm that the data got reuploaded
         equal(reuploadedPost.path, collectionRecordsPath(collectionId) + "/key-my_2D_key",
               "extension data should be posted to path corresponding to its key");
         let reuploadedData = yield new CollectionKeyEncryptionRemoteTransformer(extensionId).decode(reuploadedPost.body.data);
         equal(reuploadedData.key, "my-key",
               "extension data should have a key attribute corresponding to the extension data key");
         equal(reuploadedData.data, 5,
@@ -855,17 +924,17 @@ add_task(function* test_storage_sync_pul
       server.installCollection(collectionId);
       server.installCollection("storage-sync-crypto");
 
       let calls = [];
       yield ExtensionStorageSync.addOnChangedListener(extension, function() {
         calls.push(arguments);
       }, context);
 
-      yield ExtensionStorageSync.ensureKeysFor([extensionId]);
+      yield ExtensionStorageSync.ensureCanSync([extensionId]);
       yield server.encryptAndAddRecord(transformer, collectionId, {
         "id": "key-remote_2D_key",
         "key": "remote-key",
         "data": 6,
       });
 
       yield ExtensionStorageSync.syncAll();
       const remoteValue = (yield ExtensionStorageSync.get(extension, "remote-key", context))["remote-key"];