jimkirk@CORRAL.UWyo.Edu (James Kirkpatrick) (04/05/91)
I've been looking into Manipulation Detection Codes (MDCs), partly by
reading Virus-L archives, and have a few questions:
- Robert Jueneman published a paper describing his own QCMDCV4 algorithm,
but Don Coppersmith published a review in which he states:
... "the described scheme is insecure (a fact apparently not noted
elsewhere); its simple construction allows a direct attack. The reader
is hereby warned against its implementation."
My question is, has Coppersmith ever published or described the
attack? I have not been able to find anything other than the above
claim. Also, has anybody implemented it, or obtained Jueneman's
implementation?
- 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. This worries me because of the experience of
knapsack cryptosystems, where a single-iteration system was first
broken, followed by the introduction of multiple-iteration systems,
which were in turn broken (at least, that is my recollection; I may
have some details wrong).
Questions: does anybody have a better feel for the probable security
of the multi-pass SNEFRU, knowing that the earlier version was
broken? Does the multi-pass version slow down the whole process
(or is it still acceptably quick)?
- MD4 was also discussed, and I have obtained the paper from
CERT.SEI.CMU.EDU in pub/virus-l/docs md4.rsa.paper. However,
the paper appears to be incomplete, in that it claims to contain
an example implementation, but only contains a few declarations and
seems to be missing actual code.
Questions: How does one get MD4? Has anybody broken it yet or
even proposed a method?
General question (last one!): Jueneman carefully points out weaknesses
in other MDCs, such as the inability to distinguish between a last
block that has been padded with (say) zeros, as opposed to a last
block that is "short." He points out that, for example, ANSI/ISO
standards (X9.9? I don't have the paper handy, sorry) have this flaw.
Do MD4 and/or SNEFRU suffer from this? (MD4 appears to be free of
this problem, but it is not explicitly stated as far as I can tell.)
Thanks in advance!
Jim Kirkpatrick JIMKIRK@CORRAL.UWYO.EDUpadgett%tccslr.dnet@uvs1.orl.mmc.com (Padgett Peterson) (04/06/91)
>From: jimkirk@CORRAL.UWyo.Edu (James Kirkpatrick) > Questions: does anybody have a better feel for the probable security > of the multi-pass SNEFRU... For discussion: a lifetime ago (when ASR-33 traffic was encrypted using the tube-driven KY-26), I was involved with definition of such algorithms. The impression was that for any single key multipass system, if transposition was not used, a single-pass decryption was still possible. If transposition was used, the same number of passes may be required to decrypt (if the encryption is recursive, then the number is something between one and the recursion frequency). ANY continuous encryption method can be broken given enough horsepower (the Intel i860 family makes it easier), the real fist question must be, "How much is someone else willing to spend to break my system ?" and tailor your response accordingly. ps discontinuous cyphers are another subject but DES is continuous.
RADAI@HUJIVMS.BITNET (Y. Radai) (04/08/91)
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