hashes on restricted domains: random functions or permutations?

[Victor Duchovni]

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 majordomo at metzdowd.com