Weakness in MD5 or SHA-1 ?

Franz Scheerer 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 mailing list