From dfd046412fc94b7e5788c04a24d2db08480f75c6 Mon Sep 17 00:00:00 2001 From: Ori Livneh Date: Wed, 22 Jun 2016 15:32:58 -0700 Subject: [PATCH] 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 --- includes/resourceloader/ResourceLoader.php | 6 +- resources/Resources.php | 1 - resources/lib/phpjs-sha1/sha1.js | 147 ------------------ resources/src/mediawiki/mediawiki.js | 36 ++++- .../ResourceLoaderStartUpModuleTest.php | 2 +- tests/phpunit/structure/ResourcesTest.php | 2 +- 6 files changed, 35 insertions(+), 159 deletions(-) delete mode 100644 resources/lib/phpjs-sha1/sha1.js diff --git a/includes/resourceloader/ResourceLoader.php b/includes/resourceloader/ResourceLoader.php index 09535b731e..ccf764bc18 100644 --- 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 7f4e132441..8526ec6c57 100644 --- 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 index 93c533d7f8..0000000000 --- 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 335e0bf4e9..942f4aebfa 100644 --- 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 + * + * @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 72ea495999..ea775ae43c 100644 --- 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 5c65c1ef89..6446416109 100644 --- 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" ); } } -- 2.20.1