[53773] in cryptography@c2.net mail archive
Re: hashes on restricted domains: random functions or permutations?
daemon@ATHENA.MIT.EDU (Victor Duchovni)
Wed Oct 18 07:15:36 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 18 Oct 2006 00:00:41 -0400
From: Victor Duchovni <Victor.Duchovni@MorganStanley.com>
To: Cryptography <cryptography@metzdowd.com>
Mail-Followup-To: Cryptography <cryptography@metzdowd.com>
In-Reply-To: <d4f1333a0610171713k414561fctdba16c14559e2356@mail.gmail.com>
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@metzdowd.com
