CHAPTER 2



Conventional Encryption: Modern Technologies

We mentioned that the statistical weakness in substitution ciphers is that they don’t change the frequency of alphabetic letters. For example, if a substitution cipher scheme were used to obtain the ciphertext:

CFGPSF GJWF

A cryptanalyst may initially guess that the most frequent ciphertext letter (F) is corresponding to a disguised E. If this guess is correct, the cryptanalyst is on the road to cracking the ciphertext. The 2nd best guess is if (F) is not really a disguised (E), it may then be a (T). The cryptanalyst can also guess that the most frequent two-letter pattern in longer ciphertext may correspond to a (TH), and so forth.

Note that with the help of computers, statistical analysis for cryptanalytic purposes can be prepared much quicker.

Note 1: We need to eliminate statistical relationship between the ciphertext and the underlying plaintext.

Note 2: Combining transposition and substitution diffuses the statistical structure of plaintext over the ciphertext. This method is referred to as diffusion. Diffusion dissipates or disperses parts of letters throughout the ciphertext.

Note 3: In addition to diffusion, we may need to create confusion to prevent the cryptanalyst from using ciphertext to figure out the secret encryption key. Confusion usually means that the cipher scheme should be complex such that even one can figure out some ciphertext patterns, she cannot use the cipher method and pattern to figure out the secret key. As cipher scheme or an algorithm providing good confusion will have a complex functional relationship between the plaintext /key pair and the ciphertext.

Note 4: Confusion obscures the relationship between the plaintext and the ciphertext, while diffusion dissipates the redundancy of the plaintext by spreading it out over the ciphertext.

Note 5: Ciphers that use confusion and diffusion are called product ciphers. Each application of confusion and diffusion is called a round. Product ciphers that use many rounds are called iterated product ciphers. The idea is to make the encryption function so complex and involuted that makes it almost impossible to discover the encryption key.

Note 6: The computational complexity of an encryption algorithm is often measured by two variables:

-T (for time complexity)

-S (for space complexity, or computing memory requirement)

Note 7: An encryption algorithm is said to be computationally secure if the following two criteria are met:

-The time complexity exceeds the useful lifetime of the information.

-The space complexity exceeds the value of the encrypted information.

1. P-box and S-box

Transposition and substitution can be implemented with simple, hardware circuits. For example, Fig. 1 below shows a device, called P-box (P stands for permutation), used to implement the following transposition cipher on an 8-bit input:

|X |1 |2 |3 |4 |

Encrypted Channel

Courier

| |K2 | | |K5 |

key key

Fig 6 – Key Distribution in Pieces

(c) It can be shown that the number of keys increases with the square of the number of people exchanging secret information.

(d) The symmetric key encryption systems described so far have been relatively weak, vulnerable to various cryptanalysis attacks. A secure symmetric key system must be based on mathematically complex problems, problems that have interested mathematicians for years. In the next section we describe a secure encryption algorithm adopted in 1977 by the USA National Institute of Standards and Technology (NIST) called Data Encryption Algorithm (DEA) or Data Encryption Standard (DES).

2.5 The Data Encryption Standard ( DES )

The Data Encryption Standard (DES) is a system developed for the U.S. government for use accepted as a cryptographic standard both in the United States and aboard. Many hardware and software systems have been designed using the DES. However, recently its adequacy has been questioned.

1. Background and History

The new era in cryptography began in the late 1960’s, when companies began needing secure ways to send files. At the time, there was no industry standard – no widely accepted encryption method that had a universal seal of approval.

Financial institutions in particular wanted a standard encryption method that they could have confidence in and could use for data exchange. Because U.S. national security depends on secure cryptography, government agencies involved in cryptography, such as the National Security Agency (NSA) had not been open with their expertise. [Some people say that NSA stands for “No Such Agency” or “Never Say Anything”!].

In 1972, NIST, then known as the National Bureau of Standards, issued a call for proposal for a public encryption algorithm. This led ultimately to the adoption of Data Encryption Standard, or DES, which became the most widely used cryptosystem in the world. DES was developed at IBM, as a modification of an earlier system known as Lucifer. Much of the underlying DES cipher research is credited to the IBM researcher, Horst Feistel, who in 1967 began experimenting with a combination of substitution and transposition ciphers. The Feistel Cipher was described earlier in this chapter. Before computers, transposition was difficult to mechanize and too complex to do by hand. Increases in the size of computer memory made it possible for Feistel to use transposition in his system. Feistel blocks are still used in many (if not most) symmetric encryption systems.

DES did not evolved into the standard without significant discussion and even suspicion by some participants–suspicion that still continues. NIST requested and received assistance from NSA on DES development. Some people have said that NSA modified DES so that the agency could easily reclaim plaintext without using a brute force attack, installing what is commonly known as a trapdoor function. NSA shortened the secret key originally proposed by IBM to 56 bits from 128 bits.

