Lost password + MD5 ?

Hi there,

I've read in a few places that you should *never*
store original passwords in a mySQL DB.
Now i wonder if you encrypt it (with MD5 ?), how should
i create a lost password function, so the pass could be
sent to a corresponding e-mail address?

Greetings Frizzle.

*** frizzle wrote/escribió (2 Sep 2005 05:53:34 -0700):[color=blue]
> I've read in a few places that you should *never*
> store original passwords in a mySQL DB.
> Now i wonder if you encrypt it (with MD5 ?), how should
> i create a lost password function, so the pass could be
> sent to a corresponding e-mail address?[/color]

Since you don't know user's password (that's the point) you cannot send it
back. You can however provide the user with a temporary URL where we can
set a new one.

Steps:

1) Create a long random ID. md5() and uniqid() may help
2) Store it in DB
3) Send user a mail message with the ID:

http://www.example.com/reset_passwor...=xxxxxxxxxxxxx

4) In reset_password.php test whether ID exists in DB. If so, allow to set
pass

You can add all security features you can think of:

* Remove used ID
* Expire old unused IDs
* Store username or e-mail and ask for them

--
-- Álvaro G. Vicario - Burgos, Spain
-- http://bits.demogracia.com - Mi sitio sobre programación web
-- Don't e-mail me your questions, post them to the group
--

This is correct, never store password in plain text. The above
suggestion is correct, though I would also put in some random
characters (segment the string and rebuild it the other end).

Give them a link to log in so that they immediately have to create a
new password as suggested above. also think about using security
questions.

perhaps also pass some sort of encrypted username in the link also to
make the checking function that much quicker to validate. (i.e. select
where user= (decrypt) and pass=(decrypt).

ijsaunders@gmail.com wrote:
[color=blue]
> This is correct, never store password in plain text. The above
> suggestion is correct, though I would also put in some random
> characters (segment the string and rebuild it the other end).
>
> Give them a link to log in so that they immediately have to create a
> new password as suggested above. also think about using security
> questions.
>
> perhaps also pass some sort of encrypted username in the link also to
> make the checking function that much quicker to validate. (i.e. select
> where user= (decrypt) and pass=(decrypt).[/color]

Hi,

I don't want to ruin this party, but if you safe md5(password) you might as
well store them plaintext.
MD5 has had its best days. :-(

Some really smart Chineese guys came up with an algoritm that produces
INPUTSTRINGS that give the same MD5 hash as the original string.
That effect is called collison:
MD5(StringA) -> blakjhdsafjkh
MD5(StringB) -> blakjhdsafjkh
MD5(StringC) -> blakjhdsafjkh
etc.

They came up with an algoritm that produces some string (StringB and StringC
in the above example) that produce the same hash.

I also read some smart@ss at slashdot improved on this, and now it can be
done on a run-of-the-mill PC in 1 second.

So: effectively MD5 is broken. Do not use it.

Same goes for SHA1 (different problem).

If you are interested, read more on the topic.
Written by the best: Schneier. :-)

http://www.schneier.com/blog/archive...a1_broken.html

Regards,
Erwin Moller

frizzle wrote:[color=blue]
> Hi there,
>
> I've read in a few places that you should *never*
> store original passwords in a mySQL DB.
> Now i wonder if you encrypt it (with MD5 ?), how should
> i create a lost password function, so the pass could be
> sent to a corresponding e-mail address?[/color]
Very simple. You can't. And that's the way it's supposed to be.
That's what the hash function is for.

So you do what everybody else does that has a clue about security:
You assume that someone else is out for someones password.
So you block the account and send a special short-lived link where
they can choose a new password. This link obviously gets sent
to the email in the blocked account and not to one given by the
user interested in the password. As the other guy said, you need
to put in some token so that that kind of link can't be reused
for an attack. Keep tabs on the currently open and expired
tokens to prevent replays. Make it hard to predict the value of
of the next token by using cryptographically strong random numbers.
If you are serious, ask in sci.crypt.

Lots of Greetings!
Volker

Erwin Moller wrote:[color=blue]
> I don't want to ruin this party, but if you safe md5(password) you might as
> well store them plaintext.
> MD5 has had its best days. :-([/color]
[...][color=blue]
> I also read some smart@ss at slashdot improved on this, and now it can be
> done on a run-of-the-mill PC in 1 second.[/color]
15min is the last estimate I know, but that's a few months old.
[color=blue]
> So: effectively MD5 is broken. Do not use it.[/color]

Depends on what this guys choices are and how much effort an attacker
is going to spend on getting a password.
a) In a web application you typically deal with the
name-of-my-neighbour's-hamster class of passwords (unless it's a bank).
For instance, a truly random password of 6 lowercase letters and digits
has about 31bit of entropy in it, words something in the 10 to 20bit
range.
No attacker will attack md5 for this, they run some crack-like guesser
and that's it.
b) His toolkit may not have anything better to offer, in particular
not SHA256.

