[53881] in cryptography@c2.net mail archive
Re: hashes on restricted domains: random functions or permutations?
daemon@ATHENA.MIT.EDU (Victor Duchovni)
Wed Oct 18 15:24:50 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 18 Oct 2006 12:29:35 -0400
From: Victor Duchovni <Victor.Duchovni@MorganStanley.com>
To: Cryptography <cryptography@metzdowd.com>
Mail-Followup-To: Cryptography <cryptography@metzdowd.com>
In-Reply-To: <20061018040041.GO19878@paias899.ms.com>
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@metzdowd.com
