Iterated block ciphers

Most block cipher algorithms are classified as iterated block ciphers which means that they transform fixed-size blocks of plaintext into identically sized blocks of ciphertext, via the repeated application of an invertible transformation known as the round function, with each iteration referred to as a round.^[12]

Usually, the round function R takes different round keys K_i as a second input, which is derived from the original key:

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})}$

where ${\displaystyle M_{0}}$ is the plaintext and ${\displaystyle M_{r}}$ the ciphertext, with r being the number of rounds.

Frequently, key whitening is used in addition to this. At the beginning and the end, the data is modified with key material (often with XOR, but simple arithmetic operations like adding and subtracting are also used):

${\displaystyle M_{0}=M\oplus K_{0}}$

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})\;;\;i=1\dots r}$

${\displaystyle C=M_{r}\oplus K_{r+1}}$

Given one of the standard iterated block cipher design schemes, it is fairly easy to construct a block cipher that is cryptographically secure, simply by using a large number of rounds. However, this will make the cipher inefficient. Thus, efficiency is the most important additional design criterion for professional ciphers. Further, a good block cipher is designed to avoid side-channel attacks, such as branch prediction and input-dependent memory accesses that might leak secret data via the cache state or the execution time. In addition, the cipher should be concise, for small hardware and software implementations. Finally, the cipher should be easily crypt analyzable, such that it can be shown how many rounds the cipher needs to be reduced to so that the existing cryptographic attacks would work – and, conversely, that it can be shown that the number of actual rounds is large enough to protect against them.

Substitution–permutation networks

A sketch of a substitution–permutation network with 3 rounds, encrypting a plaintext block of 16 bits into a ciphertext block of 16 bits. The S-boxes are the S_i, the P-boxes are the same P, and the round keys are the K_i.

One important type of iterated block cipher known as a substitution–permutation network (SPN) takes a block of the plaintext and the key as inputs and applies several alternating rounds consisting of a substitution stage followed by a permutation stage—to produce each block of ciphertext output.^[13] The non-linear substitution stage mixes the key bits with those of the plaintext, creating Shannon's confusion. The linear permutation stage then dissipates redundancies, creating diffusion.^[14][15]

A substitution box (S-box) substitutes a small block of input bits with another block of output bits. This substitution must be one-to-one, to ensure invertibility (hence decryption). A secure S-box will have the property that changing one input bit will change about half of the output bits on average, exhibiting what is known as the avalanche effect—i.e. it has the property that each output bit will depend on every input bit.^[16]

A permutation box (P-box) is a permutation of all the bits: it takes the outputs of all the S-boxes of one round, permutes the bits, and feeds them into the S-boxes of the next round. A good P-box has the property that the output bits of any S-box are distributed to as many S-box inputs as possible.

At each round, the round key (obtained from the key with some simple operations, for instance, using S-boxes and P-boxes) is combined using some group operation, typically XOR.

Decryption is done by simply reversing the process (using the inverses of the S-boxes and P-boxes and applying the round keys in reversed order).^[17]

Feistel ciphers

Many block ciphers, such as DES and Blowfish utilize structures known as Feistel ciphers

In a Feistel cipher, the block of plain text to be encrypted is split into two equal-sized halves. The round function is applied to one half, using a subkey, and then the output is XORed with the other half. The two halves are then swapped.^[18]

Let ${\displaystyle {\rm {F}}}$ be the round function and let ${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$ be the sub-keys for the rounds ${\displaystyle 0,1,\ldots ,n}$ respectively.

Then the basic operation is as follows:^[18]

Split the plaintext block into two equal pieces, (${\displaystyle L_{0}}$, ${\displaystyle R_{0}}$)

For each round ${\displaystyle i=0,1,\dots ,n}$, compute

${\displaystyle L_{i+1}=R_{i}\,}$

${\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})}$.

Then the ciphertext is ${\displaystyle (R_{n+1},L_{n+1})}$.

The decryption of a ciphertext ${\displaystyle (R_{n+1},L_{n+1})}$ is accomplished by computing for ${\displaystyle i=n,n-1,\ldots ,0}$

${\displaystyle R_{i}=L_{i+1}\,}$

