--- a/services/crypto/modules/WeaveCrypto.js
+++ b/services/crypto/modules/WeaveCrypto.js
@@ -79,16 +79,45 @@ WeaveCrypto.prototype = {
         if (cipherText.length) {
             cipherText = atob(cipherText);
         }
         let cipherTextBuffer = this.byteCompressInts(cipherText);
         let decrypted = await this._commonCrypt(cipherTextBuffer, symmetricKey, iv, OPERATIONS.DECRYPT);
         return this.decoder.decode(decrypted);
     },
 
+    async sign(cipherText, encodedHmacKeyString) {
+        let cipherTextBuffer = this.byteCompressInts(cipherText);
+        let hmacKey = await this.importHmacKey(encodedHmacKeyString);
+        let signatureBuffer = await crypto.subtle.sign({ name: "HMAC" },
+                                                       hmacKey,
+                                                       cipherTextBuffer);
+        return this.expandData(new Uint8Array(signatureBuffer));
+    },
+
+    async signAsBase64(cipherTextBase64, encodedHmacKeyString) {
+        let cipherText = atob(cipherTextBase64);
+        let signature = await this.sign(cipherText, encodedHmacKeyString);
+        return btoa(signature);
+    },
+
+    async verify(signature, cipherText, encodedHmacKeyString) {
+        let cipherTextBuffer = this.byteCompressInts(cipherText);
+        let signatureBuffer = this.byteCompressInts(signature);
+        let hmacKey = await this.importHmacKey(encodedHmacKeyString);
+        return crypto.subtle.verify({ name: "HMAC" }, hmacKey, signatureBuffer,
+                                    cipherTextBuffer);
+    },
+
+    async verifyAsBase64(signatureBase64, cipherTextBase64, encodedHmacKeyString) {
+        let signature = atob(signatureBase64);
+        let cipherText = atob(cipherTextBase64);
+        return this.verify(signature, cipherText, encodedHmacKeyString);
+    },
+
     /**
      * _commonCrypt
      *
      * @args
      * data: data to encrypt/decrypt (ArrayBuffer)
      * symKeyStr: symmetric key (Base64 String)
      * ivStr: initialization vector (Base64 String)
      * operation: operation to apply (either OPERATIONS.ENCRYPT or OPERATIONS.DECRYPT)
@@ -141,16 +170,30 @@ WeaveCrypto.prototype = {
         this.log("generateRandomBytes() called");
 
         let randBytes = new Uint8Array(byteCount);
         crypto.getRandomValues(randBytes);
 
         return this.encodeBase64(randBytes);
     },
 
+    _hmacKeyMemo: {},
+    async importHmacKey(encodedKeyString) {
+        if (encodedKeyString in this._hmacKeyMemo) {
+            return this._hmacKeyMemo[encodedKeyString];
+        }
+        let hmacKeyBuffer = this.makeUint8Array(encodedKeyString, true);
+        let hmacKey = await crypto.subtle.importKey("raw", hmacKeyBuffer, {
+            name: "HMAC",
+            hash: { name: "SHA-256" },
+        }, false, ["sign", "verify"]);
+        this._hmacKeyMemo[encodedKeyString] = hmacKey;
+        return hmacKey;
+    },
+
     //
     // SymKey CryptoKey memoization.
     //
 
     // Memoize the import of symmetric keys. We do this by using the base64
     // string itself as a key.
     _encryptionSymKeyMemo: {},
     _decryptionSymKeyMemo: {},

--- a/services/sync/modules-testing/fakeservices.js
+++ b/services/sync/modules-testing/fakeservices.js
@@ -82,31 +82,43 @@ function FakeGUIDService() {
  * Mock implementation of WeaveCrypto. It does not encrypt or
  * decrypt, merely returning the input verbatim.
  */
 function FakeCryptoService() {
   this.counter = 0;
 
   delete Weave.Crypto; // get rid of the getter first
   Weave.Crypto = this;
-
-  CryptoWrapper.prototype.ciphertextHMAC = function ciphertextHMAC(keyBundle) {
-    return fakeSHA256HMAC(this.ciphertext);
-  };
 }
 FakeCryptoService.prototype = {
 
   async encrypt(clearText, symmetricKey, iv) {
     return clearText;
   },
 
   async decrypt(cipherText, symmetricKey, iv) {
     return cipherText;
   },
 
+  async sign(cipherText, hmacKeyStr) {
+    return fakeSHA256HMAC(cipherText);
+  },
+
+  async signAsBase64(cipherTextBase64, encodedHmacKeyString) {
+    return fakeSHA256HMAC(cipherTextBase64);
+  },
+
+  async verify(signature, cipherText, hmacKeyStr) {
+    return fakeSHA256HMAC(cipherText) == signature;
+  },
+
+  async verifyAsBase64(signatureBase64, cipherTextBase64, encodedHmacKeyString) {
+    return fakeSHA256HMAC(cipherTextBase64) == signatureBase64;
+  },
+
   async generateRandomKey() {
     return btoa("fake-symmetric-key-" + this.counter++);
   },
 
   generateRandomIV: function generateRandomIV() {
     // A base64-encoded IV is 24 characters long
     return btoa("fake-fake-fake-random-iv");
   },

--- a/services/sync/modules/keys.js
+++ b/services/sync/modules/keys.js
@@ -80,33 +80,22 @@ KeyBundle.prototype = {
     }
 
     if (value.length < 16) {
       throw new Error("HMAC key must be at least 128 bits long.");
     }
 
     this._hmac = value;
     this._hmacB64 = btoa(value);
-    this._hmacObj = value ? Utils.makeHMACKey(value) : null;
-    this._sha256HMACHasher = value ? Utils.makeHMACHasher(
-      Ci.nsICryptoHMAC.SHA256, this._hmacObj) : null;
   },
 
   get hmacKeyB64() {
     return this._hmacB64;
   },
 
