From: ritter@cactus.org (Terry Ritter)
Date: Thu, 17 Feb 94 00:55:18 PST
To: cypherpunks@toad.com
Subject: Isolated Double-DES
Message-ID: <9402170851.AA06184@cactus.org>
MIME-Version: 1.0
Content-Type: text






                   Ritter Software Engineering
                       2609 Choctaw Trail
                       Austin, Texas 78745
                (512) 892-0494, ritter@cactus.org



   2x Isolated Double-DES: Another Weak Two-Level DES Structure

                          Terry Ritter
                        February 16, 1994


Introduction

The time has come to replace DES, the US Data Encryption Standard,
but there is no clear alternative.  While there are many ciphers
which are demonstrably faster and also arguably stronger than DES,
the fact that cipher strength cannot be _tested_ but must instead
be_argued_ makes many users nervous.  The US government offers some
alternative ciphers, but those are secret designs whose strength
_cannot_ be argued, again making users nervous.

The current leading candidate for a replacement to DES is "triple-
DES," a three-level construct using DES at each level.  This is a
comforting design, because users are already convinced that DES
can be relied upon for a certain level of strength.  Unfortunately,
a software implementation of triple-DES takes three times the
processing of normal DES.  While this is a mere detail on systems
which process the occasional enciphered email message, operational
speed is fundamental to widespread industrial use.  Ciphering speed
is essential in LAN servers and other fully-enciphered communications
nodes.  Speed is also important when ciphering is an integral part
of laptop software which communicates to a central facility.  Fast
software ciphering is important.

Because the ciphering speed for triple-DES is not acceptable, no
three-or-more-level construct could possibly be satisfactory in
this respect.  This limits our design alternatives to one-or two-
level constructs based on DES.

The goal, then, is to find--if possible--a construct which is based
on DES, has strength substantially beyond normal DES, but requires
less processing than triple-DES.  This time we start from the base
of double-DES, and directly confront the known weakness of that
approach:


Double-DES

The classical double-DES construct is something like this:

            A
            v
     k1 -> DES1
            v
            B
            v
            C
            v
     k2 -> DES2
            v
            D

where each single capital letter represents an 8-byte DES block.
Double-DES is normally not used, because of the meet-in-the-middle
attack:


Meet-In-The-Middle Attack on Double DES

Assume we have known-plaintext A for ciphertext D:  Encipher A
under every possible key k1, and decipher D under every possible
key k2.  (The cost for this is only two full DES key searches.)
Then check for matches between B and C.  If there are multiple
matches, the correct k1 and k2 will be there somewhere, and we
can isolate the correct pair with one or two more known-plaintext
blocks (this is a loose interpretation of [2]).

This works for the normal double-DES construction because it is
possible to check for matches between B and C; the weakness seems
to be the ability to check for a match.  Assuming that we have
properly identified the principal weakness of double-DES, let's
fix it:  We can isolate the two values, making a match check
impossible, so that not even one bit can be checked.


Isolated Double-DES

Consider a two-level DES construct like this:

            A
            v
     k1 -> DES1
            v
            B
            v
     km -> XOR
            v
            C
            v
     k2 -> DES2
            v
            D

where k1 and k2 are 56-bit keys, but km is a 64-bit key.
Technically, this construct could be considered to be either
double-DES with an intermediate ("isolating") XOR operation, or
triple-DES with XOR replacing the middle DES operation.  But since
the processing cost for this system is similar to double-DES, it
is reasonable to call it a form of double-DES.

While it is true that we now have three keys for a two-level DES
structure, this is no worse than triple-DES with separate keys.
But is it stronger than double-DES?


Isolated Double-DES Meet-In-The-Middle Attack

Again, encipher A under every possible key k1, and decipher D under
every possible key k2 and check for matches between B and C.

But in the isolated construction, every possible pair of values
(B,C) has some key km which would make that pair match.  Thus, the
weakness of match identification in the original construction is
not possible in the alternate construction.

The keyspace seems to be 56 + 64 = 120 bits, which would probably
be satisfactory for another couple of decades, or until an open
science of cryptographic machine design has matured.  It still
has a small block size, however.


Larger Blocks

DES uses a relatively-small 8-byte block, so if DES were used
in Electronic Code Book (ECB) mode and large amounts of plaintext
were known, a dictionary attack would be possible.  Fortunately, DES
is normally used in Cipher Block Chain (CBC) mode, making dictionary
attacks difficult.  But a dictionary attack on ECB mode could be
viewed as a "certificational attack" which is "indicative of
weakness" in the cipher itself. [1:466]

