[233] in Kerberos_V5_Development
Re: snefru 2 pass broken
jtkohl@ATHENA.MIT.EDU (jtkohl@ATHENA.MIT.EDU)
Mon Apr 30 16:24:20 1990
Date: Mon, 30 Apr 90 12:10:44 PDT
From: Ralph Merkle <merkle@parc.xerox.com>
To: Diffie@bnr.ca, EFBrick@sandia.gov, Eric@snark.uu.net,
Gerald.Krummeck@ec.bull.fr, LNZ@Lucid.com,
MOTI%YKTVMH.BITNET@cunyvm.cuny.edu, S.Wilbur@Cs.Ucl.AC.UK,
andrews@apple.com, authenticationInterest^.pa@arisia.Xerox.COM,
cheriton@Pescadero.Stanford.EDU, chongo@toad.com,
chrisj@fawlty.towers.oz.au, devine%cookie.DEC@decwrl.dec.com,
dyson@apple.com, estrin%jerico.usc.edu@oberon.usc.edu,
gasser@ultra.enet.dec.com, gww@sun.com, ivan@daimi.dk,
jennie%csadfa.cs.adfa.oz.au%munnari.uucp@uunet.UU.NET,
jfarrell@sun.com, jon@BITSY.MIT.EDU, jtkohl@ATHENA.MIT.EDU,
karn@thumper.bellcore.com, kent@bbn.com,
lg@computer-lab.cambridge.ac.uk, mark@xanadu.com,
merkle@parc.xerox.com, merkle@parc.xerox.com, ota+@andrew.cmu.edu,
prz@ics-m.cgd.ucar.edu, randall@DOCKMASTER.NCSC.MIL, rcs@la.tis.com,
rivest@theory.LCS.MIT.EDU, roelofsen%hlsdnl5.bitnet@cunyvm.cuny.edu,
roelofsen@hlsdnl5.bitnet, sakurai@mjv870.isl.melco.co.jp,
shamir@wisdom.bitnet, silvio@mc.lcs.mit.edu, simon@actrix.co.nz,
slt@ics-m.cgd.ucar.edu, smid@st1.ncsl.nist.gov,
wayner@svax.cs.cornell.EDU
Subject: Further analysis of 2-pass Snefru by Eli Biham
Eli Biham is continuing his investigation into the security of the
2-pass version of Snefru. It has already been established that 2-pass
Snefru is insecure. Further analysis of the 2-pass version will lay the
groundwork for an attack on the 4-pass version. It will be most interesting
to see the eventual results of this attack.
As background, it is useful to observe that repeated application of simple
operations can "scramble" data into apparent randomness. The concept that
the security of a system can be improved by repeatedly applying simple
operations is well accepted, as is the idea that a relatively modest number
of repetitions of the scrambling operation should be sufficient.
Unfortunately, even if we presume that a system is secure when
enough repetitions of the basic scrambling operation are performed,
it is difficult to establish how many is "enough". Herein lies the
great value of the work being done by Eli (and others who attack
published systems). While it cannot yet be assumed that Snefru
with even an infinite number of passes is secure, it seems more
likely that there IS a fixed number of passes for which
it is secure. At present, the only way to establish this is through
vigorous attack.
Of course, setting the number of repetitions too high exacts a performance
penalty that must be paid by all users of the system, while setting the
number too low results in a system that is insecure. There are, therefore,
strong forces in both directions. Finding the smallest number of repetitions
which provides security is, therefore, a very valuable contribution.
Those who wish to be kept up-to-date on the further analysis of the 2-pass
version of Snefru should send me E-mail. Any break of the 4-pass version
will, of course, be posted.
Ralph C. Merkle
----- Begin Included Message -----
Dear Ralph,
Here is the latest news on Snefru. I arranged it as an announcement, but
wanted you to be the first to learn about the developments. So after you
get and read this message, please send it to the same list of correspondents
which received your earlier announcement (and cc to me to know that it was
received).
Best personal wishes, Adi.
IMPROVED ATTACKS ON SNEFRU
Eli Biham's attack on Merkle's Snefru hash function has been significantly
improved in the last few days:
1. It is now possible to attack the two pass version of Snefru even if its
output size is almost doubled (from 128 bits to 224 bits). The following pair
of messages hash to the same 224 bit value:
MESSAGE 1:
5BCC4D9B E1DA3DF2 A6FB6DB0 002EEF3F
00000007 00000000 00000000 00000000
00000000
MESSAGE 2: SAME AS MESSAGE 1, EXCEPT THE FIRST 3 WORDS WHICH ARE:
EB11879B E1DA3D07 1626A76E
2. It is now possible to break Snefru in a much stronger sense: Given any
particular message, it is easy to find another message which hashes to the
same value. Consider for example MESSAGE 1 which is the all zero message.
Then the following MESSAGE 2 hashes to the same value:
00000000 F1301600 13DFC53E 4CC3B093
37461661 CCD8B94D 24D9D35F 71471FDE
00000000 00000000 00000000 00000000
3. It is now possible to find not only pairs but even triplets, quartets, etc
of messages all hashing to the same value. This is true even if one of the
messages is given. For example, the following MESSAGE 3 hashes to the same
value as MESSAGE 1 of zeroes and MESSAGE 2 above:
00000000 1D197F00 2ABD3F6F CF33F3D1
8674966A 816E5D51 ACD9A905 53C1D180
00000000 00000000 00000000 00000000
All the attacks listed above were carried out by a fairly simple program
on an IBM PC.
Adi Shamir April 26-th, 1990
