Re: MD5 To Be Considered Harmful Someday

[Solar Designer <solar () openwall com>]

On Tue, Dec 07, 2004 at 10:36:27PM -0600, Gandalf The White wrote:
> What I am worried about is the integrity of MD5 hashed passwords.  This
> concern is for both Cisco and *NIX passwords.  Lets say that I have a
> password:
> "ThisIsMySecretPassphrase" MD5 = $1$Vjuf$t5QYnzXL0Sy4tThvqKDGa1

Do not worry, these FreeBSD-style MD5-based crypt(3) hashes are at no
added risk given the recent discovery (which, by the way, was expected).

The algorithm is far more complicated than "raw" MD5.  It consists of
1000 iterations of MD5 with both output from the previous iteration
and the original input (plaintext password and salt) being rolled into
the hash on each iteration.

> It actually
> is beginning to sound like there might be enough of a hole in MD5 that "we"
> (collectively) had better start working on SHA-2 hashed passwords ...

No.

It's been wrong to directly use raw MD5 (or SHA-1 or whatever fast
message digest function) for password hashing anyway.

The choice of the underlying cryptographic primitive (be it a message
digest function such as MD5 or a block cipher such as DES or Blowfish)
has very little impact on the security of a decent password hashing
algorithm.  It's the higher-level algorithm which is of more importance.

The best currently widely-deployed password hashing algorithm is
bcrypt by David Mazieres and Niels Provos.  The most important
property of bcrypt is that it is adaptable to future processor
performance improvements, allowing you to arbitrarily increase the
processing cost of checking a password while still maintaining
compatibility with your older password hashes.  Already now bcrypt
hashes you would use are several orders of magnitude stronger than
traditional Unix DES-based or FreeBSD-style MD5-based hashes.

Niels originally implemented bcrypt for OpenBSD (which uses bcrypt by
default) and that code has since been rolled into FreeBSD and NetBSD
(but still not enabled by default?!)  My public domain, faster(*), and
reentrant re-implementation of it and related links are available at:

        http://www.openwall.com/crypt/

This implementation is currently fully integrated into Owl and
distributions by ALT Linux team, as the default password hashing
scheme.  It is a part of the glibc package on ASPLinux and SuSE Linux.

(*) In this context, faster means slightly more secure since a 2x
speedup translates to twice higher iteration counts to be set by a
system administrator and thus effective strength of passwords
stretched by 1 bit more.

-- 
Alexander Peslyak <solar at openwall.com>
GPG key ID: B35D3598  fp: 6429 0D7E F130 C13E C929  6447 73C3 A290 B35D 3598
http://www.openwall.com - bringing security into open computing environments