Encrypting with Block Ciphers: A Guide to AES, CBC, and More

_In today's digital world, block ciphers are fundamental to online encryption. They handle most of the encryption on the internet, securing our communications and data. In this blog post, we'll explore the key aspects of block ciphers, delve into popular modes of operation, and take a closer look at the Advanced Encryption Standard (AES).

What Are Block Ciphers?

Block ciphers are the workhorse of encryption on the internet today. They handle the bulk of the encryption that is done over the internet. Block ciphers encrypt a fixed length chunk of bits called a block where each block is encrypted separately.

Block ciphers are made up by a family of three functions and are specified as follows:

1. A keygen function that accepts a security parameter 𝑘 and outputs a random 𝑘-bit key:
   𝑘→{0,1}𝑘

2. An encryption that accepts a 𝑏-bit plaintext and 𝑘-bit key and outputs a 𝑏-bit ciphertext:
   {0,1}𝑏×{0,1}𝑘→{0,1}𝑏

3. A decryption that accepts a 𝑏-bit ciphertext and 𝑘-bit key and outputs a 𝑏-bit plaintext:
   {0,1}𝑏×{0,1}𝑘→{0,1}𝑏

An important parameter in block ciphers is the block length 𝑏. It determines how large of chunks the overall ciphertext and plaintext will be parsed into.

An ideal block cipher requires the encryption to be injective and surjective (bijective). This means that each plaintext maps to a unique ciphertext and each ciphertext maps to a unique plaintext. This creates an encryption method that essentially just creates a permutation (shuffle) of 𝑏-bit strings.

If we have a 𝑏-bit block, there are 2𝑏 possible input plaintext messages and 2𝑏 possible output ciphertext messages. There are also 2𝑏! Permutations of 2𝑏 elements. If the key used is 𝑘-bits, then there are 2𝑘 possible key values, and each key “chooses” some permutation from the permutation space. 2𝑘 is often much smaller than 2𝑏! So there’s usually a large number of permutations that aren’t possible for a cipher.

A block cipher can be thought of as a large collection of codebooks. A codebook is a book with a list of plaintext elements on one side and a list of associated ciphertext elements on the other. The key is simply used to choose which book to use.

Modes of Operation

A modern block cipher typically encrypts 16 bits at a time, so to encrypt a large plaintext, it must first be parsed into smaller blocks. The mode of operation defines the method used to combine a block cipher and encrypt a large block of data.

Electronic Codebook Mode (ECB)

The simplest mode of operation is the electronic codebook mode (ECB). It takes the plaintext, divides it into individual 𝑏-bit blocks, and encrypts each one separately using the same key.
A 16-bit data block using an 8-bit block cipher will first be divided into 2 blocks, encrypted, each with the same key, and then recombined to create a 16-bit ciphertext.

If using a block size of 128 bits, then the codebook would have 2128 entries and be so large that you could never write it down on paper.

A limitation of this mode of operation is that on a long block of repeated data, patterns will start to emerge, revealing information about both the key and the plaintext. This mode of operation is not secure under eavesdropping (IND-EAV).

Cipher Block Chaining (CBC)

The idea of cipher block chaining (CBC) mode is to exclusive or (XOR) the plaintext of every block with the ciphertext of the previous block. This combined value is the data that is then put into the encryption function.

Using this mode of operation, even large blocks of structured data lose their structure due to the feed-forward nature of the encryption mode.

Since the first block of plaintext has no previous block of ciphertext to use, an initialization vector (IV) is used to get things going.

Due to the symmetry of the XOR operation, when decrypting, you can follow the same path as encryption, just in reverse. Note that only the vertical arrows reverse direction in the diagrams to the left, as the previous ciphertext block is still used to decrypt the plaintext following it.

An essential property of the mode of operation is that it easily allows for randomized encryption. Different IVs produce different ciphertexts on the same plaintext, and this property can be used to protect the encryption method from chosen plaintext attacks.
Note that the IV is not a secret, is sent along with the ciphertext, can only be used once, and must not be predictable.

Counter Mode (CTR)

Counter mode (CTR) is different from CBC mode as you never actually put the plaintext through the encryption function. Instead, you encrypt a counter, and XOR the result with the plaintext.
When encrypting using CTR mode, the first IV is decided upon, and then the subsequent IVs simply increment by 1. So, in an example where the IV is 2 bits, the first block might be 00, the next 01, and so on….

Decryption is the exact same as encryption, on the inputs to the XOR function are reversed. Notice that decryption involves the encryption method of the block cipher.
This model is not vulnerable to padding oracle attacks, has a simple implementation, and the computation is parallelizable, pre-processable, and random access. However, this mode is not safe for small block lengths (<128-bits).

Advanced Encryption Standard (AES)

Advanced encryption standard (AES) is the most commonly used block cipher on the internet today. At a high level, the AES cipher uses a 128-bit block. This means it takes 128 bits of plaintext and produces 128 bits of ciphertext. The key can either be 128-bits, 192-bits, or 256-bits. The plaintext is combined with the key through multiple passes of a round.

Each stage has identical rounds. The key is changed at every round using a key schedule, which creates different sub-keys for each round.

AES uses 2 types of operations:

1. Operations that act on bytes (8-bits)

2. Operations that act on bits

The first operation is called SubBytes and is a bytewise substitution. A byte has 256 substitution possibilities so the substition lookup table (s-box) has 256 entries. There are 256! potential s-boxes that can be created, but instead of choosing a random permutation, AES designers chose an algebraic relationship. The output byte is the algebraic inverse of the input byte in what’s called a galwa field, and for good measure a constant value is added.

S-boxes are designed to be highly non-linear. The idea is that a small change in the input to induce a large change in the output.

The next step in AES is called shiftRows where all 16-bytes are arranged as a 4x4 square and a circular shift is applied. The top row is unchanged, the second row is shifted by 1 byte, the third row is shifted by 2 bytes, and the final row is shifted by 3 bytes.

The third operation is called MixColumns and applies galwa field arithmetic again, but this time using matrix multiplication. Instead of applying the changes to the rows, they’re applied to the columns. This is designed to create a property called diffusion. The goal is for the variables that appear in the equation to spread out.

In the last step, called AddRoundKey, the round-specific sub-key is XORed with all bits from the previous step. The output of the process is fed into the input of the next round, and the process continues.
For most people, AES can be treated like a black box. What matters most is not how it works but that a random secret key is generated when using it, the mode of operation is safe and randomized, and the initialization vector is unpredictable.

Overall, Block ciphers are vital for internet security, underpinning our communications and data protection. With various modes of operation, such as ECB, CBC, and CTR, and the robust AES algorithm, we have powerful tools to secure information. It's crucial to understand these encryption methods, as they are key to maintaining privacy and security in the digital age.