Introduction To Network Security: Theory And Practice (2015)

Chapter 2. Data Encryption Algorithms

2.2 Data Encryption Standard

The DES was published by the U.S. National Bureau of Standards (NBS) in 1977. NBS was the predecessor of the U.S. National Institute of Standards and Technology (NIST). DES was based on the Lucifer encryption algorithm developed by an IBM research group led by Horst Feistel. In particular, DES is a concrete realization of the Feistel cipher scheme. Its encryption and decryption structures are symmetrical, and they use four basic operations: exclusive-OR, permutation, substitution, and circular shift. DES was widely used from the mid-1970s to the early 2000s. Although gradually phasing out, DES played an important role in modern cryptography and represents a popular design paradigm for data encryption.

2.2.1 Feistel's Cipher Scheme

The Feistel cipher scheme (FCS) divides the plaintext string into a sequence of blocks, each of which is bits long. FCS only uses basic operations of XOR and substitution. Let be a positive integer. FCS first generates subkeys of a fixed length from the encryption key . Let these subkeys be . Let denote the substitution function that takes an -bit binary string and a subkey as input and generates an -bit binary string as output. Divide a -bit plaintext block into two halves and of equal length, where and are, respectively, the prefix substring and the suffix substring of . The FCS encryption and decryption algorithms each executes rounds of a fixed sequence of operations (see Figure 2.1).

Figure 2.1 Feistel cipher scheme block diagram

FCS encryption executes the following operations in round , where :

2.1

2.2

After rounds, the plaintext block is transformed to . Let and be the output of FCS encryption. That is, the FCS encryption algorithm produces a ciphertext block .

Rewrite as ; namely, let and . The FCS decryption algorithm is symmetrical to the FCS encryption algorithm, except that the subkeys are applied in the reverse order. In particular, the FCS decryption algorithm executes the following operations in round , where :

2.3

2.4

After rounds, the ciphertext block is transformed to . Let and , and let be the output of FCS decryption.

We now show that the ciphertext block is transformed back to the plaintext block . Because the output of the FCS decryption is , it suffices to show the following equality:

Here is a proof. Note that and , and so it suffices to show that and . We can use mathematical induction to show that for any integer with , we have

2.5

2.6

Let , and we will get what we need to prove.

The mathematical induction proof is given as follows. We first note that and . Thus, when , Equalities 2.5 and 2.6 hold.

Induction hypothesis: for any positive integer , we have

It follows from Equality 2.3, the induction hypothesis, and Equality 2.1 that

Thus, Equality 2.5 is true.

From Equality 2.4 (the induction hypothesis), Equality 2.2, and Equality 2.1, we have

Thus, Equality 2.6 is true. This completes the proof of the correctness of the FCS decryption algorithm.

DES is an instance of FCS with . That is, the block size of DES is . The length of DES encryption keys is 56 bits. However, a DES encryption key is represented as a 64-bit binary string, where the th bit is the parity bit of the seven bits immediately before it. The parity bit is used for error detection. Let be an encryption key. DES first generates 16 subkeys from , where each subkey has exactly 48 bits. There are rounds of executions in DES.

2.2.2 DES Subkeys

Let be an encryption key of DES. To generate 16 subkeys, DES first removes each th bit from . For convenience, we still use to denote the new string. DES then permutes the remaining 56 bits using the initial permutation as follows, where bits are listed row wise:

It is evident that permutes in the following way: the indexes of the first 28 bits start from 57 such that each next index is equal to the current index minus 8 mod 65. The indexes of the next 24 bits start from 63 such that each next index is equal to the current index minus 8 mod 63. The indexes of the last four bits start from 28 such that each next index is equal to the current index minus 8.

The modular operation is a common operation when dealing with integers in a finite domain. Let be a positive integer and be a non-negative integer. Then “ mod ” is the remainder of dividing by . If and its absolute value , then mod is equal to the smallest positive integer such that . For instance, mod .

Let be a 56-bit binary string, where . Let be a compress permutation that takes as input and produces a 48-bit string as output. is defined as follows, where bits are listed row wise:

Let be a 28-bit binary string. Let denote the new string obtained by shifting circularly to the left () times, where () is defined as follows:

Rewrite as , where both and are 28-bit binary strings. Then the th subkey is generated as follows, where :

For instance, let

Then

Thus,

2.2.3 DES Substitution Boxes

The substitution function in DES is defined using eight special matrices. They are referred to as substitution boxes or S-Boxes in short. Each S-Box is a matrix (see Table 2.1), where each row in each S-Box is a permutation of integers from 0 to 15. We label these S-Boxes as . For each with , write

Table 2.1 DES S-Boxes

Let be a function that takes a 48-bit string as input and produces a 32-bit binary string as output. In particular, let be a 48-bit binary string, where . We use to denote the substring . Divide into eight 6-bit blocks:

For each 6-bit block (), we use the th S-Box to generate a 4-bit binary string as output, denoted by , as follows:

Let , where for . Let denote the binary representation for a row number and denote the binary representation for a column number. Then define to be the number in the 4-bit binary representation at row and column in matrix ; namely,

For example, if , then .

Let

Then () transforms the 48-bit input to a 32-bit output.

