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@xxxxxx> 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@xxxxxxxxx] > Sent: Thu 2/17/2005 10:30 PM > To: Scovetta, Michael V; bugtraq@xxxxxxxxxxxxxxxxx > 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@xxxxxx] > > Sent: Friday, 18 February 2005 8:34 AM > > To: Kent Borg; Gadi Evron > > Cc: bugtraq@xxxxxxxxxxxxxxxxx > > 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@xxxxxxxx] > > Sent: Wednesday, February 16, 2005 6:27 PM > > To: Gadi Evron > > Cc: bugtraq@xxxxxxxxxxxxxxxxx > > 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 > > >
