Modes of Operation

After explaining the basis of how the AES block cipher works now we’re moving into modes of operations. Basically, a block cipher by itself allows encrypting only a data block of the cipher's block length (in AES 128 bits). Although it might happen that the plaintext to be encrypted has exactly 128 bits, this is not always the case and the plaintext normally exceeds by far 128 bits. As plaintexts can be of any length they have to be broken into blocks before the encryption process takes place.

The National Institute for Standards and Technology has defined five confidentiality modes of operation for the AES block cipher, with different characteristics. The modes of operation defined for AES are ECB (Electronic Code Book), CBC (Cipher Block Chaining), CFB (Cipher FeedBack), OFB (Output FeedBack), and CTR (Counter).

Since the idea of these posts is to demonstrate the benefits of running AES in parallel I will explain only ECB and CTR modes of operations, which are the ones that might benefit the most when running in parallel due to the lack of dependencies between the data blocks they encrypt; being like that ideal candidates to be implemented on parallel processors such as a Graphic Processing Unit or GPU (we’ll come back to that later..).

Electronic Code Book

ECB is one of the simplest modes of operations. To encrypt a plaintext the forward AES cipher function is applied. The plaintext is divided into blocks each of which is, encrypted independently using a key. In ECB decryption, the inverse cipher function is as well applied directly and independently to each block of ciphertext.

One important consideration is the fact that in ECB if a similar data pattern exists and the same key is used, then the plain text will generate the same cipher text (as would happen when enciphering a file with repeated 16 bytes blocks), which is a major leak of secret information and can be exploited by cryptanalytic attacks. In the next picture it can be seen the pattern that ECB exposes when encrypting an image, this was mainly the reason why other modes of operation were designed, among them CTR. If this property is not desired, this mode of operation should not be considered.

Counter CTR

One way to hide data patterns is to provide some randomization for each block. All the modes of operation apart from ECB require an initialization vector (IV). The IV is used to provide a unique cipher text if the same key is re-used. In CTR a set of input blocks called counters are encrypted using the key, producing output blocks called keystreams, which are used to perform an XOR operation with the plaintext blocks. The sequence of counters must have the property that each block in the sequence is different than the rest, in other words all counters must be distinct. In CTR encryption, the block cipher encryption function is called on each counter block. Afterwards, the resulting output is XORed with the respective plaintext block to generate the ciphertext. While decrypting, the block cipher encryption function is invoked on each counter block. The resulting output will be then XORed with the respective ciphertext block in order to recover the plaintext block.

Summary

In these first three posts I cover the very basis of AES and modes of operations, which for our purposes are going to be enough to start with our first coding examples. Let’s make a small review!!

A brief historical remark about the Advanced Encryption Standard, followed by an overview of its functionality was provided. It was explained how input data is mapped to an intermediate matrix called the state in where all AES operations are going to take place; as well as how the state maps to the output array. The four steps contained on the AES rounds: AddRoundKey, SubBytes, ShiftRows and MixColumns were explained. The amount of rounds strongly depends on the key length and in order to compute them it is necessary to expand the key; the process of expanding the key was exemplified as well. Moreover, modes of encryption were introduced and two parallel in nature modes of operations named ECB and CTR were covered.

The first AES examples I will be presenting soon are going to run on the CPU; we’re going to create a C program that makes usage of the OpenSSL library which is the most common used cryptographic framework. The idea is to create a (hopefully short!) tutorial of how to implement AES using OpenSSL which it is kind of painful due to the lack of documentation on the web.

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.