Re: SHA-1 broken

[Michael Silk <michaelsilk () gmail com>]

Michael,

 But with such functions the point is that "input" isn't a function,
it's a string - and it can only be the inverse of one, not both; i.e.
the result of "invHashFunc1( foo )" _wont_ equal "invHashFunc2( foo
)".

 So if the user is attempting to break a login screen with his
invHashFunc's, and the hash of the users password is implemented as
described, they can't possibly provide the right inversions for _both_
functions in one string; unless they happen to be the same.

 No?

-- Michael


On Fri, 18 Feb 2005 00:45:24 -0500, Scovetta, Michael V
<Michael.Scovetta () ca com> wrote:
> Michael,
>  I'm not sure that it would help significantly. If the end-result of
> this research on breaking hash algorithms is to create "inverse-MD5" and "inverse-SHA" functions, then:
>  input = invHashFunc2( substring(invHashFunc1(result)) )
>
> By our assumptions, invHashFunc1 and invHashFunc2 are both tractable, the substring function would simply add a 
> polynomial factor to the calculation to guess it right.
>
> You could create arbitrarily complex functions, like:
>  MD5(SHA(input+salt)+MD5(input+salt)+salt)
> But in the end, if invHashFunc1 and invHashFunc2 are both tractable, then nothing you do could help it (beyond a 
> polynomial factor). And keeping the actual algorithm-composition secret wouldn't help much either.
>
> -Mike
>
> -----Original Message-----
> From:   Michael Silk [mailto:michaelsilk () gmail com]
> Sent:   Thu 2/17/2005 10:30 PM
> To:     Scovetta, Michael V; bugtraq () securityfocus com
> Cc:
> Subject:        RE: SHA-1 broken
> 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