It's been said (e.g. [1]) that hashing passwords with two rounds of MD5 is basically a waste of time these days, because brute-forcing even relatively long passwords is now feasible with cheap hardware. Indeed, you can buy software [2] which claims to be able to check 90 million MediaWiki passwords per second on an ordinary GPU. That would let you crack a random 8-letter password in 20 minutes.
So the time has probably come for us to come up with a "C" type password hashing scheme, to replace the B-type hashes that we use at the moment. I've been thinking along the lines of the following goals:
1. Future-proof: should be adaptable to faster hardware. 2. Upgradeable: it should be possible to compute the C-type hash from the B-type hash, to allow upgrades without bothering users. 3. Efficient in PHP, with default configure options. 4. MediaWiki-specific, so that generic software can't be used to crack our hashes.
The problem with the standard key strengthening algorithms, e.g. PBKDF1, is that they are not efficient in PHP. We don't want a C implementation of our scheme to be orders of magnitude faster than our PHP implementation, because that would allow brute-forcing to be more feasible than is necessary.
The idea I came up with is to hash the output of str_repeat(). This increases the number of rounds of the compression function, while avoiding tight loops in PHP code.
PHP's hash extension has been available by default since PHP 5.1.2, and we can always fall back to using B-type hashes if it's explicitly disabled. The WHIRLPOOL hash is supported. It has no patent or copyright restrictions so it's not going to be yanked out of Debian or PHP for legal reasons. It has a 512-bit block size, the largest of any hash function available in PHP, and its security goals state that it can be truncated without compromising its properties.
My proposed hash function is a B-type MD5 salted hash, which is then further hashed with a configurable number of invocations of WHIRLPOOL, with a 256-bit substring taken from a MediaWiki-specific location. The input to each WHIRLPOOL operation is expanded by a factor of 100 with str_repeat().
The number of WHIRLPOOL iterations is specified in the output string as a base-2 logarithm (whimsically padded out to 3 decimal digits to allow for future universe-sized computers). This number can be upgraded by taking the hash part of the output and applying more rounds to it. A count of 2^7 = 128 gives a time of 55ms on my laptop, and 12ms on one of our servers, so a reasonable default is probably 2^6 or 2^7.
Demo code: http://p.defau.lt/?udYa5CYhHFrgk4SBFiTpGA
Typical output: :C:007:187aabf399e25aa1:9441ccffe8f1afd8c277f4d914ce03c6fcfe157457596709d846ff832022b037
-- Tim Starling
[1] http://www.theregister.co.uk/2010/08/16/password_security_analysis/