Also, typically you salt passwords, i.e. combine them with another random
string. (frizzle, you *do* that, don't you?)
If the attacker doesn't steal the password hashes *and* the random
strings he can't do anything. If he can break into your system and steal
a file, you've IMHO got a way bigger problem than what hash function you chose.

Lots of Greetings!
Volker

I'd might really have to start it then ... :(
Anyway, thanks for all the advice.
Not quite sure on what i have to do now though ...
I'll think about it ...

On Fri, 02 Sep 2005 16:43:49 +0200, Erwin Moller
<since_humans_read_this_I_am_spammed_too_much@spam yourself.com> wrote:
[color=blue]
>I don't want to ruin this party, but if you safe md5(password) you might as
>well store them plaintext.
>MD5 has had its best days. :-(
>
>Some really smart Chineese guys came up with an algoritm that produces
>INPUTSTRINGS that give the same MD5 hash as the original string.
>That effect is called collison:
>MD5(StringA) -> blakjhdsafjkh
>MD5(StringB) -> blakjhdsafjkh
>MD5(StringC) -> blakjhdsafjkh
>etc.
>
>They came up with an algoritm that produces some string (StringB and StringC
>in the above example) that produce the same hash.
>
>I also read some smart@ss at slashdot improved on this, and now it can be
>done on a run-of-the-mill PC in 1 second.
>
>So: effectively MD5 is broken. Do not use it.[/color]

OK, so the MD5 collision attack is based on already having plaintext A and
hash M, and being able to produce a different plaintext B that has the same
hash M.

This breaks MD5's use in verifying the contents/integrity of a file by
checking the data's MD5 hash (since you can now modify the contents and tweak
it to produce the same MD5 hash), but unless I'm missing something it doesn't
affect the usage in passwords; it doesn't help in deriving from scratch a
plaintext that produces a given MD5 hash? Which is what you'd have to do to get
in through MD5-based authentication systems.

--
Andy Hassall :: andy@andyh.co.uk :: http://www.andyh.co.uk
http://www.andyhsoftware.co.uk/space :: disk and FTP usage analysis tool

================================================== ======================
Andy Hassall wrote:[color=blue]
> This breaks MD5's use in verifying the contents/integrity of a file by
> checking the data's MD5 hash (since you can now modify the contents and tweak
> it to produce the same MD5 hash), but unless I'm missing something it doesn't
> affect the usage in passwords; it doesn't help in deriving from scratch a
> plaintext that produces a given MD5 hash? Which is what you'd have to do to get
> in through MD5-based authentication systems.[/color]

I also don't see this being much of a problem in the context of
passwords since your typical password is pretty short. I can't imagine
that there would be two different, 6-character length passwords that
would result in the same hash. I could be wrong, though...

- Ryan

Do you think that it would be more secure if when you stored the users
password you also stored its string length? So then when you checked
the users password you would also check the length, because then a
hacker would have to find a string that is the same length as the
password and generates the same hash as the password. To me this sounds
pretty good, but i want to hear what you guys say.

