Weakness in MD5 or SHA-1 ?
fscheerer1 at gmx.de
Sat Oct 30 16:19:24 CEST 2004
It is funny to read about a weakness in SHA-1, which is considered to be a
secure, collision resistant hash function, while MD5 is proven to be not
collision resistant and still used.
>with all this talk of (allegedly!) weak and broken hashes, i'd like to
>throw out a construct to combine 2 or more hashes and (it seems) make the
>construct more secure than either one of the hashes independently: take
>two or more hashes and XOR them.
>if i XOR the output of an SHA-1 and RIPEMD-160 hash, the only way to
>"break" the resulting hash would require breaking *both* SHA-1 and
SHA-1 and RIPEMD-160 are collision resistant hash functions. Therefore, not
any attack is known, which may allow to find two differnent messages having
the same SHA-1 or RIPEMD-160 value. There is your problem ?
This does'nt prove that h = SHA-1 XOR RIPEMD-160 is collision resistant. This
might not be true in case SHA-1 and RIPEMD-160 are correlated. For a message
h(M) = 0 <=> SHA-1(M) = RIPEMD-160(M).
It might be possible to find two such messages even if SHA-1 and RIPEMD-160
are collision resistant.
>the same mechanism can apply to more than two hashes as input, but i'm not
>enough of a math guy to figure out where is the point of diminishing
>return (or if there is such a point). intuitively, it seems (to me) that
>if N hashes are used as input, the protocol is secure as long as any one
>of the input hashes can not be broken. i'm also not enough of a math guy
That is certainly not generally true.
Consider two collision resistant hash functions h1, h2 and define h:= h1 XOR
h2. If you can find two messages M1,M2 with h1(M1) = h2(M1) and h1(M2) =
h2(M2) there is a collision in h, since h(M1) = h(M2) = 0.
>to figure out (quantifiably) what would be gained (or lost) by combining
>hashes of different sizes, and maybe even truncating the output.
Don't worry about SHA-1 and replace MD5.
More information about the Gnupg-devel