Re: BUG #4876: author of MD5 says it's seriously broken - hash collision resistance problems

The following bug has been logged online:

Bug reference: 4876
Logged by: Jim Michaels
Email address: jmichae3(at)yahoo(dot)com
PostgreSQL version: 8.3.7-1
Operating system: windows XP Pro SP3
Description: author of MD5 says it's seriously broken - hash
collision resistance problems
Details:

If you are looking for hash collision protection, start looking at SHA-256
or SHA-512.

"In any case, you may not want to be using md5 (at least for
applications requiring collision-resistance), as it is
seriously broken. Use SHA-256 instead." - Ronald Rivest (author of MD5)

I was using MD5 in my zapdupes program and was told by the author of MD5,
and switched to SHA-512, because of the size of the files I was dealing
with. since you have BLOBs, I suggest you do the same.

this has implications for storing passwords as MD5 hashes. My
recommendation is to ditch MD5 and go with SHA-512. it takes up more space,
but it has greater collision resistance. it requires 64 bytes storage per
binary hash.

I have implemented SHA-512 as GPL'd code that you may use at

http://jesusnjim.com/code/sha512.html

it compiles with gcc (djgpp, MinGW), and Borland C++, and probably Microsoft
Visual C++.

With gcc, make sure that you do not use optimization level above -O, because
-O2 and -03 generate bad code and will give you incorrect results (the
results will not match that of the fips pdf document).

one possibility is that you could make the MD5 function actually return a
SHA-512 hash.

another possibility is that you could replace it with sha1.
sha256 only takes up one line of space-separated hexadecimal. sha512 takes
up 2 lines.

On Wednesday 24 June 2009 04:59:05 Jim Michaels wrote:
> If you are looking for hash collision protection, start looking at SHA-256
> or SHA-512.

Well, are we looking for that? We are not using MD5 for digital signatures.

Jim Michaels wrote:
> The following bug has been logged online:
>
> Bug reference: 4876
> Logged by: Jim Michaels
> Email address: jmichae3(at)yahoo(dot)com
> PostgreSQL version: 8.3.7-1
> Operating system: windows XP Pro SP3
> Description: author of MD5 says it's seriously broken - hash
> collision resistance problems
> Details:
>
> If you are looking for hash collision protection, start looking at SHA-256
> or SHA-512.
>
> "In any case, you may not want to be using md5 (at least for
> applications requiring collision-resistance), as it is
> seriously broken. Use SHA-256 instead." - Ronald Rivest (author of MD5)

We are talking about two different uses here, I think.

Using MD5 for passwords doesn't, afaik, actually require
collision-resistance. It requires resistance against preimage-attacks,
which there are none for MD5. At least not yet.

The other use is for hashes in the application, for users of pgcrypto.
pgcrypto already provides SHA-256 and SHA-512 for this use.

> I was using MD5 in my zapdupes program and was told by the author of MD5,
> and switched to SHA-512, because of the size of the files I was dealing
> with. since you have BLOBs, I suggest you do the same.

There is no hashing of the BLOBs unless you build that into your
application, in which case it's your responsibility to use a secure
algorithm. PostgreSQL just stores it.

> this has implications for storing passwords as MD5 hashes. My

That would be the only system use of MD5. What implications are those?

We might want to consider using a safer hash for the password storage at
some point, but from what I gather it's not really urgent for *that* use.

What would be more urgent is to provide a secure hashing *function* to
end users that doesn't rely on pgcrypto. But there is a solution for
this available today for those who need it - install pgcrypto.

> I have implemented SHA-512 as GPL'd code that you may use at

PostgreSQL is a BSD project and we have no use for GPL code. We also
already have implementations of SHA256 and SHA512 that are BSD licensed
in our codebase.

> one possibility is that you could make the MD5 function actually return a
> SHA-512 hash.

That seems like a horrible idea.

--
Magnus Hagander
Self: http://www.hagander.net/
Work: http://www.redpill-linpro.com/

Magnus Hagander wrote:
> Using MD5 for passwords doesn't, afaik, actually require
> collision-resistance. It requires resistance against preimage-attacks,
> which there are none for MD5. At least not yet.
Marc Stevens et al have a chosen prefix attack on MD5 (similar to a
second preimage attack, but slightly weaker) which they've successfully
used to forge root CA certs, using a cluster of PS3s. Cf. their
presentation at 25c3 last December.

>> this has implications for storing passwords as MD5 hashes. My
>>
>
> That would be the only system use of MD5. What implications are those?
>
> We might want to consider using a safer hash for the password storage at
> some point, but from what I gather it's not really urgent for *that* use.
>
It would be a lot more urgent if we weren't salting, but IIRC we are.

Cheers,
--mlp

Jim Michaels wrote:
> The following bug has been logged online:
>
> Bug reference: 4876
> Logged by: Jim Michaels
> Email address: jmichae3(at)yahoo(dot)com
> PostgreSQL version: 8.3.7-1
> Operating system: windows XP Pro SP3
> Description: author of MD5 says it's seriously broken - hash
> collision resistance problems
> Details:
>
> If you are looking for hash collision protection, start looking at SHA-256
> or SHA-512.
>

I personally avoid using sha256 and sha512 because they have proven to be cpu
hogs, profilers show them sucking the life out of my applications ... adding
large amounts of latency. If you use these, make sure their use is rather
small; ie. not for lots of files or blobs.

If you realy need good collision detection, I would recommend combining two
algorithms into a single hash, like crc32+md5 or md5+sha1. The chances of a
collision on both algorithms on the same message becomes far more unlikely.
Also, they end up being more efficient than sha256 by itself.

--
Andrew Chernow
eSilo, LLC
every bit counts
http://www.esilo.com/

Meredith L. Patterson wrote:
> Magnus Hagander wrote:
>>> this has implications for storing passwords as MD5 hashes. My
>>>
>> That would be the only system use of MD5. What implications are those?
>>
>> We might want to consider using a safer hash for the password storage at
>> some point, but from what I gather it's not really urgent for *that* use.
>>
> It would be a lot more urgent if we weren't salting, but IIRC we are.

If we really want something safer for system use in passwords, we ought
to be using HMAC instead. I don't believe and weaknesses of MD5 have
been found when it is used for HMAC. It has the added advantage that
there is no direct storage of the password itself, even in hashed form.

Joe

"Meredith L. Patterson" <mlp(at)osogato(dot)com> writes:
> Magnus Hagander wrote:
>> We might want to consider using a safer hash for the password storage at
>> some point, but from what I gather it's not really urgent for *that* use.
>>
> It would be a lot more urgent if we weren't salting, but IIRC we are.

I don't really see that there's any issue here at all. The point of the
hashing is to prevent a superuser (non-superusers can't look at the
stored hashvalue anyway) from recovering the user's actual password.
This is not for the purpose of protecting the database itself ---
superusers already have all the keys to the kingdom in that respect.
It's only meant to protect a user who's unwisely used the same password
for multiple services from having a database breakin mean that his other
services are compromised as well.

Being able to make up strings that hash to the same thing doesn't create
a vulnerability of this sort, AFAICS. You've found something that the
database would accept as being a valid password, but that doesn't mean
that it will work for other services.

regards, tom lane