On 3 Sep 2005 09:58:36 -0700, "jimmy88@gmail.com" <jimmy88@gmail.com> wrote:
[color=blue]
>Do you think that it would be more secure if when you stored the users
>password you also stored its string length? So then when you checked
>the users password you would also check the length, because then a
>hacker would have to find a string that is the same length as the
>password and generates the same hash as the password. To me this sounds
>pretty good, but i want to hear what you guys say.[/color]

No, that could make it less secure. You've then just given away information
about the plaintext, so potentially reduced the search space for brute force
attacks.

--
Andy Hassall :: andy@andyh.co.uk :: http://www.andyh.co.uk
http://www.andyhsoftware.co.uk/space :: disk and FTP usage analysis tool

Andy Hassall wrote:[color=blue]
> On Fri, 02 Sep 2005 16:43:49 +0200, Erwin Moller
> <since_humans_read_this_I_am_spammed_too_much@spam yourself.com> wrote:[/color]
<snip>[color=blue][color=green]
> >Some really smart Chineese guys came up with an algoritm that produces
> >INPUTSTRINGS that give the same MD5 hash as the original string.
> >That effect is called collison:[/color][/color]
<snip>[color=blue][color=green]
> >So: effectively MD5 is broken. Do not use it.[/color]
>
> OK, so the MD5 collision attack is based on already having plaintext A and
> hash M, and being able to produce a different plaintext B that has the same
> hash M.
>
> This breaks MD5's use in verifying the contents/integrity of a file by
> checking the data's MD5 hash (since you can now modify the contents and tweak
> it to produce the same MD5 hash), but unless I'm missing something it doesn't
> affect the usage in passwords; it doesn't help in deriving from scratch a
> plaintext that produces a given MD5 hash?[/color]

Collision of hashes help brute force attacks. For example, if the
string of length 100's hash collides with string of length 10's hash,
it makes the cracking easy.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

On 4 Sep 2005 09:43:57 -0700, "R. Rajesh Jeba Anbiah"
<ng4rrjanbiah@rediffmail.com> wrote:
[color=blue]
>Andy Hassall wrote:[color=green]
>> This breaks MD5's use in verifying the contents/integrity of a file by
>> checking the data's MD5 hash (since you can now modify the contents and tweak
>> it to produce the same MD5 hash), but unless I'm missing something it doesn't
>> affect the usage in passwords; it doesn't help in deriving from scratch a
>> plaintext that produces a given MD5 hash?[/color]
>
> Collision of hashes help brute force attacks. For example, if the
>string of length 100's hash collides with string of length 10's hash,
>it makes the cracking easy.[/color]

But how does that make it any easier to find from scratch a plaintext that
produces a given MD5? The fact that there exist collisions in MD5 is obvious
due to the pigeonhole principle, but it doesn't cut down your search space in
any meaningful or predictable way?

Surely a different class of weakness is required to affect MD5's usage in
passwords, i.e. some property of the MD5 hash value allowing deduction of some
property of the possible plaintext values that could have produced it, reducing
the brute force search space - AFAIK no such weakness has yet been found.

The fact that most user's passwords are probably 5-7 characters, consisting of
characters [A-Za-z0-9], means brute forcing the search space is not beyond the
realms of possibility with enough storage is still an issue, but it's not a new
one, and is partially addressed by salting.

--
Andy Hassall :: andy@andyh.co.uk :: http://www.andyh.co.uk
http://www.andyhsoftware.co.uk/space :: disk and FTP usage analysis tool

Andy Hassall wrote:

<snip>
[color=blue][color=green]
>>So: effectively MD5 is broken. Do not use it.[/color]
>
> OK, so the MD5 collision attack is based on already having plaintext A
> and
> hash M, and being able to produce a different plaintext B that has the
> same hash M.[/color]

No,

The MD5-attack is based on having ONLY the md5-hash.
If you had StringA already, you were ready already with the 'cracking',
since StingA contains the original password. :-)

The point is that giving a certain MD5-Hash, you can come up with some
String as input that produces the same MD5-hash.

An example:
You password is 'verySecret'
md5('verySecret') -> asgfjhasgfjhgsadfj