Even in the 1970’s, it was argued that a special – purpose machine could be built to carry out a known plaintext attack, which would essentially perform an exhaustic search for the key. That is given a 64-bit plaintext x and corresponding ciphertext y, every possible key would be tested until a key K is found such that

ek (x) = y. As early as 1977, one could build a VLSI chip, which could test106 keys per second. A machine with 106 chips could search the entire key-space in about a day.

Some people believe that NSA altered IBM’s algorithm to ensure that IBM had not secretly included its own trapdoor function. Some people also believe that NSA wanted to control the use of DES and expected DES to be implemented only in hardware.

Despite the controversy, DES was adopted as the federal standard for unclassified document in 1977, as Federal Information Processing Standard 46 (FIPS PUB 46). It is the most widely used cryptographic method in history.

The 1977 DES standard mandated a review every five years. In 1983, DES was approved for five more years. Then in 1993, DES was again approved for yet another five years. In 1997, NIST solicited candidates for a new secret key encryption standard, Advanced Encryption Standard (AES). NIST announced the candidates for AES, successor to DES, in 1999, and in October 2000, NIST selected Rijndael . (See < aes >).

2. Description of DES

DES is a special type of iterated cipher called a Feistel cipher. We described the basic form of a Feistel cipher earlier. An outline of DES is shown in Fig 7. Plaintext is encrypted in blocks of 64 bits, yielding 64 bits of ciphertext. In other words, DES is a 16-round Feistel cipher having block length 64; it encrypts a plaintext bit-string x (of length 64) using a 56-bit key K, obtaining a ciphertext bit-string ( of length 64 ). The algorithm, which is parameterized by this 56-bit key, has 19 distinct stages. The first stage is a key–independent transposition (permutation) on the 64-bit plaintext. The last stage is the exact inverse of this transposition. The stage prior to the last one exchanges the leftmost 32bits with the rightmost 32 bits. The remaining 16 stages are consisting of 16 iterations of the identical functions but are parameterized by different subkeys. The algorithm has been designed to allow decryption to be done with the same key as encryption. The steps are just run in the reverse order.

The left–hand side of the figure shows that first the 64-bit plaintext passes through the initial permutation (IP), which rearranges the bits to produce the permutated input.

Fig 7 – General Description of DES Encryption Algorithm

