Chapter 14: Block Cipher Design Principles#
14.1 Historical Context#
The design of modern block ciphers rests on a foundation laid over several decades by a small number of remarkably influential thinkers.
Claude Shannon (1949). In his landmark paper Communication Theory of Secrecy Systems, Shannon introduced two properties that every strong cipher should possess: confusion and diffusion. Confusion obscures the relationship between the key and the ciphertext, while diffusion spreads the influence of each plaintext bit across the entire ciphertext. Shannon observed that simple substitution provides confusion and simple transposition provides diffusion, and he proposed that a product cipher – one that alternates substitution and transposition layers – could achieve both properties simultaneously. This insight is the intellectual ancestor of every modern block cipher.
Horst Feistel and IBM (1970s). In the early 1970s, Horst Feistel, working at IBM’s Thomas J. Watson Research Center, translated Shannon’s theoretical principles into a practical cipher design. Feistel proposed an iterated structure – now called a Feistel network – in which the plaintext block is split into two halves, and a round function is applied repeatedly with different subkeys. The crucial advantage of the Feistel structure is that the round function need not be invertible; the structure itself guarantees invertibility. This design was embodied in the Lucifer cipher (1971) and later refined into the Data Encryption Standard (DES), adopted as a U.S. federal standard in 1977.
From product ciphers to modern designs. The limitations of DES – principally its 56-bit key and 64-bit block size – spurred the development of more sophisticated designs. The Substitution-Permutation Network (SPN) architecture, analyzed rigorously by Heys and Tavares in the 1990s, provided an alternative to the Feistel structure. In an SPN, the entire block passes through layers of S-boxes (substitution) and P-boxes (permutation) in each round. The Advanced Encryption Standard (AES), standardized in 2001, follows an SPN-like design (though its exact structure, based on operations over \(\mathrm{GF}(2^8)\), is more nuanced). Today, both Feistel networks and SPNs remain the two dominant paradigms in block cipher design.
Tip
Design philosophy matters. Understanding why block ciphers are designed the way they are – with iterated rounds of confusion and diffusion – is essential for understanding how to attack them. Differential and linear cryptanalysis, which we study in subsequent chapters, exploit precisely the situations where confusion or diffusion is insufficient.
14.2 Formal Definitions#
We now define the core concepts rigorously.
Definition 14.1 (Block Cipher)
A block cipher with block size \(n\) and key length \(\kappa\) is a function
such that for every key \(k \in \{0,1\}^\kappa\), the function \(E_k(\cdot) = E(k, \cdot)\) is a permutation on \(\{0,1\}^n\). That is, \(E_k\) is a bijection, and there exists a unique inverse \(D_k = E_k^{-1}\) satisfying \(D_k(E_k(m)) = m\) for all \(m \in \{0,1\}^n\).
A block cipher is thus a family of \(2^\kappa\) permutations on \(\{0,1\}^n\), indexed by the key.
Definition 14.2 (Confusion)
Confusion is the property that each bit of the ciphertext depends on the key in a complex, nonlinear way. Formally, for a block cipher \(E_k\), confusion requires that the mapping \(k \mapsto E_k(m)\) is highly nonlinear for every fixed plaintext \(m\). This makes it infeasible to deduce the key from statistical analysis of plaintext-ciphertext pairs.
In practice, confusion is achieved through substitution boxes (S-boxes) – small nonlinear lookup tables.
Definition 14.3 (Diffusion)
Diffusion is the property that each plaintext bit influences many (ideally all) ciphertext bits, and each ciphertext bit depends on many plaintext bits. We say that a cipher achieves full diffusion when every output bit depends on every input bit.
Full diffusion is a necessary but not sufficient condition for strong cryptographic mixing. Two stronger, quantitative criteria refine the notion:
Strict Avalanche Criterion (SAC): Flipping any single input bit causes each output bit to change with probability exactly \(\frac{1}{2}\). The SAC implies full diffusion but additionally requires that the influence is balanced.
Bit Independence Criterion (BIC): For any single input bit flip, the resulting changes in any two distinct output bits \(j\) and \(k\) are statistically independent. The BIC is strictly stronger than the SAC and ensures that output-bit changes do not exhibit correlated patterns that an attacker could exploit.
In practice, diffusion is achieved through permutation layers (P-boxes) and linear mixing operations.
Definition 14.4 (S-box)
An S-box (substitution box) is a nonlinear function \(S : \{0,1\}^m \to \{0,1\}^n\). When \(m = n\), the S-box is a permutation on \(\{0,1\}^m\) and is therefore invertible.
The S-box is the only source of nonlinearity in an SPN. Its cryptographic quality is measured by properties including:
Nonlinearity: resistance to linear approximation (measured via the Walsh-Hadamard transform).
Differential uniformity: resistance to differential attack (measured via the difference distribution table).
Algebraic degree: the degree of the Boolean polynomial representing each output bit.
Definition 14.5 (Permutation Layer / P-box)
A permutation layer (or P-box) is a bijection \(\pi : \{0, 1, \ldots, n-1\} \to \{0, 1, \ldots, n-1\}\) that rearranges the bit positions of an \(n\)-bit block. If \(x = (x_0, x_1, \ldots, x_{n-1})\), then the permuted block is \(y = (x_{\pi(0)}, x_{\pi(1)}, \ldots, x_{\pi(n-1)})\).
That is, output bit \(j\) receives the value of input bit \(\pi(j)\).
The P-box is a linear operation. Its purpose is purely to provide diffusion by ensuring that the outputs of one S-box feed into the inputs of different S-boxes in the next round.
Definition 14.6 (Substitution-Permutation Network)
A Substitution-Permutation Network (SPN) is a block cipher constructed by composing the following operations over \(R\) rounds:
For round \(r = 1, 2, \ldots, R\):
Key mixing: XOR the current state with the round key \(K_r\).
Substitution layer: Partition the state into blocks of \(m\) bits and apply an S-box \(S : \{0,1\}^m \to \{0,1\}^m\) independently to each block.
Permutation layer: Apply a P-box \(\pi\) to rearrange the bit positions of the full state.
After the final round, a terminal key mixing step XORs the state with \(K_{R+1}\) (no permutation layer in the last round).
The round keys \(K_1, K_2, \ldots, K_{R+1}\) are derived from the master key via a key schedule algorithm.
14.3 Implementation: S-Box#
We begin by implementing an S-box class. The S-box we use throughout this chapter is the one from Heys’s tutorial SPN (Heys, 2002), a 4-bit to 4-bit permutation:
Input |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Output |
E |
4 |
D |
1 |
2 |
F |
B |
8 |
3 |
A |
6 |
C |
5 |
9 |
0 |
7 |
This S-box maps, for example, \(0 \mapsto 14\) (0xE), \(1 \mapsto 4\), \(2 \mapsto 13\) (0xD), and so on.
import numpy as np
class SBox:
"""
An m-bit to m-bit substitution box (S-box).
Parameters
----------
table : list of int
The substitution table. table[i] is the output for input i.
Length must be a power of 2.
"""
def __init__(self, table):
self.table = np.array(table, dtype=np.int32)
self.size = len(table)
self.bits = int(np.log2(self.size))
assert 2**self.bits == self.size, "Table length must be a power of 2."
# Check that the table is a permutation (bijection)
self._is_permutation = (len(set(table)) == self.size)
# Compute inverse table if it is a permutation
if self._is_permutation:
self._inv_table = np.zeros(self.size, dtype=np.int32)
for i in range(self.size):
self._inv_table[self.table[i]] = i
else:
self._inv_table = None
def apply(self, x):
"""Apply the S-box to input x (integer in [0, 2^m - 1])."""
return int(self.table[x])
def inverse(self, y):
"""Apply the inverse S-box to output y."""
if not self._is_permutation:
raise ValueError("S-box is not a permutation; no inverse exists.")
return int(self._inv_table[y])
def is_permutation(self):
"""Check whether the S-box is a bijection."""
return self._is_permutation
def walsh_hadamard_spectrum(self):
"""
Compute the Walsh-Hadamard transform for every (input mask, output mask)
pair. Returns a 2D array W where W[a, b] is the Walsh coefficient for
input mask a and output mask b.
W[a, b] = sum_{x=0}^{2^m - 1} (-1)^{a.x XOR b.S(x)}
where a.x denotes the inner product of the binary representations mod 2.
"""
n = self.size
m = self.bits
W = np.zeros((n, n), dtype=np.int32)
for a in range(n):
for b in range(n):
total = 0
for x in range(n):
# Parity of (a & x) XOR (b & S(x))
ax = bin(a & x).count('1') % 2
bs = bin(b & self.table[x]).count('1') % 2
total += (-1) ** (ax ^ bs)
W[a, b] = total
return W
def nonlinearity(self):
"""
Compute the nonlinearity of the S-box.
NL(S) = 2^{m-1} - (1/2) * max_{a != 0, b != 0} |W[a, b]|
"""
W = self.walsh_hadamard_spectrum()
# Exclude (a=0, b=any) and (a=any, b=0) rows/columns
W_sub = W[1:, 1:]
max_abs = np.max(np.abs(W_sub))
return 2**(self.bits - 1) - max_abs // 2
def linearity_test(self):
"""
Test whether the S-box is an affine (linear + constant) function.
An affine S-box has Walsh coefficients of magnitude 2^m for some
entries and 0 for others.
Returns True if the S-box is affine, False otherwise.
"""
W = self.walsh_hadamard_spectrum()
# For a linear/affine function, all Walsh coefficients are either
# +/- 2^m or 0
n = self.size
unique_vals = set(np.abs(W.flatten()))
return unique_vals <= {0, n}
def __repr__(self):
hex_vals = [f"0x{v:X}" for v in self.table]
return f"SBox({self.bits}-bit, table=[{', '.join(hex_vals)}])"
# --- Instantiate the Heys tutorial S-box ---
HEYS_SBOX_TABLE = [0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7]
sbox = SBox(HEYS_SBOX_TABLE)
print(f"S-box: {sbox}")
print(f"Is permutation: {sbox.is_permutation()}")
print(f"Is affine/linear: {sbox.linearity_test()}")
print(f"Nonlinearity: {sbox.nonlinearity()}")
print()
# Verify invertibility
print("Verifying S-box invertibility:")
all_correct = all(sbox.inverse(sbox.apply(x)) == x for x in range(16))
print(f" S^{{-1}}(S(x)) == x for all x: {all_correct}")
print()
# Print the full table
print("S-box lookup table:")
print(" Input: ", " ".join(f"{i:X}" for i in range(16)))
print(" Output: ", " ".join(f"{sbox.apply(i):X}" for i in range(16)))
print(" Inverse:", " ".join(f"{sbox.inverse(i):X}" for i in range(16)))
S-box: SBox(4-bit, table=[0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7])
Is permutation: True
Is affine/linear: False
Nonlinearity: 2
Verifying S-box invertibility:
S^{-1}(S(x)) == x for all x: True
S-box lookup table:
Input: 0 1 2 3 4 5 6 7 8 9 A B C D E F
Output: E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7
Inverse: E 3 4 8 1 C A F 7 D 9 6 B 2 0 5
14.4 Implementation: Permutation Layer (P-box)#
The permutation layer rearranges the 16 bits of the state. Following Definition 14.5, output bit \(j\) receives the value of input bit \(\pi(j)\), where
This mapping is an involution (\(\pi = \pi^{-1}\)), which means that the same formula also describes where each input bit is sent: input bit \(i\) goes to output position \(\pi(i)\). Geometrically, the permutation transposes a \(4 \times 4\) matrix of bits (reading the state as 4 nibbles of 4 bits each). The key property is that the output bits of one S-box feed into the inputs of four different S-boxes in the next round, ensuring rapid diffusion.
import numpy as np
class PermutationBox:
"""
A bit-level permutation (P-box) on an n-bit block.
Parameters
----------
perm : list of int
perm[j] = i means output bit position j receives the value of
input bit position i. Equivalently, output[j] = input[perm[j]].
This matches Definition 14.5: given the permutation
pi, the output vector is y_j = x_{pi(j)}.
Note: for the Heys tutorial P-box the permutation is an
involution (pi = pi^{-1}), so the forward and inverse
permutations coincide.
"""
def __init__(self, perm):
self.perm = np.array(perm, dtype=np.int32)
self.n = len(perm)
# Compute inverse permutation
self.inv_perm = np.zeros(self.n, dtype=np.int32)
for i in range(self.n):
self.inv_perm[self.perm[i]] = i
def apply(self, bits):
"""
Apply the permutation to a bit array.
Parameters
----------
bits : numpy array of 0s and 1s, length n
Returns
-------
numpy array of 0s and 1s, length n
"""
bits = np.asarray(bits, dtype=np.int32)
return bits[self.perm]
def apply_inverse(self, bits):
"""Apply the inverse permutation."""
bits = np.asarray(bits, dtype=np.int32)
return bits[self.inv_perm]
def __repr__(self):
return f"PermutationBox({self.n}-bit, perm={list(self.perm)})"
# --- Instantiate the Heys tutorial P-box ---
HEYS_PERM = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
pbox = PermutationBox(HEYS_PERM)
print(f"P-box: {pbox}")
print(f"Inverse permutation: {list(pbox.inv_perm)}")
print()
# Verify: applying then inverting returns the original
test_bits = np.array([1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0], dtype=np.int32)
permuted = pbox.apply(test_bits)
restored = pbox.apply_inverse(permuted)
print(f"Original: {test_bits}")
print(f"Permuted: {permuted}")
print(f"Restored: {restored}")
print(f"Correct: {np.array_equal(test_bits, restored)}")
print()
# Show the permutation mapping
# Convention: output[j] = input[perm[j]], so perm[j] is where output bit j comes from.
# For this involution perm = perm^{-1}, so "comes from" and "goes to" coincide.
print("Permutation mapping (output position <- input bit):")
for j in range(16):
print(f" output {int(j):2d} <- input {int(HEYS_PERM[j]):2d}", end="")
if (j + 1) % 4 == 0:
print()
P-box: PermutationBox(16-bit, perm=[0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15])
Inverse permutation: [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
Original: [1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0]
Permuted: [1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0]
Restored: [1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0]
Correct: True
Permutation mapping (output position <- input bit):
output 0 <- input 0 output 1 <- input 4 output 2 <- input 8 output 3 <- input 12
output 4 <- input 1 output 5 <- input 5 output 6 <- input 9 output 7 <- input 13
output 8 <- input 2 output 9 <- input 6 output 10 <- input 10 output 11 <- input 14
output 12 <- input 3 output 13 <- input 7 output 14 <- input 11 output 15 <- input 15
14.5 Implementation: The Heys Tutorial SPN#
We now implement the complete Heys tutorial SPN – a 16-bit block cipher with a 28-bit key, 2 full rounds, and a final key-mixing step. This cipher is intentionally small (and therefore insecure) to allow for pedagogical analysis.
Structure of one round:
XOR the 16-bit state with the round key \(K_r\).
Split the state into four 4-bit nibbles; apply the S-box to each.
Apply the P-box to the full 16-bit state.
Final step (after round 2): 4. XOR with \(K_3\), apply S-boxes, then XOR with \(K_4\) (no P-box).
Key schedule: The 28-bit master key is partitioned into four overlapping 16-bit round keys via a sliding window:
\(K_1 = \) key bits \([0:16]\)
\(K_2 = \) key bits \([4:20]\)
\(K_3 = \) key bits \([8:24]\)
\(K_4 = \) key bits \([12:28]\)
Warning
This cipher is designed for educational purposes only. Its 16-bit block and 28-bit key make it trivially breakable by exhaustive search. It is used here to illustrate SPN structure and to set up the linear and differential cryptanalysis exercises in subsequent chapters.
import numpy as np
class SBox:
"""S-box (substitution box) for use in SPNetwork."""
def __init__(self, table):
self.table = np.array(table, dtype=np.int32)
self.size = len(table)
self.bits = int(np.log2(self.size))
self._inv_table = np.zeros(self.size, dtype=np.int32)
for i in range(self.size):
self._inv_table[self.table[i]] = i
def apply(self, x):
return int(self.table[x])
def inverse(self, y):
return int(self._inv_table[y])
class PermutationBox:
"""Bit-level permutation (P-box)."""
def __init__(self, perm):
self.perm = np.array(perm, dtype=np.int32)
self.n = len(perm)
self.inv_perm = np.zeros(self.n, dtype=np.int32)
for i in range(self.n):
self.inv_perm[self.perm[i]] = i
def apply(self, bits):
return np.asarray(bits, dtype=np.int32)[self.perm]
def apply_inverse(self, bits):
return np.asarray(bits, dtype=np.int32)[self.inv_perm]
def key_schedule(master_key_bits):
"""
Derive round keys from a 28-bit master key.
Parameters
----------
master_key_bits : array-like of int, length 28
The master key as a sequence of bits.
Returns
-------
list of numpy arrays
Four 16-bit round keys [K1, K2, K3, K4].
"""
k = np.asarray(master_key_bits, dtype=np.int32)
assert len(k) == 28, "Master key must be 28 bits."
return [k[4*i : 4*i + 16].copy() for i in range(4)]
def int_to_bits(value, n_bits):
"""Convert an integer to a numpy array of bits (MSB first)."""
return np.array([(value >> (n_bits - 1 - i)) & 1 for i in range(n_bits)],
dtype=np.int32)
def bits_to_int(bits):
"""Convert a numpy array of bits (MSB first) to an integer."""
result = 0
for b in bits:
result = (result << 1) | int(b)
return result
class SPNetwork:
"""
The Heys tutorial Substitution-Permutation Network.
- Block size: 16 bits
- Key size: 28 bits
- Rounds: 3 (2 full rounds + 1 final substitution + key mixing)
- S-box: 4-bit, applied 4 times per round
- P-box: 16-bit permutation
Parameters
----------
sbox_table : list of int
The 4-bit S-box lookup table.
perm : list of int
The 16-bit permutation table.
master_key : int or array-like
If int: the 28-bit key as an integer.
If array-like: the 28-bit key as a bit array.
"""
def __init__(self, sbox_table, perm, master_key):
self.sbox = SBox(sbox_table)
self.pbox = PermutationBox(perm)
self.n_rounds = 3 # 2 full rounds + final
# Process master key
if isinstance(master_key, (int, np.integer)):
self.master_key_bits = int_to_bits(master_key, 28)
else:
self.master_key_bits = np.asarray(master_key, dtype=np.int32)
self.round_keys = key_schedule(self.master_key_bits)
def _apply_sboxes(self, state_bits):
"""Apply four parallel 4-bit S-boxes to a 16-bit state."""
out = np.zeros(16, dtype=np.int32)
for i in range(4):
nibble = bits_to_int(state_bits[4*i : 4*i + 4])
result = self.sbox.apply(nibble)
out[4*i : 4*i + 4] = int_to_bits(result, 4)
return out
def _apply_inv_sboxes(self, state_bits):
"""Apply four parallel inverse S-boxes."""
out = np.zeros(16, dtype=np.int32)
for i in range(4):
nibble = bits_to_int(state_bits[4*i : 4*i + 4])
result = self.sbox.inverse(nibble)
out[4*i : 4*i + 4] = int_to_bits(result, 4)
return out
def encrypt(self, plaintext):
"""
Encrypt a 16-bit plaintext.
Parameters
----------
plaintext : int or array-like
The plaintext (integer or 16-bit array).
Returns
-------
int
The 16-bit ciphertext as an integer.
"""
if isinstance(plaintext, (int, np.integer)):
state = int_to_bits(int(plaintext), 16)
else:
state = np.asarray(plaintext, dtype=np.int32)
# Rounds 1-2: key XOR -> S-boxes -> P-box
for r in range(2):
state = state ^ self.round_keys[r]
state = self._apply_sboxes(state)
state = self.pbox.apply(state)
# Round 3 (final): key XOR -> S-boxes -> key XOR (no P-box)
state = state ^ self.round_keys[2]
state = self._apply_sboxes(state)
state = state ^ self.round_keys[3]
return bits_to_int(state)
def decrypt(self, ciphertext):
"""
Decrypt a 16-bit ciphertext.
Parameters
----------
ciphertext : int or array-like
The ciphertext (integer or 16-bit array).
Returns
-------
int
The 16-bit plaintext as an integer.
"""
if isinstance(ciphertext, (int, np.integer)):
state = int_to_bits(int(ciphertext), 16)
else:
state = np.asarray(ciphertext, dtype=np.int32)
# Undo round 3: XOR K4 -> inverse S-boxes -> XOR K3
state = state ^ self.round_keys[3]
state = self._apply_inv_sboxes(state)
state = state ^ self.round_keys[2]
# Undo rounds 2, 1: inverse P-box -> inverse S-boxes -> XOR K_r
for r in range(1, -1, -1):
state = self.pbox.apply_inverse(state)
state = self._apply_inv_sboxes(state)
state = state ^ self.round_keys[r]
return bits_to_int(state)
def encrypt_track_rounds(self, plaintext):
"""
Encrypt and return intermediate states after each round.
Useful for studying diffusion across rounds.
Returns
-------
list of numpy arrays
States after each round (as 16-bit arrays).
"""
if isinstance(plaintext, (int, np.integer)):
state = int_to_bits(int(plaintext), 16)
else:
state = np.asarray(plaintext, dtype=np.int32)
states = [state.copy()]
for r in range(2):
state = state ^ self.round_keys[r]
state = self._apply_sboxes(state)
state = self.pbox.apply(state)
states.append(state.copy())
state = state ^ self.round_keys[2]
state = self._apply_sboxes(state)
state = state ^ self.round_keys[3]
states.append(state.copy())
return states
# --- Demonstration ---
SBOX_TABLE = [0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7]
PERM = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
# Use a sample 28-bit key
master_key = 0x3A94D63
spn = SPNetwork(SBOX_TABLE, PERM, master_key)
print("Heys Tutorial SPN")
print("=" * 50)
print(f"Master key: 0x{master_key:07X}")
print(f"Round keys:")
for i, rk in enumerate(spn.round_keys):
print(f" K{i+1} = {bits_to_int(rk):016b} (0x{bits_to_int(rk):04X})")
print()
# Encrypt and decrypt a sample plaintext
plaintext = 0x26B7
ciphertext = spn.encrypt(plaintext)
recovered = spn.decrypt(ciphertext)
print(f"Plaintext: 0x{plaintext:04X} ({plaintext:016b})")
print(f"Ciphertext: 0x{ciphertext:04X} ({ciphertext:016b})")
print(f"Decrypted: 0x{recovered:04X} ({recovered:016b})")
print(f"Correct: {plaintext == recovered}")
print()
# Verify over many random plaintexts
rng = np.random.default_rng(42)
n_tests = 1000
all_ok = True
for _ in range(n_tests):
pt = int(rng.integers(0, 2**16))
ct = spn.encrypt(pt)
dt = spn.decrypt(ct)
if dt != pt:
all_ok = False
break
print(f"Encrypt-decrypt consistency over {n_tests} random plaintexts: {all_ok}")
Heys Tutorial SPN
==================================================
Master key: 0x3A94D63
Round keys:
K1 = 0011101010010100 (0x3A94)
K2 = 1010100101001101 (0xA94D)
K3 = 1001010011010110 (0x94D6)
K4 = 0100110101100011 (0x4D63)
Plaintext: 0x26B7 (0010011010110111)
Ciphertext: 0xD2D3 (1101001011010011)
Decrypted: 0x26B7 (0010011010110111)
Correct: True
Encrypt-decrypt consistency over 1000 random plaintexts: True
14.6 Experiments#
We now study the cryptographic properties of the Heys SPN through a series of experiments: S-box nonlinearity, the avalanche effect, diffusion across rounds, and key schedule structure.
Experiment 1: S-box Nonlinearity via Walsh-Hadamard Transform#
The Walsh-Hadamard transform (WHT) of an S-box \(S\) measures the correlation between each linear function of the input and each linear function of the output. The Walsh coefficient for input mask \(a\) and output mask \(b\) is
where \(a \cdot x\) denotes the bitwise dot product modulo 2. A perfectly nonlinear S-box would have all Walsh coefficients equal to zero (for \(a, b \neq 0\)), but this is impossible for bijective S-boxes. The nonlinearity is defined as
Higher nonlinearity means greater resistance to linear cryptanalysis.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
class SBox:
def __init__(self, table):
self.table = np.array(table, dtype=np.int32)
self.size = len(table)
self.bits = int(np.log2(self.size))
def walsh_hadamard_spectrum(self):
n = self.size
W = np.zeros((n, n), dtype=np.int32)
for a in range(n):
for b in range(n):
total = 0
for x in range(n):
ax = bin(a & x).count('1') % 2
bs = bin(b & self.table[x]).count('1') % 2
total += (-1) ** (ax ^ bs)
W[a, b] = total
return W
HEYS_SBOX_TABLE = [0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7]
sbox = SBox(HEYS_SBOX_TABLE)
W = sbox.walsh_hadamard_spectrum()
fig, axes = plt.subplots(1, 2, figsize=(14, 5.5))
# Left: heatmap of Walsh spectrum
im = axes[0].imshow(W, cmap='RdBu_r', aspect='equal', vmin=-16, vmax=16,
interpolation='nearest')
axes[0].set_xlabel('Output mask $b$', fontsize=12)
axes[0].set_ylabel('Input mask $a$', fontsize=12)
axes[0].set_title('Walsh-Hadamard Spectrum $W_S(a, b)$', fontsize=13, fontweight='bold')
axes[0].set_xticks(range(16))
axes[0].set_xticklabels([f'{i:X}' for i in range(16)], fontsize=8)
axes[0].set_yticks(range(16))
axes[0].set_yticklabels([f'{i:X}' for i in range(16)], fontsize=8)
plt.colorbar(im, ax=axes[0], shrink=0.8)
# Annotate each cell with its value
for i in range(16):
for j in range(16):
color = 'white' if abs(W[i, j]) > 8 else 'black'
axes[0].text(j, i, str(W[i, j]), ha='center', va='center',
fontsize=6, color=color)
# Right: histogram of Walsh coefficient magnitudes (excluding a=0 or b=0)
W_sub = W[1:, 1:].flatten()
abs_vals = np.abs(W_sub)
unique_vals, counts = np.unique(abs_vals, return_counts=True)
axes[1].bar(unique_vals, counts, color='steelblue', edgecolor='black', linewidth=0.8,
width=0.8)
axes[1].set_xlabel('$|W_S(a, b)|$', fontsize=12)
axes[1].set_ylabel('Count', fontsize=12)
axes[1].set_title('Distribution of $|W_S(a,b)|$ for $a,b \\neq 0$',
fontsize=13, fontweight='bold')
axes[1].spines['top'].set_visible(False)
axes[1].spines['right'].set_visible(False)
# Add nonlinearity annotation
max_abs = int(np.max(abs_vals))
nl = 2**(sbox.bits - 1) - max_abs // 2
axes[1].annotate(f'Max $|W| = {max_abs}$\nNonlinearity = {nl}',
xy=(max_abs, counts[unique_vals == max_abs][0]),
xytext=(max_abs - 3, counts.max() * 0.8),
arrowprops=dict(arrowstyle='->', color='red', lw=1.5),
fontsize=11, color='red', fontweight='bold',
bbox=dict(boxstyle='round,pad=0.3', facecolor='lightyellow',
edgecolor='red', alpha=0.9))
plt.tight_layout()
plt.savefig('fig_14_1_walsh_spectrum.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
print(f"\nS-box nonlinearity: NL(S) = {nl}")
print(f"Maximum Walsh coefficient magnitude (a,b != 0): {max_abs}")
print(f"For a perfect 4-bit S-box, the theoretical maximum nonlinearity is 4.")
S-box nonlinearity: NL(S) = 2
Maximum Walsh coefficient magnitude (a,b != 0): 12
For a perfect 4-bit S-box, the theoretical maximum nonlinearity is 4.
Experiment 2: Avalanche Effect#
The avalanche effect is the most direct manifestation of diffusion. We flip a single bit in the plaintext and measure how many ciphertext bits change. Ideally, flipping one input bit should cause approximately half (8 out of 16) of the output bits to flip.
We measure the avalanche effect as a function of the number of rounds to see how diffusion builds up progressively.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
# --- Minimal SPN reimplementation for round-by-round analysis ---
SBOX_TABLE = np.array([0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7], dtype=np.int32)
PERM = np.array([0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15], dtype=np.int32)
def int_to_bits(value, n_bits):
return np.array([(value >> (n_bits - 1 - i)) & 1 for i in range(n_bits)], dtype=np.int32)
def bits_to_int(bits):
result = 0
for b in bits:
result = (result << 1) | int(b)
return result
def apply_sboxes(state, table):
out = np.zeros(16, dtype=np.int32)
for i in range(4):
nibble = bits_to_int(state[4*i:4*i+4])
result = table[nibble]
out[4*i:4*i+4] = int_to_bits(result, 4)
return out
def encrypt_partial(plaintext_int, round_keys, n_rounds):
"""Encrypt using only the first n_rounds rounds (out of 3)."""
state = int_to_bits(plaintext_int, 16)
rounds_done = min(n_rounds, 2)
for r in range(rounds_done):
state = state ^ round_keys[r]
state = apply_sboxes(state, SBOX_TABLE)
state = state[PERM]
if n_rounds >= 3:
state = state ^ round_keys[2]
state = apply_sboxes(state, SBOX_TABLE)
state = state ^ round_keys[3]
return state
# Generate round keys
rng = np.random.default_rng(2024)
master_key_bits = rng.integers(0, 2, size=28).astype(np.int32)
round_keys = [master_key_bits[4*i:4*i+16].copy() for i in range(4)]
# Measure avalanche for each round count
n_samples = 2000
max_rounds = 3
avalanche_data = np.zeros((max_rounds, n_samples))
for trial in range(n_samples):
pt = int(rng.integers(0, 2**16))
flip_bit = int(rng.integers(0, 16))
pt_flipped = pt ^ (1 << flip_bit)
for nr in range(1, max_rounds + 1):
ct_orig = encrypt_partial(pt, round_keys, nr)
ct_flip = encrypt_partial(pt_flipped, round_keys, nr)
diff = np.sum(ct_orig != ct_flip)
avalanche_data[nr - 1, trial] = diff
# Plot
fig, axes = plt.subplots(1, 2, figsize=(14, 5.5))
# Left: box plot
bp = axes[0].boxplot([avalanche_data[r, :] for r in range(max_rounds)],
labels=[f'Round {r+1}' for r in range(max_rounds)],
patch_artist=True, widths=0.5)
colors = ['#FFCDD2', '#FFE0B2', '#C8E6C9', '#BBDEFB']
for patch, color in zip(bp['boxes'], colors):
patch.set_facecolor(color)
patch.set_edgecolor('black')
axes[0].axhline(y=8, color='red', linestyle='--', alpha=0.7, label='Ideal (8 bits)')
axes[0].set_ylabel('Number of flipped ciphertext bits', fontsize=12)
axes[0].set_xlabel('Encryption depth', fontsize=12)
axes[0].set_title('Avalanche Effect by Round', fontsize=13, fontweight='bold')
axes[0].legend(fontsize=10)
axes[0].set_ylim(-0.5, 16.5)
axes[0].spines['top'].set_visible(False)
axes[0].spines['right'].set_visible(False)
# Right: mean avalanche with error bars
means = [np.mean(avalanche_data[r, :]) for r in range(max_rounds)]
stds = [np.std(avalanche_data[r, :]) for r in range(max_rounds)]
rounds = np.arange(1, max_rounds + 1)
axes[1].errorbar(rounds, means, yerr=stds, fmt='o-', color='#1565C0',
markersize=10, capsize=6, capthick=2, linewidth=2,
ecolor='gray', elinewidth=1.5, label='Measured mean')
axes[1].axhline(y=8, color='red', linestyle='--', alpha=0.7, linewidth=1.5,
label='Ideal (8 bits)')
axes[1].fill_between(rounds, [m - s for m, s in zip(means, stds)],
[m + s for m, s in zip(means, stds)],
alpha=0.15, color='#1565C0')
axes[1].set_xlabel('Number of rounds', fontsize=12)
axes[1].set_ylabel('Mean flipped bits', fontsize=12)
axes[1].set_title('Convergence to Ideal Avalanche', fontsize=13, fontweight='bold')
axes[1].set_xticks(rounds)
axes[1].set_ylim(0, 16)
axes[1].legend(fontsize=10)
axes[1].spines['top'].set_visible(False)
axes[1].spines['right'].set_visible(False)
# Annotate means
for r, m in enumerate(means):
axes[1].annotate(f'{float(m):.2f}', (r + 1, m), textcoords='offset points',
xytext=(15, 5), fontsize=10, fontweight='bold', color='#1565C0')
plt.tight_layout()
plt.savefig('fig_14_2_avalanche_effect.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
print("\nAvalanche statistics:")
for r in range(max_rounds):
print(f" Round {r+1}: mean = {float(means[r]):.3f}, std = {float(stds[r]):.3f}")
print(f"\nIdeal avalanche: 8.000 bits (half of 16-bit block)")
Avalanche statistics:
Round 1: mean = 2.426, std = 0.556
Round 2: mean = 5.914, std = 1.778
Round 3: mean = 7.732, std = 2.206
Ideal avalanche: 8.000 bits (half of 16-bit block)
Experiment 3: Diffusion Heatmap#
To visualize diffusion more precisely, we construct a diffusion matrix. For each input bit position \(i\) (0 through 15), we flip that single bit across many random plaintexts and record the probability that each output bit position \(j\) changes. After full diffusion, every entry of this matrix should be close to 0.5.
We show this matrix after each round to observe how diffusion spreads.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
# --- Redefine minimal SPN for this cell ---
SBOX_TABLE = np.array([0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7], dtype=np.int32)
PERM = np.array([0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15], dtype=np.int32)
def int_to_bits(value, n_bits):
return np.array([(value >> (n_bits - 1 - i)) & 1 for i in range(n_bits)], dtype=np.int32)
def bits_to_int(bits):
result = 0
for b in bits:
result = (result << 1) | int(b)
return result
def apply_sboxes(state, table):
out = np.zeros(16, dtype=np.int32)
for i in range(4):
nibble = bits_to_int(state[4*i:4*i+4])
out[4*i:4*i+4] = int_to_bits(table[nibble], 4)
return out
def encrypt_partial(plaintext_int, round_keys, n_rounds):
state = int_to_bits(plaintext_int, 16)
rounds_done = min(n_rounds, 2)
for r in range(rounds_done):
state = state ^ round_keys[r]
state = apply_sboxes(state, SBOX_TABLE)
state = state[PERM]
if n_rounds >= 3:
state = state ^ round_keys[2]
state = apply_sboxes(state, SBOX_TABLE)
state = state ^ round_keys[3]
return state
# Generate round keys
rng = np.random.default_rng(2024)
master_key_bits = rng.integers(0, 2, size=28).astype(np.int32)
round_keys = [master_key_bits[4*i:4*i+16].copy() for i in range(4)]
# Build diffusion matrices for each round
n_samples = 2000
max_rounds = 3
diffusion_matrices = []
for nr in range(1, max_rounds + 1):
D = np.zeros((16, 16), dtype=np.float64)
for input_bit in range(16):
for trial in range(n_samples):
pt = int(rng.integers(0, 2**16))
pt_flipped = pt ^ (1 << (15 - input_bit)) # flip bit (MSB-first)
ct_orig = encrypt_partial(pt, round_keys, nr)
ct_flip = encrypt_partial(pt_flipped, round_keys, nr)
D[input_bit, :] += (ct_orig != ct_flip).astype(np.float64)
D /= n_samples
diffusion_matrices.append(D)
# Plot
fig, axes = plt.subplots(1, 3, figsize=(16, 5))
for r in range(3):
im = axes[r].imshow(diffusion_matrices[r], cmap='YlOrRd', aspect='equal',
vmin=0, vmax=1, interpolation='nearest')
axes[r].set_xlabel('Output bit position', fontsize=10)
axes[r].set_ylabel('Flipped input bit', fontsize=10)
axes[r].set_title(f'After Round {r+1}', fontsize=12, fontweight='bold')
axes[r].set_xticks(range(0, 16, 2))
axes[r].set_yticks(range(0, 16, 2))
fig.suptitle('Figure 14.3: Diffusion Matrices Across Rounds\n'
'(probability that output bit $j$ flips when input bit $i$ is flipped)',
fontsize=14, fontweight='bold', y=1.05)
cbar = fig.colorbar(im, ax=axes, shrink=0.8, label='P(bit flip)')
plt.tight_layout()
plt.savefig('fig_14_3_diffusion_heatmap.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
print("Mean diffusion probability per round (ideal = 0.500):")
for r in range(3):
print(f" Round {r+1}: {float(diffusion_matrices[r].mean()):.4f}")
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_13474/3557090400.py:84: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect.
plt.tight_layout()
Mean diffusion probability per round (ideal = 0.500):
Round 1: 0.1522
Round 2: 0.3712
Round 3: 0.4815
Experiment 4: Key Schedule Visualization#
The key schedule determines which bits of the master key are used in each round. In the Heys tutorial SPN, the key schedule is simple: the 28-bit master key is sliced into four overlapping 16-bit windows, each shifted by 4 bits. We visualize which master key bits contribute to each round key.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
# Key schedule: K_i uses master key bits [4*i : 4*i + 16]
n_round_keys = 4
master_key_len = 28
round_key_len = 16
# Build the contribution matrix: which master key bits go into which round key
contribution = np.zeros((n_round_keys, master_key_len), dtype=np.int32)
for i in range(n_round_keys):
start = 4 * i
contribution[i, start:start + round_key_len] = 1
fig, ax = plt.subplots(figsize=(14, 4))
cmap = plt.cm.colors.ListedColormap(['#ECEFF1', '#1565C0'])
im = ax.imshow(contribution, cmap=cmap, aspect='auto', interpolation='nearest')
ax.set_xlabel('Master Key Bit Position', fontsize=12, fontweight='bold')
ax.set_ylabel('Round Key', fontsize=12, fontweight='bold')
ax.set_yticks(range(n_round_keys))
ax.set_yticklabels([f'$K_{{{i+1}}}$' for i in range(n_round_keys)], fontsize=12)
ax.set_xticks(range(master_key_len))
ax.set_xticklabels(range(master_key_len), fontsize=7)
ax.set_title('Figure 14.4: Key Schedule -- Master Key Bit Usage per Round Key',
fontsize=13, fontweight='bold')
# Annotate the start/end of each round key window
for i in range(n_round_keys):
start = 4 * i
end = start + round_key_len - 1
ax.text(start + round_key_len / 2 - 0.5, i,
f'bits [{start}:{end}]', ha='center', va='center',
fontsize=9, color='white', fontweight='bold')
# Add a color bar
from matplotlib.patches import Patch
legend_elements = [Patch(facecolor='#ECEFF1', edgecolor='black', label='Not used'),
Patch(facecolor='#1565C0', edgecolor='black', label='Used')]
ax.legend(handles=legend_elements, loc='upper right', fontsize=10)
# Add grid
ax.set_xticks(np.arange(-0.5, master_key_len, 1), minor=True)
ax.set_yticks(np.arange(-0.5, n_round_keys, 1), minor=True)
ax.grid(which='minor', color='gray', linewidth=0.5)
ax.tick_params(which='minor', size=0)
plt.tight_layout()
plt.savefig('fig_14_4_key_schedule.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
print("Key schedule summary:")
for i in range(n_round_keys):
start = 4 * i
print(f" K{i+1}: master key bits [{start}:{start + round_key_len - 1}]")
print(f"\nNote: Each master key bit is used in at most 4 round keys.")
print(f"Bit overlap between consecutive keys: 12 bits (out of 16).")
Key schedule summary:
K1: master key bits [0:15]
K2: master key bits [4:19]
K3: master key bits [8:23]
K4: master key bits [12:27]
Note: Each master key bit is used in at most 4 round keys.
Bit overlap between consecutive keys: 12 bits (out of 16).
Experiment 5: Comparing S-boxes – Good vs. Poor Design#
To appreciate the importance of S-box design, we compare the Heys S-box against two alternatives:
The identity S-box (\(S(x) = x\)), which provides no confusion at all.
A linear S-box (\(S(x) = Ax\), matrix multiplication over \(\mathrm{GF}(2)\)), which has zero nonlinearity.
We visualize the Walsh spectrum of each to highlight the difference.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
def compute_walsh(table):
"""Compute the full Walsh-Hadamard spectrum for a 4-bit S-box."""
table = np.array(table, dtype=np.int32)
n = len(table)
W = np.zeros((n, n), dtype=np.int32)
for a in range(n):
for b in range(n):
total = 0
for x in range(n):
ax = bin(a & x).count('1') % 2
bs = bin(b & table[x]).count('1') % 2
total += (-1) ** (ax ^ bs)
W[a, b] = total
return W
def compute_nonlinearity(W, m=4):
"""Compute nonlinearity from Walsh spectrum."""
W_sub = W[1:, 1:]
max_abs = np.max(np.abs(W_sub))
return 2**(m - 1) - max_abs // 2
# Three S-boxes to compare
sboxes = {
'Heys (nonlinear)': [0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7],
'Identity (trivial)': list(range(16)),
'Linear (affine)': [0x0, 0x5, 0xA, 0xF, 0x3, 0x6, 0x9, 0xC,
0x7, 0x2, 0xD, 0x8, 0x4, 0x1, 0xE, 0xB],
}
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
for idx, (name, table) in enumerate(sboxes.items()):
W = compute_walsh(table)
nl = compute_nonlinearity(W)
im = axes[idx].imshow(W, cmap='RdBu_r', aspect='equal', vmin=-16, vmax=16,
interpolation='nearest')
axes[idx].set_title(f'{name}\nNL = {nl}', fontsize=12, fontweight='bold')
axes[idx].set_xlabel('Output mask $b$', fontsize=10)
axes[idx].set_ylabel('Input mask $a$', fontsize=10)
axes[idx].set_xticks(range(0, 16, 2))
axes[idx].set_yticks(range(0, 16, 2))
# Annotate cells
for i in range(16):
for j in range(16):
color = 'white' if abs(W[i, j]) > 8 else 'black'
axes[idx].text(j, i, str(W[i, j]), ha='center', va='center',
fontsize=5, color=color)
fig.suptitle('Figure 14.5: Walsh-Hadamard Spectra -- Nonlinear vs. Linear vs. Identity S-boxes',
fontsize=14, fontweight='bold', y=1.02)
fig.colorbar(im, ax=axes, shrink=0.8, label='Walsh coefficient $W_S(a,b)$')
plt.tight_layout()
plt.savefig('fig_14_5_sbox_comparison.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()
print("Nonlinearity comparison:")
for name, table in sboxes.items():
W = compute_walsh(table)
nl = compute_nonlinearity(W)
max_w = np.max(np.abs(W[1:, 1:]))
print(f" {name:25s}: NL = {nl}, max|W| = {max_w}")
print("\nThe identity and linear S-boxes have NL = 0, meaning they can be")
print("perfectly approximated by a linear function -- making the cipher")
print("trivially vulnerable to linear cryptanalysis.")
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_13474/1667953564.py:62: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect.
plt.tight_layout()
Nonlinearity comparison:
Heys (nonlinear) : NL = 2, max|W| = 12
Identity (trivial) : NL = 0, max|W| = 16
Linear (affine) : NL = 0, max|W| = 16
The identity and linear S-boxes have NL = 0, meaning they can be
perfectly approximated by a linear function -- making the cipher
trivially vulnerable to linear cryptanalysis.
14.7 XOR Encryption and Perfect Secrecy#
Before block ciphers, the simplest symmetric encryption is the XOR cipher (one-time pad). Shannon proved in 1949 that the one-time pad achieves perfect secrecy – the ciphertext reveals no information whatsoever about the plaintext – provided the key is at least as long as the message and is used only once.
Theorem 14.1 (Shannon, 1949)
A cryptosystem \((\mathcal{P}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})\) achieves perfect secrecy if and only if \(|\mathcal{K}| \geq |\mathcal{P}|\), and for every plaintext \(m\) and ciphertext \(c\) with \(\Pr[C = c] > 0\),
The XOR cipher (one-time pad) with uniformly random keys achieves this bound with equality.
However, perfect secrecy requires keys as long as the message – impractical for most applications. Block ciphers trade perfect secrecy for computational security with short, reusable keys.
import numpy as np
def xor_encrypt(plaintext_bytes, key_bytes):
"""
XOR encryption (one-time pad).
Parameters
----------
plaintext_bytes : numpy array of uint8
key_bytes : numpy array of uint8 (must be same length)
Returns
-------
numpy array of uint8 (ciphertext)
"""
return np.bitwise_xor(plaintext_bytes, key_bytes)
def xor_decrypt(ciphertext_bytes, key_bytes):
"""XOR decryption is identical to encryption."""
return np.bitwise_xor(ciphertext_bytes, key_bytes)
# Demonstration
message = "BLOCK CIPHERS"
plaintext = np.array([ord(c) for c in message], dtype=np.uint8)
rng = np.random.default_rng(42)
key = rng.integers(0, 256, size=len(plaintext), dtype=np.uint8)
ciphertext = xor_encrypt(plaintext, key)
recovered = xor_decrypt(ciphertext, key)
print("XOR Encryption (One-Time Pad) Demonstration")
print("=" * 55)
print(f"Plaintext: '{message}'")
print(f" {list(plaintext)}")
print(f"Key: {list(key)}")
print(f"Ciphertext: {list(ciphertext)}")
print(f"Decrypted: '{''.join(chr(b) for b in recovered)}'")
print(f"Correct: {np.array_equal(plaintext, recovered)}")
print()
print("Key reuse vulnerability:")
msg1 = np.array([ord(c) for c in "ATTACK AT DAWN"], dtype=np.uint8)
msg2 = np.array([ord(c) for c in "DEFEND AT DUSK"], dtype=np.uint8)
key_reused = rng.integers(0, 256, size=len(msg1), dtype=np.uint8)
c1 = xor_encrypt(msg1, key_reused)
c2 = xor_encrypt(msg2, key_reused)
# XOR of two ciphertexts = XOR of two plaintexts (key cancels)
c1_xor_c2 = np.bitwise_xor(c1, c2)
m1_xor_m2 = np.bitwise_xor(msg1, msg2)
print(f" c1 XOR c2 = {list(c1_xor_c2)}")
print(f" m1 XOR m2 = {list(m1_xor_m2)}")
print(f" Equal: {np.array_equal(c1_xor_c2, m1_xor_m2)}")
print(" -> The key cancels! An adversary can recover plaintext XOR differences.")
XOR Encryption (One-Time Pad) Demonstration
=======================================================
Plaintext: 'BLOCK CIPHERS'
[66, 76, 79, 67, 75, 32, 67, 73, 80, 72, 69, 82, 83]
Key: [136, 38, 217, 22, 205, 251, 33, 198, 193, 255, 145, 167, 97]
Ciphertext: [202, 106, 150, 85, 134, 219, 98, 143, 145, 183, 212, 245, 50]
Decrypted: 'BLOCK CIPHERS'
Correct: True
Key reuse vulnerability:
c1 XOR c2 = [5, 17, 18, 4, 13, 15, 0, 0, 0, 0, 0, 20, 4, 5]
m1 XOR m2 = [5, 17, 18, 4, 13, 15, 0, 0, 0, 0, 0, 20, 4, 5]
Equal: True
-> The key cancels! An adversary can recover plaintext XOR differences.
14.8 Exercises#
Exercise 14.1 (S-box Properties). Consider the Heys tutorial S-box \(S = [\text{0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7}]\).
(a) Verify by hand (or by code) that \(S\) is a permutation on \(\{0, 1, \ldots, 15\}\).
(b) Compute the difference distribution table (DDT): for each input difference \(\Delta x \in \{0, \ldots, 15\}\) and output difference \(\Delta y \in \{0, \ldots, 15\}\), count the number of pairs \((x, x')\) with \(x \oplus x' = \Delta x\) and \(S(x) \oplus S(x') = \Delta y\).
(c) What is the maximum value in the DDT (excluding the trivial entry \(\mathrm{DDT}[0][0] = 16\))? This value determines the S-box’s resistance to differential cryptanalysis.
Hint
The DDT can be computed as follows: for each input difference \(\Delta x\) and each input value \(x\), compute \(x' = x \oplus \Delta x\), then \(\Delta y = S(x) \oplus S(x')\). Increment \(\mathrm{DDT}[\Delta x][\Delta y]\). The maximum entry in the Heys S-box DDT (excluding row 0) is 4, which means that for any nonzero input difference, no output difference occurs with probability greater than \(4/16 = 1/4\).
Exercise 14.2 (Permutation Layer Design). The Heys permutation \(\pi(i) = 4(i \bmod 4) + \lfloor i/4 \rfloor\) can be viewed as transposing a \(4 \times 4\) matrix of bits.
(a) Write out the full permutation table and verify that \(\pi\) is an involution (i.e., \(\pi(\pi(i)) = i\) for all \(i\)).
(b) Explain why this particular permutation achieves good diffusion: after one round, each S-box receives one output bit from each of the four S-boxes of the previous round.
(c) Design an alternative 16-bit permutation that does not achieve good diffusion (e.g., one where the first S-box’s outputs all feed into the same S-box in the next round). Implement it and show that the avalanche effect is significantly worse.
Hint
For part (a), note that transposing a matrix twice returns the original. The Heys permutation maps \(\text{bit } 4i + j \mapsto \text{bit } 4j + i\), which is a matrix transpose. For part (c), try the identity permutation \(\pi(i) = i\) – this means each S-box feeds only into itself, so there is no cross-S-box diffusion. The avalanche effect will be confined to 4-bit groups.
Exercise 14.3 (Avalanche Criterion). The strict avalanche criterion (SAC) states that flipping any single input bit should cause each output bit to flip with probability exactly \(\frac{1}{2}\).
(a) Does the Heys S-box alone (one application, no key mixing) satisfy the SAC? Test empirically.
(b) Show that after a sufficient number of SPN rounds, the full cipher approximately satisfies the SAC. How many rounds are needed?
(c) Prove that for a random permutation on \(\{0,1\}^n\), the expected number of output bits that change when one input bit is flipped is \(n/2\).
Hint
For part (a), test all 16 inputs: for each input \(x\) and each bit position \(i\), flip bit \(i\) to get \(x' = x \oplus 2^i\), compute \(S(x) \oplus S(x')\), and check whether each output bit flips with probability 1/2 over all choices of \(x\). A 4-bit S-box generally cannot satisfy the SAC perfectly. For part (c), use the fact that for a random permutation, \(S(x)\) and \(S(x')\) are approximately independent, so each output bit has an equal chance of being 0 or 1 in the XOR.
Exercise 14.4 (Key Schedule Weakness). The Heys tutorial SPN uses a simple sliding-window key schedule.
(a) How many master key bits does each round key share with its neighbor? What fraction of each round key overlaps with the next?
(b) Argue that this key schedule is weak: if an attacker recovers bits of one round key, they learn bits of neighboring round keys for free.
(c) Design an improved key schedule that uses the S-box to introduce nonlinearity. Describe your design and explain why it would resist the attack in part (b).
Hint
For part (a), consecutive round keys \(K_i\) and \(K_{i+1}\) share 12 out of 16 bits, since \(K_{i+1}\) starts 4 bits later in the master key. This means 75% of each round key is shared with the next. For part (c), consider applying the S-box to parts of each round key and XORing with a round constant (similar to the AES key schedule). This ensures that knowledge of one round key does not directly reveal bits of another.
Exercise 14.5 (Full SPN Analysis – Challenge). Implement a function that encrypts all \(2^{16} = 65536\) possible plaintexts under a fixed key using the Heys tutorial SPN.
(a) Verify that the encryption function is indeed a permutation: all 65536 ciphertexts are distinct.
(b) Compute the cycle structure of this permutation. (A permutation of \(\{0, \ldots, N-1\}\) can be decomposed into disjoint cycles.) How many cycles are there, and what are their lengths?
(c) Compare the cycle structure to that of a random permutation of 65536 elements. A random permutation of \(N\) elements has approximately \(\ln(N)\) cycles on average. Is the SPN’s cycle structure consistent with a pseudorandom permutation?
Hint
To find cycles, start at element 0, follow \(x \to E_k(x) \to E_k(E_k(x)) \to \cdots\) until you return to 0. Record the cycle length. Then start at the smallest element not yet visited and repeat. For \(N = 65536\), the expected number of cycles in a random permutation is \(\ln(65536) \approx 11.1\), and the expected length of the longest cycle is approximately \(0.6243 \cdot N \approx 40917\).
14.9 Summary#
In this chapter, we have studied the fundamental design principles underlying modern block ciphers.
Key concepts:
Confusion (achieved by S-boxes) ensures a complex, nonlinear relationship between the key and the ciphertext. The quality of an S-box is measured by its nonlinearity (via the Walsh-Hadamard transform) and its differential uniformity.
Diffusion (achieved by P-boxes and linear mixing layers) ensures that each plaintext bit influences many ciphertext bits. The avalanche effect quantifies diffusion: ideally, flipping one input bit causes half the output bits to change.
The Substitution-Permutation Network (SPN) is a block cipher architecture that alternates S-box substitution with P-box permutation over multiple rounds. Each round also mixes in a round key derived from the master key via a key schedule.
The Heys tutorial SPN provides a minimal, analyzable example: 16-bit block, 28-bit key, 3 rounds, with a 4-bit S-box and a bit-transposition P-box.
Perfect secrecy (Shannon, 1949) requires keys as long as the message. Block ciphers sacrifice perfect secrecy for practical key sizes, relying instead on computational security through iterated confusion and diffusion.
Looking ahead. In Chapter 15, we will use the SPN implemented here as the target for linear cryptanalysis, exploiting linear approximations of the S-box to recover key bits. In Chapter 16, we will mount a differential cryptanalysis attack on the same cipher, exploiting input-output difference patterns through the S-box.
Important
The interplay between confusion and diffusion is not merely a design heuristic – it is the reason why modern block ciphers resist the two most powerful generic attacks: linear cryptanalysis and differential cryptanalysis. Understanding this interplay is essential for both designing and breaking block ciphers.
14.10 References#
Claude E. Shannon, “Communication Theory of Secrecy Systems,” Bell System Technical Journal, 28(4), pp. 656–715, 1949. The foundational paper establishing information-theoretic cryptography. Shannon introduced confusion and diffusion as the two essential properties of a secure cipher and proved that perfect secrecy requires keys at least as long as the message.
Howard M. Heys, “A Tutorial on Linear and Differential Cryptanalysis,” Cryptologia, 26(3), pp. 189–221, 2002. An accessible and widely-cited tutorial that introduces a simple SPN cipher (the one implemented in this chapter) and demonstrates linear and differential cryptanalysis on it. The S-box and permutation used here are taken directly from this paper.
Horst Feistel, “Cryptography and Computer Privacy,” Scientific American, 228(5), pp. 15–23, May 1973. Feistel’s influential article describing the design principles behind the Lucifer cipher and what later became the DES. This paper introduced the Feistel network structure to the broader scientific community.
Horst Feistel, William A. Notz, and J. Lynn Smith, “Some Cryptographic Techniques for Machine-to-Machine Data Communications,” Proceedings of the IEEE, 63(11), pp. 1545–1554, 1975. A more technical treatment of the Feistel cipher design, including discussion of key scheduling and iterative design.
Eli Biham and Adi Shamir, “Differential Cryptanalysis of DES-like Cryptosystems,” Journal of Cryptology, 4(1), pp. 3–72, 1991. The paper that introduced differential cryptanalysis, one of the two most important generic attacks on block ciphers. The resistance of an S-box to this attack is measured by its difference distribution table (DDT).
Mitsuru Matsui, “Linear Cryptanalysis Method for DES Cipher,” Advances in Cryptology – EUROCRYPT ‘93, LNCS vol. 765, pp. 386–397, Springer, 1994. The paper that introduced linear cryptanalysis. The Walsh-Hadamard spectrum and nonlinearity of the S-box, studied in this chapter, directly determine a cipher’s resistance to this attack.
Douglas R. Stinson and Maura B. Paterson, Cryptography: Theory and Practice, 4th edition, CRC Press, 2018. Chapters 4 and 6 provide rigorous treatments of block cipher design, the SPN and Feistel structures, and the mathematical foundations of S-box analysis.