Some Bad Guy ONLY gets hold of the md5-hash (asgfjhasgfjhgsadfj).
Based on this String (s)he can produce another string that also produces
asgfjhasgfjhgsadfj.
for example:
md5Cracker('asgfjhasgfjhgsadfj ') -> 'hhgttg'

md5('hhgttg') -> asgfjhasgfjhgsadfj

Regards,
Erwin Moller

Erwin Moller wrote:[color=blue]
> Andy Hassall wrote:
>
> <snip>
>[color=green][color=darkred]
>>>So: effectively MD5 is broken. Do not use it.[/color]
>>
>> OK, so the MD5 collision attack is based on already having plaintext A
>> and
>>hash M, and being able to produce a different plaintext B that has the
>>same hash M.[/color]
>
>
> No,
>
> The MD5-attack is based on having ONLY the md5-hash.
> If you had StringA already, you were ready already with the 'cracking',
> since StingA contains the original password. :-)
>
> The point is that giving a certain MD5-Hash, you can come up with some
> String as input that produces the same MD5-hash.
>
> An example:
> You password is 'verySecret'
> md5('verySecret') -> asgfjhasgfjhgsadfj
>
> Some Bad Guy ONLY gets hold of the md5-hash (asgfjhasgfjhgsadfj).
> Based on this String (s)he can produce another string that also produces
> asgfjhasgfjhgsadfj.
> for example:
> md5Cracker('asgfjhasgfjhgsadfj ') -> 'hhgttg'
>
> md5('hhgttg') -> asgfjhasgfjhgsadfj
>
> Regards,
> Erwin Moller[/color]

One thing you're all forgetting.

Obviously different strings can create the same MD5 hash. After all, it
is a one-way hash. If the hash were unique, it could be bi-directional.

Additionally, the results of a unique encryption must be at least as
long as the data being encrypted (before any compression algorithms).
This obviously isn't true here.

Yes, the hash value may be duplicated by changing only a few bits of a
1024 bit input. That's possible - an MD5 hash is not 128 bytes long.
So there is a 100% chance that there will be at least 2 128 byte strings
with the same hash. In fact, there is probably almost a 100% chance
that EVERY 128 bit string has another 128 bit string producing the same
hash.

That this can be accomplished by "changing a few bits" doesn't surprise
me, either. But finding the right bits to change would be very
difficult. There would be 1024! (1024 factorial - 1024 x 1023 x 1022 x
....) possible combinations. And yes, there would probably be more than
one which gave that same hash value.

Now - you might be able to analyze the algorithm to limit the
possibilities - I haven't tried, so I don't know. But that might help
in certain circumstances.

Virtually any hash or encryption method can be broken for specific
examples. That doesn't mean it isn't secure for general use. Only in
those specific examples.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attglobal.net
==================

Jerry Stuckle wrote:

<snip>

Hi Jerry,

For clarity's sake: I do not claim to be an encryption-expert. You might
very well know a lot more than me.
I am just restating what Schneier and Slashdot wrote because I think it is
important to all people using the SHA-0/SHA-1/MD5 algoritms.
(The math behind it all is way over my head.)
[color=blue]
>
> One thing you're all forgetting.[/color]

Tell me. :-)
[color=blue]
>
> Obviously different strings can create the same MD5 hash. After all, it
> is a one-way hash. If the hash were unique, it could be bi-directional.[/color]

I knew that.
That would be a great zip-algoritm. ;-)
[color=blue]
>
> Additionally, the results of a unique encryption must be at least as
> long as the data being encrypted (before any compression algorithms).
> This obviously isn't true here.[/color]

Agree.
[color=blue]
>
> Yes, the hash value may be duplicated by changing only a few bits of a
> 1024 bit input. That's possible - an MD5 hash is not 128 bytes long.
> So there is a 100% chance that there will be at least 2 128 byte strings
> with the same hash. In fact, there is probably almost a 100% chance
> that EVERY 128 bit string has another 128 bit string producing the same
> hash.[/color]

Indeed.
[color=blue]
>
> That this can be accomplished by "changing a few bits" doesn't surprise
> me, either. But finding the right bits to change would be very
> difficult. There would be 1024! (1024 factorial - 1024 x 1023 x 1022 x
> ...) possible combinations. And yes, there would probably be more than
> one which gave that same hash value.[/color]