The constructions of the S-Boxes followed a clear set of criteria for the purpose of resisting possible attacks. They were also bound by the computing technologies available in the mid-1970s. For example, the reason why an S-Box has a 6-bit input and a 4-bit output is due to the chip technology available at that time. It took several months of computing time at that time to compute the S-Boxes that satisfy all the criteria. Because the set of criteria for the S-Boxes was not published and because NSA played a role in selecting DES, many people suspected that NSA had planted backdoors in these S-Boxes so that NSA can decipher DES-encrypted messages should they decide to do so. This of course was sheer speculation. In the 1990s, the set of criteria used by the DES design team was discovered by cryptanalysts not in the team. After this, IBM finally decided to publish the original set of criteria for constructing the S-Boxes.

2.2.4 DES Encryption

DES implements its substitution function using permutations, exclusive-OR, subkeys, and substitutions from the S-Boxes. In particular, for each 32-bit half block , DES first uses a function called expansion permutation, denoted by EP, to expand it into a 48-bit string. It then XORs this string with a 48-bit subkey, takes the resulting 48-bit output as the input of function to generate a 32-bit string, and permutes this string to generate a 32-bit string .

2.2.4.1 Expansion Permutation

Let be a 32-bit binary string. The expansion permutation EP on is defined as follows, where bits are listed row wise:

We note that in EP(), the indexes of the four middle columns are ; the indexes of the first column start from 32, where the next index is the current index plus 4 mod 32; and the indexes of the last column start from 5, where the next index is the current index plus 4 mod 32.

2.2.4.2 DES Substitution

Let be a 32-bit binary string. Permuting using the following permutation , where bits are listed row wise:

DES defines its substitution function as follows:

2.2.4.3 Encryption Steps

Let be a 64-bit binary string. Define a permutation as follows: it first reverses as . It then lists the prefix into four columns from right to left, where each column has exactly eight rows. It also lists the suffix into four columns from right to left, where each column has exactly eight rows, and inserts them alternately in the prefix columns. That is, according to the listing order, we have

The permutation enumerates the elements in this list row wise. Denote by the inverse of .

Let be a plaintext block. Define an initial permutation IP by . It is straightforward to verify that IP() is equal to the following string, where each number represents bit () and bits are listed row wise:

It is easy to see that the indexes of the first two rows in IP() start from 58, where the next index is equal to the current index minus 8 mod 66; and the indexes of the last two rows in IP() start from 57, where the next index is equal to the current index minus 8 mod 66.

Let . Then is the inverse of IP(), defined as follows, where each number represents bit and bits are listed row wise:

It is straightforward to verify that . For example, let . Because IP changes to and changes to , where and , we know that changes back to .

Let and be, respectively, a 64-bit plaintext block and a 64-bit encryption key with added parity bits. Let be the 16 subkeys generated from as described in Section 2.2.2. The DES encryption steps are given as follows:

1. Rewrite , where .

2. For , execute the following operations in order:

3. Finally, let . (Note that the input of is , not .)

2.2.5 DES Decryption and Correctness Proof

DES decryption is symmetrical to DES encryption, except that subkeys are applied in the reverse order. The DES decryption steps are given as follows:

1. Rewrite , where .

2. For , execute the following operations in order

3. Finally, let ; we then obtain back the plaintext block .

To prove the correctness of DES decryption, we need to show that

Because , we have and . We note that except IP is used before round 1 starts and after round 16, the rest of DES is a concrete implementation of FCS. It follows from FCS decryption that and . Thus,

This completes the proof.

2.2.6 DES Security Strength

The security strength of DES depends on the number of rounds, the length of encryption key, and the construction of the substitution function. A substantial number of experiments have demonstrated that DES encryption provides good diffusion and confusion effects.

It can be shown that if the number of rounds in DES encryption is less than 16, then differential cryptanalysis can break DES encryption in a reasonable amount of time.

The length of a DES encryption key is 56 bits, which was sufficient to resist brute-force attacks in the 1970s to 1980s. However, the 56-bit key length was no longer secure in the late 1990s due to advancements of computer technologies and algorithms. For example, in 1999, the Electronic Frontier Foundation (EFF) based in the United States spent less than $250,000 to build a special-purpose supercomputer, named “DES Cracker,” to crack DES encryptions. Working with Distributed.Net and a worldwide network of nearly 100,000 PCs on the Internet, DES Cracker broke in 22 hours the “DES Challenge III” encrypted message. The DES Challenges were a series of DES-encrypted messages posted by RSA Data Security in 1997. DES Challenge III was the last one to be broken. This indicated that the DES era was approaching its end.

Does this mean that all the manpower and resources spent over the years in developing hardware and software DES products were down the drain? It is true that DES encryption keys are too short to resist brute-force attacks, but DES has other good properties that have resisted many other attacks. Thus, it is reasonable to look for ways to effectively extend the DES encryption key length without changing the DES algorithms. Fortunately, it can be shown that DES is not a group. Therefore, applying DES multiple times is different from applying DES a single time. In other words, for any three 56-bit DES encryption keys , we have , where represents DES encryption with key . We note that this property may not be true in other encryption algorithms. For example, in XOR encryption, for any given encryption keys and , let , then

where represents XOR encryption.