-----Original Message-----
From: wikitech-l-bounces(a)lists.wikimedia.org
[mailto:wikitech-l-bounces@lists.wikimedia.org] On Behalf Of
Tim Starling
Sent: 19 August 2010 07:37
To: wikitech-l(a)lists.wikimedia.org
Subject: [Wikitech-l] New password hashing proposal
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:9441ccffe8f1afd8c277f4d914ce03c6fcfe15
7457596709d846ff832022b037
-- Tim Starling
[1]
<http://www.theregister.co.uk/2010/08/16/password_security_analysis/>
PHP's crypt has been upgraded in recent times to now include Ulrich
Dreppers' SHA crypt [1]
Certainly mets 1 & 3.
[1]
http://www.akkadia.org/drepper/SHA-crypt.txt
Jared