resourceloader: Replace SHA1 with 32-bit FNV-1 as hash function

SHA-1 is not secure enough to be used as a cryptographic hash function, and its
implementation in JavaScript is too long and too slow for it to be a good
general-purpose hash function. And we currently throw away most of the work:
SHA-1 produces 160-bit hash values, of which we keep 48.

Although the JavaScript implementation is not exported, SHA-1 is a well-known
hash function, and I'm willing to bet that sooner or later someone will move to
make it accessible to other modules, at which point usage will start to spread.

For ResourceLoader, the qualities we're looking for in a hash function are:

* Already implemented in PHP
* Easy to implement in JavaScript
* Fast
* Collision-resistant

The requirement that hashes be cheap to compute in JavaScript narrows the field
to 32-bit hash functions, because in JavaScript bitwise operators treat their
operands as 32 bits, and arithmetic uses double-precision floats, which have a
total precision of 53 bits. It's possible to work around these limitations, but
it's a lot of extra work.

The best match I found is the 32-bit variant of FNV-1, which is available in
PHP as of version 5.4 (as 'fnv1a32'). The fnv132 JavaScript function is
around ten times faster and eight times shorter than sha1.

Change-Id: I1e4fb08d17948538d96f241b2464d594fdc14578

diff --git a/includes/resourceloader/ResourceLoader.php b/includes/resourceloader/ResourceLoader.php
index 09535b7..ccf764b 100644 (file)
--- a/includes/resourceloader/ResourceLoader.php
+++ b/includes/resourceloader/ResourceLoader.php
@@ -601,10 +601,8 @@ class ResourceLoader implements LoggerAwareInterface {
         * @return string Hash
         */
        public static function makeHash( $value ) {
-               // Use base64 to output more entropy in a more compact string (default hex is only base16).
-               // The first 8 chars of a base64 encoded digest represent the same binary as
-               // the first 12 chars of a hex encoded digest.
-               return substr( base64_encode( sha1( $value, true ) ), 0, 8 );
+               $hash = hash( 'fnv132', $value );
+               return Wikimedia\base_convert( $hash, 16, 36, 7 );
        }
 
        /**

diff --git a/resources/Resources.php b/resources/Resources.php
index 7f4e132..8526ec6 100644 (file)
--- a/resources/Resources.php
+++ b/resources/Resources.php
@@ -841,7 +841,6 @@ return [
                'class' => 'ResourceLoaderRawFileModule',
                // Keep in sync with maintenance/jsduck/eg-iframe.html
                'scripts' => [
-                       'resources/lib/phpjs-sha1/sha1.js',
                        'resources/src/mediawiki/mediawiki.js',
                        'resources/src/mediawiki/mediawiki.requestIdleCallback.js',
                        'resources/src/mediawiki/mediawiki.errorLogger.js',

diff --git a/resources/lib/phpjs-sha1/sha1.js b/resources/lib/phpjs-sha1/sha1.js
deleted file mode 100644 (file)
index 93c533d..0000000
--- a/resources/lib/phpjs-sha1/sha1.js
+++ /dev/null
@@ -1,147 +0,0 @@
-function sha1(str) {
-  //  discuss at: http://phpjs.org/functions/sha1/
-  // original by: Webtoolkit.info (http://www.webtoolkit.info/)
-  // improved by: Michael White (http://getsprink.com)
-  // improved by: Kevin van Zonneveld (http://kevin.vanzonneveld.net)
-  //    input by: Brett Zamir (http://brett-zamir.me)
-  //   example 1: sha1('Kevin van Zonneveld');
-  //   returns 1: '54916d2e62f65b3afa6e192e6a601cdbe5cb5897'
-
-  var rotate_left = function (n, s) {
-    var t4 = (n << s) | (n >>> (32 - s));
-    return t4;
-  };
-
-  /*var lsb_hex = function (val) {
-   // Not in use; needed?
-    var str="";
-    var i;
-    var vh;
-    var vl;
-
-    for ( i=0; i<=6; i+=2 ) {
-      vh = (val>>>(i*4+4))&0x0f;
-      vl = (val>>>(i*4))&0x0f;
-      str += vh.toString(16) + vl.toString(16);
-    }
-    return str;
-  };*/
-
-  var cvt_hex = function (val) {
-    var str = '';
-    var i;
-    var v;
-
-    for (i = 7; i >= 0; i--) {
-      v = (val >>> (i * 4)) & 0x0f;
-      str += v.toString(16);
-    }
-    return str;
-  };
-
-  var blockstart;
-  var i, j;
-  var W = new Array(80);
-  var H0 = 0x67452301;
-  var H1 = 0xEFCDAB89;
-  var H2 = 0x98BADCFE;
-  var H3 = 0x10325476;
-  var H4 = 0xC3D2E1F0;
-  var A, B, C, D, E;
-  var temp;
-
-  // utf8_encode
-  str = unescape(encodeURIComponent(str));
-  var str_len = str.length;
-
-  var word_array = [];
-  for (i = 0; i < str_len - 3; i += 4) {
-    j = str.charCodeAt(i) << 24 | str.charCodeAt(i + 1) << 16 | str.charCodeAt(i + 2) << 8 | str.charCodeAt(i + 3);
-    word_array.push(j);
-  }
-
-  switch (str_len % 4) {
-  case 0:
-    i = 0x080000000;
-    break;
-  case 1:
-    i = str.charCodeAt(str_len - 1) << 24 | 0x0800000;
-    break;
-  case 2:
-    i = str.charCodeAt(str_len - 2) << 24 | str.charCodeAt(str_len - 1) << 16 | 0x08000;
-    break;
-  case 3:
-    i = str.charCodeAt(str_len - 3) << 24 | str.charCodeAt(str_len - 2) << 16 | str.charCodeAt(str_len - 1) <<
-      8 | 0x80;
-    break;
-  }
-
-  word_array.push(i);
-
-  while ((word_array.length % 16) != 14) {
-    word_array.push(0);
-  }
-
-  word_array.push(str_len >>> 29);
-  word_array.push((str_len << 3) & 0x0ffffffff);
-
-  for (blockstart = 0; blockstart < word_array.length; blockstart += 16) {
-    for (i = 0; i < 16; i++) {
-      W[i] = word_array[blockstart + i];
-    }
-    for (i = 16; i <= 79; i++) {
-      W[i] = rotate_left(W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16], 1);
-    }
-
-    A = H0;
-    B = H1;
-    C = H2;
-    D = H3;
-    E = H4;
-
-    for (i = 0; i <= 19; i++) {
-      temp = (rotate_left(A, 5) + ((B & C) | (~B & D)) + E + W[i] + 0x5A827999) & 0x0ffffffff;
-      E = D;
-      D = C;
-      C = rotate_left(B, 30);
-      B = A;
-      A = temp;
-    }
-
-    for (i = 20; i <= 39; i++) {
-      temp = (rotate_left(A, 5) + (B ^ C ^ D) + E + W[i] + 0x6ED9EBA1) & 0x0ffffffff;
-      E = D;
-      D = C;
-      C = rotate_left(B, 30);
-      B = A;
-      A = temp;
-    }
-
-    for (i = 40; i <= 59; i++) {
-      temp = (rotate_left(A, 5) + ((B & C) | (B & D) | (C & D)) + E + W[i] + 0x8F1BBCDC) & 0x0ffffffff;
-      E = D;
-      D = C;
-      C = rotate_left(B, 30);
-      B = A;
-      A = temp;
-    }
-
-    for (i = 60; i <= 79; i++) {
-      temp = (rotate_left(A, 5) + (B ^ C ^ D) + E + W[i] + 0xCA62C1D6) & 0x0ffffffff;
-      E = D;
-      D = C;
-      C = rotate_left(B, 30);
-      B = A;
-      A = temp;
-    }
-
-    H0 = (H0 + A) & 0x0ffffffff;
-    H1 = (H1 + B) & 0x0ffffffff;
-    H2 = (H2 + C) & 0x0ffffffff;
-    H3 = (H3 + D) & 0x0ffffffff;
-    H4 = (H4 + E) & 0x0ffffffff;
-  }
-
-  temp = cvt_hex(H0) + cvt_hex(H1) + cvt_hex(H2) + cvt_hex(H3) + cvt_hex(H4);
-  return temp.toLowerCase();
-}

