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