Block Cipher
A block cipher is a deterministic symmetric cryptographic primitive that maps fixed-length blocks of plaintext into ciphertext of identical length under the control of a secret key via a keyed pseudorandom permutation.
Block Cipher is a foundational deterministic symmetric cryptographic primitive in computation and algorithms that transforms a fixed-length string of plaintext bits into a ciphertext string of identical length under the control of a secret key. In formal cryptography, a block cipher acts as a family of keyed permutations over a finite domain, functioning as the primary building block for symmetric encryption schemes, message authentication codes, and authenticated key exchange protocols.
Formally, given a block length n and key length k, a block cipher consists of two polynomial-time algorithms: an encryption function E: {0, 1}k ร {0, 1}n โ {0, 1}n and a decryption function D: {0, 1}k ร {0, 1}n โ {0, 1}n. For every key K โ {0, 1}k, the mapping EK(ยท) must be a permutation (a bijection) over {0, 1}n, satisfying DK(EK(m)) = m for every message block m.
Theoretical Foundations: Pseudorandom Permutations and LubyโRackoff
The theoretical standard for block cipher security is modeled through the concept of a Pseudorandom Permutation (PRP). A block cipher E is a secure PRP if no computationally bounded adversary with polynomial access to an evaluation oracle can distinguish EK (with a uniformly chosen secret key K) from a truly random permutation selected uniformly from all (2n)! possible permutations of n-bit strings.
In their 1988 landmark paper, Michael Luby and Charles Rackoff proved the LubyโRackoff Theorem, establishing that a four-round Feistel cipher construction employing independent pseudorandom functions (PRFs) produces a strong pseudorandom permutation (SPRP) secure against adaptive chosen-ciphertext adversaries. This theoretical milestone established that invertible permutations can be constructed from non-invertible cryptographic components.
Core Architectural Paradigms
Practical block cipher designs generally follow one of three architectural paradigms:
- Feistel Networks: Introduced by Horst Feistel, the input block is partitioned into two halves. In each round, one half passes through a round function and is XORed into the other half, followed by a swap. Because the round function itself does not require invertibility, Feistel networks simplify hardware implementations. Prominent examples include DES, Blowfish, and Camellia.
- Substitution-Permutation Networks (SPN): As exemplified by the Advanced Encryption Standard, the entire block is processed simultaneously through layers of non-linear substitution boxes (S-boxes) followed by linear diffusion permutations (such as bit permutations or Galois field matrix multiplications). SPN designs generally achieve faster full-block diffusion than Feistel networks.
- Addition-Rotation-XOR (ARX): ARX designs construct ciphers using only three lightweight processor operations: modular integer addition (providing non-linearity), bitwise rotations by fixed offsets, and bitwise XOR operations. ARX primitives require no S-box memory lookups, inherently preventing cache-timing side-channel attacks. Notable examples include ChaCha20, Threefish, and Speck.
Modes of Operation
Because block ciphers only encrypt fixed-length blocks (such as 64 or 128 bits), encrypting arbitrary-length data streams requires a mode of operation:
- Electronic Codebook (ECB): Each plaintext block is encrypted independently. Identical plaintext blocks produce identical ciphertext blocks, leaking structural patterns (famously demonstrated by the ECB Penguin bitmap). ECB is universally rejected for practical confidential data.
- Cipher Block Chaining (CBC): Each plaintext block is XORed with the preceding ciphertext block before encryption, using an initialization vector (IV) for the first block: ci = EK(mi โ ciโ1). While secure against passive eavesdropping, CBC requires deterministic padding and is vulnerable to chosen-ciphertext padding oracle attacks.
- Counter Mode (CTR): Transforms the block cipher into a stream cipher. The block cipher encrypts an incrementing counter concatenated with a unique nonce, producing a pseudorandom keystream that is XORed with the plaintext: ci = mi โ EK(Nonce || i). CTR supports parallelized encryption and decryption.
- Galois/Counter Mode (GCM): Combines CTR mode encryption with universal hash authentication (GHASH) over the binary Galois field GF(2128), providing Authenticated Encryption with Associated Data (AEAD). GCM guarantees both confidentiality and ciphertext authenticity in a single unified pass.
Cryptanalytic Attack Frameworks
Cryptanalysts evaluate block ciphers against several established theoretical frameworks:
- Differential Cryptanalysis: Formulated by Eli Biham and Adi Shamir, differential cryptanalysis studies how specific differences in plaintext pairs propagate through round transformations into observable statistical differences in ciphertext pairs, enabling recovery of round subkeys.
- Linear Cryptanalysis: Formulated by Mitsuru Matsui, this technique identifies linear approximations between plaintext bits, ciphertext bits, and subkey bits that hold with a probability bias |p โ 1/2| > 0, recovering key bits with data complexity inversely proportional to the square of the bias.
- Slide Attacks: Target ciphers with weak key schedules where round transformations repeat identically, breaking the cipher independently of the number of rounds.
Comparison of Representative Block Ciphers
| Cipher Name | Designer / Standardization | Structure | Block Size | Key Size | Historical Security Status |
|---|---|---|---|---|---|
| DES | IBM / NIST (1977) | Feistel (16 rounds) | 64 bits | 56 bits | Deprecated; broken by brute force |
| Triple-DES | ANSI / NIST (1998) | Feistel (48 rounds) | 64 bits | 112 / 168 bits | Deprecated; vulnerable to Sweet32 collision attacks |
| AES (Rijndael) | Daemen & Rijmen / NIST (2001) | SPN (10โ14 rounds) | 128 bits | 128, 192, 256 bits | Universal global standard; robust |
| Blowfish | Bruce Schneier (1993) | Feistel (16 rounds) | 64 bits | 32โ448 bits | Superseded by Twofish; small 64-bit block size |
References
- Luby, M., & Rackoff, C. (1988). How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), 373-386.
- Shannon, C. E. (1949). Communication theory of secrecy systems. Bell System Technical Journal, 28(4), 656-715.
- Rogaway, P. (2011). Evaluation of Some Blockcipher Modes of Operation. Cryptography Research and Evaluation Committees Report.
- Matsui, M. (1993). Linear cryptanalysis method for DES cipher. Advances in Cryptology โ EUROCRYPT '93, 386-397.