Message-ID: <20120609133036.GA4771@openwall.com>
Date: Sat, 9 Jun 2012 17:30:36 +0400
From: Solar Designer <solar@...nwall.com>
To: bugtraq@...urityfocus.com
Cc: phk@...eBSD.org
Subject: Re: CVE-2012-3287: md5crypt is no longer considered safe

On Fri, Jun 08, 2012 at 12:04:49AM +0000, phk@...eBSD.org wrote:
> The LinkedIn password incompetence has resulted in a number of "just use md5crypt and you'll be fine" pieces of advice on the net.
> 
> Since I no longer consider this to be the case, I have issued an official statement, as the author of md5crypt, to the opposite effect:
> 
> http://phk.freebsd.dk/sagas/md5crypt_eol.html
> 
> Please find something better now.

Thank you for posting this - it was interesting to learn of your opinion
on the matter after all those years!  Ditto re: "The history of md5crypt":

http://phk.freebsd.dk/sagas/md5crypt.html

Now, since some people are in fact still using md5crypt, they'll think
of what to move to.  You almost recommend them to roll their own - a
recommendation I disagree with (as we've already discussed off-list).

The main options are bcrypt and SHA-crypt.  Many would recommend scrypt
instead - for good reasons - but there's no crypt(3) interface for it
yet, also for good reasons, e.g.:
http://www.openwall.com/lists/crypt-dev/2011/05/12/4

Personally, I think that bcrypt and SHA-crypt are quite close to
becoming obsolete in favor of something new, yet right now I would still
recommend moving to bcrypt as the most suitable pre-existing password
hashing method.  So if you're to move to something "temporary" at all,
better move to a password hashing method already in use - and for now
this should be bcrypt - than roll your own.  (My opinion only, indeed.
Someone else may disagree.)

What's wrong with bcrypt, though?  Mainly two things, I think:

1. Not enough natural parallelism in one instance (so that it could be
made use of by an authentication server and not only by an attacker,
who always has plenty of parallelism due to having lots of candidate
passwords to try).  I started complaining about this around 1998, but
this problem was not pressing enough to introduce yet another password
hashing method so far.  The speedup from extra parallelism available to
attacker only is up to a factor of 2 on typical CPUs so far (due to
instruction level parallelism only, but not SIMD).  However, I expect
this to change with AVX2 VSIB addressing (gather) next year, which
appears to allow for parallel computation of 8 bcrypt hashes in 256-bit
vectors - by attacker only.  There may be fewer vector units than ALUs,
though, so the speedup over what the attacker currently has (already up
to 2x faster than defender) will likely be significantly less than 8x.

2. The memory requirement of 4 KB is not configurable and is rather
low - barely enough to defeat GPUs so far, but this may change, and
there may be other hardware-based attacks.  So far, experimental John
the Ripper patches by Sayantan Datta achieve CPU-like performance at
bcrypt on AMD Radeon HD 7970 (we have to either use the slow global
memory or explicitly heavily under-utilize the GPU's computing resources
so that the smaller number of concurrent bcrypt computations fits in
local memory), but there's room for improvement:
http://www.openwall.com/lists/john-dev/2012/06/06/1
(The c/s rates are for $2a$05, used as baseline for historical reasons;
for comparison, AMD FX-8120 CPU provides approx. 5400 c/s at that setting,
which is slightly faster than the GPU so far.)  I expect that
significant speedup over CPU may be demonstrated soon (just not as
significant as it is for MD5, etc.)  Here are some very rough estimates
for the potential speedup:
http://www.openwall.com/lists/john-dev/2012/05/14/1

What's wrong with SHA-crypt?  It's similar, but worse:

1. Not enough natural parallelism in one instance.  Well, at least it
uses 64-bit integers (the flavor based on SHA-512), whereas bcrypt is
32-bit only, but on the other hand in addition to extra instruction
level parallelism while cracking we can also use SIMD (on current CPUs
already, even though this is not implemented yet).

2. Almost no memory requirements.  The register pressure is a bit high
for GPUs, but not to the point where GPUs would not provide an advantage.

So far, SHA-crypt at its default rounds=5000 is crackable on a GPU at
more than 10x the speed of bcrypt at comparable settings ($2a$08, which
is default on some systems), due to John the Ripper patch by Claudio Andre:
http://www.openwall.com/presentations/PHDays2012-Password-Security/mgp00037.html

Thus, out of these two bcrypt wins, and the rest are either worse or not
yet ready for end-user consumption (sysadmin, web app author, etc.)

<plug>
(OK, I already plugged some links to openwall.com pages above, but this
is getting too much, hence the tags.)

I made a talk on this topic at PHDays last week.  Here are the slides:

http://www.openwall.com/presentations/PHDays2012-Password-Security/

I give some historical background on password security with focus on
password hashing (1960s to 2012), and then in the last 9 slides I share
some thoughts on the future:

Desirable properties of a future KDF
KDFs unfriendly to hardware we do not have
CPU + RAM friendliness
GPU friendliness
FPGA/ASIC friendliness
Local parameter
Unreadable local parameter
KDFs in scripting languages (future phpass)
Need to resist the temptation

<shameless>
Companies with large user databases (like LinkedIn's) and adequate IT
security budgets could use this approach (on top of other measures):

http://www.openwall.com/presentations/PHDays2012-Password-Security/mgp00050.html

(Move password hashing to HSMs or to servers separate from password
authentication servers, store a local parameter there.)  We (Openwall)
would be happy to help these companies implement that (and more).
</shameless>
</plug>

Alexander

Powered by blists - more mailing lists