--- a/services/sync/modules/engines/extension-storage.js
+++ b/services/sync/modules/engines/extension-storage.js
@@ -1,24 +1,31 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 "use strict";
 
-this.EXPORTED_SYMBOLS = ['ExtensionStorageEngine'];
+this.EXPORTED_SYMBOLS = ['ExtensionStorageEngine', 'EncryptionRemoteTransformer',
+                         'KeyRingEncryptionRemoteTransformer'];
 
 const {classes: Cc, interfaces: Ci, utils: Cu} = Components;
 
+Cu.import("resource://services-crypto/utils.js");
 Cu.import("resource://services-sync/constants.js");
 Cu.import("resource://services-sync/engines.js");
+Cu.import("resource://services-sync/keys.js");
 Cu.import("resource://services-sync/util.js");
 Cu.import("resource://services-common/async.js");
 XPCOMUtils.defineLazyModuleGetter(this, "ExtensionStorageSync",
                                   "resource://gre/modules/ExtensionStorageSync.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "fxAccounts",
+                                  "resource://gre/modules/FxAccounts.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "Task",
+                                  "resource://gre/modules/Task.jsm");
 
 /**
  * The Engine that manages syncing for the web extension "storage"
  * API, and in particular ext.storage.sync.
  *
  * ext.storage.sync is implemented using Kinto, so it has mechanisms
  * for syncing that we do not need to integrate in the Firefox Sync
  * framework, so this is something of a stub.
@@ -96,8 +103,128 @@ ExtensionStorageTracker.prototype = {
   },
   addChangedID: function() {
   },
   removeChangedID: function() {
   },
   clearChangedIDs: function() {
   },
 };
+
+/**
+ * Utility function to enforce an order of fields when computing an HMAC.
+ */
+function ciphertextHMAC(keyBundle, id, IV, ciphertext) {
+  const hasher = keyBundle.sha256HMACHasher;
+  return Utils.bytesAsHex(Utils.digestUTF8(id + IV + ciphertext, hasher));
+}
+
+/**
+ * A "remote transformer" that the Kinto library will use to
+ * encrypt/decrypt records when syncing.
+ *
+ * This is an "abstract base class". Subclass this and override
+ * getKeys() to use it.
+ */
+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) {
+        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};
+      if (record.hasOwnProperty("last_modified")) {
+        encryptedResult.last_modified = record.last_modified;
+      }
+      return encryptedResult;
+    });
+  }
+
+  decode(record) {
+    const self = this;
+    return Task.spawn(function* () {
+      const keyBundle = yield self.getKeys();
+      if (!record.ciphertext) {
+        throw new Error("No ciphertext: nothing to decrypt?");
+      }
+      // Authenticate the encrypted blob with the expected HMAC
+      let computedHMAC = ciphertextHMAC(keyBundle, record.id, record.IV, record.ciphertext);
+
+      if (computedHMAC != record.hmac) {
+        Utils.throwHMACMismatch(record.hmac, computedHMAC);
+      }
+
+      // 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;
+      }
+
+      return jsonResult;
+    });
+  }
+
+  /**
+   * Retrieve keys to use during encryption.
+   *
+   * Returns a Promise<KeyBundle>.
+   */
+  getKeys() {
+    throw new Error("override getKeys in a subclass");
+  }
+}
+// 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.
+ */
+class KeyRingEncryptionRemoteTransformer extends EncryptionRemoteTransformer {
+  getKeys() {
+    const self = this;
+    return Task.spawn(function* () {
+      const user = yield self._fxaService.getSignedInUser();
+      // FIXME: we should permit this if the user is self-hosting
+      // their storage
+      if (!user) {
+        throw new Error("user isn't signed in to FxA; can't sync");
+      }
+
+      if (!user.kB) {
+        throw new Error("user doesn't have kB");
+      }
+
+      let kB = Utils.hexToBytes(user.kB);
+
+      let keyMaterial = CryptoUtils.hkdf(kB, undefined,
+                                       "identity.mozilla.com/picl/v1/chrome.storage.sync", 2*32);
+      let bundle = new BulkKeyBundle();
+      // [encryptionKey, hmacKey]
+      bundle.keyPair = [keyMaterial.slice(0, 32), keyMaterial.slice(32, 64)];
+      return bundle;
+    });
+  }
+}

--- a/services/sync/modules/record.js
+++ b/services/sync/modules/record.js
@@ -276,28 +276,41 @@ RecordManager.prototype = {
 };
 
 /**
  * Keeps track of mappings between collection names ('tabs') and KeyBundles.
  *
  * You can update this thing simply by giving it /info/collections. It'll
  * use the last modified time to bring itself up to date.
  */
