[CI] Re: Finding collision resistant hash functions

Major Variola (ret) mv at cdc.gov
Wed Jul 9 11:07:31 PDT 2003


At 02:59 AM 7/9/03 -0700, Sarad AV wrote:
>hi,
>> MV:
>>There's nothing gained by
>> increasing
>> the input entropy (compressing
>
>I was looking for such a compression function such
>that the chances of collision in the message digest
>obtained by hashing these 2^80 messages is collision
>free or very low probability of collision or in other
>words I dont want the birthday attack to work on it.
>
>If i hash 2^80 messages they should be equidistibuted
>in such a manner that it does not affect the security
>of the algorithm.

Again, unless you know something about the distribution
of your input AND their interaction with your chosen
hash function, you gain nothing by remapping (compression
or otherwise) your input.  And again, a good hash function
will disperse your input randomly, regardless of its clustering.

So pick a crypto-like hash function
(which guarantees random dispersion)
and use it.  You can't do better unless
you "cheat" and know your input before
you pick a hash function.  And picking pathological
inputs (to cause collisions) will be hard.

e.g.,

hash=0
while (input)
    hash = hash ^ DES( input, fixed_key )
return hash

The only reason to compress would be to
cut down the number of DES operations,
useful only if compression is cheaper than DES.





More information about the cypherpunks-legacy mailing list