Home > Articles

This chapter is from the book

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 × 1026 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 1012 years. Hence techniques other than a brute-force 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 26-letter alphabet is to transform a message sequence M = M0, M1, . . . into a new message sequence Y = Y0, Y1, . . . according to the relationship

Image

where each character in the sequence is regarded as an integer modulo-26, 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 2n different characters (binary-to-octal 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 n-bit output.

It can be easily shown that there are (2n)! different substitution or connection patterns possible. The cryptanalyst’s task becomes computationally unfeasible as n gets large, say n = 128; then 2n = 1038, and (2n)! is an astronomical number. We recognize that for n = 128, this substitution box (S-box) transformation is complex (confusion). However, although we can identify the S-box with n = 128 as ideal, its implementation is not feasible because it would require a unit with 2n = 1038 wiring connections.

To verify that the S-box example in Figure 17.6 performs a nonlinear transformation, we need only use the superposition theorem stated below as a test. Let

Image

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: CC′

Suppose that a = 001 and b = 010; then, using T as described in Figure 17.6, we obtain

C = T (001) Image T (010) = 111 Image 000 = 111

C′ = T (001 Image 010) = T (011) = 110

where the symbol Image represents modulo-2 addition. Since CC′ , the S-box 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 (P-box). 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 n-message symbols, both of the foregoing cipher systems (the S-box and the P-box) are by themselves wanting. Shannon [5] suggested using a product cipher or a combination of S-box and P-box 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 P-boxes and S-boxes. Decryption is accomplished by running the data backward, using the inverse of each S-box. The system as pictured in Figure 17.8 is difficult to implement since each S-box 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 S-boxes, S1 and S0, which could be publicly revealed. Figure17.9 illustrates such a system. The input data are transformed by the sequence of S-boxes and P-boxes under the dictates of a key. The 25-bit key in this example designates, with a binary one or zero, the choice (S1 or S0) of each of the 25 S-boxes 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 present-day block ciphers. The messages are partitioned into successive blocks of n bits, each of which is encrypted with the same key. The n-bit block represents one of 2n different characters, allowing for (2n)! 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 input-output 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 IP-table (Table 17.1). The IP-table is read from left to right and from top to bottom, so that bits x1, x2, . . . , x64 are permuted to x58, x50, . . . , x7. 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 left-half bits and 32 right-half bits. The output of each building block becomes the input to the next building block. The input right-half 32 bits (Ri-1) are copied unchanged to become the output left-half 32 bits (Li). The Ri- 1 bits are also extended and transformed into 48 bits with the E-table (Table 17.2), and then modulo-2 summed with the 48 bits of the key. As in the case of the IP-table, the E-table 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 E-Table 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

Ri-1 = x1, x2, ... , x32

into

Image

Notice that the bits listed in the first and last columns of the E-table are those bit positions that are used twice to provide the 32 bit-to-48 bit expansion.

Next, (Ri-1)E is modulo-2 summed with the ith key selection, explained later, and the result is segmented into eight 6-bit blocks

B1, B2, ... , B8

That is,

Image

Each of the eight 6-bit blocks, Bj, is then used as an input to an S-box function which returns a 4-bit block, Sj(Bj). Thus the input 48 bits are transformed by the S-box to 32 bits. The S-box mapping function, Sj, is defined in Table 17.3. The transformation of Bj = b1, b2, b3, b4, b5, b6 is accomplished as follows. The integer corresponding to bits, b1, b6 selects a row in the table, and the integer corresponding to bits b2 b3 b4 b5 selects a column in the table. For example, if b1 = 110001, then S1 returns the value in row 3, column 8, which is the integer 5 and is represented by the bit sequence 0101. The resulting 32-bit block out of the S-box is then permuted using the P-table (Table 17.4). As in the case of the other tables, the P-table is read from left to right and from top to bottom, so that bits x1, x2, . . . , x32 are permuted to x16, x7, . . . , x25. The 32-bit output of the P-table is modulo-2 summed with the input left-half 32 bits (Li - 1), forming the output right-half 32 bits (Ri).

Table 17.3 S-Box 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

S1

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

S2

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

S3

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

S4

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

S5

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

S6

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

S7

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

S8

3

2

1

14

7

4

10

8

13

15

12

9

0

3

5

6

11

Table 17.4 P-Table 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

Image

Image

where f(Ri – 1, Ki) denotes the functional relationship comprising the E-table, S-box, and P-table 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- 1-table (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

Image

where LSi is a left circular shift by the number of positions shown in Table 17.7. The sequence Ci, Di is then transposed according to the permuted choice 2 (PC-2) shown in Table 17.8. The result is the key sequence Ki, 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 PC-2

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 S-boxes, 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 DES-encrypted messages [10]. DES is no longer a viable choice for strong encryption. The 56-bit key can be found in a matter of days with relatively inexpensive computer tools [11]. (Some alternative algorithms are discussed in Section 17.6.)

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020