Onderwerp: MD5 To Be Considered Harmful Someday

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

Paul Wouters wrote:

> On Tue, 7 Dec 2004, Gandalf The White wrote:
>
>> What I am worried about is the integrity of MD5 hashed passwords. This
>
>
>> It does not matter that I don't know the correct password, I have a
>> password
>> that collides into the correct hash. I can log into the system with my
>> generated password.
>
>
> Can't we just truncate the password to 8 characters like in the old days
> before doing the MD5 hash? It will greatly reduce the chance of a
> collision.
> In fact, I am not even sure my systems don't do this already.
>
Actually, this greatly increases the chance of a collision. 123456789
will collide with 123456780.

It is unlikely we'll find any ASCII readable payload that collide
through Wang's search technique.

--Dan

On Tue, Dec 07, 2004 at 06:51:48PM -0700, Joel Maslak wrote:
> That can be a problem. It breaks non-repudiation - someone could create
> such a "swappable" contract and go to court and say "Yes, that's a valid
> signature, but I really signed *THIS* document which just happens to have
> an identical signature." Of course if I was called upon to testify, I
> would respond, "Yes, but it is clear this contract was written with the
> intent to defraud us, as to get this property, it has to be constructed in
> a very specific mind with this fraud in mind at time of contract
> origination..."

Bruce Schneier has long suggested that when signing a document made by
others, make some cosmetic changes to break any precomputed hash that
the creator might have in store for you.

Also: those who are not fully up to speed on the details of crypto hashes
might find my Tech Tip helpful:

An Illustrated Guide to Cryptographic Hashes
http://www.unixwiz.net/techtips/igui...to-hashes.html

Steve

--
Stephen J Friedl | Security Consultant | UNIX Wizard | +1 714 544-6561
www.unixwiz.net | Tustin, Calif. USA | Microsoft MVP | steve@unixwiz.net

On Tue, 7 Dec 2004, Tim wrote:

> Due to the slowness of public key, most digital signatures are
> performed on a digest of the original document.

I think it's time to change the way we do digital signatures to
compute several hashes of the original document using different
algorithms (SHA1, MD5, ...) and sign the concatenation of the resulting
digests. Does any standard signing software do this yet?

Also, it's probably a good idea to alter in some small and
unpredictable way anything that you're asked to sign. (Add some
spaces, add text like "Signed by David F. Skoll", etc.) This makes it
impossible to precompute two versions that hash to the same value,
though it's still not very good protection if it becomes easy to find
MD5 collisions.

Regards,

David.

On Tue, Dec 07, 2004 at 06:46:20PM -0700, Joel Maslak wrote:

> The short-term fix seems to be something I've been recommending for a
> while:
>
> Compute hashes with both SHA-1 and MD5.
>
> The chance of one algorithm becoming compromised in the mid-term is
> relatively high IMHO (I was responsible for a PKI system which had to keep
> integrity for 20 year periods of time - not an easy task considering what
> we don't know about the future). The chance of two becoming compromised
> is relatively less. The chance of a problem with MD5 and SHA-1 allowing
> two different files to have collisions in both algorithms in *BOTH* is
> very very small.

Actually there are without a doubt many files where MD5 and SHA-1 both collide;
this is a simple result from the fact that you have nearly arbitrary sized
inputs (up to 2^61 bytes) and a very small output. Even if you idealize
MD5||SHA as a 288 bit hash function, you get collisions after ~2^144 tests by
the birthday paradox, same as any other hash. Which I suppose counts as very
very small, and is probably sufficient for 20 year security, but that estimate
ignores the fact that MD5||SHA is not an ideal 288 bit hash.

The most obvious example of that is that by using one of the known MD5
collision pairs, you can cause 5/9 of the hash output to change while keeping
the rest of the hash constant. While this is not a problem when the hash is
merely a hash, it does mean you can't realistically model it as a PRF.

I wouldn't be surprised if there is some way to break this much faster than
2^144 by taking advantage of the fact that you can compute each half of the
hash independently of the other, but I can't think of a convincing argument for
this at the moment.

Jack

On Wed, Dec 08, 2004 at 09:48:00PM +0100, Paul Wouters wrote:
| On Tue, 7 Dec 2004, Gandalf The White wrote:
|
| >What I am worried about is the integrity of MD5 hashed passwords. This
|
| >It does not matter that I don't know the correct password, I have a
| >password
| >that collides into the correct hash. I can log into the system with my
| >generated password.
|
| Can't we just truncate the password to 8 characters like in the old days
| before doing the MD5 hash? It will greatly reduce the chance of a collision.
| In fact, I am not even sure my systems don't do this already.

Just what I want! 8 character passwords on *your* systems.

Adam

On Tue, 7 Dec 2004, Joel Maslak wrote:

> The short-term fix seems to be something I've been recommending for a
> while:
>
> Compute hashes with both SHA-1 and MD5.

Incidentally, this is the method used by SSL/TLS. But they don't
concatentate hash values, they xor them together.


On Wed, 8 Dec 2004, Jack Lloyd wrote:

> The most obvious example of that is that by using one of the known MD5
> collision pairs, you can cause 5/9 of the hash output to change while
> keeping the rest of the hash constant. While this is not a problem
> when the hash is merely a hash, it does mean you can't realistically
> model it as a PRF.

If you mix the results with xor (or other function having similar
properties), then the result is PRF as long as at least one of
constituent functions is PRF.

Of course, I assume the constituent functions return the same number of
bits. When you take MD5 (128 bits) and SHA1 (160 bits) then you have to
either expand the result of MD5 or to truncate the result of SHA1 to make
them match.


On Wed, 8 Dec 2004, Jack Lloyd wrote:

> It actually looks like it's better to generate 2^80 MD5 collisions
> instead of 2^64 SHA-1 collisions, since the initial collisions would
> be trivial to generate, and even if MD5 wasn't broken 80*2^64 + 2^80
> << 64*2^80 + 2^64. So in fact you can generate a MD5||SHA collision
> with only a tiny bit more work than generating a SHA collision.

This means xor is no worse than concatenation.


> So this really doesn't buy you anything.

This buys you some level of resistance against specific weaknesses in hash
algorithms like the recent Chinese attacks against MD5 et al.

When you take two (or more) functions built in a different way
(unfortunately, this is not true for most of commonly used hash functions)
and combine their results properly then it is likely there will be a
strong "impedance mismatch" between their weaknesses and it will be very
difficult to break both of them simultanously.


On Sun, 5 Dec 2004, Ruth A. Kramer wrote:

> 3. At one point I read the thesis of the guy that wrote rsync (is name
> isn't on the tip of my tongue at the moment, that's embarrassing) -- I
> was fairly disappointed (and surprised) to find that the reliability of
> rsync relied on a similar "probalistic" approach (can't find the right
> words). As I recall, this was not mentioned on the first page of his
> thesis (I could be wrong), the README for rsync, nor as a user message
> when the program is invoked. IIRC, when the subject was brought up in
> his thesis, it was effectively dismissed as "it'll never happen". (The
> words invoked, if not actually used, phrases like "the heat death of the
> universe".)

Rsync trades the risk of hitting a collision for the reduction of data it
has to transfer over the network.

The only way to avoid the risk of hash collision is to transfer
everything--but the more data you transfer, the higher is the risk it
will be corrupted en route (download a handful of terabytes over FTP,
i.e. relying on TCP checksums only, and you'll see...).

It's always the "probabilistic approach".


On Wed, 8 Dec 2004, Dan Kaminsky wrote:

> There are, however, others that abuse extra rounds to great effect.
> For instance, SHA-0 is an 80 round algorithm. Biham's paper
> (http://eprint.iacr.org/2004/146/) showed that an 82 round variant is
> actually much weaker.

Yes...but the algorithm for MD5 password hashes does not add additional
rounds to the hash.

It iterates the whole hash function in a way similar to its ordinary use
on multi-block input (i.e. iterated invocation of its compression function
with a predefined initial value on one end, and Merkle-Damgaard padding on
the other end).

> Of course, as I've said elsewhere passwords really aren't at all
> vulnerable to the MD5 attack. But, if they were, extra iterations
> wouldn't be helpful. Once the first round collided, all future rounds
> would continue to collide.

The iterations are not uniform. There are 2*3*7 = 42 different ways
additional input (password plaintext, salt) is fed into the hash.


--Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."

On Wed, Dec 08, 2004 at 02:03:56PM -0800, Dan Kaminsky wrote:
> Brute force work efforts like password cracking tend to be an
> exponential times a constant -- say, 2^32 operations that take 100ms
> each. Increasing the complexity of a legitimate password verification
> increases the constant. Interestingly, the more efficient a legitimate
> verifier becomes, the more efficient your brute forcer is.

Well, it can be assumed that an attacker could always have used the
better optimized implementation in a brute-forcer.

But there's more to it. Legitimate verifiers (using your terminology -
which I like) will always remain slower than optimal cracker programs.
The primary factor which makes for the difference in favor of
password cracking is the extra parallelism which may be brought down
to instruction level (to make more effective use of resources of a
non-special-purpose CPU). For bcrypt, there's already a 2x difference
(cracking twice faster than verification) between potential optimal
implementations on some newer real-world CPUs (Itanium).

On the FreeBSD-style MD5-based password hashing:

> Of course, as I've said elsewhere passwords really aren't at all
> vulnerable to the MD5 attack.

Yes. I did not want to bring the argument that there's still no way
to produce a message for a given/fixed MD5 hash with little effort.
I felt that the argument I did make is stronger. But you seem to feel
otherwise. :-)

> But, if they were, extra iterations wouldn't be helpful.

This is not simply extra iterations of MD5, re-using _only_ output from
a previous iteration as input for a new one (if this was so, then your
statement would be precisely correct).

> Once the first round collided, all future rounds would continue to
> collide.

Not in phk's algorithm we're talking about. Somewhat simplifying
things, let's say the first iteration would collide for {password1,
salt} and {password2, salt}. But the second iteration would have
something like {C1, password1, salt} and {C1, password2, salt} as its
input, and subsequent iterations would use things like {password1,
salt, password1, C2} and {password2, salt, password2, C2'} (notice
the changes in ordering of inputs). We can't be sure whether
C2 = C2' or whether subsequent iterations would collide or not based
exclusively on the fact that the first iteration collided.

--
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