MD5 To Be Considered Harmful Someday

[Dan Kaminsky]

I've been doing some analysis on MD5 collision announced by Wang et al.
Short version: Yes, Virginia, there is no such thing as a safe hash
collision -- at least in a function that's specified to be
cryptographically secure. The full details may be acquired at the
following link:

http://www.doxpara.com/md5_someday.pdf

A tool, Stripwire, has been assembled to demonstrate some of the attacks
described in the paper. It may be acquired at the following address:

http://www.doxpara.com/stripwire-1.1.tar.gz

Incidentally, the expectations management is by no means accidental --
the paper's titled "MD5 To Be Considered Harmful Someday" for a reason.
Some people have said there's no applied implications to Joux and Wang's
research. They're wrong; arbitrary payloads can be successfully
integrated into a hash collision. But the attacks are not wildly
practical, and in most cases exposure remains thankfully limited, for
now. But the risks are real enough that responsible engineers should
take note: This is not merely an academic threat, systems designed with
MD5 now need to take far more care than they would if they were
employing an unbroken hashing algorithm, and the problems are only going
to get worse.

Some highlights from the paper:

* The attack itself is pretty limited -- essentially, we can create
"doppelganger" blocks (my term) anywhere inside a file that may be
swapped out, one for another, without altering the final MD5 hash. This
lets us create any number of binary-inequal files with the same md5sum.

* MD5 uses an appendable cascade construction -- in other words, if you
happen to find yourself with two files that MD5 to the same hash, an
arbitrary payload can be applied to both files and they'll still have
the same hash. This leads to...

* Attacks are possible using only the proof of concept test vectors
released by Wang -- the actual attack is not necessary.

* Stripwire emits two binary packages. They both contain an arbitrary
payload, but the payload is encrypted with AES. Only one of the
packages ("Fire") is decryptable and thus dangerous; the other ("Ice")
shields its data behind AES. Both files share the same MD5 hash.

* Digital Signature systems are vulnerable, as they almost always sign a
hashed representation of data rather than the data itself.

* This is an excellent vector for malicious developers to get unsafe
code past a group of auditors, perhaps to acquire a required third party
signature. Alternatively, build tools themselves could be compromised
to embed safe versions of dangerous payloads in each build. At some
later point, the embedded payload could be safely "activated", without
the MD5 changing. This has implications for Tripwire, DRM, and several
package management architectures.

* HMAC's invulnerability has been slightly overstated. It's definitely
possible, given the key, to create two datasets with the same HMAC.
Attacker possession of the key violates MAC presumptions, so the impact
of this is particularly questionable.

* Very interesting possibilities open up once the full attack is made
available -- among other things, we can create self-decrypting
executables (fire.exe and ice.exe) that exhibit differential behavior
based on their internal colliding payloads. They'll still have the same
MD5 hash.

* Several doppelgangers may (relatively quickly, as per Joux) be
computed within a single multicollision-friendly block. As such, the
particular selection of doppelganger sets within a file can itself be
made to represent data. It's relatively straightforward to embed a 128
bit signature inside an arbitrary file, in such a way that no matter the
value of the signature, a constant MD5 hash is maintained. This is
curiously steganographic.

* Many popular P2P networks (and innumerable distributed content
databases) use MD5 hashes as both a reliable search handle and a
mechanism to ensure file integrity. This makes them blind to any
signature embedded within MD5 collisions. We can use this blindness to
track MP3 audio data as it propagates from a custom P2P node.
"Strikeback" capacity against executable trafficking is even more
pronounced -- it's possible to create application installers that
self-modify with host identifying characteristics but still successfully
retransmit on P2P networks under the global search hash.

I hope this paper proves useful to the security community at large, and
I welcome feedback.

--Dan Kaminsky
www.doxpara.com
dan@doxpara.com

[Gandalf The White]

Greetings and Salutations:

On 12/6/04 5:29 PM, "Dan Kaminsky" <dan@doxpara.com> wrote:
<snip>
> Some highlights from the paper:
> * The attack itself is pretty limited -- essentially, we can create
> "doppelganger" blocks (my term) anywhere inside a file that may be
> swapped out, one for another, without altering the final MD5 hash. This
> lets us create any number of binary-inequal files with the same md5sum.

