From dawagner@tucson.princeton.edu Sat Dec 3 00:46:13 EST 1994
Article: 30782 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Subject: Hashing with SL_2
Message-ID: <1994Dec3.054445.16701@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Princeton University
Date: Sat, 3 Dec 1994 05:44:45 GMT
Lines: 59
I just managed to get my grubby little hands on a
copy of the Crypto '94 conference proceedings, and
I read with interest a paper entitled "Hashing with
SL_2." The authors propose a new hash function
based upon the properties of Cayley graphs on the
group action of SL_2(F_{2^n}). Their hash function
is a function H : {0,1}^* -> SL_2(F_{2^n}).
I don't know enough group theory to get any feel
for whether their proposal is any good or not, but
they note one property which worries me:
H(x concatenated with y) = H(x) * H(y)
where * is the group operation of SL_2(F_{2^n})
[namely, matrix multiplication].
I'm worried about this property -- doesn't it weaken
the hash function? Any cryptographically strong hash
is supposed to satisfy the property that inverting
the hash of a m bit message takes 2^m time. (if m is
less than the length of the hash)
It seems to me like there's a straightforward meet-in-the-middle
attack on their hash function which lets you invert
the hash Z of a m bit message in 2^(m/2) time:
1. Calculate H(x) for all m/2 bit messages x and
store (x,H(x)) in a hash table keyed on the second
coordinate of the ordered pair.
2. Calculate Z * H(y)^{-1} for all m/2 bit messages
y and store (y, Z * H(y)^{-1}) in the same hash
table, which is of course keyed on the second
coordinate of the ordered pair.
3. Find a collision x,y in the hash function.
Then we will have
H(x) = Z * H(y)^{-1}
or in other words
Z = H(x) H(y) = H(x concatenated with y).
This gives an algorithm to invert the hash of a m bit
message with 2^(m/2) operations and 2^(m/2) space,
doesn't it?
By using Wiener and van Oorschot's result about collision
search, I guess this could presumably be reduced to just
2^(m/2) time? I'm not sure...
[Speaking of their paper, does anyone know if there's a
copy of it on the net anywhere? I wanna see if it will
succeed in eliminating the space requirement on the
meet-in-the-middle attack on double DES... :-]
-------------------------------------------------------------------------------
David Wagner dawagner@princeton.edu