Rinjdael

If I were asked to identify a common point between banking transactions, internet communication, and important documents, I would say it’s the need for confidentiality. Confidentiality means preventing unauthorized access to information. At the time of writing this post, the most widely used algorithms to ensure confidentiality are AES algorithms, also known as Rijndael. The goal of this blog post is to briefly cover everything you need to know when working with AES.

What is AES ?

Originally, AES which stands for Advanced Encryption Standard is a competition organized by the National Institute of Standards and Technology (NIST) in 1997. Te goal was to specify "an unclassified, publicly disclosed encryption algorithm capable of protecting sensitive government information well into the next century".

In 2000, NIST announced the Rijndael familly, a set of three 128-bit block cipher algorithms as the winner of the competion. In 2001, the NIST published FIPS 197 which standardized the Rijndael algorithms. FIPS 197 describe three symmetric bloch cipher algorithms : AES-128, AES-192 and AES-256.

The standardisation of AES algorithms marked the end of DES (Data Encryption Standard), the former world encryption standard. DES had become vulnerable to brute-force attacks as computers became increasingly powerful and efficient. At the time this blog was written, it is highly recommended to avoid using DES in software applications.

Who uses AES ?

As mentioned in previous sections, AES was designed to ensure confidentiality through secure data encryption in the fields of cybersecurity and cryptography. Confidentiality means ensuring that only authorized parties can access certain information.

Thanks to its strong security and high performance, AES is widely used across many areas of information processing. Here are some common use cases:

• Confidentiality of data in transit: AES is used in many TLS (Transport Layer Security) cipher suites to encrypt data transmitted over networks (e.g., HTTPS, VPNs, secure emails).

• Confidentiality of data at rest: AES is commonly used to encrypt stored data, such as files on disk, database entries, or full disk encryption (e.g., BitLocker, FileVault).

• Foundation for other cryptographic algorithms: AES also serves as the core in building other cryptographic tools. For example:

  • Authentication: AES is used in CMAC (Cipher-based Message Authentication Code) to ensure data integrity and authenticity.

  • AEAD modes: AES in GCM or CCM provides both encryption and authentication.

Security of AES

AES is a symmetric algorithm, meaning its security relies on a shared secret key between the parties involved in the communication. Therefore, the secret key must remain confidential. The key lengths are:

• 128 bits for AES-128

• 192 bits for AES-192

• 256 bits for AES-256

Generally, the longer the key, the more secure the algorithm.

One may ask: Does AES resist all kinds of cryptanalysis attacks? The answer is no, but in practice, many attacks are not feasible. Below are some of the most notable attacks against AES:

Brute Force Attacks

AES is theoretically vulnerable to brute-force attacks. However, current computers lack the speed and storage capacity to make these attacks practical. This type of attack can be improved using techniques like the Birthday attack, which involves randomly generating potential key candidates.

Biclique Attack

The biclique attack, inspired by the Meet-in-the-Middle (MITM) attack, is a cryptanalysis technique that slightly reduces the computational complexity of breaking AES compared to brute-force methods. It exploits structural symmetries in AES to analyze parts of the key schedule and encryption process more efficiently. However, the reduction in complexity is minimal, and the attack requires an enormous amount of storage for intermediate computations, making it impractical in real-world scenarios.

Quantum Computing

The potential development of quantum computers could threaten AES-128 and AES-192 by leveraging Grover's algorithm, which effectively reduces their key strengths by half. AES-256, however, is currently considered resistant to this kind of quantum attack as the post quantum security would be equivalent to the current AES-128.

Implementation Vulnerabilities

Some attacks target poor implementations of AES, rather than the algorithm itself. For instance, attackers may exploit information leaked through computation time or power consumption during AES operations. These are known as side-channel attacks. They don't compromise the mathematical integrity of AES but stem from mistakes made by developers implementing the algorithm in software or hardware.

Below I give a sum up about the efficiency of the attack we described.