And here you missed the important point (I think):
You do NOT need to try brute-force all possible combinations.
The new MD5-cracking algoritm can do that smarter/quicker/better-guessing.
(I am not sure since they didn't publish their results yet AFAIK)
[color=blue]
>
> Now - you might be able to analyze the algorithm to limit the
> possibilities - I haven't tried, so I don't know.[/color]

And that is excactly what happened.
[color=blue]
> But that might help
> in certain circumstances.[/color]

It did for Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu: the Chineese
researchers. :-)
[color=blue]
>
> Virtually any hash or encryption method can be broken for specific
> examples.
> That doesn't mean it isn't secure for general use. Only in
> those specific examples.[/color]

True.
But we just do not know how many SHA-1 hashes are prone to collions-finding
algoritms.
A good algoritm will let the Bad Guys only break it brute force, hence
forcing them to try random inputstrings for a zillion years.

From Schneier's weblog:

<quote>
Jon Callas, PGP's CTO, put it best: "It's time to walk, but not run, to the
fire exits. You don't see smoke, but the fire alarms have gone off." That's
basically what I said last August.

It's time for us all to migrate away from SHA-1.

Luckily, there are alternatives. The National Institute of Standards and
Technology already has standards for longer -- and harder to break -- hash
functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already
government standards, and can already be used. This is a good stopgap, but
I'd like to see more.
</quote>

For clarity's sake: I do not claim to be an encryption-expert. You might
very well know a lot more than me.
I am just restating what Schneier and Slashdot wrote.
The math behind it all is way over my head.

Some links:
http://www.schneier.com/blog/archive...a1_broken.html

or this newer and much more informative article:

http://www.schneier.com/blog/archive...nalysis_o.html

Regards,
Erwin Moller

On Mon, 05 Sep 2005 10:25:52 +0200, Erwin Moller
<since_humans_read_this_I_am_spammed_too_much@spam yourself.com> wrote:
[color=blue]
>Andy Hassall wrote:
>
><snip>
>[color=green][color=darkred]
>>>So: effectively MD5 is broken. Do not use it.[/color]
>>
>> OK, so the MD5 collision attack is based on already having plaintext A
>> and
>> hash M, and being able to produce a different plaintext B that has the
>> same hash M.[/color]
>
>The MD5-attack is based on having ONLY the md5-hash.[/color]

Sorry, which MD5 attack are you referring to? The MD5 attack required to break
MD5-based password systems is indeed based on having only the MD5 hash, but I
wasn't aware of any such attacks that exist, beyond brute force.
[color=blue]
>If you had StringA already, you were ready already with the 'cracking',
>since StingA contains the original password. :-)[/color]

Exactly the point - which is why the published weakness does not appear to be
particularly relevant to this usage, since it requires this approach. It finds
collisions such that one plaintext can be transformed in a specific way into a
second plaintext, yet have the same MD5 - it does not produce any of the
infinite plaintexts from a single MD5.

e.g.
http://www.cits.rub.de/MD5Collisions/
http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf

Given both message M and hash H(M) this attack provides a method of modifying
M to produce M' such that H(M) = H(M').

