Thread: md5 collision generator

md5 collision generator

From
Wim Bertels
Date:
LS,

the sourcecode of a md5 collision generator has been released,
it takes about 45 minutes to generate.
..so to an "eve" with this knowledge md5 is almost the same as plain text..

maybe its not bad to include eg. sha2 hashes into the options for passwords

kr,
Wim Bertels

Re: md5 collision generator

From
Tom Lane
Date:
Wim Bertels <wim.bertels@khleuven.be> writes:
> the sourcecode of a md5 collision generator has been released,
> it takes about 45 minutes to generate.
> ..so to an "eve" with this knowledge md5 is almost the same as plain text..

Really?

The fact that you can construct pairs of strings with matching md5
hashes does not mean that you can find a string with the same md5 hash
as a given string.

The existence of this algorithm is disturbing, since it implies that MD5
is weaker than people thought, but it IS NOT a useful password cracker,
and there's no reason for immediate panic.

            regards, tom lane

Re: md5 collision generator

From
Wim Bertels
Date:
On Wed, 2005-11-16 at 10:29 -0500, Tom Lane wrote:
> Wim Bertels <wim.bertels@khleuven.be> writes:
> > the sourcecode of a md5 collision generator has been released,
> > it takes about 45 minutes to generate.
> > ..so to an "eve" with this knowledge md5 is almost the same as plain text..
>
> Really?
>
> The fact that you can construct pairs of strings with matching md5
> hashes does not mean that you can find a string with the same md5 hash
> as a given string.
>
> The existence of this algorithm is disturbing, since it implies that MD5
> is weaker than people thought, but it IS NOT a useful password cracker,
> and there's no reason for immediate panic.

agreed, the given "picture" was too simple

>
>             regards, tom lane


Re: md5 collision generator

From
Bruno Wolff III
Date:
On Wed, Nov 16, 2005 at 14:25:44 +0100,
  Wim Bertels <wim.bertels@khleuven.be> wrote:
> LS,
>
> the sourcecode of a md5 collision generator has been released,
> it takes about 45 minutes to generate.
> ..so to an "eve" with this knowledge md5 is almost the same as plain text..
>
> maybe its not bad to include eg. sha2 hashes into the options for passwords

There is no sha2. sha1 has similar problems to md5.

The collision attack doesn't allow you to produce data that hashes to specific
hashes. So this isn't a problem for postgres.

Re: md5 collision generator

From
"Matthew D. Fuller"
Date:
On Wed, Nov 16, 2005 at 10:29:09AM -0500 I heard the voice of
Tom Lane, and lo! it spake thus:
>
> The existence of this algorithm is disturbing, since it implies that
> MD5 is weaker than people thought,

It occurs to me that, controlling everything that would be poking into
that part of the database, it would be possible to store the password
with several DIFFERENT hash algorithms, which would save us in the
future from any of them being easily crackable (or even ALL of them,
unless you can somehow create a collision across them all
simultaneously).  It seems that even with 2 or 3 weak hashes, that
might be safer long-term than with just 1 strong hash.  I s'pose it
would add a little cost to the connection-establishing process...


--
Matthew Fuller     (MF4839)   |  fullermd@over-yonder.net
Systems/Network Administrator |  http://www.over-yonder.net/~fullermd/
           On the Internet, nobody can hear you scream.

Re: md5 collision generator

From
Joe Conway
Date:
Matthew D. Fuller wrote:
> On Wed, Nov 16, 2005 at 10:29:09AM -0500 I heard the voice of
> Tom Lane, and lo! it spake thus:
>
>>The existence of this algorithm is disturbing, since it implies that
>>MD5 is weaker than people thought,
>
> It occurs to me that, controlling everything that would be poking into
> that part of the database, it would be possible to store the password
> with several DIFFERENT hash algorithms, which would save us in the
> future from any of them being easily crackable (or even ALL of them,
> unless you can somehow create a collision across them all
> simultaneously).  It seems that even with 2 or 3 weak hashes, that
> might be safer long-term than with just 1 strong hash.  I s'pose it
> would add a little cost to the connection-establishing process...

We really should be using an HMAC instead of a simple hash anyway. I
don't believe, even given the attacks available on MD5 and SHA1, that
anyone has theorized or demonstrated any weakening of HMACs based on
these hash algorithms (someone please correct me if they know otherwise).

Joe


Re: md5 collision generator

From
Wim Bertels
Date:
On Wed, 2005-11-16 at 14:43 -0600, Bruno Wolff III wrote:
> On Wed, Nov 16, 2005 at 14:25:44 +0100,
>   Wim Bertels <wim.bertels@khleuven.be> wrote:
> > LS,
> >
> > the sourcecode of a md5 collision generator has been released,
> > it takes about 45 minutes to generate.
> > ..so to an "eve" with this knowledge md5 is almost the same as plain text..
> >
> > maybe its not bad to include eg. sha2 hashes into the options for passwords
>
> There is no sha2. sha1 has similar problems to md5.

sha2 meaning sha-512



Re: md5 collision generator

From
Wim Bertels
Date:
On Wed, 2005-11-16 at 18:31 +0100, Wim Bertels wrote:
> On Wed, 2005-11-16 at 10:29 -0500, Tom Lane wrote:
> > Wim Bertels <wim.bertels@khleuven.be> writes:
> > > the sourcecode of a md5 collision generator has been released,
> > > it takes about 45 minutes to generate.
> > > ..so to an "eve" with this knowledge md5 is almost the same as plain text..
> >
> > Really?
> >
> > The fact that you can construct pairs of strings with matching md5
> > hashes does not mean that you can find a string with the same md5 hash
> > as a given string.
> >
> > The existence of this algorithm is disturbing, since it implies that MD5
> > is weaker than people thought, but it IS NOT a useful password cracker,
> > and there's no reason for immediate panic.
>
> agreed, the given "picture" was too simple

looked around a bit,
didn't know it was so easy:
http://www.antsight.com/zsl/rainbowcrack/#Rainbow%20Table
http://www.antsight.com/zsl/rainbowcrack/demo_rainbowcrack_cfg_md5_loweralpha-numeric,1-8.txt
plaintext of a1668f5f1ca8bb7214be760580a17dba is cf4sl1q5 ..

>
> >
> >             regards, tom lane