Question 1 of 7: Symmetric Ciphers — One-Time Pad, Stream Ciphers, and Block-Cipher Modes

Question 1: Symmetric Ciphers — One-Time Pad, Stream Ciphers, and Block-Cipher Modes (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part a) — the one-time pad. A one-time pad (OTP) encrypts a plaintext by combining it, bit by bit (or character by character), with a truly random key — the pad — that is at least as long as the message, using a reversible operation such as XOR: $C_i = P_i \oplus K_i$. The receiver recovers the plaintext with the identical operation, $P_i = C_i \oplus K_i$, using its own copy of the same pad. Security depends on the pad being (1) truly random (not produced by any algorithm), (2) at least as long as the plaintext, and (3) used exactly once and then destroyed. When all three hold, the scheme achieves perfect (information-theoretic) secrecy: every possible plaintext of that length is equally consistent with the observed ciphertext under some key, so an attacker with unlimited computing power learns nothing about the message from the ciphertext alone.

Part b) — stream ciphers, and turning a block cipher into one. A stream cipher approximates the one-time pad with a much shorter, reusable secret key: a keystream generator (a deterministic pseudorandom-number generator seeded by the key and typically a nonce) produces a keystream $K_1, K_2, \dots$ one symbol at a time, combined with the plaintext the same way as the pad, $C_i = P_i \oplus K_i$, and decrypted identically by regenerating the same keystream from the shared key. A block cipher (e.g. AES) instead encrypts fixed-size blocks under a keyed, invertible transformation and, used on its own (ECB/CBC modes), must wait for a full block of plaintext before it can encrypt anything. It can be turned into a stream cipher by using it purely as the keystream generator, via a feedback or counter mode of operation: in output feedback (OFB) mode the cipher repeatedly re-encrypts its own previous output, $O_i = E_K(O_{i-1})$, and each $O_i$ is XORed with a plaintext symbol, $C_i = P_i \oplus O_i$; in cipher feedback (CFB) mode the previous ciphertext is fed back and re-encrypted, $C_i = P_i \oplus E_K(C_{i-1})$; and in counter (CTR) mode the cipher encrypts a nonce concatenated with an incrementing counter, $C_i = P_i \oplus E_K(\text{nonce} \,\|\, i)$, so blocks can even be generated out of order. All three let the block cipher produce a byte- or bit-level keystream, exactly as a native stream cipher would.

Part c) — advantage and disadvantage of the OTP versus a stream cipher. Advantage: the OTP offers unconditional (information-theoretic) security that does not depend on any assumption about an attacker's computing power or on the presumed hardness of a mathematical/algorithmic problem; a stream cipher's security is only computational — it rests on the keystream generator (whether purpose-built or a block cipher run in OFB/CFB/CTR mode) being unpredictable to a realistic attacker, and can in principle be weakened by cryptanalysis of the generator or by keystream reuse (e.g. the historical RC4/WEP failures). Disadvantage: the OTP's key must be truly random, as long as the entire message, and used only once, making key generation, distribution and storage impractical for anything beyond small, occasional exchanges; a stream cipher instead reuses one short key (with fresh nonces) across an arbitrarily long stream and across many sessions, which is what makes it practical for real systems such as secure network links.