17.3 Practical Security
For ciphertext sequences greater than the unicity distance, any system can be solved, in principle, merely by trying each possible key until the unique solution is obtained. This is completely impractical, however, except when the key is extremely small. For example, for a key configured as a permutation of the alphabet, there are 26! ≈ 4 × 10^{26} possibilities (considered small in the cryptographic context). In an exhaustive search, one might expect to reach the right key at about halfway through the search. If we assume that each trial requires a computation time of 1 s, the total search time exceeds 10^{12} years. Hence techniques other than a bruteforce search (e.g., statistical analysis) must be employed if a cryptanalyst is to have any hope of success.
17.3.1 Confusion and Diffusion
A statistical analysis using the frequency of occurrence of individual characters and character combinations can be used to solve many cipher systems. Shannon [5] suggested two encryption concepts for frustrating the statistical endeavors of the cryptanalyst. He termed these encryption transformations confusion and diffusion. Confusion involves substitutions that render the final relationship between the key and ciphertext as complex as possible. This makes it difficult to utilize a statistical analysis to narrow the search to a particular subset of the key variable space. Confusion ensures that the majority of the key is needed to decrypt even very short sequences of ciphertext. Diffusion involves transformations that smooth out the statistical differences between characters and between character combinations. An example of diffusion with a 26letter alphabet is to transform a message sequence M = M_{0}, M_{1}, . . . into a new message sequence Y = Y_{0}, Y_{1}, . . . according to the relationship
where each character in the sequence is regarded as an integer modulo26, s is some chosen integer, and n = 0, 1, 2, .... The new message, Y, will have the same redundancy as the original message, M, but the letter frequencies of Y will be more uniform than in M. The effect is that the cryptanalyst needs to intercept a longer sequence of ciphertext before any statistical analysis can be useful.
17.3.2 Substitution
Substitution encryption techniques, such as the Caesar cipher and the Trithemius progressive key cipher, are widely used in puzzles. Such simple substitution ciphers offer little encryption protection. For a substitution technique to fulfill Shannon’s concept of confusion, a more complex relationship is required. Figure 17.6 shows one example of providing greater substitution complexity through the use of a nonlinear transformation. In general, n input bits are first represented as one of 2^{n} different characters (binarytooctal transformation in the example of Figure 17.6). The set of 2 characters is then permuted so that each character is transposed to one of the others in the set. The character is then converted back to an nbit output.
It can be easily shown that there are (2^{n})! different substitution or connection patterns possible. The cryptanalyst’s task becomes computationally unfeasible as n gets large, say n = 128; then 2^{n} = 10^{38}, and (2^{n})! is an astronomical number. We recognize that for n = 128, this substitution box (Sbox) transformation is complex (confusion). However, although we can identify the Sbox with n = 128 as ideal, its implementation is not feasible because it would require a unit with 2^{n} = 10^{38} wiring connections.
To verify that the Sbox example in Figure 17.6 performs a nonlinear transformation, we need only use the superposition theorem stated below as a test. Let
where a and b are input terms, C and C′ are output terms, and T is the transformation. Then
If T is linear: C = C′ for all inputs
If T is nonlinear: C ≠ C′
Suppose that a = 001 and b = 010; then, using T as described in Figure 17.6, we obtain
C = T (001) T (010) = 111 000 = 111
C′ = T (001 010) = T (011) = 110
where the symbol represents modulo2 addition. Since C ≠ C′ , the Sbox is nonlinear.
17.3.3 Permutation
In permutation (transposition), the positions of the plaintext letters in the message are simply rearranged, rather than being substituted with other letters of the alphabet as in the classic ciphers. For example, the word THINK might appear, after permutation, as the ciphertext HKTNI. Figure 17.7 represents an example of binary data permutation (a linear operation). Here we see that the input data are simply rearranged or permuted (Pbox). The technique has one major disadvantage when used alone; it is vulnerable to trick messages. A trick message is
illustrated in Figure 17.7. A single 1 at the input and all the rest 0 quickly reveals one of the internal connections. If the cryptanalyst can subject the system to a plaintext attack, he will transmit a sequence of such trick messages, moving the single 1 one position for each transmission. In this way, each of the connections from input to output is revealed. This is an example of why a system’s security should not depend on its architecture.
17.3.4 Product Cipher System
For transformation involving reasonable numbers of nmessage symbols, both of the foregoing cipher systems (the Sbox and the Pbox) are by themselves wanting. Shannon [5] suggested using a product cipher or a combination of Sbox and Pbox transformations, which together could yield a cipher system more powerful than either one alone. This approach of alternately applying substitution and permutation transformations has been used by IBM in the LUCIFER system [7, 8] and has become the basis for the national Data Encryption Standard (DES) [9]. Figure 17.8 illustrates such a combination of Pboxes and Sboxes. Decryption is accomplished by running the data backward, using the inverse of each Sbox. The system as pictured in Figure 17.8 is difficult to implement since each Sbox is different, a randomly generated key is not usable, and the system does not lend itself to repeated use of the same circuitry. To avoid these difficulties, the LUCIFER system [8] used two different types of Sboxes, S_{1} and S_{0}, which could be publicly revealed. Figure17.9 illustrates such a system. The input data are transformed by the sequence of Sboxes and Pboxes under the dictates of a key. The 25bit key in this example designates, with a binary one or zero, the choice (S_{1} or S_{0}) of each of the 25 Sboxes in the block. The details of the encryption devices can be revealed since security of the system is provided by the key.
The iterated structure of the product cipher system in Figure 17.9 is typical of most presentday block ciphers. The messages are partitioned into successive blocks of n bits, each of which is encrypted with the same key. The nbit block represents one of 2^{n} different characters, allowing for (2^{n})! different substitution patterns. Consequently, for a reasonable implementation, the substitution part of the encryption scheme is performed in parallel on small segments of the block. An example of this is seen in the next section.
17.3.5 The Data Encryption Standard
In 1977, the National Bureau of Standards adopted a modified Lucifer system as the national Data Encryption Standard (DES) [9]. From a system inputoutput point of view, DES can be regarded as a block encryption system with an alphabet size of 2 symbols, as shown in Figure 17.10. An input block of 64 bits, regarded as a plaintext symbol in this alphabet, is replaced with a new ciphertext symbol. Figure 17.11 illustrates the system functions in block diagram form. The encryption algorithm starts with an initial permutation (IP) of the 64 plaintext bits, described in the IPtable (Table 17.1). The IPtable is read from left to right and from top to bottom, so that bits x_{1}, x_{2}, . . . , x_{64} are permuted to x_{58}, x_{50}, . . . , x_{7}. After this initial permutation, the heart of the encryption algorithm consists of 16 iterations using the standard building block (SBB) shown in Figure 17.12. The standard building block uses 48 bits of key to transform the 64 input data bits into 64 output data bits, designated as 32 lefthalf bits and 32 righthalf bits. The output of each building block becomes the input to the next building block. The input righthalf 32 bits (R_{i1}) are copied unchanged to become the output lefthalf 32 bits (L_{i}). The R_{i 1} bits are also extended and transformed into 48 bits with the Etable (Table 17.2), and then modulo2 summed with the 48 bits of the key. As in the case of the IPtable, the Etable is read from left to right and from top to bottom. The table expands bits
Table 17.1 Initial Permutation (IP)
58 
50 
42 
34 
26 
18 
10 
2 
60 
52 
44 
36 
28 
20 
12 
4 
62 
54 
46 
38 
30 
22 
14 
6 
64 
56 
48 
40 
32 
24 
16 
8 
57 
49 
41 
33 
25 
17 
9 
1 
59 
51 
43 
35 
27 
19 
11 
3 
61 
53 
45 
37 
29 
21 
13 
5 
63 
55 
47 
39 
31 
23 
15 
7 
Table 17.2 ETable Bit Selection
32 
1 
2 
3 
4 
5 
4 
5 
6 
7 
8 
9 
8 
9 
10 
11 
12 
13 
12 
13 
14 
15 
16 
17 
16 
17 
18 
19 
20 
21 
20 
21 
22 
23 
24 
25 
24 
25 
26 
27 
28 
29 
28 
29 
30 
31 
32 
1 
R_{i1} = x_{1}, x_{2}, ... , x_{32}
into
Notice that the bits listed in the first and last columns of the Etable are those bit positions that are used twice to provide the 32 bitto48 bit expansion.
Next, (R_{i1})_{E} is modulo2 summed with the ith key selection, explained later, and the result is segmented into eight 6bit blocks
B_{1}, B_{2}, ... , B_{8}
That is,
Each of the eight 6bit blocks, B_{j}, is then used as an input to an Sbox function which returns a 4bit block, S_{j}(B_{j}). Thus the input 48 bits are transformed by the Sbox to 32 bits. The Sbox mapping function, S_{j}, is defined in Table 17.3. The transformation of B_{j} = b_{1}, b_{2}, b_{3}, b_{4}, b_{5}, b_{6} is accomplished as follows. The integer corresponding to bits, b_{1}, b_{6} selects a row in the table, and the integer corresponding to bits b_{2} b_{3} b_{4} b_{5} selects a column in the table. For example, if b_{1} = 110001, then S_{1} returns the value in row 3, column 8, which is the integer 5 and is represented by the bit sequence 0101. The resulting 32bit block out of the Sbox is then permuted using the Ptable (Table 17.4). As in the case of the other tables, the Ptable is read from left to right and from top to bottom, so that bits x_{1}, x_{2}, . . . , x_{32} are permuted to x_{16}, x_{7}, . . . , x_{25}. The 32bit output of the Ptable is modulo2 summed with the input lefthalf 32 bits (L_{i  1}), forming the output righthalf 32 bits (R_{i}).
Table 17.3 SBox Selection Functions
Column 

