Block Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 87

• The round function can be nonlinear and noninvertible. In many ciphers, such as the Caesar cipher, the
core function must be invertible: We have to be able to go backwards to decrypt. However, with the
Feistel structure, we never need to compute the inverse of the round function, since both encryption and
decryption use the normal round function. Normally, the round function is a product cipher of permuta-
tions, substitutions, and other functions.
Although using the round function definitely saves time and space, since it operates on half as many bits,
there are a few issues to consider. The round function operates on half as many bits; thus, there is less to brute-
force with. Furthermore, since the security of the round function is the security of the cipher, it must be rock
solid.
4.6 DES
The Data Encryption Standard (DES) [8] is based on the Lucifer algorithm, from IBM. DES was the first
Feistel-based cipher, and Horst Feistel himself worked on it. For more on the background and history of DES,
see References [1] and [16].
DES is a 64-bit cipher in every sense: It operates on 64-bit blocks and has a 64-bit key. However, the key
in DES is effectively a 56-bit key; the other 8 bits are used for parity. Although brute-forcing a 56-bit key
means evaluating 72,057,594,037,927,936 different keys (about 72 quadrillion, or million billions), which is not
a computation to take lightly, it is not outside the realm of possibility. In 1999, a network of computers ( dis-
tributed.net and the Electronic Frontier Foundation's Deep Crack machine) succeeded in brute-forcing a
known-plaintext key in less than a day [13].
DES Encryption Algorithm
First, a note on numbering. I will try to be true to the DES specification [8], and in doing so, will have to adopt
its backwards numbering scheme. In DES, all bits are numbered from most significant to least significant, 1 to
whatever (up to 64). This means that the decimal number 18 ( 10010 in binary) has the bit numbers shown in
Table 4-3 .
Table 4-3 Binary Representation of the Decimal Number 18
This is unlike most other algorithms we will use and see, which number 0, 1, ... , and from least significant
to most significant (right-to-left).
DES first takes the 64-bit input block and does an initial permutation, shifting the 64 bits around. (I won't
show the details of every box in DES and refer the interested reader instead to Reference [8].)
The DES main round structure then operates identically to the basic Feistel structure shown in the previous
section — split the permuted plaintext into L 0 and R 0 , and run the following Feistel structure for 16 rounds:
1. Compute R i +1 = L i ⊕ f ( R i , K i +1 ).
2. Set L i +1 = R i .