${\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})}$.

Then ${\displaystyle (L_{0},R_{0})}$ is the plaintext again.

One advantage of the Feistel model compared to a substitution–permutation network is that the round function ${\displaystyle {\rm {F}}}$ does not have to be invertible.^[19]

Lai–Massey ciphers

The Lai–Massey scheme. The archetypical cipher utilizing it is IDEA.

The Lai–Massey scheme offers security properties similar to those of the Feistel structure. It also shares the advantage that the round function ${\displaystyle \mathrm {F} }$ does not have to be invertible. Another similarity is that it also splits the input block into two equal pieces. However, the round function is applied to the difference between the two, and the result is then added to both half blocks.

Let ${\displaystyle \mathrm {F} }$ be the round function and ${\displaystyle \mathrm {H} }$ a half-round function and let ${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$ be the sub-keys for the rounds ${\displaystyle 0,1,\ldots ,n}$ respectively.

Then the basic operation is as follows:

Split the plaintext block into two equal pieces, (${\displaystyle L_{0}}$, ${\displaystyle R_{0}}$)

For each round ${\displaystyle i=0,1,\dots ,n}$, compute

${\displaystyle (L_{i+1}',R_{i+1}')=\mathrm {H} (L_{i}'+T_{i},R_{i}'+T_{i}),}$

where ${\displaystyle T_{i}=\mathrm {F} (L_{i}'-R_{i}',K_{i})}$ and ${\displaystyle (L_{0}',R_{0}')=\mathrm {H} (L_{0},R_{0})}$

Then the ciphertext is ${\displaystyle (L_{n+1},R_{n+1})=(L_{n+1}',R_{n+1}')}$.

The decryption of a ciphertext ${\displaystyle (L_{n+1},R_{n+1})}$ is accomplished by computing for ${\displaystyle i=n,n-1,\ldots ,0}$

${\displaystyle (L_{i}',R_{i}')=\mathrm {H} ^{-1}(L_{i+1}'-T_{i},R_{i+1}'-T_{i})}$

where ${\displaystyle T_{i}=\mathrm {F} (L_{i+1}'-R_{i+1}',K_{i})}$ and ${\displaystyle (L_{n+1}',R_{n+1}')=\mathrm {H} ^{-1}(L_{n+1},R_{n+1})}$

Then ${\displaystyle (L_{0},R_{0})=(L_{0}',R_{0}')}$ is the plaintext again.

Operations

Brute-force attacks

This property results in the cipher's security degrading quadratically, and needs to be taken into account when selecting a block size. There is a trade-off though as large block sizes can result in the algorithm becoming inefficient to operate.^[32] Earlier block ciphers such as the DES have typically selected a 64-bit block size, while newer designs such as the AES support block sizes of 128 bits or more, with some ciphers supporting a range of different block sizes.^[33]

Differential cryptanalysis

Linear cryptanalysis

A linear cryptanalysis is a form of cryptanalysis based on finding affine approximations to the action of a cipher. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis.^[34]

The discovery is attributed to Mitsuru Matsui, who first applied the technique to the FEAL cipher (Matsui and Yamagishi, 1992).^[35]

Integral cryptanalysis

Integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. Unlike differential cryptanalysis, which uses pairs of chosen plaintexts with a fixed XOR difference, integral cryptanalysis uses sets or even multisets of chosen plaintexts of which part is held constant and another part varies through all possibilities. For example, an attack might use 256 chosen plaintexts that have all but 8 of their bits the same, but all differ in those 8 bits. Such a set necessarily has an XOR sum of 0, and the XOR sums of the corresponding sets of ciphertexts provide information about the cipher's operation. This contrast between the differences between pairs of texts and the sums of larger sets of texts inspired the name "integral cryptanalysis", borrowing the terminology of calculus.

Other techniques

The development of the boomerang attack enabled differential cryptanalysis techniques to be applied to many ciphers that had previously been deemed secure against differential attacks

In addition to linear and differential cryptanalysis, there is a growing catalog of attacks: truncated differential cryptanalysis, partial differential cryptanalysis, integral cryptanalysis, which encompasses square and integral attacks, slide attacks, boomerang attacks, the XSL attack, impossible differential cryptanalysis, and algebraic attacks. For a new block cipher design to have any credibility, it must demonstrate evidence of security against known attacks.

Standard model

Informally, a block cipher is secure in the standard model if an attacker cannot tell the difference between the block cipher (equipped with a random key) and a random permutation.

To be a bit more precise, let E be an n-bit block cipher. We imagine the following game:

1. The person running the game flips a coin.
   • If the coin lands on heads, he chooses a random key K and defines the function f = E_K.
   • If the coin lands on tails, he chooses a random permutation π on the set of n-bit strings and defines the function f = π.
2. The attacker chooses an n-bit string X, and the person running the game tells him the value of f(X).
3. Step 2 is repeated a total of q times. (Each of these q interactions is a query.)
4. The attacker guesses how the coin landed. He wins if his guess is correct.

The attacker, which we can model as an algorithm, is called an adversary. The function f (which the adversary was able to query) is called an oracle.

Note that an adversary can trivially ensure a 50% chance of winning simply by guessing at random (or even by, for example, always guessing "heads"). Therefore, let P_E(A) denote the probability that adversary A wins this game against E, and define the advantage of A as 2(P_E(A) − 1/2). It follows that if A guesses randomly, its advantage will be 0; on the other hand, if A always wins, then its advantage is 1. The block cipher E is a pseudo-random permutation (PRP) if no adversary has an advantage significantly greater than 0, given specified restrictions on q and the adversary's running time. If in Step 2 above adversaries have the option of learning f⁻¹(X) instead of f(X) (but still have only small advantages) then E is a strong PRP (SPRP). An adversary is non-adaptive if it chooses all q values for X before the game begins (that is, it does not use any information gleaned from previous queries to choose each X as it goes).

These definitions have proven useful for analyzing various modes of operation. For example, one can define a similar game for measuring the security of a block cipher-based encryption algorithm, and then try to show (through a reduction argument) that the probability of an adversary winning this new game is not much more than P_E(A) for some A. (The reduction typically provides limits on q and the running time of A.) Equivalently, if P_E(A) is small for all relevant A, then no attacker has a significant probability of winning the new game. This formalizes the idea that the higher-level algorithm inherits the block cipher's security.

Ideal cipher model

Lucifer / DES

Lucifer is generally considered to be the first civilian block cipher, developed at IBM in the 1970s based on work done by Horst Feistel. A revised version of the algorithm was adopted as a U.S. government Federal Information Processing Standard: FIPS PUB 46 Data Encryption Standard (DES).^[39] It was chosen by the U.S. National Bureau of Standards (NBS) after a public invitation for submissions and some internal changes by NBS (and, potentially, the NSA). DES was publicly released in 1976 and has been widely used.

DES was designed to, among other things, resist a certain cryptanalytic attack known to the NSA and rediscovered by IBM, though unknown publicly until rediscovered again and published by Eli Biham and Adi Shamir in the late 1980s. The technique is called differential cryptanalysis and remains one of the few general attacks against block ciphers; linear cryptanalysis is another but may have been unknown even to the NSA, prior to its publication by Mitsuru Matsui. DES prompted a large amount of other work and publications in cryptography and cryptanalysis in the open community and it inspired many new cipher designs.

DES has a block size of 64 bits and a key size of 56 bits. 64-bit blocks became common in block cipher designs after DES. Key length depended on several factors, including government regulation. Many observers in the 1970s commented that the 56-bit key length used for DES was too short. As time went on, its inadequacy became apparent, especially after a special-purpose machine designed to break DES was demonstrated in 1998 by the Electronic Frontier Foundation. An extension to DES, Triple DES, triple-encrypts each block with either two independent keys (112-bit key and 80-bit security) or three independent keys (168-bit key and 112-bit security). It was widely adopted as a replacement. As of 2011, the three-key version is still considered secure, though the National Institute of Standards and Technology (NIST) standards no longer permit the use of the two-key version in new applications, due to its 80-bit security level.^[40]

IDEA

The International Data Encryption Algorithm (IDEA) is a block cipher designed by James Massey of ETH Zurich and Xuejia Lai; it was first described in 1991, as an intended replacement for DES.

IDEA operates on 64-bit blocks using a 128-bit key and consists of a series of eight identical transformations (a round) and an output transformation (the half-round). The processes for encryption and decryption are similar. IDEA derives much of its security by interleaving operations from different groups – modular addition and multiplication, and bitwise exclusive or (XOR) – which are algebraically "incompatible" in some sense.

The designers analysed IDEA to measure its strength against differential cryptanalysis and concluded that it is immune under certain assumptions. No successful linear or algebraic weaknesses have been reported. As of 2012, the best attack which applies to all keys can break a full 8.5-round IDEA using a narrow-bicliques attack about four times faster than brute force.

RC5

One round (two half-rounds) of the RC5 block cipher

RC5 is a block cipher designed by Ronald Rivest in 1994 which, unlike many other ciphers, has a variable block size (32, 64, or 128 bits), key size (0 to 2040 bits), and a number of rounds (0 to 255). The original suggested choice of parameters was a block size of 64 bits, a 128-bit key, and 12 rounds.

A key feature of RC5 is the use of data-dependent rotations; one of the goals of RC5 was to prompt the study and evaluation of such operations as a cryptographic primitive. RC5 also consists of a number of modular additions and XORs. The general structure of the algorithm is a Feistel-like a network. The encryption and decryption routines can be specified in a few lines of code. The key schedule, however, is more complex, expanding the key using an essentially one-way function with the binary expansions of both e and the golden ratio as sources of "nothing up my sleeve numbers". The tantalizing simplicity of the algorithm together with the novelty of the data-dependent rotations has made RC5 an attractive object of study for cryptanalysts.

12-round RC5 (with 64-bit blocks) is susceptible to a differential attack using 2⁴⁴ chosen plaintexts.^[41] 18–20 rounds are suggested as sufficient protection.

Rijndael / AES

The Rijndael cipher developed by Belgian cryptographers, Joan Daemen and Vincent Rijmen was one of the competing designs to replace DES. It won the 5-year public competition to become the AES, (Advanced Encryption Standard).

Adopted by NIST in 2001, AES has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits, whereas Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits. The block size has a maximum of 256 bits, but the key size has no theoretical maximum. AES operates on a 4×4 column-major order matrix of bytes, termed the state (versions of Rijndael with a larger block size have additional columns in the state).

Blowfish

Blowfish is a block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish has a 64-bit block size and a variable key length from 1 bit up to 448 bits.^[42] It is a 16-round Feistel cipher and uses large key-dependent S-boxes. Notable features of the design include the key-dependent S-boxes and a highly complex key schedule.

It was designed as a general-purpose algorithm, intended as an alternative to the aging DES and free of the problems and constraints associated with other algorithms. At the time Blowfish was released, many other designs were proprietary, encumbered by patents, or were commercial/government secrets. Schneier has stated that "Blowfish is unpatented, and will remain so in all countries. The algorithm is hereby placed in the public domain, and can be freely used by anyone." The same applies to Twofish, a successor algorithm from Schneier.

Tweakable block ciphers

M. Liskov, R. Rivest, and D. Wagner have described a generalized version of block ciphers called "tweakable" block ciphers.^[43] A tweakable block cipher accepts a second input called the tweak along with its usual plaintext or ciphertext input. The tweak, along with the key, selects the permutation computed by the cipher. If changing tweaks is sufficiently lightweight (compared with a usually fairly expensive key setup operation), then some interesting new operation modes become possible. The disk encryption theory article describes some of these modes.

Format-preserving encryption

Block ciphers traditionally work over a binary alphabet. That is, both the input and the output are binary strings, consisting of n zeroes and ones. In some situations, however, one may wish to have a block cipher that works over some other alphabet; for example, encrypting 16-digit credit card numbers in such a way that the ciphertext is also a 16-digit number might facilitate adding an encryption layer to legacy software. This is an example of format-preserving encryption. More generally, format-preserving encryption requires a keyed permutation on some finite language. This makes format-preserving encryption schemes a natural generalization of (tweakable) block ciphers. In contrast, traditional encryption schemes, such as CBC, are not permutations because the same plaintext can encrypt multiple different ciphertexts, even when using a fixed key.