Bug 610749: add pure-JS PBKDF2 implementation.
authorRichard Newman <rnewman@mozilla.com>
Tue, 16 Nov 2010 11:42:17 -0800
changeset 58406 97f781e762191c77f119e6aae01bcd93ec907aa0
parent 57543 4bc2c08b44b04e32081932d6807f73819c8d26a8
child 58407 780ccd59ff460df8de3d6404cca2f75c36b50943
push id1
push usershaver@mozilla.com
push dateTue, 04 Jan 2011 17:58:04 +0000
bugs610749
Bug 610749: add pure-JS PBKDF2 implementation.
services/sync/modules/base_records/crypto.js
services/sync/modules/service.js
services/sync/modules/util.js
services/sync/tests/unit/test_utils_pbkdf2.js
services/sync/tests/unit/test_utils_sha1hmac.js
--- a/services/sync/modules/base_records/crypto.js
+++ b/services/sync/modules/base_records/crypto.js
@@ -154,18 +154,17 @@ CryptoMeta.prototype = {
         wrapped_key.wrapped,
         privkey.keyData,
         passphrase.passwordUTF8,
         privkey.salt,
         privkey.iv
       )
     );
 
-    unwrappedKey.hmacKey = Svc.KeyFactory.keyFromString(Ci.nsIKeyObject.HMAC,
-      unwrappedKey);
+    unwrappedKey.hmacKey = Utils.makeHMACKey(unwrappedKey);
 
     // Cache the result after the first get and just return it
     return (this.getKey = function() unwrappedKey)();
   },
 
   addKey: function CryptoMeta_addKey(new_pubkey, privkey, passphrase) {
     let symkey = this.getKey(privkey, passphrase);
     this.addUnwrappedKey(new_pubkey, symkey);
@@ -188,17 +187,17 @@ CryptoMeta.prototype = {
     this.keyring[this.uri.getRelativeSpec(new_pubkey.uri)] = {
       wrapped: wrapped,
       hmac: Utils.sha256HMAC(wrapped, this.hmacKey)
     };
   },
 
   get hmacKey() {
     let passphrase = ID.get("WeaveCryptoID").passwordUTF8;
-    return Svc.KeyFactory.keyFromString(Ci.nsIKeyObject.HMAC, passphrase);
+    return Utils.makeHMACKey(passphrase);
   }
 };
 
 Utils.deferGetSet(CryptoMeta, "payload", "keyring");
 
 Utils.lazy(this, 'CryptoMetas', CryptoRecordManager);
 
 function CryptoRecordManager() {
--- a/services/sync/modules/service.js
+++ b/services/sync/modules/service.js
@@ -1146,18 +1146,17 @@ WeaveSvc.prototype = {
     let response = new Resource(privkey.uri).put(privkey);
     if (!response.success) {
       this._log("Uploading rewrapped private key failed!");
       this._needUpdatedKeys = false;
       return;
     }
 
     // Recompute HMAC for symmetric bulk keys based on UTF-8 encoded passphrase.
-    let oldHmacKey = Svc.KeyFactory.keyFromString(Ci.nsIKeyObject.HMAC,
-                                                  this.passphrase);
+    let oldHmacKey = Utils.makeHMACKey(this.passphrase);
     let enginesToWipe = [];
 
     for each (let engine in Engines.getAll()) {
       let meta = CryptoMetas.get(engine.cryptoMetaURL);
       if (!meta)
         continue;
 
       this._log.debug("Recomputing HMAC for key at " + engine.cryptoMetaURL
--- a/services/sync/modules/util.js
+++ b/services/sync/modules/util.js
@@ -476,17 +476,17 @@ let Utils = {
       tmp = frame.name + "()@" + tmp;
 
     return tmp;
   },
 
   exceptionStr: function Weave_exceptionStr(e) {
     let message = e.message ? e.message : e;
     return message + " " + Utils.stackTrace(e);
- },
+  },
 
   stackTraceFromFrame: function Weave_stackTraceFromFrame(frame) {
     let output = [];
     while (frame) {
       let str = Utils.formatFrame(frame);
       if (str)
         output.push(str);
       frame = frame.caller;
@@ -558,26 +558,137 @@ let Utils = {
 
   sha1: function sha1(message) {
     return Utils.bytesAsHex(Utils._sha1(message));
   },
 
   sha1Base32: function sha1Base32(message) {
     return Utils.encodeBase32(Utils._sha1(message));
   },
+  
+  /**
+   * Produce an HMAC key object from a key string.
+   */
+  makeHMACKey: function makeHMACKey(str) {
+    return Svc.KeyFactory.keyFromString(Ci.nsIKeyObject.HMAC, str);
+  },
+    
+  /**
+   * Produce an HMAC hasher.
+   */
+  makeHMACHasher: function makeHMACHasher() {
+    return Cc["@mozilla.org/security/hmac;1"]
+             .createInstance(Ci.nsICryptoHMAC);
+  },
 
   /**
+   * Generate a sha1 HMAC for a message, not UTF-8 encoded,
+   * and a given nsIKeyObject.
+   * Optionally provide an existing hasher, which will be 
+   * initialized and reused.
+   */
+  sha1HMACBytes: function sha1HMACBytes(message, key, hasher) {
+    let h = hasher || this.makeHMACHasher();
+    h.init(h.SHA1, key);
+    
+    // No UTF-8 encoding for you, sunshine.
+    let bytes = [b.charCodeAt() for each (b in message)];
+    h.update(bytes, bytes.length);
+    return h.finish(false);
+  },
+  
+  /**
    * Generate a sha256 HMAC for a string message and a given nsIKeyObject
    */
   sha256HMAC: function sha256HMAC(message, key) {
-    let hasher = Cc["@mozilla.org/security/hmac;1"].
-      createInstance(Ci.nsICryptoHMAC);
+    let hasher = this.makeHMACHasher();
     hasher.init(hasher.SHA256, key);
     return Utils.bytesAsHex(Utils.digest(message, hasher));
   },
+  
+  
+  /**
+   * PBKDF2 implementation in Javascript.
+   */
+  /* For HMAC-SHA-1 */
+  _hLen : 20,
+  
+  _arrayToString : function _arrayToString(arr) {
+    let ret = '';
+    for (let i = 0; i < arr.length; i++) {
+      ret += String.fromCharCode(arr[i]);
+    }
+    return ret;
+  },
+  
+  _XOR : function _XOR(a, b, isA) {
+    if (a.length != b.length) {
+      return false;
+    }
+
+    let val = [];
+    for (let i = 0; i < a.length; i++) {
+      if (isA) {
+        val[i] = a[i] ^ b[i];
+      } else {
+        val[i] = a.charCodeAt(i) ^ b.charCodeAt(i);
+      }
+    }
+
+    return val;
+  },
+  
+  _F : function _F(PK, S, c, i, h) {
+    let ret;
+    let U = [];
+
+    /* Encode i into 4 octets: _INT */
+    let I = [];
+    I[0] = String.fromCharCode((i >> 24) & 0xff);
+    I[1] = String.fromCharCode((i >> 16) & 0xff);
+    I[2] = String.fromCharCode((i >> 8) & 0xff);
+    I[3] = String.fromCharCode(i & 0xff);
+
+    U[0] = this.sha1HMACBytes(S + I.join(''), PK, h);
+    for (let j = 1; j < c; j++) {
+      U[j] = this.sha1HMACBytes(U[j - 1], PK, h);
+    }
+
+    ret = U[0];
+    for (j = 1; j < c; j++) {
+      ret = this._arrayToString(this._XOR(ret, U[j]));
+    }
+
+    return ret;
+  },
+
+  /* PKCS #5, v2.0 pp. 9-10 */
+  pbkdf2Generate : function pbkdf2Generate(P, S, c, dkLen) {
+    let l = Math.ceil(dkLen / this._hLen);
+    let r = dkLen - ((l - 1) * this._hLen);
+
+    // Reuse the key and the hasher. Remaking them 4096 times is 'spensive.
+    let PK = this.makeHMACKey(P);
+    let h = this.makeHMACHasher();
+    
+    T = [];
+    for (let i = 0; i < l;) {
+      T[i] = this._F(PK, S, c, ++i, h);
+    }
+
+    let ret = '';
+    for (i = 0; i < l-1;) {
+      ret += T[i++];
+    }
+    ret += T[l - 1].substr(0, r);
+
+    return ret;
+  },
+  
+
 
   /**
    * Base32 encode (RFC 4648) a string
    */
   encodeBase32: function encodeBase32(bytes) {
     const key = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
     let quanta = Math.floor(bytes.length / 5);
     let leftover = bytes.length % 5;
new file mode 100644
--- /dev/null
+++ b/services/sync/tests/unit/test_utils_pbkdf2.js
@@ -0,0 +1,11 @@
+// Evil.
+let btoa = Cu.import("resource://services-sync/util.js").btoa;
+
+function run_test() {
+  let symmKey16 = Utils.pbkdf2Generate("secret phrase", "DNXPzPpiwn", 4096, 16);
+  do_check_eq(symmKey16.length, 16);
+  do_check_eq(btoa(symmKey16), "d2zG0d2cBfXnRwMUGyMwyg==");
+  do_check_eq(Utils.encodeBase32(symmKey16), "O5WMNUO5TQC7LZ2HAMKBWIZQZI======");
+  let symmKey32 = Utils.pbkdf2Generate("passphrase", "salt", 4096, 32);
+  do_check_eq(symmKey32.length, 32);
+}
new file mode 100644
--- /dev/null
+++ b/services/sync/tests/unit/test_utils_sha1hmac.js
@@ -0,0 +1,66 @@
+Cu.import("resource://services-sync/util.js");
+
+function _hexToString(hex) {
+  var ret = '';
+  if (hex.length % 2 != 0) {
+    return false;
+  }
+
+  for (var i = 0; i < hex.length; i += 2) {
+    var cur = hex[i] + hex[i + 1];
+    ret += String.fromCharCode(parseInt(cur, 16));
+  }
+  return ret;
+}
+
+function test_sha1_hmac() {
+  let test_data = 
+   [{test_case:     1,
+     key:           _hexToString("0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b"),
+     key_len:       20,
+     data:          "Hi There",
+     data_len:      8,
+     digest:        "b617318655057264e28bc0b6fb378c8ef146be00"},
+
+    {test_case:     2,
+     key:           "Jefe",
+     key_len:       4,
+     data:          "what do ya want for nothing?",
+     data_len:      28,
+     digest:        "effcdf6ae5eb2fa2d27416d5f184df9c259a7c79"}];
+  
+  let d;
+  // Testing repeated hashing.
+  d = test_data[0];
+  do_check_eq(Utils.bytesAsHex(Utils.sha1HMACBytes(d.data, Utils.makeHMACKey(d.key))), d.digest);
+  d = test_data[1];
+  do_check_eq(Utils.bytesAsHex(Utils.sha1HMACBytes(d.data, Utils.makeHMACKey(d.key))), d.digest);
+  d = test_data[0];
+  do_check_eq(Utils.bytesAsHex(Utils.sha1HMACBytes(d.data, Utils.makeHMACKey(d.key))), d.digest);
+  d = test_data[1];
+  do_check_eq(Utils.bytesAsHex(Utils.sha1HMACBytes(d.data, Utils.makeHMACKey(d.key))), d.digest);
+  let kk = Utils.makeHMACKey(d.key);
+  do_check_eq(
+      Utils.bytesAsHex(
+        Utils.sha1HMACBytes(
+          Utils.sha1HMACBytes(
+            Utils.sha1HMACBytes(d.data, kk),
+            kk),
+          kk)),
+      Utils.bytesAsHex(
+        Utils.sha1HMACBytes(
+          Utils.sha1HMACBytes(
+            Utils.sha1HMACBytes(d.data, kk),
+            kk),
+          kk)));
+  
+  d = test_data[0];
+  kk = Utils.makeHMACKey(d.key);
+  do_check_eq(Utils.bytesAsHex(Utils.sha1HMACBytes(d.data, kk)), d.digest);
+  do_check_eq(Utils.bytesAsHex(Utils.sha1HMACBytes(d.data, kk)), d.digest);
+}
+
+function run_test() {
+  test_sha1_hmac();
+}
+