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