8 DES (Data encryption standard) and AES (Advanced encryption standard) ----------------------------------------------------------------------- The Data Encryption Standard (DES) was published 1975 by the US-administration after public consultation. It was designed and used as a standard for non-military secrte communication e.g. between government bodies but also in the private sector. It is a 16-round Feistel network of message length 64 and key length 56. Mainly due to its relatively short key length it is no longer considered secure. It is nevertheless still widely used in legacy applications and in the form of three-fold repetition (3DES) which is considered secure but somewhat inefficient. The Feistel mixing function of DES uses a round key k_i of length 48 which is applied to a 32 bit long half block as follows: 1) The 32 bit half block is expanded to 48 bit by repeating half of its bits using an expansion function E() (see table below) 2) The round key is XOR-ed with the resulting block 3) The result is divided into eight 6-bit blocks to which S-boxes S_1..S_8 are applied (see table below). Each S-box has 6 inputs and 4 outputs, so a 32bit block results. 4) a mixing permutation P is applied to the resulting 32bit. The DES key schedule is as follows: initially the master key is subjected to a mixing permutation on 56 bits. Thereafter, the round key for the each round is applied by extracting (in a round-dependent fashion) 48 bits from these 56 bits in such a way that the first 24 bits stem from the first half of the (permuted) key and the second 24 bits from the second half. See below for the exact form of the bit extraction functions. The DES encryption function is now obtained by enclosing the 16-round Feistel network FN_k described above by an initial permutation IP and its inverse listed below, thus Enc_k(x) = IP^{-1}(FN_k(IP(x))). The initial permutation has no influence on security. It is there only for historical reasons having to do with 8-bit hardware. Each S-Box can be regarded as a package consisting of four *invertible* operations on size 4 bitstrings. In conjunction with the expansion function they operate as follows: The current size 32 bitstring is divided into 8 blocks of size 4. To the ith such block the ith S-box (eight in total) is applied in the following way: first the two neighbouring bits (modulo 32) are taken, e.g. for the block comprising bits 5,6,7,8 these neighbouring bits are 4 and 9. For the first block comprising bits 1,2,3,4 the neighbouring bits are 32 and 5. These two bits then are used to select the invertible substitution to be applied to the block. This intuition is reflected in the tabulation of the S-boxes below as binary functions of the central size four block and the neighbouring two bits. Also, the expansion function E() is designed to implement this idea, i.e. it duplicates the "neighbouring bits. " DES supplementary material - - - - - - - - - - - - - Initial permutation: The first bit of IP(x) is the 58th bit of x; the second bit of IP(x) is the 50th bit of x etc (read left to right and top to bottom). 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 Expansion function: to be read left to right, top to bottom. First bit of E(x) is the 32th, i.e. last, bit of x. 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 Mixing permutation 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 The S-boxes given as binary functions: S_1: to be applied to the first block E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7 0 F 7 4 E 2 D 1 A 6 C B 9 5 3 8 4 1 E 8 D 6 2 B F C 9 7 3 A 5 0 F C 8 2 4 9 1 7 5 B 3 E A 0 6 D This is to be read as follows: upon receiving a 6bit block the S-box uses the outer 2 bits to select the row and the inner four bits (read in decimal). The decimal number found there represents the output. For example, on input 011011 we select row #1 (0xxxx1) and the column #13 (x1101x) (counting from 0 each time). There we find (hexa)decimal number 5 representing output 0101. Similarly, on input 101000 we select row #2, column #4, finding D=13, hence outputting 1101. For the remaining S-boxes S_2,...,S_8 we refer to the Internet. Initial mixing function selecting 56 out of 64 bits. The remaining 8 bits serve as parity bits (each of the eight bytes comprising the key must have even parity). Does not have any influence on security. 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 The ith round key is obtained from the 56bit key by rotating both halves i bits to the left and then selecting 48 bits with the following function. 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 Discussion of DES - - - - - - - - - The S-boxes have the important property that changing one bit of the input always changes two bits of the output. For example, the first row of S_4 maps 7=0111 to 10=1010. The 1bit alterations of 7 are 15=1111, 3=0011, 5=0101, 6=0110. These are mapped to 15=1111, 3=0011, 6=0110, 9=1001. All of these differ from 10=1010 in two bits. Furthermore, the mixing permutation is such that any two bits from the same 4 bit block end up in *different* 4 bit blocks where they will cause more bit differences and so on thus ensuring the desired avalanche effect. Purportedly, the S-boxes have been designed so as to withstand a particular attack called *differential cryptanalysis* which was known to the developers but not published. Only 15 years later was this discovered again and published by Biham and Shamir. The text KL contains some more detail about attacks on variants of DES with fewer rounds which exploit the fact that the avalanche effect has not fully unfolded then. With today's technology the 2^56 keyspace can be completely searched with special hardware in several hours so that DES is no longer secure for critical applications. There is a variant 3DES (Triple DES) which uses three DES keys k1,k2,k3 (hence has key size 168) and encrypts according to the formula Enc^3DES_{(k1,k2,k3)}(m) = Enc^DES_k3(Dec^DES_k2(Enc^DES_k1(m))) Thus, to encrypt a message we encrypt it (using DES) with key k1 then decrypt it with key k2 and then encrypt it with key k3. The fact that we use decryption rather than encryption in the second phase ensures that standard DES arises as the special case of three identical keys: Enc^3DES_{(k,k,k)}(m) = Enc^DES_k(m) A version with just two phases does not provide the desired increased security due to the possibility of a meet-in-the-middle attack: suppose we (temprorarily) define 2DES by Enc^2DES_{(k1,k2)}(m) = Enc^DES_k2(Enc^DES_k1(m)) Then given a pair (m,c) where c=Enc^2DES_{(k1,k2)}(m) we can recover k1 and k2 in time ~2^56 as follows: Define x_k = Dec^DES_k(c) and y_q = Enc^DES_q(m) and tabulate x_k and y_q for any DES keys k and q. This takes 2*2^56 DES operations (and also requires this much space to store the tables). One can then sort the tables and in this way quickly find k,q so that x_k=y_q. This pair then is the desired 2DES key. One can also use this attack against 3DES (splitting either after the third or after the second phase) which reduces the effective key size to 112. It is not clear whether "meet-in-the-middle" is really practical because, at least when implemented naively, the storage requirements for the tables exceed current technology. Advanced Encryption Standard (AES) - - - - - - - - - - - - - - - - - - The AES which was selected by the US administration (NIST) from submissions to a public competition in 2000 is an S/P-network with block size 128bit and key sizes of 128, 192, or 256 bit (AES-128, AES-192, AES-256). AES-128 being the most popular variant we will only describe this one here. The original name of the cipher prior to being selected as the AES was "Rijndael" (Dutch for Rhine Valley) and chosen by its Belgian authors Joan Daemen and Vincent Rijmen. The substitution operation applies a fixed invertible function (the AES S-box) on size-8 bitstrings (bytes) to each of the 16 bytes of the text. The subsequent mixing step is in the case of AES not just a bit permutation but in fact an invertible linear transformation. AES operates on the byte level and the text is arranged into a 4x4 matrix whose entries are bytes (4x4x8=128). The bytes are mostly understood as elements of the 256-element field GF(256). Thus, there is also a multiplication operation b*b' on bytes which together with the XOR-operation (bitwise addition mod2) endows the bytes with the structure of a field. In particular, each byte b:{00,...,FF} (one adopts hexadecimal notation) except 00 has an inverse b^{-1} such that b^{-1} * b = 1. Caveat: this multiplication is not multiplication of binary numbers mod 256. We describe below how it is defined in detail. For now it suffices to know that together with addition (XOR) it satisfies the usual algebraic laws (commutativity, associativity, distributivity, inverse). Now, each round comprises the following four steps: 1. AddRoundKey(): Addition mod2 of the 128 bit round key derived from the master key according to the key schedule. Can be viewed as the addition of a "round key matrix". 2. SubBytes(): Application of the S-Box to each of the 16 bytes of the text. First, each of the 16 bytes comprising the current text matrix is replaced with its inverse in GF(256). Exception: 00 for which there is no inverse is left alone (not replaced). Thereafter, each byte is transformed by the following affine map: (b_7') (1 1 1 1 1 0 0 0) (b_7) (0) (b_6') (0 1 1 1 1 1 0 0) (b_6) (1) (b_5') (0 0 1 1 1 1 1 0) (b_5) (1) (b_4') = (0 0 0 1 1 1 1 1) (b_4) + (0) (b_3') (1 0 0 0 1 1 1 1) (b_3) (0) (b_2') (1 1 0 0 0 1 1 1) (b_2) (0) (b_1') (1 1 1 0 0 0 1 1) (b_1) (1) (b_0') (1 1 1 1 0 0 0 1) (b_0) (1) These matrix and vector operations are understood in GF(2), ie. addition is (as usual) XOR of bits whereas multiplication is logical AND. The purpose of the inversion part is to introduce a high degree of nonlinearity, i.e. to not even be close to a linear function. The purpose of the affine transformation (which is linear) is to introduce a certain amount of diffusion, i.e. that changes in one bit in the input of the S-box result in >1 bit changes at the output. The affine transformation also ensures that not the entire operation of AES can be regarded in terms of GF(256) which could possibly result in vulnerabilities based on algebraic properties. Usually, the entire S-box is implemented as a 256 byte lookup table. 3. ShiftRows(): The ith row is (cyclically) shifted i-1 columns to the left (i=1,2,3,4): (a b c d) (a b c d) (A B C D) |-> (B C D A) (u v w x) (w x u v) (U V W X) (X U V W) 4. MixColumns(): The 4x4 text matrix is multiplied (from the left) by the (invertible) matrix (02 03 01 01) (01 02 03 01) (01 01 02 03) (03 01 01 02) The entries of this matrix are understood as hexadecimal notation for bytes, e.g.03 stands for the element 00000011 of GF(256). Thus, we have 02+01=03 but 01+01=00 and 02+03=01. In the last (16th) round, MixColumns() is replaced with another AddRoundKey(). Notice that---as pointed out earlier---key-independent steps at either the beginning or the end of the cipher could be easily undone by an attacker and thus are worthless. The AES key schedule thus must transform the 128bit master key into 17 equally sized round keys. Let k be the 128bit master key. Just as the texts we view it as a 4x4 matrix with entries from GF(256). We now generate a sequence k_0,...,k_{16} of round keys (17 in number) as follows: k_0 = k (01 01 01 01) k_{i} = (k_{i-1} + (c'|0|0|0)) (00 01 01 01) (00 00 01 01) (00 00 00 01) \______ ______/ V M where the column c' is obtained from the last column c of k_{i-1} as follows: (00 00 00 01) (02^i) c' := (01 00 00 00) SubBytes(c) + ( 00 ) (00 01 00 00) ( 00 ) (00 00 01 00) ( 00 ) \______ _____/ V R Here SubBytes(c) denotes the result of the application of the AES S-box to each byte in the column c. The byte 02^i is 02*02*...*02 (i times) in GF(256). The matrix R cyclically rotates the column downwards. To then obtain k_i we add c' to the first column of k_{i-1} to obtain the first column of k_i. The next three columns are obtained by adding the previous one (of k_i) to the corresponding one of k_{i-1}. The matrix M does just that. We see that the next round key is obtained from the previous one by some simple linear operations and one nonlinear function of the last column. Decryption: We notice that all the functions used are invertible so the decryption just performs these inverse operations in the opposite order. We omit the details. Arithmetic in GF(256) - - - - - - - - - - - In order to understand how multiplication in GF(256) works one represents a byte b=b0..b7 as a polynomial with coefficients in GF(2)={0,1} b(X) = b7 * X^7 + b6 * X^6 + ... + b1 * X + b0 In order to multiply two bytes one multiplies them qua polynomials and then takes the remainder (using polynomial division) modulo the polynomial p(X) = X^8 + X^4 + X^3 + X + 1 For example, 03 is X+1, so 03*03 = X^2+1 = 05 (the coefficients are calculated modulo 2). The inverse of 03 is F6=11111010 because (X^7+X^6+X^5+X^4+X^2+X)*(X+1) = X^8+X^7+X^6+X^5+X^3+X^2+X^7+X^6+X^5+X^4+X^2+X = \___________ _________/ \_ _/ = X^8+X^4+X^3+X = 1 (mod p) V V F6 03 One finds such inverses using the extended Euclidean algorithm or using a table of logarithms. Indeed, each element of GF(256) \ {0} can be written as a power of 03 (some other elements can be used in place of 03). One may write log(x) for the number t:{0..254} such that x = 03^t. One then has x^{-1} = 03^{255-t}. The logarithms can also be used to reduce multiplication to addition mod 255.