Path: cactus.org!news.dell.com!swrinde!cs.utexas.edu!not-for-mail
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt
Subject: Fenced DES Design Context (long!)
Date: 1 Jul 1994 00:43:44 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 968
Sender: nobody@cs.utexas.edu
Message-ID: <199407010539.AAA21904@indial1.io.com>
NNTP-Posting-Host: news.cs.utexas.edu

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


                The Context of the Fenced DES Design

                           Terry Ritter
                          June 30, 1994




 This article describes the Fenced DES cipher and its theory of
 design.  Fenced DES uses the U.S. Data Encryption Standard (DES)
 as a component in a cipher which is larger and stronger than DES,
 and yet almost as fast.

 Fenced DES is an unusual block-cipher design in that it does not
 rely on conventional iterative substitution-permutation (S-P)
 technology.  Fenced DES does not use multiple "rounds," S-P
 "permutations" or selected substitutions.  Instead, Fenced DES
 connects arbitrary invertible substitutions to an internal DES
 layer, thus guaranteeing a wide avalanche in a single step
 without special substitutions.

 The overall goal is to find a way to upgrade the strength of DES
 while using substantially less computation than Triple DES.  A
 sufficiently clean and "believable" design might even achieve a
 "derivative certification," and thus avoid the huge expense and
 delay involved in certifying a totally-new cipher.



 Table of Contents

 1  Introduction
 2  Conventional Approaches to Improved DES
    2.1  Triple DES
    2.2  Double DES
 3  Toward Fenced DES
    3.1  The Block Cipher Component
    3.2  Avalanche and Substitution
    3.3  1x Fenced DES
    3.4  Fenced DES vs. Substitution-Permutation
    3.5  Keying the Substitutions
    3.6  One Approach to Large-Block Fenced DES
    3.7  2x Fenced DES
    3.8  Block Mixing Transforms
 4  Analysis of 4x Fenced DES
    4.1  About Cryptographic Proof
    4.2  The Ideal Model
    4.3  4x Fenced DES
    4.4  Invertibility in 4x Fenced DES
    4.5  Avalanche in 4x Fenced DES
 5  Fenced DES Strength
    5.1  Strength of 1x Fenced DES with Known Substitutions
    5.2  Strength of 1x Fenced DES with Known DES Key
    5.3  Strength of 1x Fenced DES
    5.4  Minimum Strength of 4x Fenced DES
    5.5  Strength of 4x Fenced DES
 6  Attacks
    6.1  Exhaustive Search
    6.2  Codebook
    6.3  Meet-in-the-Middle
    6.4  Differential Cryptanalysis
 7  Conclusions
 8  References


 1  Introduction

 The U.S. Data Encryption Standard (DES) has remained unchanged for
 almost two decades.  During this period, unprecedented advances in
 computational machinery have improved the ability to attack the
 cipher.  While the same advances can be applied to implement the
 cipher as well as attack it, DES has a keyspace which is fixed and
 limited.  So even though DES can be made to operate faster, it
 cannot be any stronger than it was designed to be almost 20 years
 ago.  Relative to available attack technology, the cipher is far
 weaker than it was, and continues to weaken.

 There can be no question that DES will eventually be obsolete [9];
 the only question is: "When?"  Unfortunately, the answer seems to
 be: "Just about now."  For example, it now seems likely that a
 substantial capital investment in engineering development and
 equipment could construct an installation which could search the
 entire DES keyspace in a few hours [27].  In other words, the "key
 exhaustion" attack on single DES, which Tuchman called "not viable"
 in 1979 [25:41] can no longer be dismissed out of hand, just fifteen
 years later.

 Would all users need to abandon DES if governments, corporations
 and organized crime could penetrate DES?  One can certainly argue
 that most data do not need ultimate protection.  But when a DES-
 cracking machine finally is built, the economics of that expense
 argue that the machine will be kept busy if at all possible.

 Since DES has been so much a fixture in commercial cryptography,
 it may take a few years for the situation to sink in, but the
 handwriting is on the wall:  DES really must be replaced--for
 sure this time--and the sooner the better.


 2  Replacements For DES

 One of the reasons DES has been a popular cipher is that the
 Government has assured everyone that it is effective.  Every five
 years, the Government "re-certifies" the cipher.  But, starting
 around 1986, the National Security Agency has been reluctant to
 continue to re-certify DES (see [11:141], [13:55] and [19:122]).
 This, of course, would be consistent with the idea that computation
 technology will soon catch up and surpass the fixed strength of DES.


 2.1  Triple DES

 One obvious replacement for DES is "Triple DES," a three-level
 structure composed of three sequential DES operations (probably
 using three different keys):

    DES
    DES
    DES

 The input block is operated on by DES three times, and this takes
 three times the computation of DES itself.  Where encryption is an
 overhead expense, this would triple that expense, thus encouraging
 users to stay with a weakening cipher.

 On the other hand, we suspect that Triple DES has tripled the
 overall key length to 168 bits, which is more than large enough.

 Another problem with Triple DES is that it retains the original DES
 block size of 64 bits.  In the same way that we could not imagine
 using an eight-bit (or even a 32-bit) block size in a secure block
 cipher, future technical advances make reliance on the old block
 size a risky practice.  (Indeed, as early as 1973, Feistel seemed to
 think that 128-bit blocks were appropriate [7:20].)  A block cipher
 intended to last for another couple of decades must not rely on
 tiny 64-bit blocks.


 2.2  Double DES

 If the computation of Triple DES is too expensive, why not just
 use Double DES?

    DES
    DES

 Unfortunately, and contrary to intuition, Double DES is barely
 stronger than DES itself [18].  When "known plaintext" is available,
 it is possible to "match" the hidden intermediate value.  A search
 of all possible keys for the input operation, and all keys for the
 output operation (a keyspace only one bit larger than for single-
 DES) will find that match.

 Double DES does not add significant strength over DES itself, and
 may indicate that two-level constructs in general are likely to be
 weak.


 3  Toward Fenced DES

 An improved form of DES is not going to appear out of a vacuum.
 Unless we are satisfied with the simple hack of using three
 cipherings where previously one would do, we need to build up
 to a finished cipher in modest steps.


 3.1  The Block Cipher Component

 One way to look at the Triple DES cipher is to see it as a three-
 level (or product) cipher, which uses DES as a component.  In doing
 this we can make some simple assumptions about DES:

    1.  There will be no statistical relationship between input and
        output values.

    2.  Given any input block and output block, if even a single bit
        is changed in the input block, we expect about half the bits
        in the output block to change.

    3.  The DES operation can be conceptually modeled as a huge
        invertible substitution table.


 3.2  Avalanche and Substitution

 When working with block ciphers, one soon notices their extreme
 sensitivity to change.  Even a tiny change in the input (plaintext)
 value does not produce a small change in the output (ciphertext),
 but instead tends to change about half of the output bits.  Feistel
 called this property "avalanche" [7:21].

 The term "avalanche" is probably most descriptive in the context
 of an iterated "product" cipher (such as DES) which has multiple
 "rounds."  In such a cipher, we can follow a small input change
 and watch it affect just a few adjacent bits, and then grow,
 round by round, as each of those bits affects a few other bits
 (see [7:20-21], [8:1547] or [5:11]).  Feistel says:

      "As the input moves through successive layers, the pattern
      of 1's generated is amplified and results in an unpredictable
      avalanche.  In the end, the final output will have, on the
      average, half 0's and half 1's . . . ." [7:22]

 Avalanche is a requirement in a good block cipher, and is also
 an inherent property of a normal invertible substitution:  Any
 change to the input value of an invertible substitution selects a
 new and necessarily different output value.  If we look at all the
 possible substitute values, we find the same count of 1's and 0's
 in each bit position.  So, if we have one value, and then change
 the input and so select another value essentially at random, we
 expect the binary values at each bit position to change with
 _almost_ probability 0.5 (excepting only that we cannot _change_
 to the original value).  This is avalanche (see, for example,
 [7], [26] and [22]).

 Avalanche does not necessarily imply strength:  The elements in a
 substitution could occur in counting order (for example), and the
 function will avalanche anyway.  But a randomized substitution
 does imply that an input error of even one bit will have the same
 expected result as a massive error.  This denies The Opponent any
 measure of "closeness," which would otherwise allow a cipher to
 be broken fairly easily.  


 3.3  1x Fenced DES

 I have proposed (after some trial and error) a DES alternative which
 I call Fenced DES (because DES appears to be "fenced off").  We will
 later develop versions with different block widths; here is the "1x"
 Fenced DES construct:

    S S S S S S S S
    ------DES------
    S S S S S S S S

 Each of the "S" characters represents an "eight-bit-wide" (256-byte)
 substitution table randomized under the control of a User Key.  (We
 will discuss the randomization in section 3.5.)  The tables will be
 initialized before ciphering, and will not change during ciphering.

 Like Triple DES, 1x Fenced DES is also a three-layer structure.
 Since all of the information flows through DES itself, the overall
 cipher cannot possibly be weaker than DES.  This is a particularly
 important point for any new cipher design.

 Moreover, the 1x Fenced DES structure is clearly stronger than DES,
 because a "known plaintext" attack requires knowing the actual
 input and output values at the DES cipher itself, and these values
 are hidden by the input and output substitution layers.  If even a
 single input bit to DES is wrong (that is, if even one value in one
 input substitution is off by even one bit), DES will "avalanche"
 and about half of the output bits from DES will be wrong.  Thus, a
 single wrong bit has the same statistical effect as a mostly-wrong
 value; this means that it is not possible to know when the input
 value is "close," so it does not appear possible to solve the
 substitutions in an advantageous way.

 But 1x Fenced DES still has the same block-width as DES, and this
 is a problem.  A block size which appeared substantial in the
 mid-70's is rapidly becoming a manipulable quantity.


 3.4  Fenced DES vs. Substitution-Permutation

 The Fenced DES design differs from the usual iterated substitution-
 permutation (S-P) cipher [7] [12].  For one thing, Fenced DES is not
 iterative: it does not repeatedly use the same layers.  And Fenced
 DES does not _have_ permutation layers; instead, bits are "mixed"
 by the avalanche effects of an internal cipher layer.  This is a
 fundamentally different design approach.

 The main difference appears to be that S-P designs often map a
 single bit or a small subset of bits from one substitution layer
 to the next, and if this particular bit could not actually change
 (due to the arrangement of the substitution), some substitution in
 the next layer will not have the chance to avalanche.  Classical
 S-P designs avoid this problem by constructing special substitutions
 at design-time [12] [6].  But Fenced DES instead uses the guarantee
 that an input change to an invertible substitution will change
 _some_ output bit, and then uses _all_ of those bits in an internal
 cipher layer.  This guarantees that any input change will avalanche
 the internal cipher.

 A classical S-P cipher is generally keyed by selecting among two
 fixed S-boxes at each position or using exclusive-OR masks [7].
 These S-box constructions are fixed by design for all time and
 are used in all implementations of a particular S-P cipher.  In
 contrast, Fenced DES constructs new substitutions for each ciphering
 key, and so does not expose particular S-box arrangements to years
 of external analysis.  Fenced DES shuffled substitutions do not
 support a "computational trapdoor" like that which may be possible
 in S-P S-boxes [2].  And Pieprzyk-Finkelstein [20:334] [21:69]
 show that random 8-bit permutations are very likely to be of near
 "maximum nonlinearity" anyway.

 In larger versions of the Fenced DES cipher, entire blocks are
 mixed in a way guaranteed to propagate any input change.  This
 forces any input change to avalanche multiple internal ciphers,
 involving each in the strength of the overall construct.


 3.5  Keying the Substitutions

 Each Fenced DES substitution must be shuffled by a cryptographic
 random number generator (RNG) before ciphering begins (the RNG
 is not needed during actual ciphering).  Presumably, the same RNG
 will also generate the DES keys.  Fortunately, in this application,
 the cryptographic strength aspects of the RNG can be minimized,
 because the only RNG exposure is in the arrangement of the values
 in the substitutions, and if that arrangement is known, the cipher
 is probably broken anyway.

 Perhaps the most efficient basis for such an RNG is the Additive
 RNG [14:27].  This has become well understood, and is basically
 a Linear Feedback Shift Register (LFSR) using addition mod 2**n
 [16] [17].  The Additive RNG is especially suited to fast software
 implementation.  In one version, there are three pointers into a
 circular queue, and the RNG "step" operation consists of taking two
 of the pointed-to elements, adding them, and placing the result
 in the queue through the third pointer.  Then the pointers are
 incremented within the queue, and the result returned.

 Thus, an Additive RNG based on a feedback trinomial (a primitive
 mod-2 polynomial) "steps" an RNG with a huge amount of internal
 state with just a single addition and a few pointer operations.
 We can compare this to a Linear Congruential Generator (LCG) which
 uses a multiply and an add, but involves only a small amount of
 state.  We can also compare it to number-theoretic generators
 [e.g., 4], which must carry out a very expensive multiple-precision
 multiplication and division for each RNG step.

 A reasonable structure for the Fenced DES RNG is 31 elements of
 32 bits each, for a total state of 992 bits.  (Recall that DES
 itself has a 56-bit key.)  This state can be initialized easily
 from a User Key by using an array of 32 deg-31 primitive mod-2
 polynomials as Cyclic Redundancy Checks (CRC's).  This produces
 32 31-bit values which can be re-arranged into 31 32-bit values
 to become the state for the RNG.  This CRC-based initialization
 has a strong mathematical basis, and allows the User Key to be
 ASCII or binary, of arbitrary length, and thus provides a strong
 universal key interface.

 Since the Additive RNG is essentially a linear mechanism, it is
 necessary to "nonlinearize" the sequence.  My usual technique [23]
 is to "drop out" pseudo-random length sections of the linear
 sequence, leaving pseudo-random length "take" islands, and to
 "offset" each take sequence with a different pseudo-random offset
 value.  With fairly short "take" islands, this should render the
 usual linear attacks worthless, at a cost of dropping some moderate
 fraction of the sequence.  Additional isolation is provided by the
 cheap width of the RNG, since only 8 bits are needed, but 32 bits
 are calculated.  This means that 3/4 of the RNG state is always
 hidden, but must nevertheless be resolved before the RNG can be
 completely exposed.


 3.6  One Approach to Large-Block Fenced DES

 Suppose we want to handle a double-sized DES block at nearly DES
 speeds, how do we do it?  Well, we certainly must mix all the
 input bits, so that a change in even one bit will affect both DES
 operations.  In addition, each and every output bit should be an
 invertible function of both DES operations.  Here is one approach:

    | | | | | | | |   | | | | | | | |
    -------S-------   -------S-------  ...
    | | | | | | | |   | | | | | | | |
    | | | | | | | |      ...
    | | | | | | | |________________________
    | | | | | | |________________________  |
    | | | | | |________________________  | |
    | | | | |________________________  | | |
    | | | |                          | | | |
    --------------------DES--...     -------------------DES--...
    | | | |  ________________________| | | |
    | | | | |  ________________________| | |
    | | | | | |  ________________________| |
    | | | | | | |  ________________________|
    | | | | | | | |      ...
    | | | | | | | |   | | | | | | | |
    -------S-------   -------S-------  ...
    | | | | | | | |   | | | | | | | |

 Here we show 2 of 16 input substitutions, and 2 of 16 output
 substitutions for a 128-bit block cipher.  Each of the lines
 represents a single bit:  Each input "S" contributes 4 bits to
 each of the two DES operations, and each output "S" takes 4 bits
 from each DES operation.

 But with this design we can only _guarantee_ that a single-bit
 input change will avalanche _one_ of the DES operations.  This
 could be a problem, because when it is possible to externally
 isolate the internal components, they can be worked on separately
 [10].  (It is not clear, however, that this would actually be
 possible in the context of the DES mixing in this design.)


 3.7  2x Fenced DES

 A guaranteed-avalanche and faster alternative is available by using
 Block Mixing Transforms (section 3.8).  Here we assume that a Block
 Mixing Transform takes two input blocks, "mixes" them, and produces
 two output blocks:

    S S S S S S S S S S S S S S S S
    --------------mix--------------
    ------DES------ ------DES------
    --------------mix--------------
    S S S S S S S S S S S S S S S S

 If we can assume that any input change to a Block Mixing Transform
 will propagate to _both_ outputs, then we can _guarantee_ that any
 one-bit change to the overall input block will avalanche _both_
 DES operations.

 Note that we do not care _how_ the DES operations are affected.  If
 the DES input is affected at all, the cipher must construct another
 output code ("at random"); and, thus, "avalanche."  It is not
 necessary that a Block Mixing Transform itself "avalanche," DES will
 do that.  It is not necessary that a Block Mixing Transform have
 "strength," DES and the fencing substitutions will do that.  It is
 only necessary that the Block Mixing Transform guarantee that a
 single change gets propagated to each DES operation.

 Another Block Mixing Transform combines the randomized outputs from
 the DES operations, producing output blocks which are, therefore,
 also randomized.  These randomized blocks are then substituted to
 produce the final output, which, of course, is also "random-like."


 3.8  Block Mixing Transforms

 A Block Mixing Transform takes multiple input blocks and generates
 the same number (and width) of output blocks, such that:

      1) the transformation is invertible,
      2) each output is a function of all inputs,
      3) a change in any single input block will change all of
         the output blocks, and
      4) stepping any input through all possible values (with the
         other inputs held fixed) will step every output through
         all possible values.

 The advantage is to be able to mix blocks of substantial size
 very efficiently; 4x Fenced DES mixes 128-bit blocks.

 The Fenced DES Block Mixing Transform uses the equations:

      X = 3A + 2B
      Y = 2A + 3B

 mod 2 and mod p, where p is a mod 2 irreducible polynomial of
 appropriate degree.  This transform is a self-inverse.


 ASSERTION:  (We have a finite field.)  Mod-2 polynomials
 modulo some irreducible polynomial p generate a finite field.

      (Comment:  Proofs can use algebra.)


 PROPOSITION:  (Example block mixing transform.)  The equations

      X = 3A + 2B = A + 2(A + B)
      Y = 2A + 3B = B + 2(A + B)

 and the inverse

      A = X + 2(X + Y)
      B = Y + 2(X + Y)

 mod 2 and mod p, where p is some mod 2 irreducible polynomial,
 represent a block mixing transform.

      (Inverse Proof:  Substitute the formulas for X and Y
      into the formulas for A and B:

           A = A + 2(A + B) + 2(A + 2(A + B) + B + 2(A + B))
             = A + 2(A + B) + 2(A + B) = A

      and

           B = B + 2(A + B) + 2(A + 2(A + B) + B + 2(A + B))
             = B + 2(A + B) + 2(A + B) = B

      so the inverse does exist for any polynomials A and B.)

      (Function Proof:  the equations for output code X includes
      both input code values A and B, so X is a function of both
      input codes.  Y reasons similarly.)

      (Change Propagation Proof: First consider one term of one
      output block equation:

      Suppose some change C is added to A:

           X  = 3A + 2B  (mod 2, mod p)
           X' = 3(A+C) + 2B
           X' = 3A + 3C + 2B
           dX = X' - X = 3C

      So, for any non-zero change, X has changed.  Similar reasoning
      covers the other term, and the other equation.)

      (Balance Proof:  Suppose that stepping an input through all
      possible values does _not_ step an output through all possible
      values.  Since the input and output blocks are the same size,
      some output value must occur for a plurality of input values.
      Assuming A is fixed, there must be at least two different
      values, B and B', which produce the same X:

           X = 3A + 2B = 3A + 2B'

      so

           X + 3A = 2B = 2B'

      which implies that

           B = B'

      a contradiction.  Fixing B or working on the other block
      reason similarly.)

 A consequence of this particularly efficient construction is that
 this particular Block Mixing Transform has essentially no "strength"
 of its own.  But the transform of two 32-bit blocks might be
 compared to a DES operation with a fixed, known key.  DES with a
 known key is also a very "weak" operation, but would nevertheless
 provide strong, invertible mixing for two 32-bit input blocks,
 basically because of "avalanche."

 The Block Mixing Transform can also be seen as two cryptographic
 combiners which are "orthogonal" (thus allowing their output to be
 transformed back to the original values).  Each of these combiners
 provides "mixing" between whole blocks, with a good statistical
 balance between the inputs.  Any particular value on an output port
 can be produced by any possible value on an input port, given some
 value on the other input port.  These properties appear to be a
 generalization of those found in the usual additive combiner, and
 would seem to be the essence of a balanced cryptographic combiner.
 Note that an exclusive-OR combiner, by itself, must be considered
 extremely "weak," and yet somehow manages to participate in strong
 cryptographic operations anyway.


 4  Analysis of 4x Fenced DES

 Here we define a theoretical model and its properties, and then
 show that the design has those properties.


 4.1  About Cryptographic Proof

 All cryptographic systems are based on keys, and if The Opponent
 happens to choose the correct key first, the system is broken with
 no more effort than is required to use it.  We can live with this
 by demanding that users have long, complex keys, and accepting that
 a large "expected" effort can sometimes (hopefully rarely) mean an
 "lucky" easy solution.

 The real problem lies in calculating a particular value for the
 expected effort.  Ideally, this value would indicate the result of
 the best of all possible attacks, including those which are far
 beyond anything we now know.  Consequently, proving a cipher
 "strong" will be difficult.  On the other hand, having a clean
 construction using simple components should help a lot.

 As a first step, I have tried to define some of the features of
 a block cipher, and then show that the Fenced DES cipher can be
 proven to possesses those features.  In general, I assume that a
 block cipher must be invertible and exhibit the "avalanche"
 property.  These very simple properties turn out to be related,
 and more substantial than they might at first appear.


 4.2  The Ideal Model

 Clearly, any block cipher must be invertible, and we will expect
 the same block-width for the output as for the input.  This means
 that a block cipher just performs a keyed permutation on the input
 values.  In a sense, a block cipher is a like a library of large
 automatic codebooks, where a User Key selects the particular book
 to use.

 For analysis, it is conventional to assume that a block cipher is a
 large invertible substitution (see, for example, [24:72], [15:375]).
 A cryptographic key in some way selects a particular substitution
 from among all possible invertible substitutions.

 In real systems like DES, the range of key values may be very much
 smaller than the number of possible substitutions.  There is no
 reason to believe, however, that only those substitutions with some
 particular quality are being selected by a DES key.  Indeed, if
 this were so, Triple DES would necessarily select other (presumably
 lower-quality) substitutions.  I assume that this is not the case.

 To be secure, a block cipher must be wide enough so that it
 cannot be searched in a "defined plaintext" "codebook" attack.  We
 cannot hope to build--or even shuffle--a direct substitution of
 such size.  The problem for the block-cipher designer is to find
 some sort of mechanism which produces a keyed set of invertible
 permutations in a simple algorithmic way.


 4.3  4x Fenced DES

 This is the 4x Fenced DES construct:

    S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S
    ------------------------------mix------------------------------
    --------------mix-------------- --------------mix--------------
    ------DES------ ------DES------ ------DES------ ------DES------
    --------------mix-------------- --------------mix--------------
    ------------------------------mix------------------------------
    S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S

 This 4x construct handles a 256-bit block.  Similar 2x and 1x
 constructs could be used at the end of a message to reduce total
 data expansion to only that of DES itself.

 Each "S" represents a separately-shuffled and independent 8-bit
 substitution table.  This implies the presence of a particular
 keyed cryptographic RNG to shuffle the tables.  The tables are set
 up and shuffled before ciphering, and then remain static during
 ciphering.

 Each "---DES---" represents an ordinary 64-bit-block DES operation.

 Each "---mix---" represents the mixing of the covered data blocks
 using "block mixing transform" technology.  There are two levels
 of mixing on each side of the DES operations:  The innermost levels
 each have two mixings which combine two 64-bit blocks; the outermost
 levels each have a single mixing which combines two 128-bit blocks.

 This entire construct requires about 4.8 times the computation to
 cipher 4 times the data.  In contrast, triple-DES would of course
 need 12 times the computation to cipher the same data.

 In the experimental implementation, the keyed initialization of
 the 16K of state present in 64 small substitution tables (plus four
 DES keys) takes about 200 times the computation of a single 256-
 bit ciphering.


 4.4  Invertibility in 4x Fenced DES

 The sequential combination of any number of invertible functions
 will itself constitute a function which is invertible.

 With respect to the 4x Fenced DES construction, we have five
 functional layers:  The input substitutions, the input mixing
 transforms, the DES operations, the output mixing transforms, and
 the output substitutions.  Because each layer is separately
 invertible, their sequential combination must also be invertible,
 so the cipher as a whole is invertible.


 4.5  Avalanche in 4x Fenced DES

 Now we ask whether the Fenced DES construct will have the avalanche
 property.  There are five levels:  Input and Output Substitution,
 Input and Output Mixing Transform, and DES.

      Since the Input Substitutions are invertible by construction,
      any change whatsoever in their input value will produce some
      change in their output value.

      The Input Mixing Transform is designed so that a single-bit
      change to one of the two input ports will produce some change
      to all four of the output ports.  Since each of the output
      ports feeds a DES operation, this is sufficient to avalanche
      all four DES operations.

           (Of course, for substantial input changes, it is possible
           to generate values which will leave one or more of the
           DES operations unaffected, although this is quite unlikely
           to happen by chance.  In the mixing transform, such a
           circumstance requires specific related 128-bit values on
           each of the two input ports, and these values are hidden
           behind the input substitutions.  We could manage to keep
           a DES operation unaffected if we knew the arrangement of
           the values in all the input substitutions, but that
           uncertainty is part of the strength of the cipher.  And
           it seems unlikely that we could tell from the outside that
           we were successful--that fewer than four DES operations
           have avalanched--because any avalanche will enter the
           output mixing transforms and so be reflected over the
           whole width of the large block, with the specific
           resulting values hidden by the output substitutions.)

      Thus, any single-bit change into the large input block will
      avalanche all four DES operations, producing a 256-bit
      avalanche overall.

      When presented with four randomized values from the DES
      operations, the Output Block Mixing Transform will have no
      choice but to also output random-like values.

      The Output Substitutions hide and protect the random-like
      values from the Output Mixing Transform.  And, since their
      inputs are random-like, their outputs will also be random-
      like.


 5  Fenced DES Strength

 Rather than attempt to analyze the whole design at once, it seems
 worthwhile to reason about the design with various features disabled.
 In this way we have a better chance of seeing the overall strength
 when we use a combination of those features.


 5.1  Strength of 1x Fenced DES with Known Substitutions

 All data flows through every layer in a Fenced DES structure.  Even
 if the input and output substitutions are known, they do not undo
 the confusion that DES provides.  Therefore, the absolute minimum
 strength of 1x Fenced DES is the same as DES.

 (Technically, the strength of DES is 55 bits, when key-symmetry is
 exploited; see, for example, [19:120].)


 5.2  Strength of 1x Fenced DES with Known DES Key

 Here we examine the ability of the input substitutions to hide
 the value going into the DES ciphering.

 The attack consists of trying all possible plaintext values until
 the known ciphertext value appears on the output.  This will
 identify a single element in each input substitution, which will
 also uniquely determine an element in each output substitution.
 We could instead work on the output substitutions, but the effort
 would be the same.

 Note that if even one bit to the DES ciphering is wrong, DES will
 avalanche, so it will be impossible to tell how many bits are right
 until the correct input transformation is found.  DES with a known
 key thus provides an example of "bit mixing" without "strength,"
 which nevertheless contributes "strength" to the overall cipher.

 For a given 64-bit input value, there are eight 8-bit values which
 select some value in eight different keyed input substitutions.
 There are 256 possible values for each of the eight substitutions,
 for 256**8 or 2**64 possibilities.  Therefore, the strength of
 1x Fenced DES with a known DES key is 64 bits.

 (Note that this attack finds just one transformation in each
 byte substitution, out of 256 total.  But each successive attack
 is slightly easier, and this is a convenient lower bound.)


 5.3  Strength of 1x Fenced DES

 When the DES key is known, the strength is 64 bits; the unknown
 DES key adds 56 bits more, for a total of 120 bits.  A 120-bit
 keysearch will identify the DES key and one element in each of
 eight small substitutions; for a complete break, the remaining
 255 values in those eight substitutions must still be found.
 Thus, the strength of 1x Fenced DES exceeds 120 bits.


 5.4  Minimum Strength of 4x Fenced DES

 The 4x Fenced DES cipher differs from the 1x Fenced DES cipher
 by mixing the entire input block and thus requiring that all
 input (or output) substitutions be searched, as well as the four
 internal keys.  Even if this mixing can be defeated, we are still
 left with attacking at least one DES key and one set of input
 substitutions.  Thus, the minimum strength of 4x Fenced DES is
 120 bits.


 5.5  Strength of 4x Fenced DES

 If we assume that the internal block mixing is indeed effective,
 the overall strength of 4x Fenced DES is four times that of
 1x Fenced DES, a total of 480 bits.


 6  Attacks

 We assume that The Opponent knows the design of the cipher, and
 has virtually any amount of plaintext and corresponding ciphertext
 ("known plaintext").  We also assume that The Opponent has the
 real-time ability to obtain "defined plaintext" by enciphering
 messages at will and collecting the resulting ciphertext.


 6.1  Exhaustive Search:  Try each key until the correct one is
 found.

 We assume that there is really no need for excessive keyspace,
 provided the keyspace is too large to search.  On the other hand,
 there is no particular reason to avoid a super-large keyspace,
 unless it happens to lead to inefficiency or weakness of another
 nature.

 Preventing exhaustive search now apparently requires a keyspace
 substantially larger than 56 bits.  Even 1x Fenced DES has a
 keyspace of 120 bits, which should be "large enough."


 6.2  Codebook:  Try to obtain all possible ciphertexts and
 associated plaintext; then, when a ciphertext occurs, look it up.

 This is normally prevented by having a large number of ciphertexts,
 which implies a large block size, like that in 4x Fenced DES.

 Codebook approaches can be combined with "divide-and-conquer" to
 isolate and define parts of some ciphers.  Fenced DES tries to
 avoid these attacks by not allowing the parts to be isolated and
 worked on separately.


 6.3  Meet-in-the-Middle:  With a two-layered structure, search the
 top keyspace to find every possible result, and search the bottom
 keyspace to find every possible input value.  When the correct key
 is used for each layer, the internal value must match.  (Inevitable
 false matches can be rejected by testing with other known-plaintext
 pairs.)  This is a keyspace search only twice as large as that
 needed for each layer, thus exhibiting a major design weakness.
 (In building a cipher, we generally intend to produce an overall
 complexity which is the _product_ of the internal complexities,
 instead of their _sum_.)

 Fenced-DES avoids this by using a three-level construction, and
 by having a huge "keyspace."


 6.4  Differential Cryptanalysis [3]:  Given an iterative S-P
 cipher, use any statistical unbalance found in the known, fixed
 substitutions to peer back into previous iteration steps.

 Clearly, the DES parts of Fenced DES might be attacked in this way,
 although, at present, Differential Cryptanalysis of DES does not
 seem to be much advantage over exhaustive key search.  In any case,
 this would apply only after the Fenced DES substitutions had been
 resolved.

 The Fenced DES substitutions avoid Differential Cryptanalysis by
 being keyed and therefore unknown.


 7  Conclusions

 DES is becoming weaker, and must be replaced soon.  The classical
 alternative, Triple DES, is too expensive for many users, taking
 three times the computation of DES itself.  And any completely new
 cipher design must raise the terrible prospect of a complete new
 certification, in an environment without an institution which both
 could and would perform this task.

 Fenced DES is based on DES, appears stronger than DES, and operates
 almost as fast.  Fenced DES is also a particularly clean design,
 which allows us to reason about the strength of the cipher in a
 particularly satisfying way.


 8  References

 [1]   Anderson, R.  1991.  Tree Functions and Cipher Systems.
       Cryptologia.  15(3): 194-202.

 [2]   Ayoub, F.  1982.  Probabilistic completeness of substitution-
       permutation encryption networks.  IEE Proceedings.  Part E.
       129(5): 195-199.

 [3]   Biham, E. and A. Shamir.  1990.  Differential Cryptanalysis
       of DES-like Cryptosystems.  Advances in Cryptology:
       CRYPTO '90.  Springer-Verlag.  2-21.

 [4]   Blum, L., M. Blum and M. Shub.  1986.  A Simple Unpredictable
       Pseudo-Random Number Generator.  SIAM Journal on Computing.
       15: 364-383.

 [5]   Brown, L.  1989.  A Proposed Design for an Extended DES.
       Computer Security in the Age of Information.  W. Caelli, Ed.
       Elsevier.  9-22.

 [6]   Dawson, M. and S. Tavares.  1991.  An Expanded Set of S-box
       Design Criteria Based on Information Theory and its Relation
       to Differential-Like Attacks.  Advances in Cryptology:
       EUROCRYPT '91.  Springer-Verlag.  353-367.

 [7]   Feistel, H.  1973.  Cryptography and Computer Privacy.
       Scientific American.  228(5): 15-23.

 [8]   Feistel, H., W. Notz and L. Smith.  1975.  Some Cryptographic
       Techniques for Machine-to-Machine Data Communication.
       Proceedings of the IEEE.  63(11): 1545-1554.

 [9]   Garon, G. and R. Outerbridge.  1992.  The sufficiency of the
       data encryption standard for financial institutions.
       Computer Security Journal.  8(1): 37-50.

 [10]  Heys, M. and S. Tavares.  1993.  Cryptanalysis of Tree-
       Structured Substitution-Permutation Networks.  Electronics
       Letters.  29(1): 40-41.

 [11]  Howe, C. and R. Rosenberg.  1987.  Government plans for
       data security spill over to civilian networks.  Data
       Communications.  March.  136-144.

 [12]  Kam, J. and G. Davida.  1979.  Structured Design of
       Substitution-Permutation Encryption Networks.  IEEE
       Transactions on Computers.  C-28(10): 747-753.

 [13]  Kerr, S.  1989.  A Secret No More.  Datamation.  July 1.
       53-55.

 [14]  Knuth, D.  1981.  The Art of Programming; Vol. 2:
       Seminumerical Algorithms.  2nd Ed.  Addison-Wesley.

 [15]  Luby, M. and C. Rackoff.  1988.  How to construct pseudorandom
       permutations from pseudorandom functions.  Siam Journal on
       Computing.  17(2): 373-386.

 [16]  Marsaglia, G.  1984.  A current view of random number
       generation.  Proceedings of the Sixteenth Symposium on the
       Interface Between Computer Science and Statistics.  3-10.

 [17]  Marsaglia, G. and L. Tsay.  1985.  Matrices and the Structure
       of Random Number Sequences.  Linear Algebra and its
       Applications.  67: 147-156.

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

 [19]  Pfleeger, C.  1989.  Security in Computing.  Prentice-
       Hall.

 [20]  Pieprzyk, J. and G. Finkelstein.  1988.  Towards effective
       nonlinear cryptosystem design.  IEE Proceedings.  Part E.
       135(6): 325-335.

 [21]  Pieprzyk, J. and G. Finkelstein.  1989.  Permutations that
       maximise non-linearity and their cryptographic significance.
       Computer Security in the Age of Information.  W. Caelli, Ed.
       63-74.

 [22]  Pieprzyk, J.  1989.  Error propagation property and
       application in cryptography.  IEE Proceedings.  Part E.
       136(4): 262-270.

 [23]  Ritter, T.  1991.  The Efficient Generation of Cryptographic
       Confusion Sequences.  Cryptologia.  15(2): 81-139.

 [24]  Sloane, N.  1982.  Encrypting by Random Rotations.
       Cryptography.  Proceedings, Burg Feuerstein 1982.  Springer-
       Verlag.  71-128.

 [25]  Tuchman, W.  1979.  Hellman presents no shortcut solutions
       to the DES.  IEEE Spectrum.  July.  40-41.

 [26]  Webster, A. and S. Tavares.  1985.  On the Design of S-Boxes.
       Advances in Cryptology: CRYPTO '85.  523-534.

 [27]  Wiener, M.  1993.  Efficient DES Key Search.  (In press?)