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/>
[2]
http://www.insidepro.com/eng/egb.shtml