Row 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 

0 
14 
4 
13 
1 
2 
15 
11 
8 
3 
10 
6 
12 
5 
9 
0 
7 

1 
0 
15 
7 
4 
14 
2 
13 
1 
10 
6 
12 
11 
9 
5 
3 
8 

2 
4 
1 
14 
8 
13 
6 
2 
11 
15 
12 
9 
7 
3 
10 
5 
0 
S_{1} 
3 
15 
12 
8 
2 
4 
9 
1 
7 
5 
11 
3 
14 
10 
0 
6 
13 

0 
15 
1 
8 
14 
6 
11 
3 
4 
9 
7 
2 
13 
12 
0 
5 
10 

1 
3 
13 
4 
7 
15 
2 
8 
14 
12 
0 
1 
10 
6 
9 
11 
5 

2 
0 
14 
7 
11 
10 
4 
13 
1 
5 
8 
12 
6 
9 
3 
2 
15 
S_{2} 
3 
13 
8 
10 
1 
3 
15 
4 
2 
11 
6 
7 
12 
0 
5 
14 
9 

0 
10 
0 
9 
14 
6 
3 
15 
5 
1 
13 
12 
7 
11 
4 
2 
8 

1 
13 
7 
0 
9 
3 
4 
6 
10 
2 
8 
5 
14 
12 
11 
15 
1 

