| [Page 165 (continued)] Simplified AES (S-AES) was developed by Professor Edward Schaefer of Santa Clara University and several of his students [MUSA03]. It is an educational rather than a secure encryption algorithm. It has similar properties and structure to AES with much smaller parameters. The reader might find it useful to work through an example by hand while following the discussion in this appendix. A good grasp of S-AES will make it easier for the student to appreciate the structure and workings of AES. Overview Figure 5.8 illustrates the overall structure of S-AES. The encryption algorithm takes a 16-bit block of plaintext as input and a 16-bit key and produces a 16-bit block of ciphertext as output. The S-AES decryption algorithm takes an 16-bit block of ciphertext and the same 16-bit key used to produce that ciphertext as input and produces the original 16-bit block of plaintext as output.
[Page 166] Figure 5.8. S-AES Encryption and Decryption (This item is displayed on page 165 in the print version) 
The encryption algorithm involves the use of four different functions, or transformations: add key (AK) nibble substitution (NS), shift row (SR), and mix column (MC), whose operation is explained subsequently. We can concisely express the encryption algorithm as a composition[7] of functions: [7] Definition: If f and g are two functions, then the function F with the equation y= F(x) = g[f(x)] is called the composition of f and g and is denoted as F = g º f.
AK2 º SR º NS º AK1 º MC º SR º NS º AK0 so that AK0 is applied first. The encryption algorithm is organized into three rounds. Round 0 is simply an add key round; round 1 is a full round of four functions; and round 2 contains only 3 functions. Each round includes the add key function, which makes use of 16 bits of key. The initial 16-bit key is expanded to 48 bits, so that each round uses a distinct 16-bit round key. Each function operates on a 16-bit state, treated as a 2 x 2 matrix of nibbles, where one nibble equals 4 bits. The initial value of the state matrix is the 16-bit plaintext; the state matrix is modified by each subsequent function in the encryption process, producing after the last function the 16-bit ciphertext. As Figure 5.9a shows, the ordering of nibbles within the matrix is by column. So, for example, the first eight bits of a 16-bit plaintext input to the encryption cipher occupy the first column of the matrix, and the second eight bits occupy the second column. The 16-bit key is similarly organized, but it is somewhat more convenient to view the key as two bytes rather than four nibbles (Figure 5.9b). The expanded key of 48 bits is treated as three round keys, whose bits are labeled as follows: K0 = k0...k15; K1 = k16...k31; K2 = k32...k47. Figure 5.9. S-AES Data Structures 
Figure 5.10 shows the essential elements of a full round of S-AES. Figure 5.10. S-AES Encryption Round (This item is displayed on page 167 in the print version) 
Decryption is also shown in Figure 5.8 and is essentially the reverse of encryption: AK0 º INS º ISR º IMC º AK1 º INS º ISR º AK2
[Page 168]in which three of the functions have a corresponding inverse function: inverse nibble substitution (INS), inverse shift row (ISR), and inverse mix column (IMC). S-AES Encryption and Decryption We now look at the individual functions that are part of the encryption algorithm. Add Key The add key function consists of the bitwise XOR of the 16-bit state matrix and the 16-bit round key. Figure 5.11 depicts this as a columnwise operation, but it can also be viewed as a nibble-wise or bitwise operation. The following is an example:  Figure 5.11. S-AES Transformations 
The inverse of the add key function is identical to the add key function, because the XOR operation is its own inverse.
[Page 169]Nibble Substitution The nibble substitution function is a simple table lookup (Figure 5.11). AES defines a 4 x 4 matrix of nibble values, called an S-box (Table 5.5a), that contains a permutation of all possible 4-bit values. Each individual nibble of the state matrix is mapped into a new nibble in the following way: The leftmost 2 bits of the nibble are used as a row value and the rightmost 2 bits are used as a column value. These row and column values serve as indexes into the S-box to select a unique 4-bit output value. For example, the hexadecimal value A references row 2, column 2 of the S-box, which contains the value 0. Accordingly, the value A is mapped into the value 0. Table 5.5. S-AES S-Boxes
Note: Hexadecimal numbers in shaded boxes; binary numbers in unshaded boxes. 
Here is an example of the nibble substitution transformation:  The inverse nibble substitution function makes use of the inverse S-box shown in Table 5.5b. Note, for example, that the input 0 produces the output A, and the input A to the S-box produces 0. Shift Row The shift row function performs a one-nibble circular shift of the second row of the state matrix; the first row is not altered (Figure 5.11). The following is an example:  The inverse shift row function is identical to the shift row function, because it shifts the second row back to its original position. Mix Column The mix column function operates on each column individually. Each nibble of a column is mapped into a new value that is a function of both nibbles in that column. The transformation can be defined by the following matrix multiplication on the state matrix (Figure 5.11): 
Performing the matrix multiplication, we get: S'0,0 = S0,0  (4 · S'1,0 = (4 · S0,0) S'0,1 = S0,1 (4 · S'1,1 = (4 · S0,1)
[Page 170]Where arithmetic is performed in GF(24), and the symbol · refers to multiplication in GF(24). Appendix E provides the addition and multiplication tables. The following is an example: 
The inverse mix column function is defined as follows: 
We demonstrate that we have indeed defined the inverse in the following fashion: 
The preceding matrix multiplication makes use of the following results in GF(24): 9 + (2 · 4) = 9 + 8 = 1; (9 · 4) + 2 = 2 + 2 = 0. These operations can be verified using the arithmetic tables in Appendix E or by polynomial arithmetic. The mix column function is the most difficult to visualize. Accordingly, we provide an additional perspective on it in Appendix E. Key Expansion For key expansion, the 16 bits of the initial key are grouped into a row of two 8-bit words. Figure 5.12 shows the expansion into 6 words, by the calculation of 4 new words from the initial 2 words. The algorithm is as follows: w2 = w0 w1) = w0 RCON(1)  SubNib(RotNib(w3 = w2 w4 = w2 w3) = w2 RCON(2) SubNib(RotNib(w5 = w4 Figure 5.12. S-AES Key Expansion (This item is displayed on page 171 in the print version) 
RCON is a round constant, defined as follows: RC[i] = xi + 2, so that RC[1] = x3 = 1000 and RC[2] = x4 mod (x4 + x + 1) = x + 1 = 0011. RC[i] forms the leftmost nibble of a byte, with the rightmost nibble being all zeros. Thus, RCON(1) = 10000000 and RCON(2) = 00110000. For example, suppose the key is 2D55 = 0010 1101 0101 0101 = w0w1. Then w2 = 00101101 10000000 SubNib(01010101) = 00101101 10000000 00010001 = 10111100 w3 = 10111100 01010101 = 11101001 w4 = 10111110 00110000 SubNib(10011110) = 10111100 00110000 00101111 = 10100011 w5 = 10100011 11101001 = 01001010 The S-Box The S-box is constructed as follows: Initialize the S-box with the nibble values in ascending sequence row by row. The first row contains the hexadecimal values 0, 1, 2, 3; the second row contains 4, 5, 6, 7; and so on. Thus, the value of the nibble at row i, column j is 4i + j.
[Page 171]Treat each nibble as an element of the finite field GF(24) modulo x4 +x + 1. Each nibble a0a1a2a3 represents a polynomial of degree 3. Map each byte in the S-box to its multiplicative inverse in the finite field GF(24) modulo x4 + x + 1; the value 0 is mapped to itself. Consider that each byte in the S-box consists of 4 bits labeled (b0, b1, b2, b3). Apply the following transformation to each bit of each byte in the S-box: The AES standard depicts this transformation in matrix form as follows: 
The prime (') indicates that the variable is to be updated by the value on the right. Remember that addition and multiplication are being calculated modulo 2.
[Page 172]Table 5.5a shows the resulting S-box. This is a nonlinear, invertible matrix. The inverse S-box is shown in Table 5.5b. S-AES Structure We can now examine several aspects of interest concerning the structure of AES. First, note that the encryption and decryption algorithms begin and end with the add key function. Any other function, at the beginning or end, is easily reversible without knowledge of the key and so would add no security but just a processing overhead. Thus, there is a round 0 consisting of only the add key function. The second point to note is that round 2 does not include the mix column function. The explanation for this in fact relates to a third observation, which is that although the decryption algorithm is the reverse of the encryption algorithm, as clearly seen in Figure 5.8, it does not follow the same sequence of functions. Thus Encryption: AK2 º SR º NS º AK1 º MC º SR º NS º AK0 Decryption: AK0 º INS º ISR º IMC º AK1 º INS º ISR º AK2 From an implementation point of view, it would be desirable to have the decryption function follow the same function sequence as encryption. This allows the decryption algorithm to be implemented in the same way as the encryption algorithm, creating opportunities for efficiency. Note that if we were able to interchange the second and third functions, the fourth and fifth functions, and the sixth and seventh functions in the decryption sequence, we would have the same structure as the encryption algorithm. Let's see if this is possible. First, consider the interchange of INS and ISR. Given a state N consisting of the nibbles (N0, N1, N2, N3) the transformation INS(ISR(N)) proceeds as follows: 
Where IS refers to the inverse S-Box. Reversing the operations, the transformation ISR(INS(N) proceeds as follows: 
which is the same result. Thus, INS(ISR(N)) = ISR(INS(N)). Now consider the operation of inverse mix column followed by add key: IMC(AK1(N)) where the round key K1 consists of the nibbles (k0,0, k1,0, k0,1, k1,1) Then: 
[Page 173]All of the above steps make use of the properties of finite field arithmetic. The result is that IMC(AK1(N)) = IMC(K1 IMC(K1) and the inverse add key operation IAK1 to be the bitwise XOR of the inverse round key with the state vector. Then we have IMC(AK1(N)) = IAK1(IMC(N)). As a result, we can write the following: Encryption: AK2 º SR º NS º AK1 º MC º SR º NS º AK0 Decryption: AK0 º INS º ISR º IMC º AK1 º INS º ISR º AK2 Decryption: AK0 º ISR º INS º AIMC(K1) º IMC º ISR º INS º AK2 Both encryption and decryption now follow the same sequence. Note that this derivation would not work as effectively if round 2 of the encryption algorithm included the MC function. In that case, we would have Encryption: AK2 º MC º SR º NS º AK1 º MC º SR º NS º AK0 Decryption: AK0 º INS º ISR º IMC º AK1 º INS º ISR º IMC º AK2 There is now no way to interchange pairs of operations in the decryption algorithm so as to achieve the same structure as the encryption algorithm. | 