Block Ciphers

A block cipher operates on a fixed-length block of plaintext $m$ of $n$ bits, mapping it to a ciphertext block $c$ of the same length under a secret key $k$, both drawn from $\{0,1\}^n$.

For a fixed key $k$, the encryption function $e_k$ is a bijection on $\{0,1\}^n$, so it is invertible via $d_k$.

Block Cipher as a PRP

A block cipher’s key design objective is to behave like a family of pseudorandom permutations (PRP) indexed by $k$.

Large messages are divided into blocks and encrypted independently per block:

Per Kerckhoffs’s principle, $e$ and $d$ are public. Only $k$ is secret.

Attacking a Block Cipher

• Ciphertext only
  Attacker has only $c$ and searches the key space exhaustively for a $k$ giving a meaningful $d_k(c)$. Requires $|K| > 2^{64}$ to make this infeasible.
• Chosen plaintext (IND-CPA)
  Attacker submits chosen plaintexts to an encryption oracle and must not be able to distinguish encryptions of chosen messages better than a coin toss.
• Chosen ciphertext (IND-CCA)
  Attacker has access to an encryption oracle, a decryption oracle (except for the challenge ciphertext), and a left-right oracle producing $c^* = e_k(m_b)$ for $b \in \{0,1\}$. Wins by guessing $b$. A secure scheme limits this to probability 0.5.

A block cipher encrypts a set of bits or characters at a time, whereas a stream cipher encrypts a single bit or character at a time. A stream cipher is used directly as an encryption scheme, but a block cipher is only a building block. The specific design combining a block cipher into a usable encryption scheme is its mode of operation.

Iterated Block Cipher Design

Security comes from repeated application of a round function to the block, over $r$ rounds. Increasing $r$ increases security up to a stable level.

Feistel Cipher

Named after Horst Feistel. Splits the plaintext block into halves $(L_0, R_0)$ and iterates a round function $F$, keyed by $k_i$, over $r$ rounds, swapping the final halves to produce the ciphertext.

Each encryption round:

Each decryption round, using the round keys in reverse order:

Design parameters of a Feistel cipher:

• Block length $n$.
• Number of rounds $r$.
• Definition of the round function $F$.
• Key schedule generating each round key $k_i$ from $k$.
• Length of the secret key $k$.

SP-Network

Proposed by Claude Shannon in 1945: a series of linked permutation and substitution operations. AES, the successor to DES, is based on this design, rather than the Feistel structure.

• Diffusion
  Permutations disperse the statistical characteristics of each input bit among all output bits.
• Confusion
  Substitutions create a complex relationship between the input and key with the output, providing the cipher’s non-linearity.

Modes of Operation

A mode of operation combines a block cipher into a usable block encryption scheme. DES was standardized with 4 modes:

• ECB, useful for encrypting short secrets such as session keys.
• CBC, useful for bulk data encryption.
• OFB, useful for real-time streamed content.
• CFB, useful for streamed content.

CTR mode, enabling parallel block encryption, was developed later.

ECB

Electronic Code Book: each plaintext block is encrypted independently.

CBC

Cipher Block Chaining: chains each ciphertext block into the encryption of the next, giving every block context.

• A single ciphertext bit error corrupts its own plaintext block fully, plus a single bit in the next block, giving 1-block error propagation.
• A fixed public IV (e.g. all-0) need not be transmitted. A random nonce IV must be sent alongside the ciphertext.

OFB

Output Feedback: runs the block cipher as a keystream generator, turning it into a stream cipher.

with $Y_0 \leftarrow IV$. Both encryption and decryption use $e_k$, never $d_k$.

CFB

Cipher Feedback: also produces a keystream, but feeds the ciphertext itself back into the cipher input.

with $Y_0 \leftarrow IV$ and $Z_i^*$ the leading $b$ bits of $Z_i$. Decryption mirrors this using $c_i$ in place of $m_i$.

CTR

Counter mode: like ECB, but XORs plaintext with the encryption of a counter rather than encrypting the plaintext directly.

where $\langle i \rangle_b$ is the $b$-bit binary representation of $i$.

• Blocks can be encrypted in parallel, like ECB, since each block is independent.
• The counter provides context, preventing the cut-and-paste and rearrangement attacks possible against ECB.