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.