From my reading it appears that you need the original source to create the
doppelganger blocks. It also appears that given a MD5 hash you could not
create a input that would give that MD5 back. Passwords encoded with MD5
would not fall prey to your discovery. Is this correct?

Unfortunately when "The Press" publicized the MD5 hash discovery by Joux and
Wang it almost sounded like "The Press" was surprised to find collisions in
the MD5 domain (intuitive to me, a limited number of outputs and a infinite
number of inputs = Collisions). I assume that a "good" hash would have a
even distribution of collisions across the domain and that the larger number
of bits for the output the better the hash (assuming no cryptographic
algorithm errors).

Thanks,
Ken

---------------------------------------------------------------
Do not meddle in the affairs of wizards for they are subtle and
quick to anger.
Ken Hollis - Gandalf The White - gandalf@digital.net - O- TINLC
WWW Page - http://digital.net/~gandalf/
Trace E-Mail forgery - http://digital.net/~gandalf/spamfaq.html
Trolls crossposts - http://digital.net/~gandalf/trollfaq.html

[Tim]

> From my reading it appears that you need the original source to create the
> doppelganger blocks. It also appears that given a MD5 hash you could not
> create a input that would give that MD5 back. Passwords encoded with MD5
> would not fall prey to your discovery. Is this correct?

Correct, it sounds as though the attacks are not a first preimage
attack. However, first preimage resistance is a necessary but not
sufficient condition for security. I have not read the paper yet, but I
imagine most of these results would imply either second preimage, or
collision insecurity.

> Unfortunately when "The Press" publicized the MD5 hash discovery by Joux and
> Wang it almost sounded like "The Press" was surprised to find collisions in
> the MD5 domain (intuitive to me, a limited number of outputs and a infinite
> number of inputs = Collisions). I assume that a "good" hash would have a
> even distribution of collisions across the domain and that the larger number
> of bits for the output the better the hash (assuming no cryptographic
> algorithm errors).

Yes, collisions are a fact of life with message digests. However, being
able to efficiently *predict* how to create a collision between two
messages is very bad for the security of a hash. Suppose you and I
agree to a contract, and I have you digitially sign a hash of it.
Unbeknownst to you, I had earlier created a second contract with
different wording, but which also hashes to the same value. Due to the
slowness of public key, most digital signatures are performed on a
digest of the original document.

I have both sources at my disposal from the beginning in this attack,
and am able to tweak each before giving you one (eg add whitespace,
comments in markup language used...).

good day,
tim

[Joel Maslak]

On Tue, 7 Dec 2004, Gandalf The White wrote:

> >From my reading it appears that you need the original source to create the
> doppelganger blocks. It also appears that given a MD5 hash you could not
> create a input that would give that MD5 back. Passwords encoded with MD5
> would not fall prey to your discovery. Is this correct?

My understanding is similar to yours.

However, imagine a PKI system in, say, a contract management system.

Let's say you can write a valid word document with a section of text that
can be "swapped" out.

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

--
Joel

[Rager, Anton]

Some things to note....

1 - Wang and Joux's attacks do not allow determination of original
inputs from a given hash.
2 - The interesting and newsworthy part of Wang's paper is not that
there are collisions in MD5 (and the other hash algs they produced
collisions for), but that they can produce colliding inputs by some
process other than random or bruteforce searching. They have some
method that allows them to produce colliding inputs at will with a
minimal amount of work - 32way 1.7ghz system produces unique 128byte
colliding texts in under 1.5hrs. They have proven this is more than just
random/bruteforce luck by providing two pairs of colliding inputs with
wrong initial values for MD5, and in the same day (at Crypto2004)
produced 2 new pairs of colliding inputs for the corrected MD5 init
values.

To truly understand the impacts of Wang's attacks, the actual collision
prediction/search method needs to be published. From the information
released so far, Wang is relying on very particular 128byte sequences
with bits flipped in 6 or 7 bit positions between the two 128 byte
sequences. It does not appear that a colliding input can be produced for
just any arbitrary input/text with this attack -- it appears the
original input needs to meet some very specific requirements to allow
creation of a colliding (alternate) input that will produce the same
output hash. More detail on Wang's alg/method is needed to know the full
extent of the applied impacts.=20
=20
Regards,

Anton Rager
arager@avaya.com

-----Original Message-----
From: Gandalf The White [mailto:gandalf@digital.net]=20
Sent: Tuesday, December 07, 2004 3:55 PM
To: Dan Kaminsky; BugTraq
Subject: Re: MD5 To Be Considered Harmful Someday

Greetings and Salutations:

On 12/6/04 5:29 PM, "Dan Kaminsky" <dan@doxpara.com> wrote:
<snip>
> Some highlights from the paper:
> * The attack itself is pretty limited -- essentially, we can create
> "doppelganger" blocks (my term) anywhere inside a file that may be
> swapped out, one for another, without altering the final MD5 hash.
This
> lets us create any number of binary-inequal files with the same
md5sum.

From my reading it appears that you need the original source to create
the
doppelganger blocks. It also appears that given a MD5 hash you could
not
create a input that would give that MD5 back. Passwords encoded with
MD5
would not fall prey to your discovery. Is this correct?

Unfortunately when "The Press" publicized the MD5 hash discovery by Joux
and
Wang it almost sounded like "The Press" was surprised to find collisions
in
the MD5 domain (intuitive to me, a limited number of outputs and a
infinite
number of inputs =3D Collisions). I assume that a "good" hash would =
have
a
even distribution of collisions across the domain and that the larger
number
of bits for the output the better the hash (assuming no cryptographic
algorithm errors).

Thanks,
Ken

---------------------------------------------------------------
Do not meddle in the affairs of wizards for they are subtle and
quick to anger.
Ken Hollis - Gandalf The White - gandalf@digital.net - O- TINLC
WWW Page - http://digital.net/~gandalf/
Trace E-Mail forgery - http://digital.net/~gandalf/spamfaq.html
Trolls crossposts - http://digital.net/~gandalf/trollfaq.html

[Joel Maslak]

On Mon, 6 Dec 2004, Dan Kaminsky wrote:

> I've been doing some analysis on MD5 collision announced by Wang et al.
> Short version: Yes, Virginia, there is no such thing as a safe hash
> collision -- at least in a function that's specified to be
> cryptographically secure. The full details may be acquired at the
> following link:

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.

--
Joel

[Gandalf The White]

Greetings and Salutations:

In my first e-mail I meant to congratulate Dan Kaminsky for the fine work
and write-up he did. Excellent.

On 12/7/04 10:01 PM, "David Schwartz" <davids@webmaster.com> wrote:
>> From my reading it appears that you need the original source to create the
>> doppelganger blocks. It also appears that given a MD5 hash you could not
>> create a input that would give that MD5 back. Passwords encoded with MD5
>> would not fall prey to your discovery. Is this correct?
>
> Correct. You will never be able to find the input given an MD5 hash. It
> might be possible to, eventually, come up with an input that has the same
> hash given just the hash, but you could never know if that was the original
> input or not. (At least, not in general.)

That is the worry that I have for MD5 hashed passwords. It doesn't matter
that you get the *correct* password, just that you have input that will hash
(collide) to the correct MD5 hash.

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

Lets say that I am very smart and I can use software that is able to
generate a collision in the passwords such that the MD5 hashes are the same,
say for example:
"AshEr37WesW28Er4E2" MD5 = $1$Vjuf$t5QYnzXL0Sy4tThvqKDGa1

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.

I just want to make sure that the MD5 hash passwords don't end up being as
easy to compute as the Cisco 7 passwords or the NTLM passwords. 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 ...

Ken

---------------------------------------------------------------
Do not meddle in the affairs of wizards for they are subtle and
quick to anger.
Ken Hollis - Gandalf The White - gandalf@digital.net - O- TINLC
WWW Page - http://digital.net/~gandalf/
Trace E-Mail forgery - http://digital.net/~gandalf/spamfaq.html
Trolls crossposts - http://digital.net/~gandalf/trollfaq.html

[David Schwartz]

> From my reading it appears that you need the original source to create the
> doppelganger blocks. It also appears that given a MD5 hash you could not
> create a input that would give that MD5 back. Passwords encoded with MD5
> would not fall prey to your discovery. Is this correct?

Correct. You will never be able to find the input given an MD5 hash. It
might be possible to, eventually, come up with an input that has the same
hash given just the hash, but you could never know if that was the original
input or not. (At least, not in general.)

