Cryptography Reference
In-Depth Information
5. If two inputs to an S-box differ in the two middle bits, their outputs must differ
in at least two bits.
6. 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 be different.
7. For any nonzero 6-bit difference between inputs, no more than 8 of the 32 pairs
of inputs exhibiting that difference may result in the same output difference.
8. A collision (zero output difference) at the 32-bit output of the eight S-boxes is
only possible for three adjacent S-boxes.
Note that some of these design criteria were not revealed until the 1990s. More
information about the issue of the secrecy of the design criteria is found in Sect. 3.5.
The S-boxes are the most crucial elements of DES because they introduce a
non-
linearity
to the cipher, i.e.,
S
(
a
)
⊕
S
(
b
)
=
S
(
a
⊕
b
)
.
Without a nonlinear building block, an attacker could express the DES input and
output with a system of linear equations where the key bits are the unknowns. Such
systems can easily be solved, a fact that was used in the LFSR attack in Sect. 2.3.2.
However, the S-boxes were carefully designed to also thwart advanced mathematical
attacks, in particular
differential cryptanalysis
. Interestingly, differential cryptanal-
ysis was first discovered in the research community in 1990. At this point, the IBM
team declared that the attack was known to the designers at least 16 years earlier,
and that DES was especially designed to withstand differential cryptanalysis.
Finally, the 32-bit output is permuted bitwise according to the
P
permutation,
which is given in Table 3.10. Unlike the initial permutation
IP
and its inverse
IP
−
1
,
the permutation
P
introduces diffusion because the four output bits of each S-box
are permuted in such a way that they affect several different S-boxes in the follow-
ing round. The diffusion caused by the expansion, S-boxes and the permutation
P
guarantees that every bit at the end of the fifth round is a function of every plaintext
bit and every key bit. This behavior is known as the
avalanche effect
.
Table 3.10
The permutation
P
within the
f
-function
P
16
7
20 21 29 12 28 17
1
15 23 26
5
18 31 10
2
8
24 14 32 27
3
9
19 13 30
6
22 11
4
25
