From: norm@netcom.com (Norman Hardy)
Date: Mon, 25 Jul 94 19:40:49 PDT
To: Hal <cypherpunks@toad.com
Subject: Re: Double DES calculations
Message-ID: <199407252223.PAA15416@netcom.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At 09:05 1994/07/22 -0700, Hal wrote:
>I missed the start of this double-des thread due to system problems and
>being gone, and I've never been able to pick up the main point since.  It
>sounds like some kind of meet-in-the-middle attack is being discussed.
>It is true that with current technology MITM generally seems more costly
>in terms of space than time.  However, I have seen references to techniques
>which shift this tradeoff some, costing more time and less space.  Un-
>fortunately, I can't remember where I saw them!
...
There may be more than one way that MITM (meet in the middle) may be used
to attack Double block cyphers. I assume the following attack. You know
some block of plain-text P and corresponding cypher text C. You believe
that C = E(k, E(j, P)) where E(k, p) is the encypherment of p with key k.
D(k, E(k, p)) = p. You need to find keys k and j. Classic MITM is to
produce a file A with records: <k, E(k, P)> for each k, and file B with
records <j, D(j, C)> for each j. Sort both A and B on the second field.
Pass over the sorted files looking for a record from file A whose second
field is the same as a record in file B.

To substantially shorten the ammount of tape used by a factor 2^n at the
expense of evaluating C and D 2^n more often do the following:

For m from 0 to 2^n-1 Do
  Produce file A with records: <k, E(k, P)> for each k where
    (the right n bits of E(k, P)) = m. (discarding other records)
  Produce file B with records <j, D(j, C)> for each j where
    (the right n bits of D(j, C)) = m
  Sort files A and B on second field.
  Pass over files looking for records from A that match records from b in the
  second field.
Enddo.

This is still a daunting job and evaluating its magnitide requires several
assumptions. The most obvious is the cost of evaluating C and D. Next is
the cost of reading and writing tape.