It doesn't, given only H(M) and _not_ M, find any M' (which may or may not
equal M) such that H(M) = H(M').

(Unless I've drastically missed the point somewhere).
[color=blue]
>The point is that giving a certain MD5-Hash, you can come up with some
>String as input that produces the same MD5-hash.
>
>An example:
>You password is 'verySecret'
>md5('verySecret') -> asgfjhasgfjhgsadfj
>
>Some Bad Guy ONLY gets hold of the md5-hash (asgfjhasgfjhgsadfj).
>Based on this String (s)he can produce another string that also produces
>asgfjhasgfjhgsadfj.
>for example:
>md5Cracker('asgfjhasgfjhgsadfj ') -> 'hhgttg'
>
>md5('hhgttg') -> asgfjhasgfjhgsadfj[/color]

But do you have a link to such an attack? That's not what the attacks being
referred to do, is it?

There is still only brute force enumeration as far as I'm aware, made easier
to look up through Rainbow Tables and the search space being reduced by users
having weak passwords, but then salted MD5 password hashes make it harder again
(you have to find the salt and then regenerate your tables all over again).

--
Andy Hassall :: andy@andyh.co.uk :: http://www.andyh.co.uk
http://www.andyhsoftware.co.uk/space :: disk and FTP usage analysis tool

Erwin Moller wrote:[color=blue]
> Jerry Stuckle wrote:[color=green]
> >[/color]
>[color=green]
>>That this can be accomplished by "changing a few bits" doesn't surprise
>>me, either. But finding the right bits to change would be very
>>difficult. There would be 1024! (1024 factorial - 1024 x 1023 x 1022 x
>>...) possible combinations. And yes, there would probably be more than
>>one which gave that same hash value.[/color]
>
>
> And here you missed the important point (I think):
> You do NOT need to try brute-force all possible combinations.
> The new MD5-cracking algoritm can do that smarter/quicker/better-guessing.
> (I am not sure since they didn't publish their results yet AFAIK)
>[/color]

No, I didn't say you had to brute force all possible combinations. But
- there are any number of algorithms for various things which work for a
limited subset of the possibilities - but fail when applied to the
larger set.

But since they haven't published their results, we really don't know, do
we? To me it's suspicious. If it did apply to everything, I would
think they would want to publish it for peer review - and recognition,
if it does pass the peer review. After all - there would be some fame
to the first people to crack it.
[color=blue]
>[color=green]
>>Now - you might be able to analyze the algorithm to limit the
>>possibilities - I haven't tried, so I don't know.[/color]
>
>
> And that is excactly what happened.
>[/color]

Are you sure? After all - they didn't publish their work.
[color=blue]
>[color=green]
>>But that might help
>>in certain circumstances.[/color]
>
>
> It did for Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu: the Chineese
> researchers. :-)
>[/color]
So, why haven't they published it?
[color=blue]
>[color=green]
>>Virtually any hash or encryption method can be broken for specific
>>examples.
>>That doesn't mean it isn't secure for general use. Only in
>>those specific examples.[/color]
>
>
> True.
> But we just do not know how many SHA-1 hashes are prone to collions-finding
> algoritms.
> A good algoritm will let the Bad Guys only break it brute force, hence
> forcing them to try random inputstrings for a zillion years.
>[/color]

Sure we do. Every single one of them. Since there are 160 bits, the
average chance of duplication is 1 in 2^160.
[color=blue]
> From Schneier's weblog:
>
> <quote>
> Jon Callas, PGP's CTO, put it best: "It's time to walk, but not run, to the
> fire exits. You don't see smoke, but the fire alarms have gone off." That's
> basically what I said last August.
>
> It's time for us all to migrate away from SHA-1.
>
> Luckily, there are alternatives. The National Institute of Standards and
> Technology already has standards for longer -- and harder to break -- hash
> functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already
> government standards, and can already be used. This is a good stopgap, but
> I'd like to see more.
> </quote>
>
>[/color]
Yep. I'm not saying we shouldn't migrate away from SHA-1. However, I
would like to see the details.[color=blue]
>
> For clarity's sake: I do not claim to be an encryption-expert. You might
> very well know a lot more than me.
> I am just restating what Schneier and Slashdot wrote.
> The math behind it all is way over my head.
>[/color]

I'm not an encryption expert, but I do have some math background. Been
a few years, though :-).
[color=blue]
> Some links:
> http://www.schneier.com/blog/archive...a1_broken.html
>
> or this newer and much more informative article:
>
> http://www.schneier.com/blog/archive...nalysis_o.html
>
> Regards,
> Erwin Moller[/color]

I still want to see the results of peer reviews.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attglobal.net
==================

Hi,

I called in the cavalery. :-)
I posted our (my) questions to sci.crypt and will keep you posted here.

Regards,
Erwin Moller

Hi,