Attack Type	Computational complexity	Feasibility	Notes
Classical computers brute force theoric	$O(2^{\|K\|})$	Impractical	Too slow with current hardware
Biclique attack	AES-128 : $O(2^{126.1})$ AES-192 : $O(2^{189.7})$ AES-1256 : $O(2^{254.4})$	Impractical	Only slight improvement over brute-force, high memory requirements
Quantum computers brute force theoritical (Grover)	$O(2^{\frac{\|K\|}{2}})$	Theoretical (future)	Affects AES-128 and AES-192 not AES-256
Side channel	$O(\|K\|)$	Depends on implementation	Exploits weaknesses in AES libraries or hardware

AES internals

AES is a PRP (Pseudorandom Permutation) function, which simply means that the output bits can be described as a unique permutation of the input bit positions. In other words, AES transforms plaintext into ciphertext in a way that appears random, but is actually deterministic when the key is known.

I’ll explain the internals of AES in the following paragraphs. I’ve also uploaded some example code on my my personal Github if you want to try AES while learning.

Let’s introduce some basic notation for clarity:

• $m$ is the 128 bits message to encrypt.

• $c$ is the encrypted form of $m$.

• $K$ is the secret key (16, 24 or 32 bytes long).

• $N$ is the number of rounds (10, 12, 14).

We denote:

$$m = \begin{bmatrix} m_0 & m_4 & m_8 & m_{12} \\ m_1 & m_5 & m_9 & m_{13} \\ m_2 & m_6 & m_{10} & m_{14} \\ m_3 & m_7 & m_{11} & m_{15} \end{bmatrix}$$

The encryption and decryption process in AES

An AES algorithm consists of a sequence of rounds. Each round represents a sub-encryption step in the overall encryption process. These sub-steps are designed to introduce confusion and diffusion, two essential properties in secure cryptographic systems.

Type	Block Size (bits)	Key Length (bits)	Number of Rounds (N)
AES-128	128	128	10
AES-192	128	192	12
AES-256	128	256	14

Each encryption round (except the last) is composed of the following functions:

1. AddRoundKey – XORs the current state with a portion of the expanded key

2. SubBytes – Applies a non-linear substitution to each byte using a fixed S-box

3. ShiftRows – Performs a cyclic shift of the rows in the state

4. MixColumns – Mixes the bytes in each column using a linear transformation

The first round only includes AddRoundKey, and the final round omits the MixColumns step.

The decryption process mirrors encryption but applies the inverse operations in reverse order (e.g., InvShiftRows, InvSubBytes, InvMixColumns, and AddRoundKey).

AddRoundKey

AddRoundKey is a XOR cipher function based on the secret round key. Is is equal to its reciprocal used in the deciphering process ($\oplus = \oplus^{-1}$).

SubBytes

SubBytes brings the confusion property. It guaranties that each byte is a non-linear and complex transformation of the input. For each byte $c$ :

$\text {SubByte}(c) = M \cdot c^{-1} \oplus v$