2 
13 
6 
4 
9 
8 
15 
3 
0 
11 
1 
2 
12 
5 
10 
14 
7 
S_{3} 
3 
1 
10 
13 
0 
6 
9 
8 
7 
4 
15 
14 
3 
11 
5 
2 
12 

0 
7 
13 
14 
3 
0 
6 
9 
10 
1 
2 
8 
5 
11 
12 
4 
15 

1 
13 
8 
11 
5 
6 
15 
0 
3 
4 
7 
2 
12 
1 
10 
14 
9 

2 
10 
6 
9 
0 
12 
11 
7 
13 
15 
1 
3 
14 
5 
2 
8 
4 
S_{4} 
3 
3 
15 
0 
6 
10 
1 
13 
8 
9 
4 
5 
11 
12 
7 
2 
14 

0 
2 
12 
4 
1 
7 
10 
11 
6 
8 
5 
3 
15 
13 
0 
14 
9 

1 
14 
11 
2 
12 
4 
7 
13 
1 
5 
0 
15 
10 
3 
9 
8 
6 

2 
4 
2 
1 
11 
10 
13 
7 
8 
15 
9 
12 
5 
6 
3 
0 
14 
S_{5} 
3 
11 
8 
12 
7 
1 
14 
2 
13 
6 
15 
0 
9 
10 
4 
5 
3 

0 
12 
1 
10 
15 
9 
2 
6 
8 
0 
13 
3 
4 
14 
7 
5 
11 

1 
10 
15 
4 
2 
7 
12 
9 
5 
6 
1 
13 
14 
0 
11 
3 
8 

