AES Round Steps

The AES algorithm encrypts data by executing 4 different operations; modifying gradually the state matrix until the ciphertext is obtained. The operations are: AddRoundKey, SubBytes, ShiftRows, MixColumns and an extra operation called the KeySchdule which is in charge to expand the original key for each AES round. This operations are going to be executed N times depending on the key length.

AddRoundKey: This transformation applies a bitwise XOR between the elements of the State array and the elements of the RoundKey. The RoundKey is obtained from the cipher key by computing the KeySchedule which will be explained later. The State and the RoundKey are of the same size where “a” is the current state, “k” the round key and “b” is the next state. AddRoundKey is denoted by:

SubBytes: This step provides non linearity byte substitution; it operates independently on each byte of the state matrix using a look up table, called the Rijndael S-box. The design ofthe S-box is thought to be resistant to attacks made by differential and linear cryptanalysis and algebraic manipulation, and has been extensively analyzed during the competition to verify its security. It is constructed by the following two transformations:

1. Compute the multiplicative inverse in the finite field GF(2^8)
2. Apply a bitwise affine transformation over GF(2), which is a polynomial multiplication by a constant matrix using the inversed byte, followed by a XOR operation with a constant byte

The constant matrix and the constant byte are provided by the AES Standard as described in FIPS 197. On image 2 we can see the constant matrix and the constant byte, where b0….b7 is the multiplicative inverse as a vector

After doing the previous steps we will obtain the Rijndael S-Box. Image 4 shows the S-Box generated; afterwards, each byte of the state table is updated. For example if state(i,j)={3D} the new value is determined by the intersection of the row with value 3 and the column with value D, providing an output of state'(i,j)=27.

ShiftRows: This operation shifts each row of the state cyclically to the left depending on the row index. First row is not shifted, second row is shifted one position, third row two positions and finally the fourth row is shifted three positions to the left.

MixColumns: The MixColumns step along with the ShiftRows step is the primary source of diffusion in AES. MixColumns performs a column by column transformation, treating each column of the state as polynomials over GF (2^8). Each polynomial or column is then multiplied with a fixed polynomial:

this latter polynomial is expressed as a fixed matrix, the operation can be written as matrix multiplication as follows:

Each column of the state is then multiplied by the fixed polynomial expressed as a matrix and and the next state is obtained

KeySchedule: The AES algorithm takes the cipher key and performs a key schedule also referred to as a key expansion to generate keys for each AES round. The number of round keys necessary to encrypt one block of information is related to the key length because this will determine the number of rounds. For example, a key length of 128 bits will require in total 11 round keys, 1 for the initial round, 9 for standard rounds and 1 for the final round. The key schedule is therefore a method to extend the cipher key, where it can be seen as an array of 32 bit columns numbered from 0 to 43. The i-th column of the cipher key k matrix is denoted by Wi. The first four columns are filled with the given cipher key

Columns in position that are multiple of 4 are calculated by:

• Applying a rotation operation and SubBytes transformation to the previous column W(i-1)
• Adding this result to the column 4 positions earlier W(i-4) plus a round constant Rcon.

The reminding 3 columns are calculated by adding the previous column W(i-1) with the column 4 positions earlier W(i-4)

Advanced Encryption Standard Algorithm

In the next days I will be writing about the AES algorithm, so I am going to start with a brief historical introduction and basic description of the algorithm before I move into more technical stuff.

In January 1997, the US National Institute for Standards and Technology (NIST) announced a competition to develop a new encryption algorithm to replace the old Data Encryption Standard DES. This latter algorithm was urged to be replaced due to computational power improvements making of DES a weak cipher. Some computers at the time were capable to break DES inspecting its key space of 2^56 keys by brute force.

The new encryption standard developed, was the Advanced Encryption Standard or AES becoming the United States encryption standard for sensitive information defined in Federal Information Processing Standard (FIPS 197). Unlike the design of DES, AES was designed as an open and public competition and many companies and researchers around the world participated in the contest . In total fifteen new algorithms were submitted and a second round narrow the choice to five of these. Among them was the Rijndael algorithm which in 2001 was announced to be the winner cipher. Rijndael was designed by two Belgium cryptographers; Joan Daemen and Vincent Rijmen from which the algorithm receives its name.

AES is a symmetric algorithm based on the original Rijndael algorithm. It encrypts in blocks of 128 bits of data called plaintext, and transforms it into an encrypted new block of the same length called ciphertext. The difference between Rijnadael and AES is that Rijndael encrypts blocks of data of 128, 192 and also 256 bits and AES only encrypts blocks of 128 bits. In order to encrypt AES makes usage of a key which is going to be secret and shared between the encryption/decryption parties. The key was designed to have sizes of 128-bits, 192-bits or 256-bits length.

Image taken from a very cool AES animation found in: http://www.formaestudio.com/rijndaelinspector

The algorithm performs a number of rounds transforming the plaintext depending on the key length. For example, when using a 128 bit key the algorithm executes 10 rounds, when using 192 bit keys 12 rounds and finally when using a 256 bit key 14 rounds are executed. Through the process the 128 bit block of plaintext will go to what we are going to call as the AES encryption process illustrated in the image above, and the key will go through a process called the KeyExpansion or sometimes referred to as the KeySchedule (Generate expanded keys for the different AES rounds). The 128 bit block of plaintext will be processed in an intermediate state which “can” be seen as a 4x4 matrix holding 16 bytes (is not always a real matrix and can be a vector).

If we look back to the AES process illustrated this refers particularly to AES-128 bit key which executes a total of 10 rounds. As we can see, AES consists of only 4 operations: SubBytes, ShiftRows, MixColumns and AddRoundKey. It is important to note that the very last round differs from the rest of rounds by skipping the MixColumns process. Before the plaintext is transformed to ciphertext it has to pass through all these operations transforming gradually the plaintext stored on the state matrix into encrypted text which will result into the final cipher text.

This is an introductory and general explanation of the AES algorithm. In future posts I will be explaining how the different AES operations work. However, if in the meantime you feel interested in getting to know more about the AES steps I really recommend checking out this AES encryption animation (http://www.formaestudio.com/rijndaelinspector) it gives a very simple understanding of how AES works without digging into complex mathemtical explanations. Though, if that is what you need “The Design of Rijndael” or the “AES specification” might be more useful.