This is followed by 16 rounds of iterations; the left and right halves of the output from round 16 are swapped to produce an input to be passed through a permutation function (IP)-1, to produce the 64(bit ciphertext.

The right(hand portion of Figure 7 shows the way in which the 56(bit key is used. Initially the key is passed through a permutation function (i.e., permuted choice 1 in this figure). Then, for each of the 16 iterations, a subkey Ki is produced by the combination of a left circular shift and a permutation (permutated choice 2 in this figure). The permutation function is the same for each iteration, but a different subkey is produced because of the repeated shifting of the key bits.

[pic]

The operation of one of these 16 rounds is illustrated in Fig. 8 (above). Each round takes two 32(bit inputs and produces two 32(bit outputs. The left and right halves of each 64(bit intermediate value are treated as separate 32(bit quantities, labeled L (left) and R (right). The overall processing at each iteration can be summarized in the following formulas:

[pic]

where denotes XOR function. That is, the left output is simply a copy of the right input. The right output is the bit-wise EXCLUSIVE OR of the left input and a function of the right input and the key for this round, Ki. All the complexity lies in this function. This complex function involves both permutation and substitution operation.

The function F consists of four steps, carried out in sequence. First, a 48(bit number, E, is constructed by expanding the 32(bit Ri-1 according to a fixed transposition and duplication rule. Second, E and Ki are EXCLUSIVE ORed together. This output is then partitioned into eight groups of 6 bits each, each of which is fed into a different “S(box”. Each of the 64 possible inputs to an S(box is mapped onto a 4(bit output. This step uses eight S(boxes. Each S(box mapped six bits to four bits. Finally, the 8(4 bits, outputs of eight S(boxes, are passed through a permutation operator, i.e. a P(box.

In each of the 16 iterations, a different key is used. Figure 7 shows that before the algorithm starts, a 56(bit transposition is applied to the key. Figure 8 shows that just before each iteration, the key is partitioned into two 28(bit units, each of which is rotated left (i.e. circular left shift) by a number of bits dependent on the iteration number. Ki is derived from this rotated key by applying yet another 56(bit transposition to it. A different 48(bit subset of the 56(bit is extracted and permuted on each round.

The process of decryption with DES is essentially the same as the encryption process. The rule is as follows: use the ciphertext as input to the DES algorithm, but use the keys Ki in reverse order. That is, use K16 on the first iteration, K15 on the second iteration, and so on until K1is used on the sixteenth and last iteration.

2.6 DES Modes of Operation

The DES algorithm is basically a monoalphabetic substitution cipher using a 64(bit character. Whenever the same 64(bit plaintext block goes in the front end, the same 64(bit ciphertext block comes out the back end. A cryptanalyst can exploit this property to help break DES.

To apply DES in a variety of application four “modes of operation” have been defined (FIPS PUB 74, 81). These four modes are intended to cover virtually all the possible application of encryption for which DES could be used. The modes are described as follows and summarized in Table 1. These same modes can be applied for any symmetric block cipher.

Table 1 ( DES Modes of Operation

|Mode |Description |Typical Application |

|Electronic Code Book |Each block of 64 plaintext bits is encoded |Secure transmission of single values (e.g. |

|(ECB) |independently using the same key. |an encryption key) |

|Cipher Block Chaining |The input to the encryption algorithm is the |General-purpose block-oriented transmission |

|(CBC) |XOR of the next 64 bits of plaintext and the |Authentication |

| |preceding 64 bits of ciphertext. | |

|Cipher Feedback |Input is processed J bits at a time. Preceding |General-purpose block-oriented transmission |

|(CFB) |ciphertext is used as input to the encryption |Authentication |

| |algorithm to produce pseudo-random output, | |

| |which is XORed with plaintext to produce next | |

| |unit of ciphertext. | |

|Output Feedback |Similar to CFB, except that the input to the |Stream-oriented transmission over noisy |

|(OFB) |encryption algorithm is the preceding DES |channel (e.g. satellite communication) |

| |output. | |

2.6.1 Triple DES

Given the potential vulnerabilities of DES to a brute-force attack, there has been considerable interest in finding an alternative. One approach is to design a completely new algorithm. Examples are International Data Encryption Algorithm (IDEA), Advanced Encryption Standard (AES), Blowfish, RC5, CAST (developed by Carlisle Adams and Stafford Tavares in 1997) and RC2.

Another alternative, which would preserve the existing investment in software and equipment, is to use multiple encryptions with DES and multiple keys.

The simplest form of multiple encryption has two stages and two keys as shown in Figure below. Given Plaintext P and two encryption keys K1 and K2, ciphertext C is generated as:

K1 K2

X

P C

Encryption

K2 K1

C X P

Decryption

(a) Double Decryption

K1 K2 K1

P C

Encryption

K1 K2 K1

C

P

Decryption

(b) Triple Encryption

Figure Multiple Encryption

C = ek2 (ek1 (P))

Decryption requires that the keys be applied in reverse order:

P = dk1 (dk2 (C))

For DES, this scheme apparently involves a key length of 56 x 2 = 112 bits, resulting in a dramatic increase in cryptographic strength.

Note 1:

It can be shown that any block encryption cipher such as Double DES is mot immune to an attack known as a meet-in-the-middle attack, which was first described by Diffie and Hellman in 1977.

An obvious counter to the meet-in-the-middle attack is to use three stages of encryption with three different keys. However, it has the drawback of requiring a key length of 56 x 3 = 168 bits, which may be somewhat unwieldy. As an alternative, there has been proposed a triple encryption method that uses only two keys. The function follows an encryption-decryption-encryption (EDE) sequence, as shown in the previous figure:

C = ek1 (dk2 (ek1 (P)))

Note 2:

The advantage of the use of decryption for the second record stage is that it allows users of 3DES to decrypt data encrypted by using the older version of single DES:

C = ek1 (dk1 (ek1 (P))) = ek1 (P)

Note 3:

Triple DES (or 3DES) with two keys is a relatively popular alternative to DES and has been adopted for use in the key management standards ANS X9.17 and ISO 8732.

Note 4:

Many researchers now feel that three-key triple DES is the preferred alternative. Three-key 3DES has an effective key length of 168 bits and is defined as follows:

C = ek3 (dk2 (ek1 (P)))

Backward compatibility with DES is provided by putting K3 = K2 or K1 = K2.

Note 5:

A number of Internet-based applications have adopted three-key 3DES, including PGP (Pretty Good Privacy) and S/MIME (Secure/Multipurpose Internet Mail Extension).

2.6.2 Electronic Code-Book Mode

This is the simplest mode, in which plaintext is handled 64 bits at a time and each block of plaintext is encrypted using the same key, as shown in the following Fig. 9. The term code-book is used because, for a given key, there is a unique ciphertext for every 64-bit block of plaintext. For a message longer than 64 bits, the procedure is simply to break the message into 64-bit blocks, padding the last block if necessary. Decryption is performed one block at a time, always using the same key. In Fig. 9, the plaintext (padded as necessary) consists of a sequence of 64-bit blocks, P1, P2,…, PN; the corresponding sequence of ciphertext blocks is C1, C2,…, CN.

[pic]

Note 1 (If the message has repetitive elements, with a period of repetition a multiple of 64 bits, then these elements can be identified by the analyst. To overcome the security deficiencies of ECB, we would like a technique in which the same plaintext block, if repeated, produces different ciphertext blocks. DES can be chained in various ways so that replacing a block will cause the plaintext decrypted starting at the replaced block to be garbage.

2.3.2 Cipher Block Chaining Mode

One way of chaining is cipher block chaining (CBC). In this method, shown in Fig. 10 (below), each plaintext block is XORed with the previous ciphertext block before being encrypted. Consequently, the same plaintext block no longer maps onto the same ciphertext block, and the encryption is no longer a big monoalphabetic substitution cipher. The same key is used for each block. The first block is XORed with a randomly chosen initial vector(IV), which is transmitted along with the ciphertext. For maximum security, the IV should be protected as well as the key. This could be done by sending the IV using ECB encryption.

[pic]

For decryption, each cipher block is passed through the decryption algorithm. The result is XORed with the preceding ciphertext block to produce the plaintext block. To see that this works, we can write:

[pic]

Then

[pic]

However, the CBC has the disadvantage of requiring an entire 64-bit block to arrive before decryption can begin.

2.6.3 Cipher Feedback Mode

For byte-by-byte encryption, cipher feedback (CFB) mode, shown in Fig. 11 below, can be used. For example, if 8-bit characters are being transmitted, each character should be encrypted using 8 bits. If more than 8 bits are used, transmission capacity is wasted. In the figure, it is assumed that the unit of transmission is j bits; a common value is j=8. As with CBC, the units of plaintext are chained together, so that the ciphertext of any plaintext unit is a function of all the preceding plaintext.

[pic]

First, consider encryption. The input to the encryption function is a 64-bit shift register that is initially set to some initialization vector (IV). The leftmost (most significant) j bits of the output of the encryption function are XORed with the first unit of plaintext P1 to produce the first unit of ciphertext C1, which is then transmitted. In addition, the contents of the shift register are shifted left by j bits and C1 is placed in the rightmost (least significant) j bits of the shift register. This process continues until all plaintext units have been encrypted.

For decryption, the same scheme is used, except that the received ciphertext unit is XORed with the output of the encryption function to produce the plaintext unit.

Note that the contents of the shift register depend on the entire previous history of the plaintext, so pattern that repeats multiple times in the plaintext will be encrypted differently each time in the ciphertext.

In addition to its use to achieve confidentiality, the CFB mode can be used for authentication.

As an aside, it should be noted that if one bit of the ciphertext is accidentally inverted during transmission, the 8 bytes that are decrypted while the bad byte is in the shift register will be corrupted. Once the bad byte is pushed out of the shift register, correct plaintext will once again be generated. Thus the effects of a single inverted bit are relatively localized and do not ruin the rest of the message.

Nevertheless, if the effect of 1-bit transmission error is too large, a fourth option, output feedback (OFB) mode, exists.

2.6.4 Output Feedback Mode

It is identical in structure to that of CFB, as shown in Fig. 12 (below).

[pic]

As can be seen, it is the output of the encryption function that is fed back to the shift register in OFB, whereas in CFB, the ciphertext unit is fed back to the shift register.

One advantage of OFB method is that bit errors in transmission do not propagate. For example, if a bit error occurs in C1, only the recovered value of P1 is affected; subsequent plaintext units are not corrupted. With CFB, C1 also serves as input to the shift register and therefore causes additional corruption downstream.

The disadvantage of OFB is that it is more vulnerable to a message stream modification attack than is CFB. Thus, it should be avoided for general-purpose use. The ECB mode should also be avoided except under special circumstances (e.g., for encrypting a single random number, such as a session key or the IV). For normal operation, CBC should be used when the input arrived in 8-byte units (e.g., for encrypting disk files) and CFB mode should be used for irregular input streams, such as keyboard input.

-----------------------

Output ( (x)

input (x)

Output

3-bit

Input

3-bit

Decoder:

3 to 8

Encoder:

8 to 3

S1 S5 S9

S2 S6 S10

P1 P2 P3 P4

S3 S7 S11

S4 S8 S12

F

Long Random Numbers

Same Series of Numbers

F

64-bit plaintext

K16

K2

K1

56-bit key

64-bit ciphertext

ciphertext

Original plaintext

plaintext

---13592731

Li

Ki

Ri

XOR combining function

I am ……………………

Li

Ki

Ri

Round i

Round i

k1

K3

K5

K2

K4

Seder separates

“key”

Receiver reassembles “key”

Secure channel

Certified Mail

Trust Worthy channel

Left circular shift

Permuted choice 2

Round 16

Round 2

Permuted choice 2

Left circular shift

Left circular shift

Permuted choice 1

32-bit swap

Inverse initial permutation

Round 1

Initial permutation

Permutation choice 2

+

E

E

D

D

E

D

E

D

D

E

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download