diff --git a/resources/src/mediawiki/mediawiki.js b/resources/src/mediawiki/mediawiki.js
index 335e0bf..942f4ae 100644 (file)
--- a/resources/src/mediawiki/mediawiki.js
+++ b/resources/src/mediawiki/mediawiki.js
@@ -8,7 +8,6 @@
  * @singleton
  */
 /*jshint latedef:false */
-/*global sha1 */
 ( function ( $ ) {
        'use strict';
 
@@ -19,6 +18,36 @@
                trackHandlers = [],
                trackQueue = [];
 
+       /**
+        * FNV132 hash function
+        *
+        * This function implements the 32-bit version of FNV-1.
+        * It is equivalent to hash( 'fnv132', ... ) in PHP, except
+        * its output is base 36 rather than hex.
+        * See <https://en.wikipedia.org/wiki/FNV_hash_function>
+        *
+        * @private
+        * @param {string} str String to hash
+        * @return {string} hash as an seven-character base 36 string
+        */
+       function fnv132( str ) {
+               /*jshint bitwise:false */
+               var hash = 0x811C9DC5,
+                       i;
+
+               for ( i = 0; i < str.length; i++ ) {
+                       hash += ( hash << 1 ) + ( hash << 4 ) + ( hash << 7 ) + ( hash << 8 ) + ( hash << 24 );
+                       hash ^= str.charCodeAt( i );
+               }
+
+               hash = ( hash >>> 0 ).toString( 36 );
+               while ( hash.length < 7 ) {
+                       hash = '0' + hash;
+               }
+
+               return hash;
+       }
+
        /**
         * Create an object that can be read from or written to from methods that allow
         * interaction both with single and multiple properties at once.
@@ -931,10 +960,7 @@
                                var hashes = $.map( modules, function ( module ) {
                                        return registry[ module ].version;
                                } );
-                               // Trim for consistency with server-side ResourceLoader::makeHash. It also helps
-                               // save precious space in the limited query string. Otherwise modules are more
-                               // likely to require multiple HTTP requests.
-                               return sha1( hashes.join( '' ) ).slice( 0, 12 );
+                               return fnv132( hashes.join( '' ) );
                        }
 
                        /**

diff --git a/tests/phpunit/includes/resourceloader/ResourceLoaderStartUpModuleTest.php b/tests/phpunit/includes/resourceloader/ResourceLoaderStartUpModuleTest.php
index 72ea495..ea775ae 100644 (file)
--- a/tests/phpunit/includes/resourceloader/ResourceLoaderStartUpModuleTest.php
+++ b/tests/phpunit/includes/resourceloader/ResourceLoaderStartUpModuleTest.php
@@ -5,7 +5,7 @@ class ResourceLoaderStartUpModuleTest extends ResourceLoaderTestCase {
        // Version hash for a blank file module.
        // Result of ResourceLoader::makeHash(), ResourceLoaderTestModule
        // and ResourceLoaderFileModule::getDefinitionSummary().
-       protected static $blankVersion = 'GqV9IPpY';
+       protected static $blankVersion = '0a56zyi';
 
        protected static function expandPlaceholders( $text ) {
                return strtr( $text, [

diff --git a/tests/phpunit/structure/ResourcesTest.php b/tests/phpunit/structure/ResourcesTest.php
index 5c65c1e..6446416 100644 (file)
--- a/tests/phpunit/structure/ResourcesTest.php
+++ b/tests/phpunit/structure/ResourcesTest.php
@@ -40,7 +40,7 @@ class ResourcesTest extends MediaWikiTestCase {
                $data = self::getAllModules();
                foreach ( $data['modules'] as $moduleName => $module ) {
                        $version = $module->getVersionHash( $data['context'] );
-                       $this->assertEquals( 8, strlen( $version ), "$moduleName must use ResourceLoader::makeHash" );
+                       $this->assertEquals( 7, strlen( $version ), "$moduleName must use ResourceLoader::makeHash" );
                }
        }