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
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