> Unfortunately when "The Press" publicized the MD5 hash discovery
> by Joux and Wang it almost sounded like "The Press" was
> surprised to find collisions in the MD5 domain

Lots of people were surprised. We all knew we were there, and we all knew
they'd be found eventually. I don't think many people suspected, however,
that they would be found quite so soon. Some of the early "mainstream"
articles missed the boat, of course.

> (intuitive to me, a limited number of outputs and
> a infinite
> number of inputs = Collisions). I assume that a "good" hash would have a
> even distribution of collisions across the domain and that the
> larger number
> of bits for the output the better the hash (assuming no cryptographic
> algorithm errors).

Yes. At this point, MD5 should no longer be used for applications where an
adversary might have access to the data that is being signed. That means
it's no longer suitable for signing certificates or authenticating data sent
over a peer-to-peer network. SHA1 with 160-bits is still, as far as we know,
suitable for all of these purposes.

I generally advise not using MD5 for any applications except (P)RNGs and as
a non-cryptographically-secure checksum.

DS

[Keith Oxenrider]

For what it is worth, I have an ANSI standard C++ implementation of the
sha-160/224/256/384/512 bit algorithms that auto-detects endian-ness and
adjusts accordingly (tested on Wintel, Lintel and Solaris). It can be
found at http://sol-biotech.com/code/sha2/ (it comes with a test suite that
was developed by Aaron D. Gifford who did the C implementation I based it
on). For some reason the default directory display does not list the
README File, it is here: http://sol-biotech.com/code/sha2/README. I
created a simple password class for creating and managing passwords based
on my sha* implementation, it can be found here:
http://sol-biotech.com/code/SimplePass/. I would love to have constructive
feedback.

Keith Oxenrider
CISSP

At 10:36 PM 12/7/2004 -0600, Gandalf The White wrote:
>Greetings and Salutations:
>
><snip>
>
>I just want to make sure that the MD5 hash passwords don't end up being as
>easy to compute as the Cisco 7 passwords or the NTLM passwords. 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 ...
>
>Ken
>
>---------------------------------------------------------------
>Do not meddle in the affairs of wizards for they are subtle and
>quick to anger.
>Ken Hollis - Gandalf The White - gandalf@digital.net - O- TINLC
>WWW Page - http://digital.net/~gandalf/
>Trace E-Mail forgery - http://digital.net/~gandalf/spamfaq.html
>Trolls crossposts - http://digital.net/~gandalf/trollfaq.html

[Dragos Ruiu]

On December 7, 2004 04:13 pm, Tim wrote:
> > Unfortunately when "The Press" publicized the MD5 hash discovery by Joux
> > and Wang it almost sounded like "The Press" was surprised to find
> > collisions in the MD5 domain (intuitive to me, a limited number of
> > outputs and a infinite number of inputs = Collisions). I assume that a
> > "good" hash would have a even distribution of collisions across the
> > domain and that the larger number of bits for the output the better the
> > hash (assuming no cryptographic algorithm errors).
>
> Yes, collisions are a fact of life with message digests. However, being
> able to efficiently *predict* how to create a collision between two
> messages is very bad for the security of a hash. Suppose you and I
> agree to a contract, and I have you digitially sign a hash of it.
> Unbeknownst to you, I had earlier created a second contract with
> different wording, but which also hashes to the same value. Due to the
> slowness of public key, most digital signatures are performed on a
> digest of the original document.
>
> I have both sources at my disposal from the beginning in this attack,
> and am able to tweak each before giving you one (eg add whitespace,
> comments in markup language used...).


Which brings up a good point: Proving the existence of collisions is not the
same thing as being able to predict the collisions.

Dan, your attack application(s) presumes that there is a way to predict
the collisions in a general form, and more so is primarily useful only
if there is a way to predict collisions for ANY arbitrary hash.

AFAIK the only thing proven so far is that there are collisions, and though
this certainly increases the probability of a generalized collision method,
it is not discovered/documented yet.

Your proposal is an interesting application(s) of collisions - and certainly
does much to dispel some of the belittling of the collision discovery.
However the extent of the collisionabililty (collideability?) of md5
is still under debate afaik... feel free to correct me if I am wrong.

