From dawagner@phoenix.princeton.edu Wed Feb 15 14:50:08 EST 1995
Article: 32484 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!phoenix.princeton.edu!dawagner
From: dawagner@phoenix.princeton.edu (David A. Wagner)
Subject: hashes which can be iterated quickly
Message-ID: <1995Feb15.194829.17429@Princeton.EDU>
Summary: They'd be useful, but they seem strange, and might not even exist.
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: phoenix.princeton.edu
Organization: Princeton University
Date: Wed, 15 Feb 1995 19:48:29 GMT
Lines: 63

Someone asked a while back for a hash function h which has the
special property that the n-th iterate h^n(x) can be computed
in time O(log n) or so.  [By h^2(x) I mean h(h(x)), etc.]
This would be useful for S/Key-like applications.

I've been thinking about it, and I think I can show that if
such a hash exists, it certainly cannot be collision-free.
[By a collision-free hash, I mean one in which a birthday
attack is the most efficient way to find a collision.]

Suppose h were such a hash with b bits of output.  I'll
exhibit an attack which finds a collision of h in O(2^(b/4))
time; birthday attacks should take O(2^(b/2)) time.
[Ignore logarithmic factors for simplicity.]

Let k = 10 2^(b/2), say.  Fix a bit string a.  For convenience
in ASCII notation, let f(j) = h^j(a).  The typical method
of finding a collision goes like this: by the birthday paradox,
the sequence f(0), f(1), f(2), ..., f(k) will hit a cycle
with very high probability.  This leads to a collision in h.
[Because if i, j are the least i < j with f(i) = f(j),
then f(i-1) and f(j-1) are two colliding preimages of h.]

In my special attack, I'll compute the following values:

f(k), f(k + sqrt(k)), f(k + 2 sqrt(k)), f(k + 3 sqrt(k)), ..., f(2k),
f(2k + 1), f(2k + 2), f(2k + 3), ..., f(2k + sqrt(k)).

This can be done in O(sqrt(k) log k) = O(b 2^(b/4)) time.
[Since I'm ignoring logarithmic factors, we could call
this O(2^(b/4)).]

Now I claim that if the original sequence f(0), ..., f(k)
cycles, then this new shorter sequence will have a collision
in it.  Why?  Let m be the cycle length of the original
sequence.  If m <= sqrt(k), there will surely be a collision
in the last m+1 elements of the new sequence.  Otherwise,
note that for any i, j >= k with i = j mod m, we'll have
f(i) = f(j).  But now looking at the residue classes of
k, k + sqrt(k), k + 2 sqrt(k), ... mod m, and knowing that
sqrt(k) < m <= k, we can use a pigeonholing argument to
see that there must be a collision in the new sequence.
[Email me if I've lost you.]  Then we can easily search
back in the cycle to find two different preimages for h
which collide.

A million thanks to Seth Breidbart <sethb@panix.com>
who suggested this type of probe sequence.

What does this mean for the original request for a iterable
hash function for S/Key?  Well, it means you must look to a
one-way hash function which isn't really collision-free,
which seems like a rather strange beast to me.  [All the
crypto one-way functions I know of, like MD5, SHA, discrete
exponentiation, etc. are collision-free: anyone know of any
that aren't?]

I don't know if there's a general attack which can succeed
in inverting an iterable one-way function by this type of
approach; if so, that'd be a big problem...

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu