The criteria used in the design of DES, as reported in [COPP94], focused on the design of the S-boxes and on the P function that takes the output of the S-boxes (Figure 3.7). The criteria for the S-boxes are as follows.

**BLOCK CIPHER DESIGN PRINCIPLES**

Although much progress has been made in designing block
ciphers that are cryptographically strong, the basic principles have not changed
all that much since the work
of Feistel and the DES design team in the early 1970s. It is useful to begin
this discussion by looking at the published design criteria used in the DES
effort. Then we look at three critical
aspects of block cipher design: the number of rounds, design of the function F, and key scheduling.

DES Design Criteria

The criteria used in the design of DES, as
reported in [COPP94], focused on the design of the S-boxes and on the P
function that takes the output of the S-boxes (Figure 3.7). The criteria for
the S-boxes are as follows.

**1.
**No
output bit of any
S-box should be too close
a linear
function of the input bits. Specifically,
if we select any output bit
and any subset of the six input bits,
the
fraction of inputs for which this
output bit equals the
XOR of these input bits should not be close
to 0 or 1, but rather should be near 1/2.

**2.
**Each row of an S-box
(determined by a fixed value of the leftmost and right- most input bits) should include
all 16 possible output bit combinations.

**3.
**If two inputs to an S-box differ in exactly one
bit, the outputs must differ in at
least two bits.

**4.
**If two inputs
to an S-box differ in the two middle
bits exactly, the outputs
must differ in at least two bits.

**5.
**If two inputs
to an S-box differ in their first two bits and are identical in their last two
bits, the two outputs must not be the same.

**6.
**For any nonzero 6-bit difference between inputs, no more than eight of the 32 pairs of inputs exhibiting that difference may result in the same output difference.

**7.
**This
is a criterion
similar to the previous
one, but for the case of three
S-boxes.

Coppersmith pointed out that the first
criterion in the preceding list was needed because the S-boxes are the only
nonlinear part of DES. If the S-boxes were linear (i.e., each output bit is a
linear combination of the input bits), the entire algorithm would be linear and
easily broken. We have seen this phenome- non with the Hill cipher, which is
linear. The remaining criteria were primarily aimed at thwarting differential
cryptanalysis and at providing good confusion properties.

The criteria for the permutation P are as
follows.

**1.
**The four output bits from each
S-box at round *i *are distributed so that two of them affect (provide input for) “middle bits” of round (*i *+ 1)
and the other two affect end bits. The two
middle bits of input to an S-box are not shared with adjacent S-boxes. The end bits
are the two left-hand bits and
the two right-hand bits, which
are shared with adjacent S-boxes.

**2.
**The
four
output bits from each S-box affect six different S-boxes
on the next round, and no two affect
the same S-box.

**3.
**For
two S-boxes *j*,
*k*, if an output bit from S*j *affects a middle bit of S*k *on
the next round, then an output bit from S*k *cannot affect a middle bit
of S*j*. This implies that, for *j *= *k*, an output bit from
S*j *must not affect a middle bit of S*j*.

These criteria are intended to increase the
diffusion of the algorithm.

Number of Rounds

The cryptographic
strength of a Feistel cipher derives
from three aspects of the design: the number of rounds, the function F, and the key schedule algorithm. Let us look first
at the choice of the number of rounds.

The greater the number of rounds, the more
difficult it is to perform crypt- analysis, even for a relatively weak F. In general, the criterion should be
that the number of rounds is chosen
so that known cryptanalytic efforts
require greater effort than a simple brute-force key search attack.
This criterion was certainly used in
the design of DES. Schneier [SCHN96]
observes that for 16-round DES, a differ-
ential cryptanalysis attack
is slightly less efficient than brute force:
The differential cryptanalysis attack requires
255.1
operations,10 whereas brute force requires 255. If DES had 15
or fewer rounds, differential cryptanalysis would require less effort than a brute-force key search.

This criterion is attractive, because
it makes it easy to judge the strength of an
algorithm and to compare different algorithms. In the absence of a
cryptanalytic breakthrough, the strength
of any algorithm that satisfies the criterion can
be judged solely
on key length.

Design of Function F

The heart of a Feistel block cipher is the function F. As we have seen, in DES, this function relies on the use of S-boxes. This
is also the case for many other
symmetric block ciphers. However, we can make some general
comments about the criteria for designing F. After
that, we look specifically at S-box design.

*DESIGN **CRITERIA FOR *** F **The function F provides the element of confusion in a Feistel cipher. Thus, it must be difficult to “unscramble” the substitution performed by F. One obvious criterion is that F be nonlinear, as we discussed
previously. The more nonlinear F, the
more difficult any type of cryptanalysis will be. There are several measures of nonlinearity, which are beyond the scope of this book. In rough
terms, the more difficult it is to approximate F by a set of linear equations, the more nonlinear
F is.

Several other criteria
should be considered in designing F.
We
would like the algorithm to
have
good avalanche properties.
Recall that, in general, this
means that a change in one bit of the
input should produce a change in many
bits of the output. A more
stringent version of this is the **strict avalanche criterion
(SAC) **[WEBS86], which states that
any output bit *j *of an S-box should change
with probability 1/2 when any single input
bit *i *is inverted for all *i*, *j*. Although
SAC is
expressed in terms
of S-boxes, a similar criterion could be
applied to F as a whole. This is important when considering designs that do not include S-boxes.

Another criterion proposed in [WEBS86] is
the **bit independence criterion (BIC)**, which states that output bits *j *and *k *should change independently when any single input
bit *i *is inverted for all *i*,
*j*, and *k*. The SAC
and BIC criteria appear to strengthen
the effectiveness of the confusion
function.

*S-BOX *** DESIGN **One of the most intense areas of research in the field of
symmetric block ciphers is that of S-box design. The papers are almost too
numerous to count. Here we mention some general principles. In essence, we
would like any change to the input vector to an S-box to result in
random-looking changes to the output. The relationship should be nonlinear and
difficult to approximate with linear functions.

One obvious characteristic of the S-box
is its size. An *n ** *m *S-box has *n *input bits and *m *output bits. DES has 6 × 4 S-boxes.
The encryption algorithm Blowfish, has 8 × 32 S-boxes.
Larger S-boxes, by and large, are more resistant to differential
and linear cryptanalysis [SCHN96]. On the other
hand, the larger
the dimension *n*, the (exponentially) larger the lookup table. Thus, for practical reasons, a limit of *n *equal to about 8 to 10 is usually imposed.
Another practical consideration is that the larger the S-box, the more difficult
it is to design it properly.

S-boxes are typically organized in a
different manner than used in DES. An
*n ** *m *S-box typically consists of 2*n *rows of *m *bits each. The *n *bits of input
select one of the rows of the S-box,
and the *m *bits in that row are the output.
For example, in an 8 * 32
S-box, if the input is **00001001**, the output consists of the 32 bits in row 9 (the first row is labeled row 0).

Mister and Adams [MIST96] propose a number
of criteria for S-box design. Among these are that the S-box should
satisfy both SAC and BIC. They also suggest that all linear combinations of
S-box columns should be *bent*. Bent
functions are a special class of
Boolean functions that are highly nonlinear according to certain mathematical
criteria [ADAM90]. There has been increasing interest in designing and analyzing S-boxes using bent
functions.

A related criterion for S-boxes is proposed
and analyzed in [HEYS95]. The authors define
the **guaranteed avalanche
(GA) **criterion as follows: An S-box satisfies GA of order *g *if, for a 1-bit input
change, at least *g *output bits change.
The authors conclude that a GA in the range of order 2 to order 5
provides strong diffusion characteristics for the overall encryption algorithm.

For larger S-boxes, such as 8 * 32, the question arises as to the best method of selecting
the S-box entries in order to meet the type of criteria we have been
discussing. Nyberg, who has written a lot about the theory and practice of
S-box design, suggests the following approaches (quoted in [ROBS95b]):

•
**Random:**** **Use some pseudorandom number generation or some table of random
digits to generate the entries
in the S-boxes. This may lead to boxes with undesir-
able characteristics for small sizes (e.g., 6 * 4) but should
be acceptable for large
S-boxes (e.g., 8 * 32).

•
**Random with testing: **Choose S-box entries randomly, then test the results against various
criteria, and throw away those that do not pass.

•
**Human-made: **This is a more or less manual
approach with only simple mathe- matics to support it. It is apparently the technique used in the DES design.
This approach is difficult to carry through
for large S-boxes.

•
**Math-made: **Generate S-boxes according to mathematical principles. By using
mathematical construction, S-boxes can be constructed that offer proven security
against linear
and differential cryptanalysis, together with good diffusion.

•
A variation on the first technique is to use S-boxes
that are both random and key
dependent. An example of this approach
is Blowfish, which starts with S-boxes
filled with pseudorandom digits and
then alters the contents using the key. A tremendous advantage of key-dependent S-boxes is that,
because they are not fixed, it is impossible
to analyze the S-boxes ahead of time to look for weaknesses.

•

•
Key Schedule Algorithm

•
A final area of
block cipher design, and one that has received less attention than S-box design,
is the key schedule algorithm. With any Feistel
block cipher, the key is used to generate one subkey for each
round. In general, we would like to select subkeys to maximize the difficulty of deducing individual subkeys and the difficulty
of working back to the main key.
No general principles for this
have yet been promulgated.

•
Hall suggests [ADAM94] that,
at minimum, the
key schedule should
guarantee key/ciphertext Strict Avalanche Criterion and Bit Independence Criterion.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Block Ciphers and the Data Encryption Standard : Block Cipher Design Principles |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.