Michael Silk wrote:
> 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 )
> --
>
I assume you mean hashFUnc2 inside the parentheses (I'll refer to it as
that anyway, for clarity).
No it won't, because if hashFunc2 has collisions the resulting output
will collide in hashFunc1 as well. The collision resistance in this case
is somewhat less than that of hashFunc2 (because two different outputs
of hashFunc2 might collide in hashFunc1, and collisions in hashFunc2
will always produce the same output from hashFunc1) and not, as someone
else suggested, the smallest of the two.
If the attacker doesn't know this is how the algorithm works, he might
be stumped for a whole five minutes or so, but a strong hash isn't
supposed to depend on the algorithm not being known.
If you didn't mean hashFunc2 inside the parentheses, you have actually
lessened the collision resistance, owing to the possibility that two
different outputs might collide as well.
> 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 (at) ca (dot) com [email concealed]]
>>Sent: Friday, 18 February 2005 8:34 AM
>>To: Kent Borg; Gadi Evron
>>Cc: bugtraq (at) securityfocus (dot) com [email concealed]
>>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 (at) borg (dot) org [email concealed]]
>>Sent: Wednesday, February 16, 2005 6:27 PM
>>To: Gadi Evron
>>Cc: bugtraq (at) securityfocus (dot) com [email concealed]
>>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
>
>
>
> 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 )
> --
>
I assume you mean hashFUnc2 inside the parentheses (I'll refer to it as
that anyway, for clarity).
No it won't, because if hashFunc2 has collisions the resulting output
will collide in hashFunc1 as well. The collision resistance in this case
is somewhat less than that of hashFunc2 (because two different outputs
of hashFunc2 might collide in hashFunc1, and collisions in hashFunc2
will always produce the same output from hashFunc1) and not, as someone
else suggested, the smallest of the two.
If the attacker doesn't know this is how the algorithm works, he might
be stumped for a whole five minutes or so, but a strong hash isn't
supposed to depend on the algorithm not being known.
If you didn't mean hashFunc2 inside the parentheses, you have actually
lessened the collision resistance, owing to the possibility that two
different outputs might collide as well.
> 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 (at) ca (dot) com [email concealed]]
>>Sent: Friday, 18 February 2005 8:34 AM
>>To: Kent Borg; Gadi Evron
>>Cc: bugtraq (at) securityfocus (dot) com [email concealed]
>>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 (at) borg (dot) org [email concealed]]
>>Sent: Wednesday, February 16, 2005 6:27 PM
>>To: Gadi Evron
>>Cc: bugtraq (at) securityfocus (dot) com [email concealed]
>>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
>
>
>
[ reply ]