RE: SHA-1 broken

[Michael Silk <michaelsilk () gmail com>]

Michael,

 But wouldn't it render a login-based hashing system resistant to the
current hashing problems if it is implemented something like:

 --
 result = hashFunc1( input + hashFunc1(input) + salt )
 //
 // instead of
 //
 result = hashFunc1( input + salt )
 --

 We can see that the input to the functions is the same, so although a
collision could be found within one or the other but it would not give
the correct result unless the hashFunc1( foo ) = hashFunc2( foo )
where foo is the magical input that gives the same result as "bar"
(the initial password).

-- Michael


> -----Original Message-----
> From: Scovetta, Michael V [mailto:Michael.Scovetta () ca com] 
> Sent: Friday, 18 February 2005 8:34 AM
> To: Kent Borg; Gadi Evron
> Cc: bugtraq () securityfocus com
> Subject: RE: SHA-1 broken
>
> Kent--
>
> Compositions won't really help very much. Lets say (I'm sure 
> the exact numbers are wrong here) that it takes brute-forcing 
> MD5 takes 2**80, and brute-forcing SHA-1 takes 2**90. And due 
> to recent discoveries, we can push those down to 2**50 and 
> 2**55 respectively. Breaking a composition would still take 
> on the order of 2**55 (the harder of the two)-- you're not 
> going to make it exponentially harder to crack by composing. 
> Doing something a little more slick like interweaving the 
> bits of the two algorithms would make it geometrically 
> harder, but not exponentially.
> You'd really have to get a new algorithm.
>
> Of course, this is assuming that the actual attack allows one 
> to take some predefined input A, and compute some evil input 
> A' such that Hash(A)=Hash(A'). If the attacks are simply to 
> create colliding input data, then the underlying algorithm is 
> still safe for most applications.
>
> Of course, I'm not a crypto-expert, so this may all be totally wrong.
>
> Michael Scovetta
> Computer Associates
> Senior Application Developer
>
>
> -----Original Message-----
> From: Kent Borg [mailto:kentborg () borg org]
> Sent: Wednesday, February 16, 2005 6:27 PM
> To: Gadi Evron
> Cc: bugtraq () securityfocus com
> Subject: Re: SHA-1 broken
>
> On Wed, Feb 16, 2005 at 02:56:27PM +0200, Gadi Evron wrote:
> > Now, we've all seen this coming for a while.
> > http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
> >
> > Where do we go from here?
>
> I am feeling smug that in a project I am working on I earlier 
> decided our integrity hashes would be a concatenation of MD5 
> and SHA-1, not that that's a fix, but it helps.
>
> I am also appreciating that hashes are used (this project 
> included) for many different things, not all of which are 
> directly affected by this break.  Yes, this is a bad omen for 
> the longevity of SHA-1 for other uses, so we will keep an eye on it.
>
> Something I am intrigued about is more sophiticated 
> compositions of, say, SHA-1 and MD5.
>
> -kb