Posted by Erwin Moller on 09/06/05 13:20

Hi Jerry and Andy and others,

I posted the question in sci.crypt because I was increasingly unsure about
the topic.
It seems I was panicing too much and indeed misinterpreted the original
article.
That is actually good news. :-)
But judge for yourself.

Regards,
Erwin Moller


My question in sci.crypt:


-----------------------------------------------------
Dear group,

I need some advice regarding the safety of SHA-0 SHA-1 and MD5, being quite
ignorant on the subject myself.
I expect the subject is old news for most of you, but I hope some friendly
sould can help me a bit understanding the issue.


I read the following articles by Bruce Schneier:

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
and the follow up:
http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

[Quote from the first article]
******************************************************
February 15, 2005
SHA-1 Broken

SHA-1 has been broken. Not a reduced-round version. Not a simplified
version. The real thing.

The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly
from Shandong University in China) have been quietly circulating a paper
describing their results:

* collisions in the the full SHA-1 in 2**69 hash operations, much less
than the brute-force attack of 2**80 operations based on the hash length.

* collisions in SHA-0 in 2**39 operations.

* collisions in 58-round SHA-1 in 2**33 operations.

This attack builds on previous attacks on SHA-0 and SHA-1, and is a major,
major cryptanalytic result. It pretty much puts a bullet into SHA-1 as a
hash function for digital signatures (although it doesn't affect
applications such as HMAC where collisions aren't important).

The paper isn't generally available yet. At this point I can't tell if the
attack is real, but the paper looks good and this is a reputable research
team.
******************************************************
[end quote]


We just had a discussion on the subject in a PHP-ng (PHP is a
scriptinglanguage).
We wondered if storing passwords hashed as MD5 was safe.
I hope somebody can answer the following questions.

Our most nagging questions are:
1) Based on only a MD5 hash, can the abovementioned new algoritms create new
inputstrings that produce the same hash in a reasonable short time?
(That is called a collision, right?)

Or can it only be used in certain isolated situations?
(I mean: Does it only work for a special subset of MD5 hashes?)


2) If yes to 1) -> Should we consider SHA-0/1 and MD5 unsafe?
What other hash do you advise us to use?

Thanks in advance for your time!

Regards,
Erwin Moller

-----------------------------------------------------

The response:


Erwin Moller <since_humans_read_this_I_am_spammed_too_much@spamyourself.com>
writes:
> The paper isn't generally available yet. At this point I can't tell if the
> attack is real, but the paper looks good and this is a reputable research
> team.

It's real and it's been improved some since that announcement.

> We just had a discussion on the subject in a PHP-ng (PHP is a
> scriptinglanguage).
> We wondered if storing passwords hashed as MD5 was safe.

If you have some stored passwords hashed with md5, don't panic,
they're fine. If you're implementing something new, you're better off
choosing a more modern hash function.

> I hope somebody can answer the following questions.
>
> Our most nagging questions are:
> 1) Based on only a MD5 hash, can the abovementioned new algoritms create
new
> inputstrings that produce the same hash in a reasonable short time?

No.

> (That is called a collision, right?)

No, that's called a preimage (you control the desired hash and the
attacker has to find a string that matches it). Collision means
finding two arbitrary strings with the same md5 hash, where the
attacker gets to control both strings.

Analogy: being able to find md5 preimages is like being able to find
someone with the same fingerprints as Dick Cheney (or whoever else you
might want to impersonate). That's bad because that person can then
log in as Cheney and start a war or something. Finding a collision is
like finding two random people, somewhere in the world, who have the
same fingerprints as each other. That's not good, because those two
people can potentially team up to commit some interesting crimes. But
it's much less bad than being able to choose someone ahead of time and
find someone else with matching prints.

> Or can it only be used in certain isolated situations?
> (I mean: Does it only work for a special subset of MD5 hashes?)

It doesn't work at all the way you're imagining.

> 2) If yes to 1) -> Should we consider SHA-0/1 and MD5 unsafe?

You shouldn't use sha0, which has been deprecated for years and isn't
much used for anything. There's not much good reason to use md5.
Sha1 is still an approved FIPS standard, though approval will be
withdrawn in 2007 IIRC.

> What other hash do you advise us to use?
> Thanks in advance for your time!

Sha1 is still what pretty much everyone still uses. The current
approved successor to sha1 is sha256 (one of the sha-2 family), but
it's not used much yet. There's an upcoming NIST workshop on hash
functions where the sha1 situation will be discussed, and who knows
what will come out.

Anyway, I don't think you have an urgent security situation with any
of these functions given what you're doing, but generally it's best to
follow standards, to maximize interoperability and to know that you're
doing the best that you know how to do.

Note that preferable to simply storing an unkeyed hash of a password,
if your system has a way to use a secret key when hashing the
passwords, you should use something like HMAC-SHA1 (or these days
HMAC-SHA256). See RFC 2104 (www.ietf.org/rfc/rfc2104.txt) for how
HMAC works. Basically, HMAC-SHA1(x) is SHA1(a+SHA1(b+x)) for
some specific constants a and b, where + means concatenation.

[Back to original message]