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