Re: Collision in SHA-0

From: Bill Unruh (unruh_at_string.physics.ubc.ca)
Date: 08/18/04 

Date: 17 Aug 2004 22:14:49 GMT

Martin Bodenstedt <martin.bodenstedt@landtag-bw.de> writes:

]S. Vinder wrote:

]> Tom St Denis <tomstdenis@iahu.ca> wrote in message news:<211Tc.392646$rCA1.212242@news01.bloor.is.net.cable.rogers.com>...
]>
]>
]>>It wasn't broken and now it is.
]>
]>
]> It's incorrect to say that one discovered collision means the the
]> algorithm is "broken" in this case. If you test 2^2048 input values,
]> you cannot expect to get 2^2048 different output values from a hash
]> function that is only capable of producing 2^160 output values.

And if he tested 2^2048 inputs, then he is a far far far greater genius
than just finding a collision.
Even 2^160 inputs is pretty great.

Note that if he manufactured the collision then it truely is broken.
.

]That was my thinking as well.

]Any hash function is bound to create collisions when its output value
]range is orders of magnitude smaller than the range of input values.

]Or am I missing something here?

No it is true. That is why all modern crypto hash functions have many bits
in them (eg 128 bits). A 4 bit hash is very easy to find collisions. a 128
bit hash much more difficult.

Relevant Pages

  • Re: Hash Function problem
    ... It depends what do you call _fast_ hash function. ... I just want the risk of collision to be lower than, ... use the full 160 bits out of MD5 or SHA-1. ... decrease the input cardinality or raise hashcode output bits number. ...
    (comp.programming)
  • Re: keys and counters
    ... how many times can the counter be incremented before there is a collision in the hash, that is what i am asking. ... A hash function operated in such a counter mode as you suggest does not have this property - if I can guess or discover the input to the first block then I will know all the other blocks. ... You might think that some attacks are unreasonable/infeasible but do you really know what is possible to the world's largest employer of mathematicians, who have had for many years the world's largest computer budget and unlimited access to 60 plus years of classified research or what is possible for any of the other multi-billion dollar "smaller" big brothers?. ...
    (sci.crypt)
  • Re: Question about tcp hash function tcp_hashfn()
    ... TCP implementation in Linux. ... efficient hash function. ... on the length of the collision list. ... at startup further reducing the size of collision lists. ...
    (Linux-Kernel)
  • Fast non-cryptographic hash
    ... I'm looking for a very fast (on intel/amd) hash function, ... Finding a collision may be tractable. ... a similar problem using md5. ...
    (sci.crypt)
  • Re: HMAC -NMAC security
    ... >> It all depends on what you assume about the hash function H. If you ... Now in the HMAC case, ... If I have an oracle that takes as input any message m and always gives me ... A collision in the inner hash computation will automatically translate into ...
    (sci.crypt)