--- a/services/sync/modules/engines/extension-storage.js
+++ b/services/sync/modules/engines/extension-storage.js
@@ -124,18 +124,18 @@ function ciphertextHMAC(keyBundle, id, I
 class EncryptionRemoteTransformer {
   encode(record) {
     const self = this;
     return Task.spawn(function* () {
       const keyBundle = yield self.getKeys();
       if (record.ciphertext) {
         throw new Error("Attempt to reencrypt??");
       }
-      let id = record.id;
-      if (!record.id) {
+      let id = yield self.getEncodedRecordId(record);
+      if (!id) {
         throw new Error("Record ID is missing or invalid");
       }
 
       let IV = Svc.Crypto.generateRandomIV();
       let ciphertext = Svc.Crypto.encrypt(JSON.stringify(record),
                                           keyBundle.encryptionKeyB64, IV);
       let hmac = ciphertextHMAC(keyBundle, id, IV, ciphertext);
       const encryptedResult = {ciphertext, IV, hmac, id};
@@ -174,23 +174,16 @@ class EncryptionRemoteTransformer {
       // Handle invalid data here. Elsewhere we assume that cleartext is an object.
       let cleartext = Svc.Crypto.decrypt(record.ciphertext,
                                          keyBundle.encryptionKeyB64, record.IV);
       let jsonResult = JSON.parse(cleartext);
       if (!jsonResult || typeof jsonResult !== "object") {
         throw new Error("Decryption failed: result is <" + jsonResult + ">, not an object.");
       }
 
-      // Verify that the encrypted id matches the requested record's id.
-      // This should always be true, because we compute the HMAC over
-      // the original record's ID, and that was verified already (above).
-      if (jsonResult.id != record.id) {
-        throw new Error("Record id mismatch: " + jsonResult.id + " != " + record.id);
-      }
-
       if (record.hasOwnProperty("last_modified")) {
         jsonResult.last_modified = record.last_modified;
       }
 
       // _status: deleted records were deleted on a client, but
       // uploaded as an encrypted blob so we don't leak deletions.
       // If we get such a record, flag it as deleted.
       if (jsonResult._status == "deleted") {
@@ -204,16 +197,29 @@ class EncryptionRemoteTransformer {
   /**
    * Retrieve keys to use during encryption.
    *
    * Returns a Promise<KeyBundle>.
    */
   getKeys() {
     throw new Error("override getKeys in a subclass");
   }
+
+  /**
+   * Compute the record ID to use for the encoded version of the
+   * record.
+   *
+   * The default version just re-uses the record's ID.
+   *
+   * @param {Object} record The record being encoded.
+   * @returns {Promise<string>} The ID to use.
+   */
+  getEncodedRecordId(record) {
+    return Promise.resolve(record.id);
+  }
 }
 // You can inject this
 EncryptionRemoteTransformer.prototype._fxaService = fxAccounts;
 
 /**
  * An EncryptionRemoteTransformer that provides a keybundle derived
  * from the user's kB, suitable for encrypting a keyring.
  */

--- a/toolkit/components/extensions/ExtensionStorageSync.jsm
+++ b/toolkit/components/extensions/ExtensionStorageSync.jsm
@@ -267,33 +267,52 @@ if (AppConstants.platform != "android") 
      * [a-zA-Z0-9][a-zA-Z0-9_-]*. We thus encode the hash using
      * "base64-url" without padding (so that we don't get any equals
      * signs (=)). For fear that a hash could start with a hyphen
      * (-) or an underscore (_), prefix it with "ext-".
      *
      * @param {string} extensionId The extension ID to obfuscate.
      * @returns {Promise<bytestring>} A collection ID suitable for use to sync to.
      */
-    extensionIdToCollectionId: Task.async(function* (extensionId) {
+    extensionIdToCollectionId(extensionId) {
+      return this.hashWithExtensionSalt(CommonUtils.encodeUTF8(extensionId), extensionId)
+        .then(hash => `ext-${hash}`);
+    },
+
+    /**
+     * Hash some value with the salt for the given extension.
+     *
+     * The value should be a "bytestring", i.e. a string whose
+     * "characters" are values, each within [0, 255]. You can produce
+     * such a bytestring using e.g. CommonUtils.encodeUTF8.
+     *
+     * The returned value is a base64url-encoded string of the hash.
+     *
+     * @param {bytestring} value The value to be hashed.
+     * @param {string} extensionId The ID of the extension whose salt
+     *                             we should use.
+     * @returns {Promise<bytestring>} The hashed value.
+     */
+    hashWithExtensionSalt: Task.async(function* (value, extensionId) {
       const salts = yield this.getSalts();
       const saltBase64 = salts && salts[extensionId];
       if (!saltBase64) {
         // This should never happen; salts should be populated before
         // we need them by ensureCanSync.
         throw new Error(`no salt available for ${extensionId}; how did this happen?`);
       }
 
       const hasher = Cc["@mozilla.org/security/hash;1"]
           .createInstance(Ci.nsICryptoHash);
       hasher.init(hasher.SHA256);
 
       const salt = atob(saltBase64);
-      const message = `${salt}\x00${CommonUtils.encodeUTF8(extensionId)}`;
+      const message = `${salt}\x00${value}`;
       const hash = CryptoUtils.digestBytes(message, hasher);
-      return `ext-${CommonUtils.encodeBase64URL(hash, false)}`;
+      return CommonUtils.encodeBase64URL(hash, false);
     }),
 
     /**
      * Retrieve the actual keyring from the crypto collection.
      *
      * @returns {Promise<CollectionKeyManager>}
      */
     getKeyRing: Task.async(function* () {
@@ -342,18 +361,24 @@ if (AppConstants.platform != "android") 
     // Used only for testing.
     _clear: Task.async(function* () {
       const collection = yield this.getCollection();
       yield collection.clear();
     }),
   };
 
   /**
-   * An EncryptionRemoteTransformer that uses the special "keys" record
-   * to find a key for a given extension.
+   * An EncryptionRemoteTransformer for extension records.
+   *
+   * It uses the special "keys" record to find a key for a given
+   * extension, thus its name
+   * CollectionKeyEncryptionRemoteTransformer.
+   *
+   * Also, during encryption, it will replace the ID of the new record
+   * with a hashed ID, using the salt for this collection.
    *
    * @param {string} extensionId The extension ID for which to find a key.
    */
   CollectionKeyEncryptionRemoteTransformer = class extends EncryptionRemoteTransformer {
     constructor(extensionId) {
       super();
       this.extensionId = extensionId;
     }
@@ -366,16 +391,28 @@ if (AppConstants.platform != "android") 
         if (!collectionKeys.hasKeysFor([self.extensionId])) {
           // This should never happen. Keys should be created (and
           // synced) at the beginning of the sync cycle.
           throw new Error(`tried to encrypt records for ${this.extensionId}, but key is not present`);
         }
         return collectionKeys.keyForCollection(self.extensionId);
       });
     }
+
+    getEncodedRecordId(record) {
+      // It isn't really clear whether kinto.js record IDs are
+      // bytestrings or strings that happen to only contain ASCII
+      // characters, so encode them to be sure.
+      const id = CommonUtils.encodeUTF8(record.id);
+      // Like extensionIdToCollectionId, the rules about Kinto record
+      // IDs preclude equals signs or strings starting with a
+      // non-alphanumeric, so prefix all IDs with a constant "id-".
+      return cryptoCollection.hashWithExtensionSalt(id, this.extensionId)
+        .then(hash => `id-${hash}`);
+    }
   };
   global.CollectionKeyEncryptionRemoteTransformer = CollectionKeyEncryptionRemoteTransformer;
 }
 /**
  * Clean up now that one context is no longer using this extension's collection.
  *
  * @param {Extension} extension
  *                    The extension whose context just ended.

--- a/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
+++ b/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
@@ -891,17 +891,18 @@ add_task(function* checkSyncKeyRing_flus
               "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",
+        const hashedId = "id-" + (yield cryptoCollection.hashWithExtensionSalt("key-my_2D_key", extensionId));
+        equal(reuploadedPost.path, `${collectionRecordsPath(collectionId)}/${hashedId}`,
               "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,
               "extension data should have a data attribute corresponding to the extension data value");
       });
     });
@@ -985,34 +986,35 @@ add_task(function* test_storage_sync_pus
       // install this AFTER we set the key to 5...
       let calls = [];
       ExtensionStorageSync.addOnChangedListener(extension, function() {
         calls.push(arguments);
       }, context);
 
       yield ExtensionStorageSync.syncAll();
       const localValue = (yield ExtensionStorageSync.get(extension, "my-key", context))["my-key"];
+      const hashedId = "id-" + (yield cryptoCollection.hashWithExtensionSalt("key-my_2D_key", extensionId));
       equal(localValue, 5,
             "pushing an ExtensionStorageSync value shouldn't change local value");
 
       let posts = server.getPosts();
       // FIXME: Keys were pushed in a previous test
       equal(posts.length, 1,
             "pushing a value should cause a post to the server");
       const post = posts[0];
       assertPostedNewRecord(post);
-      equal(post.path, collectionRecordsPath(collectionId) + "/key-my_2D_key",
+      equal(post.path, `${collectionRecordsPath(collectionId)}/${hashedId}`,
             "pushing a value should have a path corresponding to its id");
 
       const encrypted = post.body.data;
       ok(encrypted.ciphertext,
          "pushing a value should post an encrypted record");
       ok(!encrypted.data,
          "pushing a value should not have any plaintext data");
-      equal(encrypted.id, "key-my_2D_key",
+      equal(encrypted.id, hashedId,
             "pushing a value should use a kinto-friendly record ID");
 
       const record = yield transformer.decode(encrypted);
       equal(record.key, "my-key",
             "when decrypted, a pushed value should have a key field corresponding to its storage.sync key");
       equal(record.data, 5,
             "when decrypted, a pushed value should have a data field corresponding to its storage.sync value");
       equal(record.id, "key-my_2D_key",
@@ -1025,25 +1027,25 @@ add_task(function* test_storage_sync_pus
       yield ExtensionStorageSync.syncAll();
 
       // Doesn't push keys because keys were pushed by a previous test.
       posts = server.getPosts();
       equal(posts.length, 2,
             "updating a value should trigger another push");
       const updatePost = posts[1];
       assertPostedUpdatedRecord(updatePost, 1000);
-      equal(updatePost.path, collectionRecordsPath(collectionId) + "/key-my_2D_key",
+      equal(updatePost.path, `${collectionRecordsPath(collectionId)}/${hashedId}`,
             "pushing an updated value should go to the same path");
 
       const updateEncrypted = updatePost.body.data;
       ok(updateEncrypted.ciphertext,
          "pushing an updated value should still be encrypted");
       ok(!updateEncrypted.data,
          "pushing an updated value should not have any plaintext visible");
-      equal(updateEncrypted.id, "key-my_2D_key",
+      equal(updateEncrypted.id, hashedId,
             "pushing an updated value should maintain the same ID");
     });
   });
 });
 
 add_task(function* test_storage_sync_pulls_deletes() {
   const collectionId = yield cryptoCollection.extensionIdToCollectionId(defaultExtensionId);
   const extension = defaultExtension;
@@ -1117,22 +1119,23 @@ add_task(function* test_storage_sync_pus
       equal(calls.length, 1,
             "deleting a value should call the on-changed listener");
 
       yield ExtensionStorageSync.syncAll();
       equal(calls.length, 1,
             "pushing a deleted value shouldn't call the on-changed listener");
 
       // Doesn't push keys because keys were pushed by a previous test.
+      const hashedId = "id-" + (yield cryptoCollection.hashWithExtensionSalt("key-my_2D_key", extensionId));
       posts = server.getPosts();
       equal(posts.length, 3,
             "deleting a value should trigger another push");
       const post = posts[2];
       assertPostedUpdatedRecord(post, 1000);
-      equal(post.path, collectionRecordsPath(collectionId) + "/key-my_2D_key",
+      equal(post.path, `${collectionRecordsPath(collectionId)}/${hashedId}`,
             "pushing a deleted value should go to the same path");
       ok(post.method, "PUT");
       ok(post.body.data.ciphertext,
          "deleting a value should have an encrypted body");
       const decoded = yield new CollectionKeyEncryptionRemoteTransformer(extensionId).decode(post.body.data);
       equal(decoded._status, "deleted");
       // Ideally, we'd check that decoded.deleted is not true, because
       // the encrypted record shouldn't have it, but the decoder will