It may still be a little early to prepare applications for something we
haven't discovered yet - though we can have a debate on the likelyhood of
this discovery again over tequila at your leisure :-). It's a neat attack
scenario, certainly worth consideration, and you bring up
a number of interesting points about md5, but without the
collision logic it remains a theoretical concern for education
and a future attack vector caveat.

cheers,
--dr

--
World Security Pros. Cutting Edge Training, Tools, and Techniques
Vancouver, Canada May 4-6 2005 http://cansecwest.com
pgpkey http://dragos.com/ kyxpgp

[Jack Lloyd]

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.

You might want to read this:
http://www.mail-archive.com/cryptography@metzdowd.com/msg02611.html

Essentially you can use Joux's attack to generate 2^64 collisions for SHA-1
with about 64*2^80 effort; out of those 2^64 collisions you have an even chance
that at least one of them will also collide in MD5. That's still 2^86 hash
computations, nothing to sneeze at, but nowhere near the expected 2^144
operations. That workfactor might be doable in a 20 year timeframe.

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.

So this really doesn't buy you anything.

Jack

[Ruth A. Kramer]

Gandalf The White wrote:
> Unfortunately when "The Press" publicized the MD5 hash discovery by Joux and
> Wang it almost sounded like "The Press" was surprised to find collisions in
> the MD5 domain (intuitive to me, a limited number of outputs and a infinite
> number of inputs = Collisions). I assume that a "good" hash would have a
> even distribution of collisions across the domain and that the larger number
> of bits for the output the better the hash (assuming no cryptographic
> algorithm errors).

Somehow there may be a lesson in this somewhere (not entirely sure for
whom (?)), or maybe not. Anyway, I'm copying this to my offline
wiki/askSam thingie for future cogitation.

My point: I'm sure "The Press" one way or another was told or got the
impression that MD5 hashes were the "answer to a maiden's prayers" with
respect to file security (against corruption). Not sure exactly how
they got that impression, probably neither you nor I (nor any of "us")
told them that -- if asked, we might have said something with
reservations -- like, MD5 can assure no file system corruption with a
probability of failure of (for example) 1 chance in some very big number
of failing.

Gradually that second clause gets forgotten, sometimes intentionally
(but innocently, I think: "don't worry about it, it'll never happen").
The further the news of MD5 travels, the more likely only the first part
("MD5 can assure no file system corruption") of the message gets
through, not the qualifier ("with a probability of failure ..."). Even
if the initial clause is crafted better ("MD5 can almost assure no file
system corruption"), the "almost" disappears as the message is
propagated. (Not everyone would use the same words for this example,
but choose almost any other set of words and you get the same result.)

Not sure what can be done about it, but I guess awareness of the problem
is one step toward a solution, which is why I'm noting this to myself
(and the list ;-).

regards,
Randy Kramer

Asides:

1. Is part of the solution to always stress the "almost"?
(Although, without thinking about it.

2. We (mostly) are insiders. What is intuitive to us is (usually?) not
intuitive to outsiders, depending on the subtlety of the issue.

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".)

[Dan Kaminsky]

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

Not that brute force is the only approach available. There are numerous
attacks that might break "pure" MD5 but fail given such massive
overlapping. 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. And Joux's unreleased paper makes it very
clear that simply stacking primitives doesn't create nearly the level of
combinatorial complexity that you'd expect.

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.

--Dan
www.doxpara.com

[Dan Kaminsky]

>Since you can't possibly mean absolutely suitable, can you clarify your
>basis for suitability? I'm not asking for a technical proof, just the
>general metrics used to make the determination.
>
>If 160 bit SHA1 is good enough for one application but not another, what
>does one need to know to decide for their own application?
>
>
SHA-1 is truncatable to 128 bits for applications that have limited
space available for hashes. This limits the birthday paradox attack to
a 2^64 effort, but MD5 isn't anywhere close to that anymore.
(Incidentally, the output of birthday attack is an unchosen collision,
just like Wang's.)

SHA-1 isn't perfect, but we haven't known its been broken for a decade
like we have for MD5.

--Dan

[Paul Wouters]

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.

Paul

[Solar Designer]

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

[Dan Kaminsky]

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

[Steve Friedl]

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/iguide-crypto-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

[David F. Skoll]

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.

[Jack Lloyd]

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

[Adam Shostack]

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

[Pavel Kankovsky]

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

[Solar Designer]

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