If we make the modest assumption that ordinary text has an
information content of under 40 percent of the binary size, then
a 64-bit block of text generally contains less than 26 bits of
uniqueness.  Worse, short words occur far more often than an even
distribution would indicate.  Although it would certainly be ill-
advised to send 2^26 blocks (2^29 bytes) of data under a single set
of keys, it is interesting to note the relatively small size of this
figure when compared to other cryptographic quantities.

For this reason, it seems appropriate that any new standard specify
an expanded block width.  Here is a double-width approach, 2x2 DES
described in an earlier article:

             A             B
             v             v
      k1 -> DES1    k2 -> DES2
             v             v
             C             D
          Exchange Right 4 Bytes
             E             F
             v             v
      k3 -> DES3    k4 -> DES4
             v             v
             G             H

Note that the 64-bit quantity G (for example) is a complex nonlinear
function of A, B, k1, k2, and k3; a total of 296 bits.  Nevertheless
the system is still solvable with meet-in-the-middle:


2x2 DES Meet-In-The-Middle Attack

With one known-plaintext block, we can search one top key and one
bottom key (say, k1 and k3) and find pairs (E,C) which match at the
appropriate 32 bit-positions.  Then we can identify the correct
pair with additional known-plaintext blocks, resolving the keys at
32-bits per known-plaintext pair.

We can guarantee that the two keys will be found by searching all
possible k1 and k3.  This is only twice the normal DES keyspace,
but may well require a huge amount of storage to identify all the
values and associated keys (say, E and k3) which match a particular
result (say, C).  We do not want to run through every k3 every
time we change k1.


2x2 DES Differential Attack

Eli Biham [1] points out that a differential attack can eliminate
the need to store the result from every possible key.  In this case
we need two different large blocks of known-plaintext with plaintext
or ciphertext half the same (say, A:B -> G:H and A:X -> Y:Z).  With
A the same in both large blocks, we know that the left-half of E
must also be the same.  Then, since we have two different blocks, we
can step through all possible values for k3, deciphering G into E
and Y into E' each time, looking for any results with the left-half
the same.  This should occur about every 2^32 trials, producing 2^24
trials which match, which should be resolved in only one or two more
set of known-plaintext blocks.  No huge storage is needed.


2x Isolated Double-DES

Consider a pair of isolated double-DES structures, combined as
described for 2x2 DES:

            A              B
            v              v
     k1 -> DES1     k2 -> DES2
            v              v
     km -> XOR1     kn -> XOR2
            v              v
         Exchange Right 4 Bytes
            v              v
     k3 -> DES3     k4 -> DES4
            v              v
            C              D

The result is a double-width structure, in which every ciphertext
bit in C depends on each and every bit in A, B, k1, k2, and k3, as
well as half the bits in km and kn.  Ciphering occurs at the rate
of double-DES.  While it is certainly true that six keys are needed,
keys need be transmitted far less often than data, and by having
separate keys we avoid attacks which depend upon having the same
key at multiple parts of the operation.  If we say that enciphering
occurs "from the top down," (XOR before exchange) then we would say
that deciphering occurs "from the bottom up" (exchange before XOR).


2x Isolated Double-DES Meet-In-The-Middle Attack

The double-DES meet-in-the-middle attack depended upon having a
structure in which the enciphered plaintext was identical to the
deciphered ciphertext.  This allowed both keys to be manipulated
and the resulting data space searched for matches.

In isolated double-DES any enciphered plaintext value can be
related to any deciphered ciphertext value by varying the middle
or "isolating" key.  Thus, meet-in-the-middle seems not very useful.


2x Isolated Double-DES Differential Attack

The 2x2 differential attack depended not upon identical top and
bottom values, but upon producing an identical value (in particular
known bit positions) from a bottom deciphering (for example).  This
situation is not affected by the XOR and so the differential attack
will still work.


Conclusion

2x Isolated double-DES falls to a differential attack.


References

[1]  Biham, E.  Mon, 7 Feb 1994 16:59:28 GMT.  Comments on Nx2 DES.
     <CKv5v5.EnF@chinet.chinet.com>

[2]  Merkle, R. and M. Hellman.  1981.  On the Security of Multiple
     Encryption.  Communications of the ACM.  24(7): 465-467.