[230] in Kerberos_V5_Development
snefru 2 pass broken
jtkohl@ATHENA.MIT.EDU (jtkohl@ATHENA.MIT.EDU)
Tue Apr 24 14:32:36 1990
Date: Mon, 23 Apr 90 16:36:29 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,
MBerstein@DOCKMASTER.NCSC.MIL, MOTI%YKTVMH.BITNET@cunyvm.cuny.edu,
S.Wilbur@Cs.Ucl.AC.UK, andrews@apple.com,
cheriton@Pescadero.Stanford.EDU, chongo@toad.com,
chrisj@fawlty.towers.oz.au, cjm%otter@hplabs.com,
devine%cookie.DEC@decwrl.dec.com, dyson@apple.com,
estrin%jerico.usc.edu@oberon.usc.edu, fin@net.umn.edu,
gasser@ultra.enet.dec.com, gww@sun.com, ivan@daimi.dk,
jfarrell@sun.com, jon@BITSY.MIT.EDU, jtkohl@ATHENA.MIT.EDU,
karn@thumper.bellcore.com, kent@bbn.com,
lg@computer-lab.cambridge.ac.uk, linn@bbn.com, mark@xanadu.com,
merkle@parc.xerox.com,
jennie%csadfa.cs.adfa.oz.au%munnari.uucp@uunet.UU.NET,
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, roelofsen%hlsdnl5.bitnet@cunyvm.cuny.edu,
sakurai@mjv870.isl.melco.co.jp, silvio@mc.lcs.mit.edu,
simon@actrix.co.nz, slt@ics-m.cgd.ucar.edu, smid@st1.icst.nbs.gov,
stigfro@idt.unit.no, wayner@svax.cs.cornell.EDU
Subject: Break of 2-pass Snefru, reward for 4-pass Snefru
The following was posted to sci.crypt:
This is to announce that Eli Biham in Israel has won the
$1,000 prize for breaking the 2-pass version of Snefru.
Congratulations, Eli!
The first message is:
3F E1 5E 26
23 B7 C0 30
C7 08 99 99
90 EF C4 8F
A0 4D 87 EE
16 49 33 92
00 04 60 85
00 00 34 15
00 00 00 00
00 00 00 00
00 00 00 00
00 00 00 00
The second message is the same as the first,
except for rows 5, 6, 7 and 8; which are:
A9 A0 9F EE
D7 4A F7 AE
09 6C 78 85
C1 9E F0 29
I don't know the actual method, but do know that
"The attack can create an unlimited number of pairs
hashing to the same 128 bit value." The cracking
program was run on an IBM PC, so the attack relies
more on clever analysis than brute force. In due
course, I expect that the method will be published
-- I look forward to seeing it.
Eli Biham is a Ph.D. student of Adi Shamir's.
It goes without saying that I recommend against the use of
Snefru with 2 passes at this time!
The complexity of cryptanalysis normally goes up quite rapidly with
the number of rounds, so it will be interesting to see how well
the attack works against the 4-pass version of Snefru. To
encourage this analysis (and to provide further projects for
Adi's students!), I am posting a $1,000 reward for breaking
Snefru with 4 passes.
Snefru can be set to 4 passes by setting the command-line
option to "4" (for Snefru 2.0 or 2.1) or by compiling with
the "-DSECURITY_LEVEL=4" cc option (for Snefru 2.3). The
default security level can be changed from 2 to 4 by changing
the line:
int securityLevel = 2;
to
int securityLevel = 4;
(The security parameter cannot be increased above 4 in the released
versions of Snefru because each pass uses two S-boxes. The released
version of Snefru provides 8 S-boxes, sufficient for 4 passes.)
Naturally, it would be prudent to wait a while to let Eli and
others examine the 4-pass version before drawing any conclusions
about its security. In particular, production use of Snefru is
not recommended at this time.
MD4 and Snefru
Although Snefru provides greater flexibility in selecting
input and output block sizes, MD4 was already slightly
faster than Snefru with 2 passes. The change to
4 passes means MD4 is now over twice as fast as Snefru. Further,
MD4 does not use any tables or S-boxes. From a system point of
view the functionality provided by the two hash functions is
nearly identical, and the better performance of MD4 makes
it more attractive if it proves secure. While it is still too
early to make confident statements about the security of MD4,
should it resist attack for the next year or so then it would
become the obvious choice for a standard one-way hash function.
Should MD4 show signs of weakness, then Snefru with 4 passes would
be the obvious next candidate.
I would also like to add that, in my experience, offering a prize
is an effective method for encouraging vigorous attacks upon a system
and thus of providing better information about the actual level of
security provided by the system. Both the actual monetary value and
the recognition provided by a prize are important. It is a practice
which should be encouraged.
Once again, congratulations to Eli Biham!
New Reward for breaking Snefru with 4 passes:
A reward of $1,000 is offered to the first person who shows
they have broken Snefru with 4 passes. A "break"
is defined as providing two different inputs that produce the
same output. The output size will be 128 bits, and the "security level"
parameter will be set at 4.
Fine print: Xerox employees cannot enter. The winner must send his
name, address, and social security number (if available) along with the
inputs x and x' that produce the same output. It is expected that
other relevant information (the nature of the algorithm used, the
hardware, etc) will also be sent, though this is not required. Any
taxes are the responsibility of the winner. We reserve the right
to decide ties (multiple entries on or about the same date) and our
decision will be final.
