# 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](https://competitions.cr.yp.to/aes.html) is a competition organized by the [National Institute of Standards and Technology (NIST)](https://www.nist.gov/) 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**](https://www.nist.gov/publications/advanced-encryption-standard-aes-0) 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)](https://csrc.nist.gov/files/pubs/fips/46-3/final/docs/fips46-3.pdf), 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**](https://eprint.iacr.org/2022/053) 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](https://en.wikipedia.org/wiki/Birthday_attack), which involves randomly generating potential key candidates. ### [**Biclique Attack**](https://eprint.iacr.org/2011/449.pdf) 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**](https://www.polytechnique-insights.com/tribunes/science/lordinateur-quantique-tout-comprendre-en-15-minutes/) The potential development of **quantum computers** could threaten AES-128 and AES-192 by leveraging [Grover's algorithm](https://blog.cr.yp.to/20171017-collisions.html), 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**](https://en.wikipedia.org/wiki/Side-channel_attack) 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 TypeComputational complexityFeasibility Notes
Classical computers brute force theoricO(2^{\|K\|})ImpracticalToo slow with current hardware
Biclique attackAES-128 : O(2^{126.1})
AES-192 : O(2^{189.7})
AES-1256 : O(2^{254.4})		ImpracticalOnly 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 channelO(\|K\|)Depends on implementationExploits weaknesses in AES libraries or hardware
## AES internals AES is a [PRP (Pseudorandom Permutation)](https://en.wikipedia.org/wiki/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 ](https://github.com/kmanu225/cryptoword/tree/main/algorithms/modern/rijndael)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](https://en.wikipedia.org/wiki/Rijndael_S-box) 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](https://www.iacr.org/museum/shannon45.html) 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](https://datatracker.ietf.org/doc/html/rfc5652#section-6.3). **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](https://www.di.ens.fr/~fouque/pub/acns08.pdf) | Complex and work in two pass. | [Variable-Length Authentication Tags](https://csrc.nist.gov/csrc/media/projects/block-cipher-techniques/documents/bcm/comments/800-38-series-drafts/ccm/rw_ccm_comments.pdf) | | [AES-EAX](https://en.wikipedia.org/wiki/EAX_mode) | Designed as a replacement for AES-CCM. | | | [AES-GCM](https://en.wikipedia.org/wiki/Galois/Counter_Mode) | The nonce must not be reused. | [Forbidden Attack](https://eprint.iacr.org/2016/475.pdf) | | [AES-GCM-SIV](https://en.wikipedia.org/wiki/AES-GCM-SIV) | A countermeasure against nonce reuse vulnerability of AES-GCM. | | | [AES-OCB](https://www.cs.ucdavis.edu/~rogaway/ocb/index.html) | 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](https://en.wikipedia.org/wiki/AES_instruction_set) 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.