hashes on restricted domains: random functions or permutations?

Victor Duchovni Victor.Duchovni at MorganStanley.com
Wed Oct 18 00:00:41 EDT 2006


On Tue, Oct 17, 2006 at 07:13:11PM -0500, Travis H. wrote:

> So I was reading about the OTP system (based on S/Key) described in RFC 
> 2289.
> It basically hashes a secret several times (with salt to individualize
> it) and stores
> the value that the correct password will hash to.
> 
> Now my question is, if we restrict ourselves to, say, 160-bit inputs, is 
> SHA-1
> a permutation, or do collisions exist?

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.

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.

-- 

 /"\ 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



More information about the cryptography mailing list