Where $M = \begin{bmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&1\\1&1&1&1&1&0&0&0\\0&1&1&1&1&1&0&0\\0&0&1&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{bmatrix}$

• $v = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \end{bmatrix} = 63_{16}$

• $c^{-1}$ is the multiplicative inverse of $c$ in the Rinjdael field ($GF(2^{8})/x^{8}+x^{4}+x^{3}+x+1$)

By reduction, $\text {SubByte}(c)=c^{-1}\oplus (c^{-1} \lll 1)\oplus (c^{-1}\lll 2)\oplus (c^{-1}\lll 3)\oplus (c^{-1}\lll 4)\oplus v$.

A look up table called the Sbox can be used to find the SubByte image of a byte.

ShiftRows

$$\text {ShiftRows}(m) = \begin{bmatrix} m_0 & m_4 & m_8 & m_{12} \\ m_5 & m_9 & m_{13}&m_1 \\ m_{10} & m_{14}&m_2 & m_6 \\ m_{15}&m_3 & m_7 & m_{11} \end{bmatrix}$$

MixColumns

$$\text {MixColumns}(m) = \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03&01 \\ 01 & 01&02 & 03 \\ 03&01& 02 & 02 \end{bmatrix}.m$$

ShiftRows and MixColumns are made such that every single byte is related to all the other bytes.

Due to confusion and diffusion, AES respect the Shannon conditions for devising a block cipher algorithm.

Key expansion

The key expansion or key scheduling is used to generate different keys for each round of AES. Each round key is derived from the previous round key using a series of transformations. Side channel attacks take advantage of this property to find the initial secret key. That is the reason why each round key should be keept secret.. The key expansion process ensures that each round key is unique and contributes to the overall security of the encryption process.

Key scheduling for AES-256

We denote:

• $N$ as the length of the key in 32-bit words

• $K_0, K_1, ... K_{N-1}$ as the 32-bit words of the original key

• $R$ as the number of round keys needed

• $W_0, W_1, ... W_{4R-1}$ as the 32-bit words of the expanded key

We define for $W = \begin{bmatrix} B_0 & B_1 & B_2 & B_3 \end{bmatrix}$a 32-bits word:

• $\text {RotWord}(W) = \begin{bmatrix}B_1 & B_2 & B_3 & B_0\end{bmatrix}$ a one byte circular shift;

• $\text {SubBytes}(W) =\begin{bmatrix}S(B_0) & S(B_1) & S(B_2) & S(B_3) \end{bmatrix}$ an SBox transformation to each of the 4 bytes of the word. These functions bring diffusion and confusion during the key expansion.

We also need to introduce the round constants denoted $rcon_i = \begin{bmatrix} (rc_i)_{16} & 00_{16} & 00_{16} & 00_{16} \end{bmatrix}$ for $i =1 ... Q$. $rcon_i$ is a 32-bits word. $rc_i$ is computed in the Rinjdael field ($GF(2^{8})/x^{8}+x^{4}+x^{3}+x+1)$

$$rc_{i}={\begin{cases}01_{16}&{\text{if }}i=1\\rc_{i-1}\ll 1&{\text{if }}i>1{\text{ and }}rc_{i-1}<80_{16}\\(rc_{i-1}\ll 1)\oplus {\text{11B}}_{16}&{\text{if }}i>1{\text{ and }}rc_{i-1}\geq 80_{16}\end{cases}}$$

$rcon_i$ is used to mask the original bits. This is a function similar to stream encryption.

Type	Number of words in key (N)	Number of round keys (R)	Number of $rc_i$ used (Q)
AES-128	4	11	10
AES-192	6	13	8
AES-256	8	15	7

$W_i$ is defined as :

$$W_{i}={\begin{cases}K_{i}&{\text{if }}i < N\\W_{i-N}\oplus \text {SubWord} (\text {RotWord} (W_{i-1}))\oplus rcon_{i/N}&{\text{if }}i\geq N{\text{ and }}i\equiv 0{\pmod {N}}\\W_{i-N}\oplus \text {SubWord} (W_{i-1})&{\text{if }}i\geq N{\text{, }}N > 6{\text{, and }}i\equiv 4{\pmod {N}}\\W_{i-N}\oplus W_{i-1}&{\text{otherwise.}}\\\end{cases}}$$

Data processing

AES is a 128-bit block cipher, which means it processes data in fixed-size blocks of 128 bits (16 bytes). As a consequence, the input data must be exactly 128 bits for a single call to the AES encryption function.

However, real-world data is rarely neatly sized to match block boundaries. To handle this, there are two main strategies:

• Padding: If the data is shorter than 128 bits, padding schemes (like PKCS#7) are used to fill the remaining bytes so the block is the correct size.

• Modes of operation: If the data is larger than 128 bits, AES is used in conjunction with a mode of operation (such as CBC, CTR, or GCM), which defines how to securely encrypt sequences of blocks.

Padding

Suppose we need to encrypt the message "DEADBEEF" (hex: 0x4445414442454546). This message is 64 bits long (8 bytes), which is smaller than the 128-bit block size required by AES. Without padding, we wouldn't be able to encrypt this message, as AES requires input data to match the block size exactly.

To make the message suitable for encryption, we must extend it by adding extra data : a process known as padding.

But how do we choose which bits to add? There are various padding schemes, each with different rules. One padding method is PKCS#7.

PKCS#7 works by adding n bytes to the end of the message, where n is the number of bytes needed to reach 16 bytes (128 bits). Each added byte has the value n. For example, if 8 bytes are missing, eight bytes of 0x08 will be appended.

Mode of operation

Modes of operation are essential when working with data larger than 128 bits, as they define how AES (a block cipher) should process multiple blocks of data securely.

There are two main categories of operation modes:

1. Non-authenticated modes – These modes only provide confidentiality, such as ECB (Electronic Codebook), CBC (Cipher Block Chaining), and CTR (Counter Mode).

2. AEAD (Authenticated Encryption with Associated Data) – These modes provide both confidentiality and integrity. Examples include GCM (Galois/Counter Mode) and CCM (Counter with CBC-MAC).

When evaluating a mode of operation, three key factors are considered:

• Resistance to cryptanalysis attacks – How well the mode defends against known vulnerabilities, such as replay attacks, chosen-plaintext attacks, or ciphertext manipulation.

• Parallelizability – Whether encryption and decryption can be performed in parallel, improving performance on modern multi-core systems.

• Implementation complexity – How easy or difficult it is to implement the mode correctly and securely in software or hardware.

Non authenticated mode of operation

These mode of operation can not guarantie authenticity of the encrypted data. They are a bunch of operation of this kind see illustration below.

Non authenticated mode of operation

Let's point out the specificity of ECB (Electronic Code Book). This is the most natural mode of operation. In this mode, the long message to encrypt (≥ 128 bits long) is divided into multiples of 128 bits using padding for the last block if necessary and then encrypted independently.

Advantages:

• Easy to compute

• parallelization is possible

• Decryption works the same as encryption

Drawbacks:

• Vulnerable to CPA (Chosen Plaintext Attack) due to the absence of an IV (Initialization Vector)

• Data integrity issues: no errors are detected during the decryption process, and each block is independent of the others.

Authenticated Mode of Encryption with Associated Data (AEAD)

AEAD modes provide both confidentiality and authenticity during encryption. In addition to encrypting the message, these modes generate an authentication tag that ensures the data has not been tampered with.

These modes can also protect associated data (like headers or metadata) that must remain unencrypted but still verified for authenticity.

Popular AEAD modes include:

• GCM (Galois/Counter Mode) – widely used in TLS and modern cryptographic libraries.

• CCM (Counter with CBC-MAC) – combines CTR mode for encryption and CBC-MAC for authentication.

• OCB (Offset Codebook Mode) – high-performance and secure, though patent-restricted in some regions.

AEAD modes are the recommended choice in most real-world applications where both encryption and integrity are required.

Mode	Comment	Known Vulnerability
AES-CCM	Complex and work in two pass.	Variable-Length Authentication Tags
AES-EAX	Designed as a replacement for AES-CCM.
AES-GCM	The nonce must not be reused.	Forbidden Attack
AES-GCM-SIV	A countermeasure against nonce reuse vulnerability of AES-GCM.
AES-OCB	Adoption has been slowered because the algorithm was patented.

Impementation optimization

Most of systems worldwide are design with hardware optimization to enhance so as to accelerate the processing time of AES. These are some specific instructions called AES-NI listed below.

Instruction	Description
AESENC	Perform one round of an AES encryption flow
AESENCLAST	Perform the last round of an AES encryption flow
AESDEC	Perform one round of an AES decryption flow
AESDECLAST	Perform the last round of an AES decryption flow
AESKEYGENASSIST	Assist in AES round key generation
AESIMC	Assist in AES decryption round key generation. Applies Inverse Mix Columns to round keys.

Wrapping Up

In this article, I set out to explore the essential aspects of AES, starting with its real-world applications and gradually delving into the technical considerations that arise when integrating AES into a cryptographic protocol. Throughout this journey, I’ve gained a deeper understanding of how AES works and why it remains a cornerstone of data security. I hope this article not only clarified key concepts but also sparked further interest in exploring the broader field of symmetric encryption. As we continue to build secure systems, understanding and correctly applying tools like AES will be critical to ensuring data protection in an increasingly connected world.