-this.CollectionKeyManager = function CollectionKeyManager() {
-  this.lastModified = 0;
-  this._collections = {};
-  this._default = null;
+this.CollectionKeyManager = function CollectionKeyManager(lastModified, default_, collections) {
+  this.lastModified = lastModified || 0;
+  this._default = default_ || null;
+  this._collections = collections || {};
 
   this._log = Log.repository.getLogger("Sync.CollectionKeyManager");
 }
 
 // TODO: persist this locally as an Identity. Bug 610913.
 // Note that the last modified time needs to be preserved.
 CollectionKeyManager.prototype = {
 
+  /**
+   * Generate a new CollectionKeyManager that has the same attributes
+   * as this one.
+   */
+  clone() {
+    const newCollections = {};
+    for (let c in this._collections) {
+      newCollections[c] = this._collections[c];
+    }
+
+    return new CollectionKeyManager(this.lastModified, this._default, newCollections);
+  },
+
   // Return information about old vs new keys:
   // * same: true if two collections are equal
   // * changed: an array of collection names that changed.
   _compareKeyBundleCollections: function _compareKeyBundleCollections(m1, m2) {
     let changed = [];
 
     function process(m1, m2) {
       for (let k1 in m1) {
@@ -364,41 +377,91 @@ CollectionKeyManager.prototype = {
   asWBO: function(collection, id) {
     return this._makeWBO(this._collections, this._default);
   },
 
   /**
    * Compute a new default key, and new keys for any specified collections.
    */
   newKeys: function(collections) {
-    let newDefaultKey = new BulkKeyBundle(DEFAULT_KEYBUNDLE_NAME);
-    newDefaultKey.generateRandom();
+    let newDefaultKeyBundle = this.newDefaultKeyBundle();
 
     let newColls = {};
     if (collections) {
       collections.forEach(function (c) {
         let b = new BulkKeyBundle(c);
         b.generateRandom();
         newColls[c] = b;
       });
     }
-    return [newDefaultKey, newColls];
+    return [newDefaultKeyBundle, newColls];
   },
 
   /**
    * Generates new keys, but does not replace our local copy. Use this to
    * verify an upload before storing.
    */
   generateNewKeysWBO: function(collections) {
     let newDefaultKey, newColls;
     [newDefaultKey, newColls] = this.newKeys(collections);
 
     return this._makeWBO(newColls, newDefaultKey);
   },
 
+  /**
+   * Create a new default key.
+   *
+   * @returns {BulkKeyBundle}
+   */
+  newDefaultKeyBundle() {
+    const key = new BulkKeyBundle(DEFAULT_KEYBUNDLE_NAME);
+    key.generateRandom();
+    return key;
+  },
+
+  /**
+   * Create a new default key and store it as this._default, since without one you cannot use setContents.
+   */
+  generateDefaultKey() {
+    this._default = this.newDefaultKeyBundle();
+  },
+
+  /**
+   * Return true if keys are already present for each of the given
+   * collections.
+   */
+  hasKeysFor(collections) {
+    // We can't use filter() here because sometimes collections is an iterator.
+    for (let collection of collections) {
+      if (!this._collections[collection]) {
+        return false;
+      }
+    }
+    return true;
+  },
+
+  /**
+   * Return a new CollectionKeyManager that has keys for each of the
+   * given collections (creating new ones for collections where we
+   * don't already have keys).
+   */
+  ensureKeysFor(collections) {
+    const newKeys = Object.assign({}, this._collections);
+    for (let c of collections) {
+      if (newKeys[c]) {
+        continue;  // don't replace existing keys
+      }
+
+      const b = new BulkKeyBundle(c);
+      b.generateRandom();
+      newKeys[c] = b;
+    }
+    return new CollectionKeyManager(this.lastModified, this._default, newKeys);
+  },
+
   // Take the fetched info/collections WBO, checking the change
   // time of the crypto collection.
   updateNeeded: function(info_collections) {
 
     this._log.info("Testing for updateNeeded. Last modified: " + this.lastModified);
 
     // No local record of modification time? Need an update.
     if (!this.lastModified)
@@ -419,19 +482,16 @@ CollectionKeyManager.prototype = {
   //
   // * If the default key was modified, return true.
   // * If the default key was not modified, but per-collection keys were,
   //   return an array of such.
   // * Otherwise, return false -- we were up-to-date.
   //
   setContents: function setContents(payload, modified) {
 
-    if (!modified)
-      throw "No modified time provided to setContents.";
-
     let self = this;
 
     this._log.info("Setting collection keys contents. Our last modified: " +
                    this.lastModified + ", input modified: " + modified + ".");
 
     if (!payload)
       throw "No payload in CollectionKeyManager.setContents().";
 
@@ -451,44 +511,47 @@ CollectionKeyManager.prototype = {
     if ("collections" in payload) {
       this._log.info("Processing downloaded per-collection keys.");
       let colls = payload.collections;
       for (let k in colls) {
         let v = colls[k];
         if (v) {
           let keyObj = new BulkKeyBundle(k);
           keyObj.keyPairB64 = v;
-          if (keyObj) {
-            newCollections[k] = keyObj;
-          }
+          newCollections[k] = keyObj;
         }
       }
     }
 
     // Check to see if these are already our keys.
     let sameDefault = (this._default && this._default.equals(newDefault));
     let collComparison = this._compareKeyBundleCollections(newCollections, this._collections);
     let sameColls = collComparison.same;
 
     if (sameDefault && sameColls) {
-      self._log.info("New keys are the same as our old keys! Bumped local modified time.");
-      self.lastModified = modified;
+      self._log.info("New keys are the same as our old keys!");
+      if (modified) {
+        self._log.info("Bumped local modified time.");
+        self.lastModified = modified;
+      }
       return false;
     }
 
     // Make sure things are nice and tidy before we set.
     this.clear();
 
     this._log.info("Saving downloaded keys.");
     this._default     = newDefault;
     this._collections = newCollections;
 
     // Always trust the server.
-    self._log.info("Bumping last modified to " + modified);
-    self.lastModified = modified;
+    if (modified) {
+      self._log.info("Bumping last modified to " + modified);
+      self.lastModified = modified;
+    }
 
     return sameDefault ? collComparison.changed : true;
   },
 
   updateContents: function updateContents(syncKeyBundle, storage_keys) {
     let log = this._log;
     log.info("Updating collection keys...");
 

--- a/services/sync/services-sync.js
+++ b/services/sync/services-sync.js
@@ -26,17 +26,16 @@ pref("services.sync.errorhandler.network
 
 pref("services.sync.engine.addons", true);
 pref("services.sync.engine.bookmarks", true);
 pref("services.sync.engine.history", true);
 pref("services.sync.engine.passwords", true);
 pref("services.sync.engine.prefs", true);
 pref("services.sync.engine.tabs", true);
 pref("services.sync.engine.tabs.filteredUrls", "^(about:.*|chrome://weave/.*|wyciwyg:.*|file:.*|blob:.*)$");
-pref("services.sync.engine.extension-storage", true);
 
 pref("services.sync.jpake.serverURL", "https://setup.services.mozilla.com/");
 pref("services.sync.jpake.pollInterval", 1000);
 pref("services.sync.jpake.firstMsgMaxTries", 300); // 5 minutes
 pref("services.sync.jpake.lastMsgMaxTries", 300);  // 5 minutes
 pref("services.sync.jpake.maxTries", 10);
 
 // If true, add-on sync ignores changes to the user-enabled flag. This

new file mode 100644
--- /dev/null
+++ b/services/sync/tests/unit/test_extension_storage_crypto.js
@@ -0,0 +1,93 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+"use strict";
+
+Cu.import("resource://services-crypto/utils.js");
+Cu.import("resource://services-sync/engines/extension-storage.js");
+Cu.import("resource://services-sync/util.js");
+
+/**
+ * Like Assert.throws, but for generators.
+ *
+ * @param {string | Object | function} constraint
+ *        What to use to check the exception.
+ * @param {function} f
+ *        The function to call.
+ */
+function* throwsGen(constraint, f) {
+  let threw = false;
+  let exception;
+  try {
+    yield* f();
+  }
+  catch (e) {
+    threw = true;
+    exception = e;
+  }
+
+  ok(threw, "did not throw an exception");
+
+  const debuggingMessage = `got ${exception}, expected ${constraint}`;
+  let message = exception;
+  if (typeof exception === "object") {
+    message = exception.message;
+  }
+
+  if (typeof constraint === "function") {
+    ok(constraint(message), debuggingMessage);
+  } else {
+    ok(constraint === message, debuggingMessage);
+  }
+
+}
+
+/**
+ * An EncryptionRemoteTransformer that uses a fixed key bundle,
+ * suitable for testing.
+ */
+class StaticKeyEncryptionRemoteTransformer extends EncryptionRemoteTransformer {
+  constructor(keyBundle) {
+    super();
+    this.keyBundle = keyBundle;
+  }
+
+  getKeys() {
+    return Promise.resolve(this.keyBundle);
+  }
+}
+const BORING_KB = "0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef";
+const STRETCHED_KEY = CryptoUtils.hkdf(BORING_KB, undefined, `testing storage.sync encryption`, 2*32);
+const KEY_BUNDLE = {
+  sha256HMACHasher: Utils.makeHMACHasher(Ci.nsICryptoHMAC.SHA256, Utils.makeHMACKey(STRETCHED_KEY.slice(0, 32))),
+  encryptionKeyB64: btoa(STRETCHED_KEY.slice(32, 64)),
+};
+const transformer = new StaticKeyEncryptionRemoteTransformer(KEY_BUNDLE);
+
+add_task(function* test_encryption_transformer_roundtrip() {
+  const POSSIBLE_DATAS = [
+    "string",
+    2,          // number
+    [1, 2, 3],  // array
+    {key: "value"}, // object
+  ];
+
+  for (let data of POSSIBLE_DATAS) {
+    const record = {data: data, id: "key-some_2D_key", key: "some-key"};
+
+    deepEqual(record, yield transformer.decode(yield transformer.encode(record)));
+  }
+});
+
+add_task(function* test_refuses_to_decrypt_tampered() {
+  const encryptedRecord = yield transformer.encode({data: [1, 2, 3], id: "key-some_2D_key", key: "some-key"});
+  const tamperedHMAC = Object.assign({}, encryptedRecord, {hmac: "0000000000000000000000000000000000000000000000000000000000000001"});
+  yield* throwsGen(Utils.isHMACMismatch, function*() {
+    yield transformer.decode(tamperedHMAC);
+  });
+
+  const tamperedIV = Object.assign({}, encryptedRecord, {IV: "aaaaaaaaaaaaaaaaaaaaaa=="});
+  yield* throwsGen(Utils.isHMACMismatch, function*() {
+    yield transformer.decode(tamperedIV);
+  });
+});

--- a/services/sync/tests/unit/test_records_crypto.js
+++ b/services/sync/tests/unit/test_records_crypto.js
@@ -143,14 +143,40 @@ function run_test() {
     }
     do_check_eq("Record SHA256 HMAC mismatch", err.substr(0, 27));
 
     // Explicitly check that it's using the bookmarks key.
     // This should succeed.
     do_check_eq(bookmarkItem.decrypt(Service.collectionKeys.keyForCollection("bookmarks")).stuff,
         "my payload here");
 
+    do_check_true(Service.collectionKeys.hasKeysFor(["bookmarks"]));
+
+    // Add a key for some new collection and verify that it isn't the
+    // default key.
+    do_check_false(Service.collectionKeys.hasKeysFor(["forms"]));
+    do_check_false(Service.collectionKeys.hasKeysFor(["bookmarks", "forms"]));
+    let oldFormsKey = Service.collectionKeys.keyForCollection("forms");
+    do_check_eq(oldFormsKey, Service.collectionKeys._default);
+    let newKeys = Service.collectionKeys.ensureKeysFor(["forms"]);
+    do_check_true(newKeys.hasKeysFor(["forms"]));
+    do_check_true(newKeys.hasKeysFor(["bookmarks", "forms"]));
+    let newFormsKey = newKeys.keyForCollection("forms");
+    do_check_neq(newFormsKey, oldFormsKey);
+
+    // Verify that this doesn't overwrite keys
+    let regetKeys = newKeys.ensureKeysFor(["forms"]);
+    do_check_eq(regetKeys.keyForCollection("forms"), newFormsKey);
+
+    const emptyKeys = new CollectionKeyManager();
+    payload = {
+      default: Service.collectionKeys._default.keyPairB64,
+      collections: {}
+    };
+    // Verify that not passing `modified` doesn't throw
+    emptyKeys.setContents(payload, null);
+
     log.info("Done!");
   }
   finally {
     server.stop(do_test_finished);
   }
 }

--- a/services/sync/tests/unit/xpcshell.ini
+++ b/services/sync/tests/unit/xpcshell.ini
@@ -157,16 +157,17 @@ tags = addons
 [test_bookmark_smart_bookmarks.js]
 [test_bookmark_store.js]
 # Too many intermittent "ASSERTION: thread pool wasn't shutdown: '!mPool'" (bug 804479)
 skip-if = debug
 [test_bookmark_tracker.js]
 [test_bookmark_validator.js]
 [test_clients_engine.js]
 [test_clients_escape.js]
+[test_extension_storage_crypto.js]
 [test_extension_storage_engine.js]
 [test_extension_storage_tracker.js]
 [test_forms_store.js]
 [test_forms_tracker.js]
 # Too many intermittent "ASSERTION: thread pool wasn't shutdown: '!mPool'" (bug 804479)
 skip-if = debug
 [test_history_engine.js]
 [test_history_store.js]