[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: SHA-1 broken

Michael Silk wrote:
Inline.


Naturally. Likewise.


-----Original Message-----
From: exon [mailto:exon@xxxxxxx] Sent: Saturday, 19 February 2005 8:58 PM
To: bugtraq@xxxxxxxxxxxxxxxxx
Subject: Re: SHA-1 broken

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 + hashFunc2(input) + salt ) // // instead of
//
result = hashFunc1( input + salt )
--


I assume you mean hashFUnc2 inside the parentheses


Yes.



No it won't, because if hashFunc2 has collisions the resulting output will collide in hashFunc1 as well.


How?

The attackers input is "input". He can only choose to enter a
collision for "hashFunc1" _OR_ "hashFunc2". He can't enter a
collision for both, but that is what he needs to pass this
function with a different string from the original.



The collision resistance in this case is somewhat less than that of hashFunc2 (because two different outputs of hashFunc2 might collide in hashFunc1, 


Sure, hashFunc2 might give collisions, but it doesn't mean anything
unless _THOSE_ collisions are collisions in hashFunc1 that lead to the
original hash.


if(HF2(xxx) == HF2(XXX))
then
HF1(HF2(xxx)) == HF1(HF2(XXX))
regardless of collisions in HF1, since HF1 is fed the same input for both those inputs. In effect, this means that if HF1 is a perfect hash (no collisions, ever) it would still collide because it is given the same input from HF2.

To force a collision to exist in both hashes you would have to do something like this, which was posted to this list erlier by someone whose name I can't recall (assume + means concatenation)
output = HF1(input + HF2(input))

Note that this is just off the top of my head and would most likely depend on the algorithms used, but the input MUST be fed unaltered to both hashing functions for it to be any stronger than the original implementation (in theory, that is).

/exon