-  get hmacKeyObject() {
-    return this._hmacObj;
-  },
-
-  get sha256HMACHasher() {
-    return this._sha256HMACHasher;
-  },
-
   /**
    * Populate this key pair with 2 new, randomly generated keys.
    */
   async generateRandom() {
     // Compute both at that same time
     let [generatedHMAC, generatedEncr] = await Promise.all([
       Weave.Crypto.generateRandomKey(),
       Weave.Crypto.generateRandomKey()

--- a/services/sync/modules/record.js
+++ b/services/sync/modules/record.js
@@ -110,25 +110,16 @@ function CryptoWrapper(collection, id) {
   WBORecord.call(this, collection, id);
   this.ciphertext = null;
   this.id = id;
 }
 CryptoWrapper.prototype = {
   __proto__: WBORecord.prototype,
   _logName: "Sync.Record.CryptoWrapper",
 
-  ciphertextHMAC: function ciphertextHMAC(keyBundle) {
-    let hasher = keyBundle.sha256HMACHasher;
-    if (!hasher) {
-      throw new Error("Cannot compute HMAC without an HMAC key.");
-    }
-
-    return CommonUtils.bytesAsHex(Utils.digestBytes(this.ciphertext, hasher));
-  },
-
   /*
    * Don't directly use the sync key. Instead, grab a key for this
    * collection, which is decrypted with the sync key.
    *
    * Cache those keys; invalidate the cache if the time on the keys collection
    * changes, or other auth events occur.
    *
    * Optional key bundle overrides the collection key lookup.
@@ -136,35 +127,36 @@ CryptoWrapper.prototype = {
   async encrypt(keyBundle) {
     if (!keyBundle) {
       throw new Error("A key bundle must be supplied to encrypt.");
     }
 
     this.IV = Weave.Crypto.generateRandomIV();
     this.ciphertext = await Weave.Crypto.encrypt(JSON.stringify(this.cleartext),
                                                  keyBundle.encryptionKeyB64, this.IV);
-    this.hmac = this.ciphertextHMAC(keyBundle);
+    this.hmac = await Weave.Crypto.signAsBase64(this.ciphertext,
+                                                keyBundle.hmacKeyB64);
     this.cleartext = null;
   },
 
   // Optional key bundle.
   async decrypt(keyBundle) {
     if (!this.ciphertext) {
       throw new Error("No ciphertext: nothing to decrypt?");
     }
 
     if (!keyBundle) {
       throw new Error("A key bundle must be supplied to decrypt.");
     }
 
     // Authenticate the encrypted blob with the expected HMAC
-    let computedHMAC = this.ciphertextHMAC(keyBundle);
-
-    if (computedHMAC != this.hmac) {
-      Utils.throwHMACMismatch(this.hmac, computedHMAC);
+    let matches = await Weave.Crypto.verifyAsBase64(this.hmac, this.ciphertext,
+                                                    keyBundle.hmacKeyB64);
+    if (!matches) {
+      Utils.throwHMACMismatch(this.hmac, /* is */ null);
     }
 
     // Handle invalid data here. Elsewhere we assume that cleartext is an object.
     let cleartext = await Weave.Crypto.decrypt(this.ciphertext,
                                                keyBundle.encryptionKeyB64, this.IV);
     let json_result = JSON.parse(cleartext);
 
     if (json_result && (json_result instanceof Object)) {

--- a/services/sync/tests/unit/test_keys.js
+++ b/services/sync/tests/unit/test_keys.js
@@ -17,32 +17,16 @@ function sha256HMAC(message, key) {
 
 function do_check_keypair_eq(a, b) {
   Assert.equal(2, a.length);
   Assert.equal(2, b.length);
   Assert.equal(a[0], b[0]);
   Assert.equal(a[1], b[1]);
 }
 
-add_task(async function test_time_keyFromString() {
-  const iterations = 1000;
-  let o;
-  let b = new BulkKeyBundle("dummy");
-  let d = Utils.decodeKeyBase32("ababcdefabcdefabcdefabcdef");
-  await b.generateRandom();
-
-  _("Running " + iterations + " iterations of hmacKeyObject + sha256HMAC.");
-  for (let i = 0; i < iterations; ++i) {
-    let k = b.hmacKeyObject;
-    o = sha256HMAC(d, k);
-  }
-  Assert.ok(!!o);
-  _("Done.");
-});
-
 add_test(function test_set_invalid_values() {
   _("Ensure that setting invalid encryption and HMAC key values is caught.");
 
   let bundle = new BulkKeyBundle("foo");
 
   let thrown = false;
   try {
     bundle.encryptionKey = null;

--- a/toolkit/components/extensions/ExtensionStorageSync.jsm
+++ b/toolkit/components/extensions/ExtensionStorageSync.jsm
@@ -105,30 +105,16 @@ function throwIfNoFxA(fxAccounts, action
 }
 
 // Global ExtensionStorageSync instance that extensions and Fx Sync use.
 // On Android, because there's no FXAccounts instance, any syncing
 // operations will fail.
 var extensionStorageSync = null;
 
 /**
- * Utility function to enforce an order of fields when computing an HMAC.
- *
- * @param {KeyBundle} keyBundle  The key bundle to use to compute the HMAC
- * @param {string}    id         The record ID to use when computing the HMAC
- * @param {string}    IV         The IV to use when computing the HMAC
- * @param {string}    ciphertext The ciphertext over which to compute the HMAC
- * @returns {string} The computed HMAC
- */
-function ciphertextHMAC(keyBundle, id, IV, ciphertext) {
-  const hasher = keyBundle.sha256HMACHasher;
-  return CommonUtils.bytesAsHex(Utils.digestUTF8(id + IV + ciphertext, hasher));
-}
-
-/**
  * Get the current user's hashed kB.
  *
  * @param {FXAccounts} fxaService  The service to use to get the
  *     current user.
  * @returns {string} sha256 of the user's kB as a hex string
  */
 const getKBHash = async function(fxaService) {
   const signedInUser = await fxaService.getSignedInUser();
@@ -159,17 +145,19 @@ class EncryptionRemoteTransformer {
     let id = await this.getEncodedRecordId(record);
     if (!id) {
       throw new Error("Record ID is missing or invalid");
     }
 
     let IV = WeaveCrypto.generateRandomIV();
     let ciphertext = await WeaveCrypto.encrypt(JSON.stringify(record),
                                                keyBundle.encryptionKeyB64, IV);
-    let hmac = ciphertextHMAC(keyBundle, id, IV, ciphertext);
+    let rawHMAC = await WeaveCrypto.sign(id + IV + ciphertext,
+                                         keyBundle.hmacKeyB64);
+    let hmac = CommonUtils.bytesAsHex(rawHMAC);
     const encryptedResult = {ciphertext, IV, hmac, id};
 
     // Copy over the _status field, so that we handle concurrency
     // headers (If-Match, If-None-Match) correctly.
     // DON'T copy over "deleted" status, because then we'd leak
     // plaintext deletes.
     encryptedResult._status = record._status == "deleted" ? "updated" : record._status;
     if (record.hasOwnProperty("last_modified")) {
@@ -184,20 +172,21 @@ class EncryptionRemoteTransformer {
       // This can happen for tombstones if a record is deleted.
       if (record.deleted) {
         return record;
       }
       throw new Error("No ciphertext: nothing to decrypt?");
     }
     const keyBundle = await this.getKeys();
     // 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);
+    let matches = await WeaveCrypto.verify(CommonUtils.hexToBytes(record.hmac),
+                                           record.id + record.IV + record.ciphertext,
+                                           keyBundle.hmacKeyB64);
+    if (!matches) {
+      Utils.throwHMACMismatch(record.hmac, /* is */ null);
     }
 
     // Handle invalid data here. Elsewhere we assume that cleartext is an object.
     let cleartext = await WeaveCrypto.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.");

--- a/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync_crypto.js
+++ b/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync_crypto.js
@@ -54,18 +54,18 @@ class StaticKeyEncryptionRemoteTransform
 
   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)),
+  hmacKeyB64: btoa(STRETCHED_KEY.slice(0, 32)),
 };
 const transformer = new StaticKeyEncryptionRemoteTransformer(KEY_BUNDLE);
 
 add_task(async function test_encryption_transformer_roundtrip() {
   const POSSIBLE_DATAS = [
     "string",
     2,          // number
     [1, 2, 3],  // array