Block cipher

A block cipher is a deterministic symmetric-key algorithm that encrypts a fixed-length group of bits, called a block, into a block of the same length under a secret key. The algorithm defines a family of invertible permutations on the block space, one permutation for each valid key. Because it handles only fixed-size inputs, a block cipher is normally combined with a mode of operation to encrypt messages of arbitrary length or to provide other security services such as authentication.

Definition and notation

A block cipher consists of two algorithms: encryption \(E\) and decryption \(D\). For a key \(K\) from the key space and an \(n\)-bit plaintext block \(P\), the ciphertext is \(C = E_K(P)\). Decryption recovers \(P = D_K(C)\), so \(D_K(E_K(P)) = P\) for every \(K\) and \(P\). The value \(n\) is the block size, usually 64, 128, or 256 bits. The key length \(k\) may be independent of \(n\). Modern block ciphers commonly use 128-bit or larger keys.

For each key, \(E_K\) is a permutation of the set \(\{0,1\}^n\). A well-designed block cipher behaves like a pseudorandom permutation: an adversary who does not know \(K\) cannot efficiently distinguish \(E_K\) from a randomly chosen permutation on \(n\)-bit strings, even with chosen plaintext or ciphertext access.

History

The conceptual foundations of modern block ciphers were laid by Claude Shannon, who identified confusion and diffusion as desirable properties for cryptographic systems. A practical early influence was the Lucifer cipher developed at IBM in the 1970s. Lucifer evolved into the Data Encryption Standard (DES), published as a U.S. federal standard in 1977. DES has a 64-bit block and a 56-bit key, and uses a Feistel network structure.

During the 1990s, DES's 56-bit key became vulnerable to exhaustive search, and its 64-bit block size raised concerns about birthday-bound attacks. Triple DES was widely adopted as a stopgap. In 1997 the U.S. National Institute of Standards and Technology (NIST) began a public competition for the Advanced Encryption Standard (AES). In 2001 NIST selected Rijndael as AES, with a 128-bit block and 128-, 192-, or 256-bit keys. AES is now the most widely used block cipher.

Design principles

Block ciphers are built by repeatedly applying simple operations to mix the key and plaintext. Two classical structural approaches are Feistel networks and substitution-permutation networks.

A Feistel network divides the block into two halves and applies a round function to one half, then combines it with the other half, swapping halves in successive rounds. This structure allows encryption and decryption to use the same round function with the round keys in reverse order. DES, Blowfish, and Camellia use Feistel designs.

A substitution-permutation network (SPN) alternates layers of substitution boxes (S-boxes), which produce nonlinear local confusion, with linear diffusion transformations such as bit permutations or matrix multiplication. AES and Serpent use SPN designs.

Other important design elements include:

• Key schedule: an expansion of the main key into round keys.
• Round constants: values changed per round to prevent symmetries.
• S-box design: nonlinearity and resistance to differential and linear cryptanalysis.
• Diffusion layers: ensuring that changing one input bit affects many output bits.
• Number of rounds: selected so that known attacks do not reach full-round security.

The avalanche effect is a common design goal: a one-bit change in the plaintext or key should change about half of the ciphertext bits.

Common block ciphers

Prominent block ciphers include:

• DES: 64-bit block, 56-bit key, Feistel network, 16 rounds. Now considered insecure for direct use because of its short key.
• Triple DES (3DES): applies DES three times with two or three keys. Effective key length is about 112 bits for two-key 3DES, but its 64-bit block remains a limitation.
• AES: 128-bit block, 128/192/256-bit keys, SPN with 10, 12, or 14 rounds. Standardized in FIPS 197.
• Blowfish: 64-bit block, variable key length up to 448 bits, Feistel network.
• Twofish: 128-bit block, up to 256-bit key, Feistel-like structure.
• Serpent: 128-bit block, 128/192/256-bit keys, SPN with conservative security margin.
• IDEA: 64-bit block, 128-bit key, uses mixed operations from different algebraic groups.
• Camellia: 128-bit block, 128/192/256-bit keys, Feistel network.
• SM4: 128-bit block, 128-bit key, standardized in China and used in some commercial protocols.
• RC5 and RC6: variable-block and variable-key ciphers; RC6 was an AES finalist.

Many applications now require at least a 128-bit block and a 128-bit key to avoid birthday-bound and brute-force attacks.

Modes of operation

A block cipher alone encrypts exactly one block. To encrypt longer messages, it is used in a mode of operation. Modes can be confidentiality-only or authenticated encryption modes.

Electronic Codebook (ECB)

Each plaintext block is encrypted independently: \(C_i = E_K(P_i)\). ECB is deterministic and leaks plaintext patterns. Identical plaintext blocks produce identical ciphertext blocks, so ECB is generally unsuitable for structured data. It should be used only for single blocks or random data without repeated blocks.

Cipher Block Chaining (CBC)

Each plaintext block is XORed with the previous ciphertext before encryption: \(C_i = E_K(P_i \oplus C_{i-1})\). An initialization vector (IV) is required for the first block. CBC hides patterns of repeated blocks, but it is sequential and requires padding. The IV should be unpredictable for CBC. Bit errors in a ciphertext block affect that block and one part of the next block.

Cipher Feedback (CFB)

CFB turns a block cipher into a self-synchronizing stream cipher. The block cipher's output is XORed with plaintext to produce ciphertext, and the ciphertext is fed back into the next block's input. CFB can process messages shorter than the block size.

Output Feedback (OFB)

OFB repeatedly encrypts an IV to produce a keystream, which is XORed with plaintext. It is a synchronous stream mode. Reusing an IV with the same key is catastrophic because it produces the same keystream.

Counter (CTR)

