                   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.



