Cryptography Reference
In-Depth Information
S-boxes. The alternating rounds are a compromise designed to se-
curely scramble the message with only 64 bits.
The confusion and diffusion functions were designed differently.
Confusion was deliberately constructed to be as nonlinear as possi-
ble. Linear functions, straight lines, are notoriously easy to predict.
The results don't even come close.
Creating a nonlinear S-box is not an easy process. The original
technique was classified, leading many to suspect that the U.S. gov-
ernment had installed a trap door or secret weakness in the design.
The recent work of two Israeli cryptographers, Eli Biham and Adi
Shamir, however, showed how almost linear tendencies in S-boxes
could be exploited to break a cipher like DES. Although the technique
was very powerful and successful against DES-like systems, Biham
and Shamir discovered that DES itself was optimally designed to re-
sist this attack.
The diffusion function, on the other hand, was limited by tech-
nology. Ideally, every bit of the 64-bit block will affect the encryption
of any other bit. If one bit at the beginning of the block is changed,
then every other bit in the block may turn out differently. This insta-
bility ensures that those attacking the cipher won't be able to localize
their effort. Each bit affects the others.
Figure 2.1 shows how one half of the data encrypts the other half.
Alternating which half scrambles the other is a good way to ensure
that the contents of one half affect the other. The diffusion in DES is
even more subtle. Although the information in one half would affect
the other after only one round, the bits inside the halves wouldn't
affect each other quite as quickly. This part of the topic does not go
into the design of the S-boxes in detail, but the amount of scrambling
was limited by the technology available in the mid-1970s when the
cipher was designed. It takes several rounds of this process to diffuse
the information thoroughly.
Figure 2.2 shows one of the eight S-boxes from DES. It is simply a
table. If the input to the S-box is 000000 then the output is 1110. This
is the most basic form of scrambling and it is fairly easy to reverse.
The S-box takes 6 bits as input to implement diffusion. The 32 bits of
one half are split into eight 4-bit blocks. Each of the 4-bit blocks then
grabs one bit from the block to the left and one bit from the block to
the right. That means that each 4-bit block influences the processing
of the adjacent 4-bit block. This is how the bits inside each of the
halves affect each other.
This is already too much detail for this part of the topic. The rest
of DES is really of more interest to programmers who actually need
to implement the cipher. The important lesson is how the design-
