Discuss the four types of transformations used by AES?

In AES, all operations are performed on 8-bit bytes. In particular, the arithmetic

operations of addition, multiplication, and division are performed over the finite

field GF(28 ). Section 5.6 discusses such operations in some detail. For the reader

who has not studied Chapter 5, and as a quick review for those who have, this

section summarizes the important concepts.

 In essence, a field is a set in which we can do addition, subtraction, multiplication,

and division without leaving the set. Division is defined with the following

 rule: a /b = a (b-1 ). An example of a finite field (one with a finite number of elements)

is the set Zp  consisting of all the integers {0, 1, . . . . , p -  1}, where p is a prime number

and in which arithmetic is carried out modulo p .

  • In the Advanced Encryption Standard (AES) all operations are performed on 8-bit bytes
  • The arithmetic operations of addition, multiplication, and division are performed over the finite field GF(28)
  •  A field is a set in which we can do addition, subtraction, multiplication, and division without leaving the set (closure property)
  • Division is defined with the following  rule:
    •  a /b = a (b-1 )

f01.pdf

  • Figure shows the overall structure of the AES encryption process. 
  • The cipher takes a plaintext block size of 128 bits, or 16 bytes. 
  • The key length can be 16, 24, or 32 bytes (128, 192, or 256 bits). The algorithm is referred to as AES-128, AES-192, or AES-256, depending on the key length.

Input and state array

  • The input to the algorithms is a single 128-bit block.
  • In FIPS PUB 197, this block is depicted as a 4 * 4 square matrix of bytes. 
  • This block is copied into the State array, which is modified at each stage of encryption or decryption. 
  • After the final stage, State  is copied to an output matrix.

AES Key expansion

  •  the key is depicted as a square matrix of bytes, k0, k1, k2, …. k15. (or 4 words w0,w1,w2,w3, where w0=k0,k1,k2,k3  , w1=k4,k5,k6,k7   etc. one word=32 bits)
  • This key is then expanded into an array of key schedule words. 
  •  ie 4 original key words, expanded into 44 words.

f03.pdf

  •  Figure shows the AES cipher in more detail, indicating the sequence of transformations in each round and showing the corresponding decryption function. 
  • the encryption proceeds down the page and decryption proceed up the page.

 Figure 6.3 shows the AES cipher in more detail, indicating the sequence of transformations

in each round and showing the corresponding decryption function. As was

done in Chapter 4, we show encryption proceeding down the page and decryption

proceeding up the page.

Detailed Structure of AES

  • Processes the entire data block as a single matrix during each round using substitutions and permutation
  • The 128-bit (four 32-bit word) key that is provided as input is expanded into an array of forty-four 32-bit words, w[i] to be used in 11 rounds
  • At each round , it uses Four different stages:
    • Substitute bytes – uses an S-box to perform a byte-by-byte substitution of the block
    • ShiftRows – a simple permutation
    • MixColumns – a substitution that makes use of arithmetic over GF(28)
    • AddRoundKey – a simple bitwise XOR of the current block with a portion of the expanded key
  • The cipher begins and ends with an AddRoundKey stage
  • Can view the cipher as alternating operations of XOR encryption (AddRoundKey) of a block, followed by scrambling of the block (the other three stages), followed by XOR encryption, and so on
  • Each stage is easily reversible
  • The decryption algorithm makes use of the expanded key in reverse order, however the decryption algorithm is not identical to the encryption algorithm
  • State is the same for both encryption and decryption
  • Final round of both encryption and decryption consists of only three stages

1. AES SubBytes transformation

  • At each stage, a state consists of 16 bytes. 
  • Each of these bytes is substituted by another byte.
  • For this transformation either a Lookup table can be used (see next page)
  • Or using some arithmetic operations over GF(28) under modulo m(x)
    1. Finding inverse of the byte
    2. Multiply by a constant matrix
    3. Then add a column vector 

These are standard values. You need not By-heart these values. Consider each byte of input state is represented in hex format as xy; x defines the row number , y defines column number. The hex value at the intersection of x and y gives the substituted byte.  For eg the byte with value E6 is substituted by 8E.

  • Another Look up table is used  for the InvSubByte Transformation

 AES defines a 16 *  16 matrix of byte values, called an S-box (Table 6.2a), that contains

a permutation of all possible 256 8-bit values. Each individual byte of State

 is mapped into a new byte in the following way: The leftmost 4 bits of the byte

are used as a row value and the rightmost 4 bits are used as a column value.

These row and column values serve as indexes into the S-box to select a unique

8-bit output value. For example, the hexadecimal value {95} references row 9,

column 5 of the S-box, which contains the value {2A}. Accordingly, the value {95}

is mapped into the value {2A}.

The S-box for SubByte can be constructed in the following fashion also

  • First multiplicative Inverse of the byte value in GF(28) is found with modulus polynomial m(x) = x8 + x4 + x3 + x + 1
  • It is converted into column vector.
  • Then multiplied by a constant matrix, and added another constant 0110 0011
  • Resultant column vector is converted back to byte 
  • The SubByte transformation is non-linear, since finding the multiplicative inverse is nonlinear.
  • Right side shows inverse transformation

2. AES  ShiftRows Transformation

  • The first row of State is not altered. 
  • For the second row, a 1-byte circular left shift is performed. 
  • For the third row, a 2-byte circular left shift is performed. 
  • For the fourth row, a 3-byte circular left shift is performed. 

This transformation ensures that the 4 bytes of one column in a state are spread out to four different columns

3. AES  Mixcolumn Transformation

  • Each byte of a column is mapped into a new value that is a function of all four bytes in that column. 
  • It is achieved by multiplying the state by a constant matrix shown in fig.
  • This can be made more clear by the following matrix operation: (next slide..

  • The Byte S’0,0 is 2*S0,0 + 3*S1,0+ 1*S2,0 + 1*S3,0 ? a function of all four bytes in that column. 
  • The mix column transformation combined with the shift row transformation ensures that after a few rounds all output bits depend on all input bits -  which ensures better Diffusion              

4. AES  AddRoundKey Transformation

  • Here the 128 bits of State are bitwise XORed with the 128 bits of the round key. 
  • The add round key transformation is as simple as possible, but affects every bit of State
  • The complexity of the round key expansion, plus the complexity of the other stages of AES, ensure security.
  • The key expansion algorithm (where 44 words are derived from the initial 4 word key),  is resistant to known cryptanalytic attacks. 
  • The inclusion of a round-dependent round constant eliminates the similarity between the ways in which round keys are generated in different rounds. Other criteria are:
    • Knowledge of a part of the cipher key or round key does not enable calculation of other round-key bits.
    • Speed on a wide range of processors.
    • Diffusion of cipher key differences into the round keys; that is, each key bit affects many round key bits.

Leave a reply