I called in the cavalery. :-)
I posted our (my) questions to sci.crypt and will keep you posted here.

Regards,
Erwin Moller

On Tue, 06 Sep 2005 10:32:35 +0200, Erwin Moller wrote:
[color=blue]
> I called in the cavalery. :-)[/color]

Men on horses are Cavalry :-(

Rincewind wrote:
[color=blue]
> On Tue, 06 Sep 2005 10:32:35 +0200, Erwin Moller wrote:
>[color=green]
>> I called in the cavalery. :-)[/color]
>
> Men on horses are Cavalry :-([/color]

:-)

Thanks. That is what I ment.
(Stupid Dutch trying to write english.)

Regards,
Erwin Moller

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/archive...a1_broken.html
and the follow up:
http://www.schneier.com/blog/archive...nalysis_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@spam yourself.com>
writes:[color=blue]
> 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.[/color]

It's real and it's been improved some since that announcement.
[color=blue]
> 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.[/color]

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.
[color=blue]
> 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[/color]
new[color=blue]
> inputstrings that produce the same hash in a reasonable short time?[/color]

No.
[color=blue]
> (That is called a collision, right?)[/color]

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.
[color=blue]
> Or can it only be used in certain isolated situations?
> (I mean: Does it only work for a special subset of MD5 hashes?)[/color]

It doesn't work at all the way you're imagining.
[color=blue]
> 2) If yes to 1) -> Should we consider SHA-0/1 and MD5 unsafe?[/color]

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.
[color=blue]
> What other hash do you advise us to use?
> Thanks in advance for your time![/color]

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.

I noticed that Message-ID: <431d6c4a$0$11075$e4fe514c@news.xs4all.nl>
from Erwin Moller contained the following:
[color=blue]
>Thanks. That is what I ment.
>(Stupid Dutch trying to write english.)[/color]

It's a heck of a lot better than my Dutch!

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker/

Well, nice to see such a big discussion
on a topic 'of mine', but with all these pro's
and contra's i'm still kinda stuck here :-(

I read "If you're implementing something new,
you're better off choosing a more modern hash
function. "

What *should* i use then to create a safe
password system ... ?

Greetings Frizzle ...
(Stupid & Dutch as well ... )

On 6 Sep 2005 14:18:00 -0700, "frizzle" <phpfrizzle@gmail.com> wrote:
[color=blue]
>Well, nice to see such a big discussion
>on a topic 'of mine', but with all these pro's
>and contra's i'm still kinda stuck here :-(
>
>I read "If you're implementing something new,
>you're better off choosing a more modern hash
>function. "
>
>What *should* i use then to create a safe
>password system ... ?[/color]

The conclusion was that this usage of MD5 remains unaffected by the recent
findings, so in practice it's fine to keep using that.

HMAC-SHA1 is probably a good bet if you're still worried.

See the user-contributed notes on http://uk.php.net/sha1 for an implementation
of HMAC-SHA1. Or: http://pear.php.net/package/Crypt_HMAC

The person who posted the HMAC-SHA1 code in the notes above also linked to
this PDF which has a good chunk of information about holes in authentication
systems:

http://cookies.lcs.mit.edu/pubs/webauth:tr.pdf

But anyway, it's far more likely you'll have real bugs or security holes
elsewhere that'll allow more direct levels of access (e.g. your post on SQL
injection), so you should be worrying more about that, than theoretical levels
of reversability of cryptographically secure hash functions.

--
Andy Hassall :: andy@andyh.co.uk :: http://www.andyh.co.uk
http://www.andyhsoftware.co.uk/space :: disk and FTP usage analysis tool

Ok, thanks a lot Andy (and the rest) !

Erwin Moller wrote:[color=blue]
> 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.[/color]
<snip>

For others, the thread is here
<http://groups.google.com/groups?threadm=431d53c8$0$11072$e4fe514c@news.xs4a ll.nl>
I would also like to present Wikipedia article on MD5
<http://en.wikipedia.org/wiki/MD5>

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

re: Lost password + MD5 ?

Similar PHP bytes

/bytes/development

/bytes/it

/bytes/about