Block Ciphers

A block cipher is an encryption scheme which converts the plaintext into chunks (or blocks) of a fixed length and encrypts each chunk individually.

Security in block ciphers is based upon a complex function with a short, fixed size key rather than a complex, changing key.

Basic building blocks

Block ciphers are generally created by composing a set of functions that produce transposition and substitution.

Transposition

Transposition simply moves symbols around inside the plaintext. A transposition-only cipher would contain all of the same symbols as the plaintext but in a different order. Transposition is useful as it provides diffusion in the encryption scheme. This means that underlying structures of the plaintext (English words for instance) are hidden by moving parts of the structure to different places.

Substitution

Substition turns symbols into different symbols in a reversible manner.

The most basic substitution is a mapping from your alphabet $A$ to a different alphabet $B$ (often $B$ is a permutation of $A$).

More complex substitutions will change a symbol to different symbols depending on other factors (such as the position of the symbol in the text or the symbol that was before it). Such substitutions are known as polyalphabetic because they convert from your alphabet $A$ to a set of alphabets $\{B_1, B_2, \cdots\}$.

Product Ciphers

Given reversible (bijective) ciphers (transposition and substitution) one can easily produce compound or product ciphers by simple function composition.

This works because the composition of two bijections is also a bijection.

If our encryption function $E_e$ is $$E1_e \cdot E2_e \cdot\ \cdots\ \cdot EN_e$$ then our decryption function $D_d$ is $$ EN_e^{-1} \cdot\ \cdots\ \cdot E2_e^{-1} \cdot E1_e^{-1} $$ where $\cdot$ represents function composition.

Block cipher modes

With a given block cipher with encryption function $E_k$ we can modify the encryption in various ways to improve security. These are known as modes.

Electronic Codebook Mode (ECB)

The most basic and obvious mode is to just use the function as-is; encryption of each block is independent of other blocks. Apparently it is insecure in obvious ways.

Cipherblock Chaining Mode (CBC)

Each plaintext block $x_j$ is XORed with the previous ciphertext before encryption. Requires an initialisation vector to act as the initial ciphertext.

$$c_j = E_k\left(x_j \oplus C_{j-1}\right)\ \ \ \ \ \ \ \ \ x_j = c_{j-1} \oplus E_k^{-1}\left(c_j\right)$$

where $\oplus$ means XOR, $c_j$ is the ciphertext for block $j$, and $x_j$ is the plaintext for block $j$.

Output Feedback Mode (OFB)

In OFB mode the encryption function is never applied directly to the plaintext; rather it is repeatedly applied to itself (with an initialisation vector) and the output of that is XORed with a block of plaintext.

This is a method for using a block cipher encryption function as the keystream generator for a Vernam Cipher.

$$c_j = x_j \oplus s_j\ \ \ \ \ \ \ \ s_j = E_k\left(s_{j-1}\right)$$

$$x_j = c_j \oplus s_j$$

where $s_j$ is the keystream at iteration $j$ (equivalent to block $j$)

It is important to note that $s_j$ is truncated to the leftmost bits. So if the length of the block is less than the length of the key then we will leave out bits in the keystream.

Cipher Feedback Mode (CFB)

Similarly to OFB: CFB uses the encryption function to generate a keystream for a Vernam Cipher.

It differs in that it uses ciphertext from the previous block as the input to the encryption function at each iteration, rather than the previous block of keystream.

$$c_j = x_j \oplus E_k\left(c_{j-1}\right)\ \ \ \ \ \ \ \ x_j = c_j \oplus E_k\left(c_{j-1}\right) $$

As with OFB, CFB will need an initialisation vector.

The Feistel Principle

The Feistel principle allows us to construct ciphers so that the same circuit is used for both encryption and decryption. Given an encryption function $E_k$ we construct a Feistel cipher by splitting the input into $L$ and $R$ (leftmost and rightmost bits). We then use the following iterative computations $n$ times (where $n$ is chosen):

$$ L_{i+1} = R_i\ \ \ \ \ \ \ \ R_{i+1} = L_i \oplus E_{K_i}\left(R_i\right) $$

Note that this will require $n$ keys.

The decryption operation is simply running through the encryption with the keys in reverse order, but is written in the slides as:

$$ R_i = L_{i+1}\ \ \ \ \ \ \ \ L_i = R_{i+1} \oplus E_{K_i}\left(L_{i+1}\right) $$

Back to Computer Security