3.2. Symmetric Ciphers

Symmetric ciphers get their name from the fact that the same key is used for both encryption and decryption. A trivialand horribly insecureexample is a cipher that merely performs an exclusive-OR () of each byte of a message with a corresponding byte of the key (see Figure A.1). For example, if our key is 0123, we would encrypt and decrypt the message trivial as shown in Figure 3.1.

Figure 3.1. A Trivial Symmetric Cipher

	ASCII	HEX
Plaintext	trivial	74 72 69 76 69 61 6c
Key	0123012	30 31 32 33 30 31 32
Plaintext key = ciphertext	DC[EYP^	44 43 5b 45 59 50 5e
Key	0123012	30 31 32 33 30 31 31
Ciphertext key = plaintext	trivial	74 72 69 76 69 61 6c

In this case, the decryption operation (exclusive-OR) as well as the key are the same as for encryption, but in many symmetric ciphers, only the key is the same.

Interestingly, even though this cipher is trivial to break (see [Dawson and Nielsen 1996] and Section 1.4 of [Schneier 1996]), it is almost identical to the only known provably unbreakable cipher: the one-time pad. The crucial difference is that with the one-time pad, the key is never repeated. This implies, of course, that the key must be at least as long as the message and that each message must have its own key.

Stream Ciphers

Our trivial cipher is an example of a stream cipher. The distinguishing characteristic of stream ciphers is that they operate on the plaintext one character at a time, and that the same character does not necessarily encrypt to the same cipher text each time it is encountered. We can see an example of this last phenomenon in Figure 3.1, where the first i of trivial encrypts to [ and the second i encrypts to Y.

When we say character in the preceding definition, we are deliberately speaking loosely. Stream ciphers can operate on individual bits, on bytes, or even on 32-bit "characters." The point is that stream ciphers operate on relatively small units of information and may encrypt a given character differently at different places in the text stream.

Probably the most common stream cipherowing to its use in SSL (Secure Sockets Layer), discussed in Chapter 6is RC4. The idea behind RC4 is to generate a sequence of pseudorandom bytes, called the key stream, that can be exclusive-ORed into the plaintext, as we did in Figure 3.1. Because the sequence of bytes in the key stream does not repeat for a very long time, it is not vulnerable to the easy attacks that a cipher based on the repeated exclusive-ORing of a key into the plaintext is. Because that sequence is not truly random, it does not offer the perfect security of a one-time pad.

RC4 was invented in 1987 by Ron Rivest at RSA Data Security, Inc. The RC4 algorithm is proprietary to RSA Security, and the details of its operation have never been publicly revealed. What we are about to describe is a reverse engineered version sometimes called alleged RC4. Independent observers with access to the licensed RC4 code have confirmed that alleged RC4 is, in fact, the same algorithm.

RC4 is simple to describe and implement. Indeed, there is a three-line Perl implementation of it at <http://www.cypherspace.org/~adam/rsa/rc4.html>. The algorithm has an initialization, or key-scheduling, phase, in which the initial state of the pseudorandom byte generator is set up. In the second phase, the key stream is generated and exclusive-ORed into the plaintext to produce the ciphertext.

RC4's internal state consists of a 256-byte array, S, of unique 8-bit values, and two counters, i and j. The key-scheduling algorithm takes as input the sequence K_i, which is the key concatenated with itself repeatedly to make a sequence of length 256 bytes, and performs the following three operations:

Once the key-scheduling algorithm initializes the internal state, a random byte, R, is generated by:

i = (i +1) mod 256

j = ( j +S_i) mod 256

k = (S_i +S_j) mod 256

swap S_i and S_j

R = S_k

These steps are iterated to produce a sequence of pseudorandom bytes R_i. Encryption proceeds by exclusive-ORing the i^th byte of plaintext with the corresponding random byte. That is, C_i = P_i R_i, where the P_i are the plaintext bytes and the C_i are the ciphertext bytes. Decryption works in exactly the same way. We show a python implementation of RC4 in Figure A.2.

Although RC4 is simple and may even seem ad hoc, it is an excellent algorithm with many desirable cryptographic properties. It is also very fast. RSA claims speeds of 1 MB/second even on a 33 MHz machine [Robshaw 1995], and the OpenSSL speed benchmark reports speeds on the order of 60 MB/second on a 1.6 GHz Pentium 4. In 2004, Marc Bevand achieved speeds of 319 MB/second on the AMD64 processor (<http://etud.epita.fr/~bevand_m/papers/rc4-amd64.html>). See [Mister and Tavares 1999] for an analysis of RC4's cryptographic properties. An important vulnerability in RC4's use with wired equivalent privacy (WEP) is discussed in [Fluhrer, Mantin, and Shamir 2001]. [Roos 1995] identifies a class of weak keys and recommends the first few bytes of RC4 output be discarded. A cautionary tale involving the misuse of RC4in this case, reusing the key streamcan be found in [Stevenson 1995].

Block Ciphers

As their name implies, block ciphers operate on fixed-sized blocks of data. The traditional size was usually 64 bits, but more recent block ciphers use block sizes of 128, 192, or even 256 bits. A block cipher takes an N-bit block of plaintext as input and outputs an N-bit block of ciphertext.

At first glance, it's difficult to see the difference between stream and block ciphers except for the larger unit of data operated on by block ciphers, and, indeed, each can take on the characteristics of the other. The salient difference is that whereas stream ciphers might encrypt two occurrences of the same character differently, depending on their position in the text stream, block ciphers will always encrypt the same block of bits the same way. In this sense, block ciphers are really just a "code book" that specifies an encrypted block for each plaintext block, and we could, in principle, implement them as a table lookup. As a practical matter, this isn't feasible, because such a code book would require two arrays of 2^N entries of N bits each.

For the reasons discussed in the previous paragraph, block ciphers are said to operate in electronic code book (ECB) mode. This mode has some security problems because many messages have data in common, and it is sometimes possible to infer information about a message that has a block in common with another message. That is, if two messages have the same block of plaintext, they will have the same block of ciphertext.

To avoid these problems, we can add an extra step to the encryption process. We choose an arbitrary block, called an initialization vector (IV), and exclusive-OR it with the first plaintext block before we encrypt it. Before encrypting the second plaintext block, we exclusive-OR it with the first cipher block, and so on. That is, if E_K is the block encryption algorithm with key K, we encrypt the message as:

CB₀ = E_K(PB₀ IV)

CB_i = E_K(PB_i CB_i-1), i > 0

where IV is the initialization vector, PB_i is the sequence of plaintext blocks, and CB_i is the sequence of cipher blocks.

This is called cipher block chaining (CBC) mode. The IV need not be kept secret, although it often is, but it must be different for every message. Most experts recommend using a random value for the IV. Note that even if two plaintext blocks are the same, they will almost certainly encrypt to different blocks because they will be exclusive-ORed with different blocks first. The CBC mode process is illustrated in Figure 3.2. Decryption is similar, except that the IV and cipher blocks are exclusive-ORed after the decryption step.

Figure 3.2. Cipher Block Chaining

[View full size image]

Another effective way of using block ciphers is called counter (CTR) mode [Dworkin 2001]. With this mode, a counter is encrypted with the block cipher, the resulting n-bit block is exclusive-ORed into the plaintext block, and the counter is incremented. That is:

CB_i = PB_i E_K(CTR_i)

where <PB_i> is the sequence of plaintext blocks, <CB_i> is the sequence of corresponding ciphertext blocks, CTR_i is the i^th counter value, and E_K(X) represents encryption of X with the block cipher, using key K.

Notice that CTR mode effectively turns a block cipher into a stream cipher. As we'll see later, CTR mode can have certain advantages over CBC mode, but we must take care to ensure that the key stream is not reused. This means that we can never reuse a counter/key pair. It also means that we cannot allow the counter to wrap, or the key stream will be repeated. Typically, the counter is chosen to have a component that depends on the message, such as a message number, and another component that serves as the actual counter. Another suggested implementation merely takes a random IV as the counter and increments it after every encryption.

[Ferguson and Schneier 2003] regard counter mode as the preferred way of using block ciphers. Although they emphasize the dangers involved with its misuse, they believe that it leaks less information than any of the other modes (see Exercise 3.4). The advantages of CTR mode for block ciphers are also discussed in [Lipmaa, Rogaway, and Wagner 2000].

DES

The best-known and most-studied block cipher is, of course, the Data Encryption Standard (DES). It has been the worldwide standard for more than 25 years, but is now at the end of its life. The problem is not with the algorithm itselfthat's held up remarkably wellbut with its small key size of 56 bits, and to a lesser extent, the small, by modern standards, block size of 64 bits.

It is worthwhile to briefly examine the operation of DES because it illustrates many of the features of block ciphers. The complete specification is given in [NIST 1999], so we will content ourselves with covering the concepts without looking at every detail. [Schneier 1996] gives a fascinating history of DES, and discusses its design and cryptographic properties.

At first glance, the DES algorithm seems complex, especially in comparison to the simplicity of RC4. The basic idea, however, is quite simple. First, the 56-bit key is used to generate 16 48-bit round keys. Each round key is obtained from the original by shifting the original key by an amount that depends on the round and then extracting a 48-bit subset. After an initial permutation, an input block of 64 bits is split into two halves, L and R. The right half, R, is combined with one of the round keys by a function traditionally called f . The result is then exclusive-ORed into the left half, L, and L and R are swapped. This is repeated 16 times, after which the inverse of the original permutation is applied to the result. The traditional way of presenting this is shown in Figure 3.3, but it's easier to think of it as the recursion

Equation 1

Equation 2

where K_i is the i^th round key, and we have ignored the initial and final permutations. Ciphers that divide the input block into two halves and use a recursion such as this are called Feistel ciphers, or Feistel networks. Notice that from (1), we can obtain R_i-1 from L_i and that if we exclusive-OR both sides of (2) with f (R_i-1, K_i), we recover L_i-1 from R_i . This means that we can use the same algorithm for encryption and decryption by merely reversing the order of the round keys. That is, encryption uses the sequence K₁, K₂, . . . , K₁₆, whereas decryption uses the sequence K₁₆, K₁₅, . . . , K₁.

This fact also explains an apparent anomaly in Figure 3.3. Observe that in the last round, L₁₆ and R₁₆ are not swapped. Thus, an encrypted block can be fed back into the algorithm as is for decryption. This was an important consideration for DES because the original specification required that it be implemented in hardware, and the ability to decrypt by feeding the cipher text as is into the same algorithm meant that the same circuitry could be used for both encryption and decryption.

The ability to use the same algorithm for encryption and decryption is a characteristic of Feistel ciphers. As long as f (R_i-1, K_i) can be reproduced, it is always possible to invert the encryption using the same algorithm, even if f itself is not invertible.

Putting aside the internals of the f function for the moment, we see that each round of DES is reminiscent of RC4. The f function produces some pseudorandom data that is exclusive-ORed into the plaintext stream. There are obvious differences, of course. For one thing, the bits that get exclusive-ORed into L_i depend on the plaintext as well as the key. This is an important point; one of the goals of the DES algorithm is to ensure that every bit of the encrypted block depends on every bit of the plaintext block and every bit of the key. Feeding the plaintext into f is a vital part of guaranteeing this.

The operation of the f function is illustrated in Figure 3.4. First, the expansion permutation rearranges the 32 bits of the R half-block and expands the result to 48 bits by repeating some of the bits. The expansion to 48 bits makes the result match the size of the round key, but more important, it means that half the bits in any R_i will affect multiple bits in the output of f.

Figure 3.4. The DES f Function

[View full size image]

Next, the round key is exclusive-ORed with the output of the expansion permutation, and the resulting 48 bits are split into eight groups of 6 bits. Each 6-bit group is fed into one of eight substitution boxes, or S-boxes. Each S-box maps its input into 4 output bits that are combined with the output of the other S-boxes to create a 32-bit result. These 32 bits are permuted by the P permutation to form the final output of f .

The S-boxes are the heart of the DES algorithm and are what gives it most of its strength. The structure of the S-boxes is simple; they merely perform a table lookup on the 6-bit input to obtain a 4-bit entry. The values used for those tables are anything but simple, however. They are carefully chosen to have certain cryptographic properties that make DES resistant to cryptanalytic attack.

The ever-expanding power of modern computers has rendered DES obsolete. As far back as the late 1970s, Diffie and Hellman speculated that a DES-cracking machine that could break DES by brute forcethat is, by trying every possible keycould be built for $20 million. They estimated that the machine would take a day to recover a key. And, indeed, in 1998 the Electronic Frontier Foundation built a DES-cracking machine, called Deep Crack, for less than $250,000. Deep Crack was able to recover the key for RSA's DES Challenge II in less than three days. The design of the machine and the story of its development are recounted in [Electronic Frontier Foundation 1998]. More recently, distributed networks of small general-purpose computers have been used in conjunction with Deep Crack to break DES in less than a day.

Triple DES

As we noted above, the major problem with DES is that the key has only 56 bits. That means that a brute-force attack takes at most 2⁵⁶ attempts, a number well within practical limits for today's machines. Triple DES (3DES) deals with this problem by encrypting the plaintext three times with three different keys. Although this yields an effective key size of only 112 bits, rather than the 168 we might expect, it does extend the life of DES for a few more years.

Triple DES is usually implemented in encrypt-decrypt-encrypt (EDE) mode, where the first key is used to encrypt a block, the second key is used to decrypt the result of step 1, and the third key is used to encrypt the result of step 2. If E_Ki is the encryption function for key K_i, and D_Ki is the decryption function for key K_i, we have

CB = E_K3(D_K2(E_K1 (PB)))

PB = D_K1(E_K2(D_K3 (CB)))

where PB is a plaintext block, and CB is the corresponding encrypted block. EDE mode does not have any cryptographic effect, but it does allow 3DES to be backward compatible with DES by setting K₁ = K₂ = K₃. Note that when the three keys are the same, the result is the same as a single encryption or decryption with DES.

Despite partially solving the problem of the small key size of DES, 3DES still has problems. First, it is three times slower than DES, which is already slow when compared to most modern block ciphers. More important, 3DES still uses the 64-bit block size, which yields less security than the larger block size used in recent block ciphers. [Ferguson and Schneier 2003] recommend against using 3DES except for legacy applications that demand it.

AES

In 1997, the National Institute of Standards and Technology (NIST) solicited proposals for a new cipher to replace the aging DES. This new cipher was to be called the Advanced Encryption Standard (AES). NIST specified that AES must support a block size of at least 128 bits and key sizes of at least 128, 192, and 256 bits.

Fifteen candidates were submitted, and in August 1999, NIST announced the five finalists. The criteria for selection of the finalists and for AES itself included the security of the cipher, its performance, and its ease of implementation in hardware and software. On October 2, 2000, NIST revealed its selection of the Rijndael cipher for AES.

Rijndael (AES)

Rijndael supports block and key sizes of 128, 192, and 256 bits. There are 10 to 14 rounds, depending on the key size. The key-scheduling algorithm expands the initial key to N x (R + 1) bits, where N is the block size in bits, and R is the number of rounds. The first N bits are used as the key for round 1, the second N bits for round 2, and so on. The last N bits are used in a final key mixing after the last round.

Although both AES and DES use some of the same basic operations, such as S-boxes and permutations, AES is different from DES in several ways. First, AES is byte oriented: All the basic operations are performed on bytes rather than on bits as in DES. Second, AES is not a Feistel cipher. Indeed, decryption uses a different algorithm from encryption. Finally, the number of rounds is variable, depending on the key and block sizes.

Figure 3.5 shows a typical AES round for a block size of 128. The rounds for the other block sizes are similar. The input block is delivered to the round as 16 bytes labeled b₀, . . . , b₁₅. The output of the round is also 16 bytes, labeled c₀, . . . , c₁₅.

Figure 3.5. One Round of AES

[View full size image]

As the bytes enter at the top of Figure 3.5, they are exclusive-ORed with the 16 bytes of the round key K⁽ⁱ⁾. The result is fed into 16 identical S-boxes that do a table lookup on the input byte to produce an output byte. Next, the outputs from the 16 S-boxes are permuted by the permutation

Equation 3

where the meaning of (3) is that b₀ b₀, b₁ b₅, b₂ b₁₀, and so on. Notice that the bytes from each group of four are dispersed uniformly to each of the other three groups.

Finally, the output of the byte permutation is divided into groups of 4 bytes, and each group is subjected to a linear mixing function that produces 4 output bytes.

Technically, the linear mixing function is the linear transformation

over the finite Galois field GF(2⁸), but as a practical matter, we can think of the linear mixing function as exclusive-ORing input bytes to produce an output byte.

The last round differs from the others in that the linear mixing function is skipped, and the output bytes from the permutation are exclusive-ORed with the final 128 bits of the expanded key.

The decryption rounds follow the same pattern except that the data flow is from bottom to top, the inverse of each of the operations is used, and the round keys are used in reverse order, as they were with DES.

The specification for Rijndael is given in [NIST 2002a]. NIST maintains an AES home page at <http://www.nist.gov/aes>, with pointers to the Rijndael home page, implementations, and information about the other AES candidates.

Blowfish

Blowfish is a block cipher developed by Bruce Schneier. Because the algorithm is fast and unencumbered, it's a popular encryption method that is used in several VPNs. Although its 64-bit block size is considered too small by modern standards, many of the applications that we are concerned with are still using Blowfish, so it is worth our while to take a quick look at it.

Blowfish uses a variable-length key of up to 448 bits, although 128 bits are more usual. The large key size adds considerable strength to the algorithm compared to DES, which Blowfish was designed to replace. Like DES, Blowfish is a Feistel cipher, and the Blowfish f function uses S-boxes, but the S-boxes depend on the key, which makes cryptanalysis of the algorithm more difficult. The key-scheduling algorithm generates 18 subkeys, P₁, . . . , P₁₈, and four S-boxes, S₁, . . . , S₄, from the key. Each S-box maps an 8-bit input to a 32-bit output.

Figure 3.6 shows the operation of the algorithm and also makes its structural similarity to DES clear. Each of the 16 rounds consists of simply exclusive-ORing its left input with one of the 18 subkeys, and its right input with the output of the f function. The f function is also simple. It uses only the S-boxes, exclusive-ORs, and 2³² modular addition. This simplicity is what gives Blowfish its speed, especially on modern 32-bit processors. The operation of the f function is shown in Figure 3.7.

The Blowfish key-scheduling algorithm requires considerable computation. It is roughly equivalent to encrypting 4 kilobytes of data. The algorithm works by initializing the 18 subkeys and the 256 32-bit entries of each S-box to the hexadecimal digits of the fractional part of p. Next, the user's key is exclusive-ORed into the subkeys, cycling through the key repeatedly, if necessary, to fill out the 18 subkeys. Then, a block of 0s is encrypted, and the result replaces P₁ and P₂. The modified algorithm is now used to encrypt the results of the previous encryption, and the output replaces P₃ and P₄. This operation is performed 521 times until each of the subkeys and all the S-box entries are initialized.

Because of the time it takes to initialize the algorithm's state, Blowfish is not suitable for situations in which the key is changed frequently. Blowfish is ideal for applications such as VPNs, in which a key is used for some time before it is replaced.

Additional information about Blowfish is available on Schneier's Web site, <http://www.schneier.com/blowfish.html>, where he gives a complete discussion of the algorithm, an explanation of some of the design decisions, and pointers to several free implementations. As of this writing, there is no known practical attack against Blowfish. Certain weak keys can be detected, but not identified or exploited, in a reduced 14-round version of Blowfish, and a 4-round version is vulnerable to a differential analysis attack.