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?)