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:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
1 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
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
|
14 |
4 |
13 |
1 |
2 |
15 |
11 |
8 |
3 |
10 |
6 |
12 |
5 |
9 |
0 |
7 |
0 |
15 |
7 |
4 |
14 |
2 |
13 |
1 |
10 |
6 |
12 |
11 |
9 |
5 |
3 |
8 |
|
4 |
1 |
14 |
8 |
13 |
6 |
2 |
11 |
15 |
12 |
9 |
7 |
3 |
10 |
5 |
0 |
|
15 |
12 |
8 |
2 |
4 |
9 |
1 |
7 |
5 |
11 |
3 |
14 |
10 |
0 |
6 |
13 |
|
|
15 |
1 |
8 |
14 |
6 |
11 |
3 |
4 |
9 |
7 |
2 |
13 |
12 |
0 |
5 |
10 |
3 |
13 |
4 |
7 |
15 |
2 |
8 |
14 |
12 |
0 |
1 |
10 |
6 |
9 |
11 |
5 |
|
0 |
14 |
7 |
11 |
10 |
4 |
13 |
1 |
5 |
8 |
12 |
6 |
9 |
3 |
2 |
15 |
|
13 |
8 |
10 |
1 |
3 |
15 |
4 |
2 |
11 |
6 |
7 |
12 |
0 |
5 |
14 |
9 |
|
|
10 |
0 |
9 |
14 |
6 |
3 |
15 |
5 |
1 |
13 |
12 |
7 |
11 |
4 |
2 |
8 |
13 |
7 |
0 |
9 |
3 |
4 |
6 |
10 |
2 |
8 |
5 |
14 |
12 |
11 |
15 |
1 |
|
13 |
6 |
4 |
9 |
8 |
15 |
3 |
0 |
11 |
1 |
2 |
12 |
5 |
10 |
14 |
7 |
|
1 |
10 |
13 |
0 |
6 |
9 |
8 |
7 |
4 |
15 |
14 |
3 |
11 |
5 |
2 |
12 |
|
|
7 |
13 |
14 |
3 |
0 |
6 |
9 |
10 |
1 |
2 |
8 |
5 |
11 |
12 |
4 |
15 |
13 |
8 |
11 |
5 |
6 |
15 |
0 |
3 |
4 |
7 |
2 |
12 |
1 |
10 |
14 |
9 |
|
10 |
6 |
9 |
0 |
12 |
11 |
7 |
13 |
15 |
1 |
3 |
14 |
5 |
2 |
8 |
4 |
|
3 |
15 |
0 |
6 |
10 |
1 |
13 |
8 |
9 |
4 |
5 |
11 |
12 |
7 |
2 |
14 |
|
|
2 |
12 |
4 |
1 |
7 |
10 |
11 |
6 |
8 |
5 |
3 |
15 |
13 |
0 |
14 |
9 |
14 |
11 |
2 |
12 |
4 |
7 |
13 |
1 |
5 |
0 |
15 |
10 |
3 |
9 |
8 |
6 |
|
4 |
2 |
1 |
11 |
10 |
13 |
7 |
8 |
15 |
9 |
12 |
5 |
6 |
3 |
0 |
14 |
|
11 |
8 |
12 |
7 |
1 |
14 |
2 |
13 |
6 |
15 |
0 |
9 |
10 |
4 |
5 |
3 |
|
|
12 |
1 |
10 |
15 |
9 |
2 |
6 |
8 |
0 |
13 |
3 |
4 |
14 |
7 |
5 |
11 |
10 |
15 |
4 |
2 |
7 |
12 |
9 |
5 |
6 |
1 |
13 |
14 |
0 |
11 |
3 |
8 |
|
9 |
14 |
15 |
5 |
2 |
8 |
12 |
3 |
7 |
0 |
4 |
10 |
1 |
13 |
11 |
6 |
|
4 |
3 |
2 |
12 |
9 |
5 |
15 |
10 |
11 |
14 |
1 |
7 |
6 |
0 |
8 |
13 |
|
|
4 |
11 |
2 |
14 |
15 |
0 |
8 |
13 |
3 |
12 |
9 |
7 |
5 |
10 |
6 |
1 |
13 |
0 |
11 |
7 |
4 |
9 |
1 |
10 |
14 |
3 |
5 |
12 |
2 |
15 |
8 |
6 |
|
1 |
4 |
11 |
13 |
12 |
3 |
7 |
14 |
10 |
15 |
6 |
8 |
0 |
5 |
9 |
2 |
|
6 |
11 |
13 |
8 |
1 |
4 |
10 |
7 |
9 |
5 |
0 |
15 |
14 |
2 |
3 |
12 |
|
|
13 |
2 |
8 |
4 |
6 |
15 |
11 |
1 |
10 |
9 |
3 |
14 |
5 |
0 |
12 |
7 |
1 |
15 |
13 |
8 |
10 |
3 |
7 |
4 |
12 |
5 |
6 |
11 |
0 |
14 |
9 |
2 |
|
7 |
11 |
4 |
1 |
9 |
12 |
14 |
2 |
0 |
6 |
10 |
13 |
15 |
3 |
5 |
8 |
|
2 |
1 |
14 |
7 |
4 |
10 |
8 |
13 |
15 |
12 |
9 |
0 |
3 |
5 |
6 |
11 |
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.