Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!mips!pacbell.com!iggy.GW.Vitalink.COM!widener!netnews.upenn.edu!vax1.cc.lehigh.edu!cert.sei.cmu.edu!krvw
From: RADAI@HUJIVMS.BITNET (Y. Radai)
Newsgroups: comp.virus
Subject: Re: MDC questions
Message-ID: <0006.9104091351.AA04984@ubu.cert.sei.cmu.edu>
Date: 8 Apr 91 12:22:00 GMT
Sender: Virus Discussion List <VIRUS-L@LEHIIBM1>
Lines: 45
Approved: krvw@sei.cmu.edu


  In answer to some of Jim Kirkpatrick's questions:

>-SNEFRU was discussed on this list, but I was dismayed to find it
> had been broken, and that Merkle's response was to increase the
> number of passes.

  Yes, 2-pass Snefru was broken, but I think only in the sense that it
is computationally feasible to find *some* pairs x1, x2 (x1 != x2)
such that Snefru(x1) = Snefru(x2).  I'm not sure in what context this
type of breaking is significant.  It does not imply that for a *given*
x it is feasible to find an x' != x such that Snefru(x') = Snefru(x)
(unless one collects an enormous number of such pairs (x1,x2), which
hardly seems practical).
  (Btw, 3-pass Snefru is also weaker than expected, but apparently not
by enough to make it breakable in the way that 2-pass Snefru was
broken.)

> .......  Does the multi-pass version slow down the whole process
> (or is it still acceptably quick)?

  Increasing the number of passes slows down Snefru considerably.
Here are some relative times that I once obtained:
                   MD4                         7.9
                   Snefru, 2 passes           17.5
                   Snefru, 4 passes           27.7

  Btw, the source code for Snefru which Merkle supplies does *not*
give correct results on a PC (it ignores 0Dh bytes and halts on a 1Ah
byte).  This is because he neglected to perform his reads in binary
mode.

> Questions:  How does one get MD4?  Has anybody broken it yet or
> even proposed a method?

  I have the source code for MD4 and could send it to you.  As far as
its being broken, I'm pretty sure it hasn't (unless someone is keeping
the fact secret).  Maybe that's because Rivest didn't offer a reward,
as Merkle did :-) .  More seriously, the structure of MD4 is quite
different.

                                     Y. Radai
                                     Hebrew Univ. of Jerusalem, Israel
                                     RADAI@HUJIVMS.BITNET
                                     RADAI@VMS.HUJI.AC.IL