Block ciphers encrypt plaintext messages in blocks of fixed lengths and are more ubiquitously used than public-key encryption routines. In a sense, public-key encryption is also block encryption. Since public-key routines are much slower than (secret-key) block ciphers, it is a custom to use public-key algorithms only in specific situations, for example, for encrypting single blocks of data, like keys of symmetric ciphers.
In the rest of this chapter, we use the word bit in the conventional sense, that is, to denote a quantity that can take only two possible values, 0 and 1. It is convenient to use the symbol to refer to the set {0, 1}. We also let stand for the set of all bit strings of length m. Whenever we plan to refer to the field (or group) structure of , we will use the alternative notation .
A block cipher f of block-size n and of key-size r is a map
that encrypts a plaintext block m of bit length n to a ciphertext block c of bit length n under a key K, a bit string of length r. To ensure unique decryption, the map
for a fixed key K has to be a permutation of (that is, a bijective function on) . In that case, the decryption of c to get back m is carried out as . |
A good block cipher has the following desirable properties:
The sizes n and r should be big enough, so that an adversary cannot exhaustively check all possibilities of m or K in feasible time.
For most, if not all, keys K, the permutations fK should be sufficiently random. In other words, if the key K is not known, it should be computationally infeasible to guess the functions fK and . That is, it should be difficult to guess c from m or m from c, unless the key K is provided. The identity map on , though a permutation of , is a bad candidate for an encryption function fK. It is also desirable that the functions fK for different values of K are unpredictably selected from the set of all permutations of . Thus, for example, taking fK to be a fixed permutation for all choices of K leads to a poor design of a block cipher f.
For most, if not all, pairs of distinct keys K1 and K2, the functions gK1 ο gK2 should not equal gK for some key K, where g stands for f or f–1 with independent choices in the three uses. A more stringent demand is that the subgroup generated by the permutations fK for all possible keys K should be a very big subset of the group of all permutations of . If gK = gK1 ο gK2 ο · · · ο gKt for some t ≥ 2, multiple encryption (see Section A.3) forfeits its expected benefits.
A block cipher provably possessing all these good characteristics (in particular, the randomness properties) is difficult to construct in practice. Practical block ciphers are manufactured for reasonably big n and r and come with the hope of representing reasonably unpredictable permutations. We dub a block cipher good or safe, if it stands the test of time. Table A.1 lists some widely used block ciphers.
Name | n | r |
---|---|---|
DES (Data Encryption Standard) | 64 | 56 |
FEAL (Fast Data Encipherment Algorithm) | 64 | 64 |
SAFER (Secure And Fast Encryption Routine) | 64 | 64 |
IDEA (International Data Encryption Algorithm) | 64 | 128 |
Blowfish | 64 | ≤ 448 |
Rijndael, accepted as AES (Advanced Encryption Standard) by NIST (National Institute of Standards and Technology, a US government organization) | 128/192/256 | 128/192/256 |
The data encryption standard (DES) was proposed as a federal information processing standard (FIPS) in 1975. DES has been the most popular and the most widely used among all block ciphers ever designed. Although its relatively small key-size offers questionable security under today’s computing power, DES still enjoys large-scale deployment in not-so-serious cryptographic applications.
DES encryption requires a 64-bit plaintext block m and a 56-bit key K.[1] Let us plan to use the notations DESK and to stand respectively for DES encryption and decryption functions under the key K.
[1] A DES key K = k1k2 . . . k64 is actually a 64-bit string. Only 56 bits of K are used for encryption. The remaining 8 bits are used as parity-check bits. Specifically, for each i = 1, . . . , 8 the bit k8i is adjusted so that the i-th byte (k8i – 7k8i – 6 . . . k8i) has an odd number of one-bits.
The DES algorithm first computes sixteen 48-bit keys K1, K2, . . . , K16 from K using a procedure known as the DES key schedule described in Algorithm A.1. These 16 keys are used in the 16 rounds of encryption. The key schedule uses two fixed permutations PC1 and PC2 described after Algorithm A.1 and to be read in the row-major order. Here, PC is an abbreviation for permuted choice.
Input: A DES key K = k1k2 . . . k64 (containing the parity-check bits). Output: Sixteen 48-bit round keys K1, K2, . . . , K16. Steps: Use PC1 to generate . |
PC1 | ||||||
---|---|---|---|---|---|---|
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 |
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 |
DES encryption, as described in Algorithm A.2, proceeds in 16 rounds. The i-th round uses the key Ki (obtained from the key schedule) in tandem with the encryption primitive e. A fixed permutation IP and its inverse IP–1 are also used.[2]
[2] A block cipher that executes several encryption rounds with the i-th round computing the two halves as Li := Ri – 1 and Ri := Li – 1 ⊕ e(Ri – 1, Ki) for some round key Ki and for some encryption primitive e, is called a Feistel cipher. Most popular block ciphers mentioned earlier are of this type. Rijndael is an exception, and its acceptance as the new standard has been interpreted as an end of the Feistel dynasty.
It requires a specification of the round encryption function e to complete the description of DES encryption. The function e can be compactly depicted as:
e(X, J) := P(S(E(X) ⊕ J)),
Input: Plaintext block m = m1m2 . . . m64 and the round keys K1, . . . , K16. Output: The ciphertext block . Steps: Apply the initial permutation on m to get |
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 |
IP–1 | |||||||
---|---|---|---|---|---|---|---|
40 | 8 | 48 | 16 | 56 | 24 | 64 | 32 |
39 | 7 | 47 | 15 | 55 | 23 | 63 | 31 |
38 | 6 | 46 | 14 | 54 | 22 | 62 | 30 |
37 | 5 | 45 | 13 | 53 | 21 | 61 | 29 |
36 | 4 | 44 | 12 | 52 | 20 | 60 | 28 |
35 | 3 | 43 | 11 | 51 | 19 | 59 | 27 |
34 | 2 | 42 | 10 | 50 | 18 | 58 | 26 |
33 | 1 | 41 | 9 | 49 | 17 | 57 | 25 |
where is an expansion function, is a contraction function and P is a fixed permutation of (called the permutation function). S uses eight S-boxes (substitution boxes) S1, S2, . . . , S8. Each S-box Sj is a 4 × 16 matrix with each row a permutation of 0, 1, 2, . . . , 15 and is used to convert a 6-bit string y1y2y3y4y5y6 to a 4-bit string z1z2z3z4 as follows. Let μ denote the integer with binary representation y1y6 and ν the integer with binary representation y2y3y4y5. Then, z1z2z3z4 is the 4-bit binary representation of the μ, ν-th entry in the matrix Sj. (Here, the numbering of the rows and columns starts from 0.) In this case, we write Sj(y1y2y3y4y5y6) = z1z2z3z4. Algorithm A.3 provides the description of e.
Input: and . Output: e(X, J). Steps: Y := E(X) ⊕ J (where E(x1x2 . . . x32) = x32x1x2 . . . x32x1). |
The tables for E and P are as follows.
E | |||||
---|---|---|---|---|---|
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 |
P | |||
---|---|---|---|
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 |
Finally, the eight S-boxes are presented:
S1 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
S2 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
S3 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
S4 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
S5 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
S6 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
S7 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
S8 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
DES decryption is analogous to DES encryption. To obtain one first computes the round keys K1, K2, . . . , K16 using Algorithm A.1. One then calls a minor variant of Algorithm A.2. First, the roles of m and c are interchanged. That is, one inputs c instead of m, and obtains m in place of c as output. Moreover, the right half Ri in the i-th round is computed as Ri := Li – 1 ⊕ e(Ri – 1, K17 – i). In other words, DES decryption is same as DES encryption, only with the sequence of using the keys K1, K2, . . . , K16 reversed. Solve Exercise A.1 in order to establish the correctness of this decryption procedure.
Some test vectors for DES are given in Table A.2.
Key | Plaintext block | Ciphertext block |
---|---|---|
0101010101010101 | 0000000000000000 | 8ca64de9c1b123a7 |
fefefefefefefefe | ffffffffffffffff | 7359b2163e4edc58 |
3101010101010101 | 1000000000000001 | 958e6e627a05557B |
1010101010101010 | 1111111111111111 | f40379ab9e0ec533 |
0123456789abcdef | 1111111111111111 | 17668dfc7292532d |
1010101010101010 | 0123456789abcdef | 8a5ae1f81ab8f2dd |
fedcba9876543210 | 0123456789abcdef | ed39d950fa74bcc4 |
DES, being a popular block cipher, has gone through a good amount of cryptanalytic studies. At present, linear cryptanalysis and differential cryptanalysis are the most sophisticated attacks on DES. But the biggest problem with DES is its relatively small key size (56 bits). An exhaustive key search for a given plaintext–ciphertext pair needs carrying out a maximum of 256 encryptions in order to obtain the correct key. But how big is this number 256 = 72,057,594,037,927,936 (nearly 72 quadrillion) in a cryptographic sense?
In order to review this question, RSA Security Inc. posed several challenges for obtaining the DES key from given plaintext–ciphertext pairs. The first challenge, posed in January 1997, was broken by Rocke Verser of Loveland, Colorado, with approximately 96 days of computing. DES Challenge II-1 was broken in February 1998 by distributed.net with 41 days of computing, and the DES challenge II-2 was cracked in July 1998 by the Electronic Frontier Foundation (EFF) in just 56 hours. Finally, DES Challenge III was broken in a record of 22 hours 15 minutes in January 1999. The computations were carried out in EFF’s supercomputer Deep Crack with collaborative efforts from nearly 105 PCs on the Internet guided by distributed.net. These figures demonstrate that DES offers hardly any security against a motivated adversary.
Another problem with DES is that its design criteria (most importantly, the objectives behind choosing the particular S-boxes) were never made public. Chances remain that there are hidden backdoors, though none has been discovered till date.
The advanced encryption standard (AES) [219] has superseded the older standard DES. The Rijndael cipher designed by Daemen and Rijmen has been accepted as the advanced standard. As mentioned in Footnote 2, Rijndael is not a Feistel cipher. Its working is based on the arithmetic in the finite field and in the finite ring .
AES encrypts data in blocks of 128 bits. Let B = b0b1 . . . b127 be a block of data, where each bi is a bit. Keeping in view typical 32-bit processors, each such block B is represented as a sequence of four 32-bit words, that is, B = B0B1B2B3, where Bi represents the bit string b32ib32i+1 . . . b32i+31. Each word C = c0c1 . . . c31, in turn, is viewed as a sequence of four octets, that is, C = C0C1C2C3, where Ci stores the bit string c8ic8i+1 . . . c8i+7. Each octet is identified as an element of , whereas an entire 32-bit word is identified with an element of .
The field is represented as , where f(X) is the irreducible polynomial X8 + X4 + X3 + X + 1. Let x := X + 〈f(X)〉. The element is identified with the octet d7d6 . . . d1d0. Thus, the i-th octet c8ic8i+1 . . . c8i+7 in a word is treated as the finite field element .
Now, let us explain the interpretation of a 32-bit word C = C0C1C2C3. The -algebra is not a field, since the polynomial Y4 + 1 is reducible (over and so over ). However, each element β of A can be uniquely expressed as a polynomial β = α3y3 + α2y2 + α1y + α0, where y := Y + 〈Y4 + 1〉 and where each αi is an element of . As described in the last paragraph, each αi is represented as an octet. We take Ci to be the octet representing α3 – i, that is, the 32-bit word α3α2α1α0 stands for the element .
and A are rings and hence equipped with arithmetic operations (addition and multiplication). These operations are different from the usual addition and multiplication operations defined on octets and words. For example, the addition of two octets or words under the AES interpretation is the same as bit-wise XOR of octets or words. The AES multiplication of octets and words, on the other hand, involves polynomial arithmetic and reduction modulo the defining polynomials and so cannot be expressed so simply as addition. To resolve ambiguities, let us plan to denote the multiplication of by ⊙ and that of A by ⊗, whereas regular multiplication symbols (·, × and juxtaposition) stand for the standard multiplication on octets or words. Exercises A.5, A.6 and A.7 discuss about efficient implementations of the arithmetic in and A.
Every non-zero element is invertible; the inverse is denoted by α–1 and can be computed by the extended gcd algorithm on polynomials over . With an abuse of notation, we take 0–1 := 0. Every non-zero element of A is not invertible (under the multiplication of A). The AES algorithm uses the following invertible element β := 03010102 (in hex notation); its inverse is β–1 = 0b0d090e.
The AES algorithm uses an object called a state, comprising 16 octets arranged in a 4 × 4 array. Each message block also consists of 16 octets. Let M = μ0μ1 . . . μ15 be a message block (of 16 octets). This block is translated to a state as follows:
Equation A.1
Thus, each word in the block is relocated in a column of the state. At the end of the encryption procedure, AES makes the reverse translation of a state to a block:
Equation A.2
A collection of round keys is generated from the given AES key K. The number of rounds of the AES encryption algorithm depends on the size of the key. Let us denote the number of words in the AES key by Nk and the corresponding number of rounds by Nr. We have:
One first generates an initial 128-bit key K0K1K2K3. Subsequently, for the i-th round, 1 ≤ i ≤ Nr, a 128-bit key K4iK4i+1K4i+2K4i+3 is required. Here, each Kj is a 32-bit word. The key schedule (also called key expansion) generates a total of 4(Nr + 1) words K0, K1, . . . , K4Nr+3 from the given secret key K using a procedure described in Algorithm A.4. Here, (02)j – 1 stands for the octet that represents the element . The following table summarizes these values for j = 1, 2, . . . , 15.
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
xj – 1 | 01 | 02 | 04 | 08 | 10 | 20 | 40 | 80 | 1b | 36 | 6c | d8 | ab | 4d | 9a |
The transformation SubWord on a word T = τ0τ1τ2τ3 is the octet-wise application of AES S-box substitution SubOctet, that is,
SubWord(T) = SubOctet(τ0) ‖ SubOctet(τ1) ‖ SubOctet(τ2) ‖ SubOctet(τ3).
The transformation SubOctet is also used in each encryption round and is now described. Let A = a0a1 . . . a7 be an octet that can be identified with an element of as mentioned earlier. Let B = b0b1 . . . b7 denote the octet representing the inverse of this finite field element. (We take 0–1 = 0.) One then applies the following affine transformation on B to generate the final value C := SubOctet(A) := c0c1 . . . c7. Here, D = d0d1 . . . d7 is the constant octet 63 = 01100011.
Equation A.3
In order to speed up this octet substitution, one may use table lookup. Since the output octet C depends only on the input octet A, one can precompute a table of values of SubOctet(A) for the 256 possible values of A. This list is given in Table A.3. The table is to be read in the row-major fashion. In other words, if hi and lo respectively represent the most and the least significant four bits of A, then SubOctet(A) can be read off from the entry in the table having row number hi and column number lo. For example, SubOctet(a7) = 5c. In an actual implementation, a one-dimensional array is to be used. We use a two-dimensional format in Table A.3 for the sake of clarity of presentation.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | |
0 | 63 | 7c | 77 | 7b | f2 | 6b | 6f | c5 | 30 | 01 | 67 | 2b | fe | d7 | ab | 76 |
1 | ca | 82 | c9 | 7d | fa | 59 | 47 | f0 | ad | d4 | a2 | af | 9c | a4 | 72 | c0 |
2 | b7 | fd | 93 | 26 | 36 | 3f | f7 | cc | 34 | a5 | e5 | f1 | 71 | d8 | 31 | 15 |
3 | 04 | c7 | 23 | c3 | 18 | 96 | 05 | 9a | 07 | 12 | 80 | e2 | eb | 27 | b2 | 75 |
4 | 09 | 83 | 2c | 1a | 1b | 6e | 5a | a0 | 52 | 3b | d6 | b3 | 29 | e3 | 2f | 84 |
5 | 53 | d1 | 00 | ed | 20 | fc | b1 | 5b | 6a | cb | be | 39 | 4a | 4c | 58 | cf |
6 | d0 | ef | aa | fb | 43 | 4d | 33 | 85 | 45 | f9 | 02 | 7f | 50 | 3c | 9f | a8 |
7 | 51 | a3 | 40 | 8f | 92 | 9d | 38 | f5 | bc | b6 | da | 21 | 10 | ff | f3 | d2 |
8 | cd | 0c | 13 | ec | 5f | 97 | 44 | 17 | c4 | a7 | 7e | 3d | 64 | 5d | 19 | 73 |
9 | 60 | 81 | 4f | dc | 22 | 2a | 90 | 88 | 46 | ee | b8 | 14 | de | 5e | 0b | db |
a | e0 | 32 | 3a | 0a | 49 | 06 | 24 | 5c | c2 | d3 | ac | 62 | 91 | 95 | e4 | 79 |
b | e7 | c8 | 37 | 6d | 8d | d5 | 4e | a9 | 6c | 56 | f4 | ea | 65 | 7a | ae | 08 |
c | ba | 78 | 25 | 2e | 1c | a6 | b4 | c6 | e8 | dd | 74 | 1f | 4b | bd | 8b | 8a |
d | 70 | 3e | b5 | 66 | 48 | 03 | f6 | 0e | 61 | 35 | 57 | b9 | 86 | c1 | 1d | 9e |
e | e1 | f8 | 98 | 11 | 69 | d9 | 8e | 94 | 9b | 1e | 87 | e9 | ce | 55 | 28 | df |
f | 8c | a1 | 89 | 0d | bf | e6 | 42 | 68 | 41 | 99 | 2d | 0f | b0 | 54 | bb | 16 |
AES encryption is described in Algorithm A.5. The algorithm first converts the input plaintext message block to a state, applies a series of transformations on this state and finally converts the state back to a message (the ciphertext).
The individual state transition transformations are now explained. The transition SubState is an octet-by-octet application of the substitution function SubOctet, that is, SubState maps
where for all r, c. The transform ShiftRows cyclically left rotates the r-th row by r byte positions, that is, maps
The AddKey operation uses four 32-bit round keys L0, L1, L2, L3. Name the octets of Li as λi0λi1λi2λi3. The i-th key Li is XORed with the i-th column of the state, that is, AddKey transforms
Finally, the MixCols transform multiplies each column of the state, regarded as an element of , by the element , where the coefficients (expressions within square brackets) are octet values in hexadecimal, that can be identified with elements of . For the c-th column, this transformation can be represented as:
Input: The plaintext message M = μ0μ1 . . . μ15 and the round keys K0, K1, . . . , K4Nr+3. Output: Ciphertext message C = γ0γ1 . . . γ15. Steps: Convert M to the state S. /* Use Transform (A.1) */ |
AES decryption involves taking inverse of each state transition performed during encryption. The key schedule needed for encryption is to be used during decryption too. The straightforward decryption routine is given in Algorithm A.6.
What remains is a description of the inverses of the basic state transformations. AddKey involves octet-by-octet XORing and so is its own inverse. Table A.4 summarizes the inverse of the substitution transition SubOctet (Exercise A.8). For computing SubState–1(S), one should apply SubOctet–1 on each octet of S. The inverse of ShiftRows is also straightforward and can be given by
Finally, MixCols–1 involves multiplication of each column by the inverse of the element , that is, by the element [0b]y3 + [0d]y2 + [09]y + [0e]. So MixCols–1 transforms each column of the state as follows:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | |
0 | 52 | 09 | 6a | d5 | 30 | 36 | a5 | 38 | bf | 40 | a3 | 9e | 81 | f3 | d7 | fb |
1 | 7c | e3 | 39 | 82 | 9b | 2f | ff | 87 | 34 | 8e | 43 | 44 | c4 | de | e9 | cb |
2 | 54 | 7b | 94 | 32 | a6 | c2 | 23 | 3d | ee | 4c | 95 | 0b | 42 | fa | c3 | 4e |
3 | 08 | 2e | a1 | 66 | 28 | d9 | 24 | b2 | 76 | 5b | a2 | 49 | 6d | 8b | d1 | 25 |
4 | 72 | f8 | f6 | 64 | 86 | 68 | 98 | 16 | d4 | a4 | 5c | cc | 5d | 65 | b6 | 92 |
5 | 6c | 70 | 48 | 50 | fd | ed | b9 | da | 5e | 15 | 46 | 57 | a7 | 8d | 9d | 84 |
6 | 90 | d8 | ab | 00 | 8c | bc | d3 | 0a | f7 | e4 | 58 | 05 | b8 | b3 | 45 | 06 |
7 | d0 | 2c | 1e | 8f | ca | 3f | 0f | 02 | c1 | af | bd | 03 | 01 | 13 | 8a | 6b |
8 | 3a | 91 | 11 | 41 | 4f | 67 | dc | ea | 97 | f2 | cf | ce | f0 | b4 | e6 | 73 |
9 | 96 | ac | 74 | 22 | e7 | ad | 35 | 85 | e2 | f9 | 37 | e8 | 1c | 75 | df | 6e |
a | 47 | f1 | 1a | 71 | 1d | 29 | c5 | 89 | 6f | b7 | 62 | 0e | aa | 18 | be | 1b |
b | fc | 56 | 3e | 4b | c6 | d2 | 79 | 20 | 9a | db | c0 | fe | 78 | cd | 5a | f4 |
c | 1f | dd | a8 | 33 | 88 | 07 | c7 | 31 | b1 | 12 | 10 | 59 | 27 | 80 | ec | 5f |
d | 60 | 51 | 7f | a9 | 19 | b5 | 4a | 0d | 2d | e5 | 7a | 9f | 93 | c9 | 9c | ef |
e | a0 | e0 | 3b | 4d | ae | 2a | f5 | b0 | c8 | eb | bb | 3c | 83 | 53 | 99 | 61 |
f | 17 | 2b | 04 | 7e | ba | 77 | d6 | 26 | e1 | 69 | 14 | 63 | 55 | 21 | 0c | 7d |
AES decryption is as efficient as AES encryption, since each state transformation primitive has the same structure as its inverse. However, the sequence of application of these primitives in the loop (rounds) for decryption differs from that for encryption. For some implementations, mostly in hardware, this may be a problem. Compare this with DES for which the encryption and decryption algorithms are identical save the sequence of using the round keys (Exercise A.1). With little additional effort AES can also be furnished with this useful property of DES. All we have to do is to use a different key schedule for decryption. The necessary modifications are explored in Exercise A.9.
Table A.5 provides the ciphertexts for the plaintext block
M = 00112233445566778899aabbccddeeff
under different keys.
Cipher | Key | Ciphertext block |
---|---|---|
AES-128 | 0001020304050607 08090a0b0c0d0e0f | 69c4e0d86a7b0430 d8cdb78070b4c55a |
AES-192 | 0001020304050607 08090a0b0c0d0e0f 1011121314151617 | dda97ca4864cdfe0 6eaf70a0ec0d7191 |
AES-256 | 0001020304050607 08090a0b0c0d0e0f 1011121314151617 18191a1b1c1d1e1f | 8ea2b7ca516745bf eafc49904b496089 |
AES has been designed so that linear and differential attacks are infeasible. Another attack known as the square attack has been proposed by Lucks [184] and Ferguson et al. [93], but at present can tackle less number of rounds than used in Rijndael encryption. Also see Gilbert and Minier [112] to know about the collision attack.
The distinct algebraic structure of AES encryption invites special algebraic attacks. One such potential attack (the XSL attack) has been proposed by Courtois and Pieprzyk [68]. Although this attack has not yet been proved to be effective, a better understanding of the algebra may, in foreseeable future, lead to disturbing consequences for the advanced standard.
For more information on AES, read the book [71] from the designers of the cipher. Also visit the following Internet sites:
http://www.esat.kuleuven.ac.be/~rijmen/rijndael/ | Rijndael home |
http://csrc.nist.gov/CryptoToolkit/aes/index1.html | NIST site for AES |
http://www.cryptosystem.net/aes/ | Algebraic attacks |
Multiple encryption presents a way to achieve a desired level of security by using block ciphers of small key sizes. The idea is to cascade several stages of encryption and/or decryption, with different stages working under different keys. Figure A.1 illustrates double and triple encryption for a block cipher f. Each gi or hj represents either the encryption or the decryption function of f under the given key.
For double encryption, we have K1 ≠ K2 and both g1 and g2 are usually the encryption function. Unless fK2 ο fK1 is the same as fK for some key K and if the permutations of f are reasonably random, it appears at the first glance that double encryption increases the effective key size by a factor of two. Unfortunately, this is not the case. The meet-in-the-middle attack on double encryption works as follows.
Suppose that an adversary knows a plaintext–ciphertext pair (m, c) under the unknown keys K1, K2. We assume as before that f has block-size n and key-size r. The adversary computes for each possibility of the encrypted message xi := fi(m). She also computes for each the decrypted message . Now, (i, j) is a possible value of (K1, K2) if and only if .
A given pair (m, c) usually gives many such candidates (i, j) for (K1, K2). More precisely, if each is assumed to be a random permutation of , for a given i we have the equality for an expected number of 2r/2n values of j. Considering all possibilities for i gives an expected number of 2r × 2r/2n = 22r – n candidate pairs (i, j). If f = DES, this number is 22 × 56–64 = 248.
If a second pair (m′, c′) under (K1, K2) is also known to the adversary, then for a given i the pair (i, j) is consistent with both (m, c) and (m′, c′) with probability 2r/(2n × 2n). Thus, we get an expected number of (2r × 2r)/(2n × 2n) = 22r – 2n candidates (i, j). For DES, this number is 2–16. This implies that it is very unlikely that a false candidate (i, j) satisfies both (m, c) and (m′, c′). Thus, with high probability the adversary uniquely identifies the double DES key (K1, K2) from two plaintext–ciphertext pairs.
This attack calls for O(2r) encryptions and O(2r) decryptions. With the assumption that each encryption takes roughly the same time as each decryption (as in the case of DES), the adversary spends a time for O(2r) encryptions. Moreover, she can find all the matches in O(r2r) time. This implies that double encryption increases the effective key size (over single encryption) by a few bits only. On the other hand, both the actual key size and the encryption time get doubled. In view of these shortcomings, double encryption is rarely used in practice.
For the triple encryption scheme of Figure A.1, a meet-in-the-middle attack at x or y demands an effort equivalent to O(22r) encryptions, that is, the effective key size gets doubled. It is, therefore, customary to take K1 = K3 and K2 different from this common value. The actual key size also gets doubled with this choice—one doesn’t have to remember K3 separately. It is also a common practice to take h1 and h3 the encryption function (under K1 = K3) and h2 the decryption function (under K2). One often calls this particular triple encryption an E-D-E scheme.
In practice, the length of the message m to be encrypted need not equal the block length n of the block cipher f. One then has to break up m into blocks of some fixed length n′ ≤ n and encrypt each block using the block cipher. In order to make the length of m an integral multiple of n′, one may have to pad extra bits to m (say, zero bits at the end). It is often necessary to store the initial size of m in a separate block, say, after the last message block. In what follows, we shall assume that the input message m gives rise to l blocks m1, m2, . . . , ml each of size n′. The corresponding ciphertext blocks c1, c2, . . . , cl will also be of bit length n′ each. The reason for choosing the block size n′ ≤ n will be clear soon.
The easiest way to encrypt multiple blocks m1, . . . , ml is to take n′ = n and encrypt each block mi as ci := fK(mi). Decryption is analogous: . This mode of operation of a block cipher is called the electronic code-book or the ECB mode. Algorithms A.7 and A.8 describe this mode.
Input: The plaintext blocks m1, . . . , ml and the key K. Output: The ciphertext c = c1 . . . cl. Steps: for i = 1, . . . , l { ci := fK(mi) } |
Input: The ciphertext blocks c1, . . . , cl and the key K. Output: The plaintext m = m1 . . . ml. Steps: for |
In this mode, identical message blocks encrypt to identical ciphertext blocks (under the same key), that is, partial information about the plaintext may be leaked out. The following three modes overcome this problem.
In the cipher-block chaining or the CBC mode, one takes n′ = n and each plaintext block is first XOR-ed with the previous ciphertext block and then encrypted. In order to XOR the first plaintext block, one needs an n-bit initialization vector (IV). The IV need not be kept secret and may be sent along with the ciphertext blocks.
Input: The plaintext blocks m1, . . . , ml, the key K and the IV. Output: The ciphertext c = c1 . . . cl. Steps: c0 := IV. for i = 1, . . . , l { ci := fK(mi ⊕ ci – 1). } |
Input: The ciphertext blocks c1, . . . , cl, the key K and the IV. Output: The plaintext m = m1 . . . ml. Steps: c0 := IV. for |
In the cipher feedback or the CFB mode, one chooses . In this mode, the plaintext blocks are not encrypted, but masked by XOR-ing with a stream of random keys generated from a (not necessarily secret) n-bit IV. In this sense, the CFB mode works like a stream cipher (see Section A.3).
Algorithm A.11 explains CFB encryption. The notation msbk(z) (resp. lsbk(z)) stands for the most (resp. least) significant k bits of a bit string z. For CFB decryption (Algorithm A.12), the identical key stream k0, k1, . . . , kl is generated and used to mask off the message blocks from the ciphertext blocks.
The output feedback or the OFB mode also works like a stream cipher by masking the plaintext blocks using a stream of keys. The key stream in the OFB mode is generated by successively applying the block encryption function on an n-bit (not necessarily secret) IV. Here, one chooses any .
OFB encryption is explained in Algorithm A.13. OFB decryption (Algorithm A.14) is identical, with only the roles of m and c interchanged, and requires the generation of the same key stream k0, k1, . . . , kl used during encryption.
Input: The ciphertext blocks c1, . . . , cl, the key K and the IV. Output: The plaintext m = m1 . . . ml. Steps: k0 := IV. /* Initialize the key stream */ |
A.1 | Let us use the notations of Algorithm A.2. For a message m and round keys Ki, we have the values V, Li, Ri, W, c. For another message m′ and another set of round keys , let us denote these values by V′, , , W′, c′. Show that if m′ = c and if for i = 1, . . . , 16, then and for all i = 0, 1, . . . , 16. Deduce that in this case we have c′ = m. (This shows that DES decryption is the same as DES encryption with the key schedule reversed.) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.2 | For a bit string z, let denote the bit-wise complement of z. Deduce that , that is, complementing both the plaintext message and the key complements the ciphertext message. [H] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.3 | A DES key K is said to be weak, if the DES key schedule on K gives K1 = K2 = · · · = K16. Show that there are exactly four weak DES keys which in hexadecimal notation are:
0101 0101 0101 0101 FEFE FEFE FEFE FEFE 1F1F 1F1F 0E0E 0E0E E0E0 E0E0 F1F1 F1F1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.4 | A DES key K is said to be anti-palindromic, if the DES key schedule on K gives for all i = 1, . . . , 16. Show that the following four DES keys (in hexadecimal notation) are anti-palindromic:
01FE 01FE 01FE 01FE FE01 FE01 FE01 FE01 1FE0 1FE0 0EF1 0EF1 E01F E01F F10E F10E | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.5 | Represent , where f(X) = X8 + X4 + X3 + X + 1 (Section A.2.2).
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.6 | The multiplication of can be made table-driven. Since this field contains 256 elements, a 256 × 256 array suffices to store all the products. That requires a storage of 64 kb. We can considerably reduce the storage by using discrete logs.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.7 | Denote the multiplication of by ⊗ (Section A.2.2).
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.8 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.9 |
Algorithm A.15. Equivalent form of AES decryption
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.10 | Show that a multiple encryption scheme with exactly k stages provides an effective security of ⌈k/2⌉ keys against the meet-in-the-middle attack. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A.11 | Consider a message m broken into blocks m1, . . . , ml, encrypted to c1, . . . , cl and sent to an entity.
|
18.227.72.15