--- a/toolkit/components/extensions/ExtensionStorageSync.jsm
+++ b/toolkit/components/extensions/ExtensionStorageSync.jsm
@@ -219,16 +219,23 @@ const cryptoCollection = this.cryptoColl
     } else {
       // We never actually use the default key, so it's OK if we
       // generate one multiple times.
       collectionKeys.generateDefaultKey();
     }
     return collectionKeys;
   }),
 
+  updateKBHash: Task.async(function* (kbHash) {
+    const coll = yield this.getCollection();
+    yield coll.update({id: STORAGE_SYNC_CRYPTO_KEYRING_RECORD_ID,
+                       kbHash: kbHash},
+                      {patch: true});
+  }),
+
   upsert: Task.async(function* (record) {
     const collection = yield this.getCollection();
     yield collection.upsert(record);
   }),
 
   sync: Task.async(function* () {
     const collection = yield this.getCollection();
     return yield ExtensionStorageSync._syncCollection(collection, {
@@ -343,16 +350,17 @@ this.ExtensionStorageSync = {
     const extensions = extensionContexts.keys();
     const extIds = Array.from(extensions, extension => extension.id);
     log.debug(`Syncing extension settings for ${JSON.stringify(extIds)}\n`);
     if (extIds.length == 0) {
       // No extensions to sync. Get out.
       return;
     }
     yield this.ensureKeysFor(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);
   }),
 
@@ -467,35 +475,119 @@ this.ExtensionStorageSync = {
    * @returns {Promise<CollectionKeyManager>}
    */
   ensureKeysFor: Task.async(function* (extIds) {
     const collectionKeys = yield cryptoCollection.getKeyRing();
     if (collectionKeys.hasKeysFor(extIds)) {
       return collectionKeys;
     }
 
+    const kbHash = yield this.getKBHash();
     const newKeys = yield collectionKeys.ensureKeysFor(extIds);
     const newRecord = {
       id: STORAGE_SYNC_CRYPTO_KEYRING_RECORD_ID,
       keys: newKeys.asWBO().cleartext,
+      // Add a field for the current kB hash.
+      kbHash: kbHash,
     };
     yield cryptoCollection.upsert(newRecord);
     const result = yield cryptoCollection.sync();
     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);
     }
 
     // No conflicts. We're good.
     return newKeys;
   }),
 
   /**
+   * Get the current user's hashed kB.
+   *
+   * @returns sha256 of the user's kB as a hex string
+   */
+  getKBHash: Task.async(function* () {
+    const signedInUser = yield this._fxaService.getSignedInUser();
+    if (!signedInUser) {
+      throw new Error("User isn't signed in!");
+    }
+
+    if (!signedInUser.kB) {
+      throw new Error("User doesn't have kB??");
+    }
+
+    let kBbytes = CommonUtils.hexToBytes(signedInUser.kB);
+    let hasher = Cc["@mozilla.org/security/hash;1"]
+                    .createInstance(Ci.nsICryptoHash);
+    hasher.init(hasher.SHA256);
+    return CommonUtils.bytesAsHex(CryptoUtils.digestBytes(signedInUser.uid + kBbytes, hasher));
+  }),
+
+  /**
+   * Update the kB in the crypto record.
+   */
+  updateKeyRingKB: Task.async(function* () {
+    const signedInUser = yield this._fxaService.getSignedInUser();
+    if (!signedInUser) {
+      // Although this function is meant to be called on login,
+      // it's not unreasonable to check any time, even if we aren't
+      // logged in.
+      //
+      // If we aren't logged in, we don't have any information about
+      // the user's kB, so we can't be sure that the user changed
+      // their kB, so just return.
+      return;
+    }
+
+    const thisKBHash = yield this.getKBHash();
+    yield cryptoCollection.updateKBHash(thisKBHash);
+  }),
+
+  /**
+   * Make sure the keyring is up to date and synced.
+   *
+   * This is called on syncs to make sure that we don't sync anything
+   * to any collection unless the key for that collection is on the
+   * server.
+   */
+  checkSyncKeyRing: Task.async(function* () {
+    yield this.updateKeyRingKB();
+
+    const cryptoKeyRecord = yield cryptoCollection.getKeyRingRecord();
+    if (cryptoKeyRecord && cryptoKeyRecord._status !== "synced") {
+      // We haven't successfully synced the keyring since the last
+      // change. This could be because kB changed and we touched the
+      // keyring, or it could be because we failed to sync after
+      // adding a key. Either way, take this opportunity to sync the
+      // keyring.
+      //
+      // We use server_wins here because whatever is on the server is
+      // at least consistent with itself -- the crypto in the keyring
+      // matches the crypto on the collection records. This is because
+      // we generate and upload keys just before syncing data.
+      //
+      // We can also get into the unhappy situation where we need to
+      // resolve conflicts with a record uploaded by a client with a
+      // different password. In this case, we will fail (throw an
+      // exception) because we can't decrypt the record. This behavior
+      // is correct because we have absolutely no chance of resolving
+      // conflicts intelligently -- in particular, we can't prove that
+      // uploading our key won't erase keys that have already been
+      // used on remote data. If this happens, hopefully the user will
+      // relogin so that all devices have a consistent kB; this will
+      // ensure that the most recent version on the server is
+      // encrypted with the same kB that other devices have, and they
+      // will sync the keyring successfully on subsequent syncs.
+      yield cryptoCollection.sync();
+    }
+  }),
+
+  /**
    * Get the collection for an extension, and register the extension
    * as being "in use".
    *
    * @param {Extension} extension
    *                    The extension for which we are seeking
    *                    a collection.
    * @param {Context} context
    *                  The context of the extension, so that we can

--- a/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
+++ b/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
@@ -12,19 +12,21 @@ const {
   CollectionKeyEncryptionRemoteTransformer,
   cryptoCollection,
   idToKey,
   extensionIdToCollectionId,
   keyToId,
 } = Cu.import("resource://gre/modules/ExtensionStorageSync.jsm");
 Cu.import("resource://services-sync/engines/extension-storage.js");
 Cu.import("resource://services-sync/keys.js");
+Cu.import("resource://services-sync/util.js");
 
 /* globals BulkKeyBundle, CommonUtils, EncryptionRemoteTransformer */
 /* globals KeyRingEncryptionRemoteTransformer */
+/* globals Utils */
 
 function handleCannedResponse(cannedResponse, request, response) {
   response.setStatusLine(null, cannedResponse.status.status,
                          cannedResponse.status.statusText);
   // send the headers
   for (let headerLine of cannedResponse.sampleHeaders) {
     let headerElements = headerLine.split(":");
     response.setHeader(headerElements[0], headerElements[1].trimLeft());
@@ -493,16 +495,71 @@ add_task(function* ensureKeysFor_handles
       ok(body.keys.collections[extensionId],
          `decrypted failed post should have a key for ${extensionId}`);
       notEqual(body.keys.collections[extensionId], RANDOM_KEY.keyPairB64,
                `decrypted failed post should have a randomly-generated key for ${extensionId}`);
     });
   });
 });
 
+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;
+  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]);
+      ok(collectionKeys.hasKeysFor([extensionId]),
+         `ensureKeysFor 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");
+    });
+
+    // 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* () {
+      yield ExtensionStorageSync.checkSyncKeyRing();
+
+      let posts = server.getPosts();
+      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`);
+    });
+
+    // 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) {
+        error = e;
+      }
+      ok(error, "decrypting the keyring with the old kB should fail");
+      ok(Utils.isHMACMismatch(error),
+         "decrypting the keyring with the old kB should throw an HMAC mismatch");
+    });
+  });
+});
+
 add_task(function* test_storage_sync_pulls_changes() {
   const extensionId = defaultExtensionId;
   const collectionId = defaultCollectionId;
   const extension = defaultExtension;
   yield* withContextAndServer(function* (context, server) {
     yield* withSignedInUser(loggedInUser, function* () {
       let transformer = new CollectionKeyEncryptionRemoteTransformer(extensionId);
       server.installCollection(collectionId);