On Wed, Oct 18, 2006 at 12:00:41AM -0400, Victor Duchovni wrote: > Hash functions are supposed to be pseudo-random. For a 160 bit hash In > an input set of 2^80 elements we should expect to find a collision... > > If we iterate from a random starting point we expect to enter a cycle > of length ~2^79 after ~2^79 initial outputs. So the subsets on which > an iterated hash acts as a right-shift are expected to be ~2^79 in > length.
This part is right. > An intuitive (but possibly grossly wrong) leap is that there should be > ~~2^80 disjoint cycles with half of the inputs outside a cycle and half > inside a cycle. None of this should lead to any apparent weakness after > a modest number of iterations. This had to be wrong of course, the range does not separate into disjoint loops with a single linear strand leading into the loop. There is branching before the loop and multiple entry points into the loop. This reminds me of the analysis of the space-time tradeoff for brute forcing password hashes. Don't have it in front of me, but in that work effective estimates of the branching were taken into account. -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAIL Morgan Stanley confidentiality or privilege, and use is prohibited. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]