2 
9 
14 
15 
5 
2 
8 
12 
3 
7 
0 
4 
10 
1 
13 
11 
6 
S_{6} 
3 
4 
3 
2 
12 
9 
5 
15 
0 
11 
14 
1 
7 
6 
0 
8 
13 

0 
4 
11 
2 
14 
15 
0 
8 
13 
3 
12 
9 
7 
5 
10 
6 
1 

1 
13 
0 
11 
7 
4 
9 
1 
10 
14 
3 
5 
12 
2 
15 
8 
6 

2 
1 
4 
11 
13 
12 
3 
7 
14 
10 
15 
6 
8 
0 
5 
9 
2 
S_{7} 
3 
6 
11 
13 
8 
1 
4 
10 
7 
9 
5 
0 
15 
14 
2 
3 
12 

0 
13 
2 
8 
4 
6 
15 
11 
1 
10 
9 
3 
14 
5 
0 
12 
7 

1 
1 
15 
13 
8 
10 
3 
7 
4 
12 
5 
6 
11 
0 
14 
9 
2 

2 
7 
11 
4 
1 
9 
12 
14 
2 
0 
6 
10 
13 
15 
3 
5 
8 
S_{8} 
3 
2 
1 
14 
7 
4 
10 
8 
13 
15 
12 
9 
0 
3 
5 
6 
11 
Table 17.4 PTable Permutation
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 
The algorithm of the standard building block can be represented by
where f(R_{i – 1}, K_{i}) denotes the functional relationship comprising the Etable, Sbox, and Ptable we have described. After 16 iterations of the SBB, the data are transposed according to the final inverse permutation (IP^{} 1) described in the IP^{} 1table (Table 17.5), where the output bits are read from left to right and from top to bottom, as before.
Table 17.5 Final Permutation (IP^{} 1)
57 
49 
41 
33 
25 
17 
9 
1 
58 
50 
42 
34 
26 
18 
10 
2 
59 
51 
43 
35 
27 
19 
11 
3 
60 
52 
44 
36 
63 
55 
47 
39 
31 
23 
15 
7 
62 
54 
46 
38 
30 
22 
14 
6 
61 
53 
45 
37 
29 
21 
13 
5 
28 
20 
12 
4 
where LS_{i} is a left circular shift by the number of positions shown in Table 17.7. The sequence C_{i}, D_{i} is then transposed according to the permuted choice 2 (PC2) shown in Table 17.8. The result is the key sequence K_{i}, which is used in the ith iteration of the encryption algorithm.
Table 17.7 Key Schedule of Left Shifts
Iteration, i 
Number of left shifts 
1 
1 
2 
1 
3 
2 
4 
2 
5 
2 
6 
2 
7 
2 
8 
2 
9 
1 
10 
2 
11 
2 
12 
2 
13 
2 
14 
2 
15 
2 
16 
1 
Table 17.8 Key Permutation PC2
14 
17 
11 
24 
1 
5 
3 
28 
15 
6 
21 
10 
23 
19 
12 
4 
26 
8 
16 
7 
27 
20 
13 
2 
41 
52 
31 
37 
47 
55 
30 
40 
51 
45 
33 
48 
44 
49 
39 
56 
34 
53 
46 
42 
50 
36 
29 
32 
The DES can be implemented as a block encryption system (see Figure17.11), which is sometimes referred to as a codebook method. A major disadvantage of this method is that a given block of input plaintext will always result in the same output ciphertext (under the same key). Another encryption mode, called the cipher feedback mode, encrypts single bits rather than characters, resulting in a stream encryption system [3]. With the cipher feedback scheme (described later), the encryption of a segment of plaintext not only depends on the key and the current data, but also on some of the earlier data.
Since the late 1970s, two points of contention have been widely publicized about the DES [10]. The first concerns the key variable length. Some researchers felt that 56 bits are not adequate to preclude an exhaustive search. The second concerns the details of the internal structure of the Sboxes, which were never released by IBM. The National Security Agency (NSA), which had been involved in the testing of the DES algorithm, had requested that the information not be publicly discussed, because it was sensitive. The critics feared that NSA had been involved in design selections that would allow NSA to “tap into” any DESencrypted messages [10]. DES is no longer a viable choice for strong encryption. The 56bit key can be found in a matter of days with relatively inexpensive computer tools [11]. (Some alternative algorithms are discussed in Section 17.6.)