CTR encrypts successive values of a counter or nonce-counter combination and XORs the resulting keystream with plaintext. CTR is highly parallelizable and allows random access. It also turns the block cipher into a stream cipher. As with OFB, unique nonce/counter combinations must be used for a given key.

XTS

XTS is a tweakable mode designed for disk encryption. It uses two keys and a tweak derived from the disk sector position, providing confidentiality for fixed-length storage units without expansion.

Authenticated encryption modes

Modes such as Galois/Counter Mode (GCM) and CCM combine encryption with message authentication. GCM uses CTR mode for encryption and a universal hash function called GHASH for authentication. CCM combines CTR encryption with CBC-MAC. These modes produce a ciphertext and an authentication tag, protecting both confidentiality and integrity.

Padding and message length handling

Some modes, especially ECB and CBC, require the plaintext length to be a multiple of the block size. Padding schemes add bytes to the final block. Common schemes include:

• PKCS#7: appends \(n\) bytes each with value \(n\), where \(n\) is the number of padding bytes needed. It is unambiguous and widely used.
• Bit padding: appends a single 1 bit followed by zeros.
• Zero padding: appends zero bytes; it may be ambiguous if the plaintext can end with zero bytes.

Padding can introduce vulnerabilities if not verified correctly, such as padding oracle attacks, in which an attacker learns whether a modified ciphertext has valid padding and gradually decrypts data. Modern authenticated encryption modes usually avoid padding because CTR-like encryption handles arbitrary-length data.

Ciphertext stealing is another technique for CBC-like modes that avoids expanding the ciphertext beyond the plaintext length.

Security and cryptanalysis

The security of a block cipher depends on its block size, key size, design quality, and the modes and protocols in which it is used.

• Brute-force attacks: try all keys. A \(k\)-bit key has \(2^k\) possibilities. A key length of at least 128 bits is considered safe against classical exhaustive search.
• Birthday-bound attacks: with an \(n\)-bit block, repeated ciphertext blocks or key-recovery attacks based on collisions become likely after about \(2^{n/2}\) blocks. For 64-bit block ciphers such as DES, this is around 32 GiB of data, which is practical. This is a major reason modern ciphers use 128-bit blocks.
• Differential cryptanalysis: studies how differences in plaintext pairs propagate to ciphertext differences and can recover key bits in some rounds.
• Linear cryptanalysis: approximates nonlinear components with linear expressions and exploits statistical biases.
• Integral attacks, boomerang attacks, impossible differentials, and meet-in-the-middle attacks: further families of cryptanalytic techniques.
• Related-key attacks: assume an attacker can request encryptions under related keys.
• Side-channel attacks: exploit physical implementation leakage, such as power consumption, electromagnetic emission, or timing, rather than mathematical weaknesses.
• Quantum attacks: Grover's algorithm can speed up brute-force search. A \(k\)-bit key offers roughly \(k/2\) bits of quantum security in a generic setting, motivating 256-bit keys in some scenarios.

A block cipher should be used as a pseudorandom permutation. Even a secure block cipher can be misused by an insecure mode, a predictable IV, or poor key management.

Theoretical role

Block ciphers are often modeled as ideal ciphers or pseudorandom permutations in security proofs of higher-level protocols. The Luby-Rackoff construction shows that a pseudorandom function can be converted into a pseudorandom permutation using a Feistel network with a sufficient number of rounds.

Block ciphers also serve as building blocks for other primitives:

• Hash functions: compression functions such as Davies-Meyer, Matyas-Meyer-Oseas, and Miyaguchi-Preneel use a block cipher.
• Message authentication codes: CBC-MAC, CMAC, and other MACs are built from block ciphers.
• Key derivation and pseudorandom generators: counter and feedback modes can generate pseudorandom output.
• Format-preserving encryption: Feistel-based constructions using a block cipher can encrypt data while preserving its length and alphabet.

Tweakable block ciphers extend the classical model by adding a public tweak input, allowing efficient construction of modes like XTS and some authenticated encryption schemes.

Standards and interoperability

Several standards define block ciphers and their modes:

• NIST FIPS 197 defines AES.
• NIST FIPS 46-3 defined DES, now withdrawn.
• NIST Special Publication 800-38 series defines modes of operation, including ECB, CBC, CFB, OFB, CTR, GCM, XTS, and CCM.
• ISO/IEC 18033-3 specifies block ciphers including AES, Camellia, SEED, and others.
• RFC standards define the use of AES and other ciphers in TLS, IPsec, SSH, and other protocols.

Applications

Block ciphers are ubiquitous in information security. Common applications include:

• Transport security: TLS, SSH, and IPsec use AES-based cipher suites.
• Data at rest: disk and file encryption typically use AES in XTS, CBC, or GCM modes.
• Database encryption: block ciphers protect columns or files, often with deterministic or randomized modes depending on query requirements.
• Digital payments: block ciphers or derived MACs protect transaction data and PINs.
• Key wrapping: block ciphers encrypt other cryptographic keys.
• Virtual private networks: AES-GCM and similar modes protect traffic.
• Mobile and embedded systems: lightweight block ciphers or optimized AES implementations protect constrained devices.

Comparison with stream ciphers

Stream ciphers generate a keystream and combine it with plaintext, often bit by bit or byte by byte. Block ciphers process fixed-size blocks. The distinction is not rigid: block ciphers can be used in CTR, OFB, or CFB modes to create stream-cipher-like behavior. Stream ciphers may be faster in hardware and require less buffering, while block ciphers have well-studied security properties and are widely standardized. Many modern systems prefer AES in CTR or GCM mode over dedicated stream ciphers, although dedicated stream ciphers such as ChaCha20 are also common when hardware AES is unavailable.