ISE Cryptography — Midterm Solutions
L01–L03 · MCQs and Written Responses
Structure: 25 MCQs (2 marks each, 50 marks) + 5 written responses (10 marks each, 50 marks) = 100 marks total.
Part 1: Multiple Choice Questions
Lecture 1 — Shannon Ciphers and Semantic Security
Q01: Kerckhoffs’s Principle
Under Kerckhoffs’s Principle, the security of a cryptosystem must rest entirely on one component being kept secret from the adversary. Which component is it?
Answer:
The key.
Q02: Shannon cipher correctness
Let \(\mathcal{E} = (E, D)\) be a Shannon cipher defined over key space \(\mathcal{K}\), message space \(\mathcal{M}\), and ciphertext space \(\mathcal{C}\). Which equation expresses the correctness property of \(\mathcal{E}\)?
Answer:
\(D(k, E(k, m)) = m\) for all \(k \in \mathcal{K}\) and \(m \in \mathcal{M}\).
Q03: Uniform keys and the OTP
The proof that the one-time pad is perfectly secure relies on the key being sampled uniformly at random from \(\{0,1\}^L\). Suppose instead the key is drawn from a biased distribution. What specifically goes wrong in the proof?
Answer:
Different plaintexts produce a given ciphertext with different probabilities, so observing the ciphertext reveals information about which plaintext was encrypted.
Q04: Many-time pad
Alice encrypts two different plaintexts \(m_1\) and \(m_2\) with the same one-time pad key \(k\), producing ciphertexts \(c_1\) and \(c_2\). What can Eve compute from \(c_1\) and \(c_2\) alone?
Answer:
\(m_1 \oplus m_2\), because the keys cancel when the ciphertexts are combined.
Q05: Key length and perfect security
A student proposes a Shannon cipher with \(\mathcal{K} = \{0,1\}^{120}\) and \(\mathcal{M} = \{0,1\}^{192}\), with a uniformly sampled key and efficient \(E\) and \(D\). Which assessment is correct?
Answer:
It cannot be perfectly secure for these spaces, regardless of how \(E\) and \(D\) are defined.
Q06: Semantic security advantage
An adversary \(\mathcal{A}\) plays the semantic-security attack game against cipher \(\mathcal{E}\) as defined in L01, guessing the challenger’s message correctly with probability \(0.80\). What is \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}]\)?
Answer:
\(0.60\)
Working: Anchor the formula at the two extremes. A win probability of 50% gives \(\text{SS}_\text{adv} = 0\) (pure guessing, no advantage). A win probability of 100% gives \(\text{SS}_\text{adv} = 1\). The L01 formula \(|2p - 1|\) fits both: \(|2(0.5) - 1| = 0\) and \(|2(1) - 1| = 1\). Applying it here: \(|2(0.80) - 1| = |0.60| = 0.60\).
Equivalently: if \(\mathcal{A}\) wins with probability \(0.80\), it loses with probability \(0.20\). The advantage is \(|\Pr[\text{correct}] - \Pr[\text{incorrect}]| = |0.80 - 0.20| = 0.60\). This is the same formula — \(|p - (1-p)| = |2p - 1|\) — just written in terms of the two outcome probabilities directly.
Q07: Post-processing a semantically secure cipher
Cipher \(\mathcal{E} = (E, D)\) is semantically secure. Define \(\mathcal{E}' = (E', D')\) where \(E'(k, m) = E(k, m) \| 0^\ell\) and \(D'\) strips the \(\ell\) trailing bits before running \(D\). Is \(\mathcal{E}'\) semantically secure?
Answer:
Yes, because appending a public, message-independent constant to every ciphertext cannot help any adversary distinguish encryptions of \(m_0\) from encryptions of \(m_1\).
Q08: Shannon vs computational ciphers
A classmate claims Shannon ciphers and computational ciphers are the same thing under different names. What is the correct critique?
Answer:
Every deterministic computational cipher is a Shannon cipher, but a probabilistic computational cipher need not be.
Lecture 2 — PRGs and Stream Ciphers
Q09: PRG definition
Which statement correctly describes a pseudo-random generator (PRG)?
Answer:
An efficient, deterministic algorithm that maps a seed to an output.
Q10: The security parameter
In the stream cipher security framework, what role does the security parameter \(\lambda\) play?
Answer:
The bit length of the seed or key; security advantages are required to be negligible as a function of this length.
Q11: Stream cipher construction
A stream cipher is defined by \(E(s, m) = G(s) \oplus m\). Why does security depend on \(G\) being a secure PRG?
Answer:
If \(G\) is secure, \(G(s)\) is indistinguishable from a uniformly random string, so the ciphertext is indistinguishable from a one-time pad ciphertext.
Q12: Nonce purpose
A stream cipher is extended to take a nonce alongside the key, producing a fresh keystream for each (key, nonce) pair. Which problem does the nonce solve?
Answer:
It allows multiple messages to be encrypted under the same key without producing identical keystreams.
Q13: Stream cipher XOR
Alice uses \(E(s, m) = G(s) \oplus m\) with keystream \(G(s) = 00111011\) and plaintext \(m = 11010100\). What is the ciphertext?
Answer:
\(11101111\)
Working: \(00111011 \oplus 11010100 = 11101111\).
Q14: Proof by reduction
A proof shows that any efficient adversary with non-negligible advantage \(\epsilon\) against \(E = G(s) \oplus m\) yields a PRG distinguisher against \(G\) with the same advantage. Given that \(G\) is a secure PRG, what can we conclude about \(E\)?
Answer:
\(E\) is semantically secure, because a successful attack on \(E\) would contradict the assumption that \(G\) is a secure PRG.
Q15: Mersenne Twister
A developer builds a session-token generator using Python’s random.Random (Mersenne Twister), arguing that the period exceeds the lifetime of the Earth and the output passes all statistical test suites. What is the correct critique?
Answer:
Once an attacker observes enough consecutive outputs, they can reconstruct the internal state and predict every future token.
Q16: PRG composition tradeoff
An engineer compares \(n\)-wise sequential and \(n\)-wise parallel compositions of a PRG \(G : \{0,1\}^\lambda \to \{0,1\}^L\) to produce \(n \cdot L\) bits. How do the two constructions differ in seed cost?
Answer:
Sequential composition uses a single seed of length \(\lambda\), while parallel composition uses \(n\) independent seeds each of length \(\lambda\).
Lecture 3 — Block Ciphers and Modes of Operation
Q17: AES block size
What is the block size of AES, regardless of which key length is used?
Answer:
128 bits.
Q18: DES key size
What is the size of a DES key?
Answer:
56 bits.
Q19: ECB mode and the penguin
When Tux the penguin is encrypted in ECB mode using AES, the outline remains visible in the ciphertext. Which statement best explains why?
Answer:
ECB mode encrypts each block independently, so identical plaintext blocks always produce identical ciphertext blocks.
Q20: PRP vs PRF
What is the essential difference between a pseudo-random permutation (PRP) and a pseudo-random function (PRF)?
Answer:
A PRP is invertible and therefore its outputs can never collide on distinct inputs, while a PRF’s outputs can collide.
Q21: CBC and IV unpredictability
CBC mode is IND-CPA secure only if the IV is chosen unpredictably at random. Suppose an implementation instead uses a counter-based IV. Why does this break IND-CPA security?
Answer:
Because predicting the IV lets the adversary cancel it inside a chosen-plaintext query, making CBC behave as a deterministic cipher.
Q22: Deterministic ciphers and IND-CPA
No deterministic cipher is IND-CPA secure. What is the adversary’s winning strategy in the IND-CPA game?
Answer:
The adversary submits a challenge pair \((m_0, m_1)\), receives \(c^*\), queries the oracle on \(m_0\), and checks whether the oracle’s response matches \(c^*\).
Q23: Birthday bound
A block cipher has a block size of 64 bits. Under the birthday bound, roughly how many encryptions under the same key can be performed before an output collision becomes likely?
Answer:
\(2^{32}\)
Q24: Feistel networks and invertibility
A Feistel network builds a block cipher using a round function \(f\). Why does this structure allow decryption even when \(f\) has no inverse?
Answer:
Because each round preserves one half of the state unchanged, so \(f\) can be recomputed on that half and its contribution XORed out.
Q25: Grover’s algorithm and AES
For AES-128, what is the effective security level against a quantum adversary running Grover’s algorithm?
Answer:
64 bits, because Grover’s algorithm provides a quadratic speedup over classical exhaustive key search.
Part 2: Written Response Questions
WR1 — Perfect Security and the One-Time Pad (10 marks)
Scenario: The one-time pad is the canonical example of a perfectly secure cipher. L01 introduced two distinct notions: perfect security (what the OTP achieves) and semantic security (the computational analogue).
(a) [1 mark] State the maximum semantic-security advantage permitted against a perfectly secure cipher. The bound applies to all adversaries, including those with unbounded computational power.
Answer:
Zero. \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}] = 0\) for every adversary \(\mathcal{A}\), without exception.
(b) [3 marks] Explain in prose what the OTP achieves that AES-CBC with a fresh random IV does not. Name the difference in which adversaries the two definitions constrain, the difference in the advantage each permits, and how at least one of these distinctions manifests in both the OTP and AES-CBC.
Answer:
Perfect security is an information-theoretic (unconditional) guarantee: the ciphertext distribution is independent of the plaintext, so any adversary (including one with unbounded computational power) has advantage exactly zero. Semantic security is a computational guarantee: only efficient (polynomial-time) adversaries are constrained, and their advantage must be negligible in the security parameter.
The OTP achieves the stronger guarantee unconditionally because the ciphertext \(c = k \oplus m\) is uniformly distributed over \(\{0,1\}^L\) regardless of \(m\), as long as \(k\) is uniform. AES-CBC cannot achieve this: its security rests on AES being a secure PRP, which is a computational assumption. An adversary with unbounded time could in principle break AES; no such adversary can gain any information from an OTP ciphertext.
(c) [3 marks] Give two distinct reasons why the OTP is impractical for everyday use.
Answer:
Key length. The key must be at least as long as the message. Encrypting \(N\) bits requires \(N\) bits of fresh key material, which is impractical for any realistic data volume.
No key reuse. Each key can be used to encrypt exactly one message. Reusing a key for two messages \(m_1, m_2\) produces ciphertexts \(c_1 = k \oplus m_1\) and \(c_2 = k \oplus m_2\), from which \(c_1 \oplus c_2 = m_1 \oplus m_2\), leaking a combination of the plaintexts and destroying perfect security entirely.
(d) [3 marks] Alice proposes: \(E(k, m) = (k \| k) \oplus m\) where \(k \in \{0,1\}^{L/2}\) and \(m \in \{0,1\}^L\). Is Alice’s scheme perfectly secure? Give a yes/no answer and justify using a result or argument from L01.
Answer:
No.
Key-length argument: The key space has size \(|\mathcal{K}| = 2^{L/2}\), while the message space has size \(|\mathcal{M}| = 2^L\). L01 proved that any perfectly secure Shannon cipher must satisfy \(|\mathcal{K}| \geq |\mathcal{M}|\). Since \(2^{L/2} < 2^L\) for any \(L > 0\), Alice’s scheme cannot be perfectly secure regardless of how \(E\) and \(D\) are defined.
Direct attack (alternative justification): Split the ciphertext \(c\) into two halves \(c_\text{top}\) and \(c_\text{bot}\), each \(L/2\) bits. Then \(c_\text{top} = k \oplus m_\text{top}\) and \(c_\text{bot} = k \oplus m_\text{bot}\), so \(c_\text{top} \oplus c_\text{bot} = m_\text{top} \oplus m_\text{bot}\). An adversary can compute this from the ciphertext alone, revealing non-trivial information about the plaintext. A perfectly secure cipher’s ciphertext must be statistically independent of the plaintext; this one is not.
WR2 — Nonce Reuse Incident (10 marks)
Scenario: A team uses ChaCha20 to encrypt log entries under a single long-lived key \(k\) with a unique 96-bit nonce per entry. A bug caused entries 3 and 7 to be encrypted under the same nonce. All ten ciphertexts are public.
(a) [2 marks] State precisely what information an attacker can compute about the plaintexts of entries 3 and 7 from the public ciphertexts alone.
Answer:
The attacker can compute \(m_3 \oplus m_7\): the XOR of the two plaintexts.
(b) [4 marks] Explain why this is computable. Reference the structure of the ChaCha20-style stream cipher and make clear the attack does not depend on any weakness in ChaCha20 itself.
Answer:
ChaCha20 is a stream cipher: \(E(k, n, m) = \text{ChaCha20}(k, n) \oplus m\). Since entries 3 and 7 share the same nonce, they were encrypted with the same keystream: \(\text{ChaCha20}(k, n_3) = \text{ChaCha20}(k, n_7)\). Call this common keystream \(z\).
Then \(c_3 = z \oplus m_3\) and \(c_7 = z \oplus m_7\). XORing the ciphertexts:
\[c_3 \oplus c_7 = (z \oplus m_3) \oplus (z \oplus m_7) = m_3 \oplus m_7\]
The keystream cancels entirely. No weakness in ChaCha20 is required: the attack follows from the algebraic structure of XOR-based encryption and is unavoidable whenever two messages share a (key, nonce) pair.
(c) [4 marks] Suppose the plaintext of entry 3 is English log text with predictable prefixes (timestamps, log levels). Sketch a concrete strategy for recovering the plaintext of entry 7.
Answer:
Compute the XOR. Calculate \(x = c_3 \oplus c_7 = m_3 \oplus m_7\).
Exploit the known prefix of \(m_3\). Log entries begin with a predictable timestamp and log-level field (e.g.
2024-01-15T14:32:01 INFO). Substitute the known bytes of \(m_3\) directly: \(x[i] \oplus m_3[i] = m_7[i]\) for each known position \(i\). This recovers the corresponding prefix of \(m_7\) immediately.Apply crib-dragging to the remainder. For the unknown portion, guess common English words or log-specific tokens (IP addresses, method names, status codes) at shifted positions. Each correct crib reveals the matching bytes of the other plaintext, which can then be fed forward as new cribs.
Use log-format structure as a constraint. Known field separators, field widths, and delimiters in the log schema narrow the plausible byte values at each position. Candidates that violate the schema (e.g. non-printable ASCII where a digit is expected) can be discarded, accelerating convergence.
Iterate. Each recovered portion of \(m_3\) immediately reveals the same-position bytes of \(m_7\), and vice versa. Recovery is self-reinforcing as more context accumulates.
WR3 — PRG Construction Critique (10 marks)
Scenario: Let \(G : \{0,1\}^\lambda \to \{0,1\}^L\) be a secure PRG. A student proposes \(G'(k) = G(k) \| G(k)\), producing \(2L\) bits by running \(G\) once and concatenating the output with itself.
(a) [1 mark] Is \(G'\) a secure PRG?
Answer:
No.
(b) [3 marks] Describe an efficient distinguishing adversary \(\mathcal{A}\) against \(G'\).
Answer:
\(\mathcal{A}\) on input \(y \in \{0,1\}^{2L}\):
- Split \(y\) into two \(L\)-bit halves: \(y_1 \leftarrow y[1 \ldots L]\) and \(y_2 \leftarrow y[L+1 \ldots 2L]\).
- Output 1 if \(y_1 = y_2\); output 0 otherwise.
This runs in linear time and requires no knowledge of the seed.
(c) [2 marks] State, in terms of \(L\), the advantage of the adversary from (b). Show how you arrived at the value.
Answer:
- When \(y = G'(k)\): \(y_1 = G(k)\) and \(y_2 = G(k)\), so \(y_1 = y_2\) always. \(\Pr[\mathcal{A} = 1] = 1\).
- When \(y \xleftarrow{R} \{0,1\}^{2L}\): The two halves are independent uniform \(L\)-bit strings, so \(\Pr[y_1 = y_2] = 2^{-L}\).
\[\text{PRG}_\text{adv}[\mathcal{A}, G'] = \left|1 - 2^{-L}\right| = 1 - 2^{-L}\]
This is overwhelming (approaches 1 as \(L\) grows) and is far from negligible.
(d) [4 marks] What does this example show about composing PRGs? Refer explicitly to the sequential and parallel composition constructions from L02.
Answer:
\(G'\) fails because it reuses the same seed \(k\) for both \(L\)-bit output halves. The two halves are not just correlated; they are identical. A truly uniform \(2L\)-bit string has independently random halves with overwhelming probability, so the duplication is immediately detectable.
The secure constructions from L02 avoid this by ensuring the output blocks are independent:
- Parallel composition uses \(n\) independent seeds \(k_1, \ldots, k_n\), each of length \(\lambda\), producing independent output blocks \(G(k_1), \ldots, G(k_n)\). Independence is guaranteed because the seeds are drawn separately.
- Sequential (chained) composition uses a single seed but feeds internal state forward: each evaluation of \(G\) on the current state produces both an output block and a fresh state for the next round. No two blocks share a seed or state.
\(G'\) satisfies neither property: it has a single seed and no forward state propagation, so both halves are generated from the same input and are trivially distinguishable from uniform.
WR4 — Mode Selection for a System (10 marks)
Scenario: A team is building an append-only audit log for a healthcare platform. Each log entry is a fixed-size 256-byte record encrypted at rest under a single key \(k\). Requirements: (1) frequent writes, rare decryption; (2) parallel decryption of large batches during an audit; (3) one corrupt record must not prevent others from being decrypted. The modes under consideration are ECB, CBC, and CTR.
(a) [2 marks] Give a principled reason to rule out ECB. Appeal to a property of ECB, not just the penguin example.
Answer:
ECB is deterministic given the key: identical plaintext blocks always produce identical ciphertext blocks. This leaks plaintext equality across and within records, which is a real information leak for structured log entries that may share fields, headers, or common values. More formally, no deterministic cipher is IND-CPA secure: an adversary can simply re-encrypt \(m_0\) using the encryption oracle and check whether the result matches the challenge ciphertext \(c^*\), winning the IND-CPA game with advantage 1.
(b) [4 marks] Compare CBC and CTR on two dimensions.
Answer:
Parallelisability of encryption
CTR encryption computes \(c_i = E_k(\text{nonce} \| i) \oplus p_i\) for each block independently. There are no data dependencies between blocks, so all blocks can be encrypted in parallel. CBC encryption computes \(c_i = E_k(p_i \oplus c_{i-1})\), which requires the previous ciphertext block before the current one can be encrypted. Encryption must proceed sequentially. CTR has a clear advantage for high-throughput write workloads.
IV/nonce discipline
CBC requires the IV to be unpredictable (uniformly random) for each message. A predictable IV (e.g. a counter) lets an adversary cancel it inside a chosen-plaintext query, reducing CBC to a deterministic cipher and breaking IND-CPA security entirely. CTR requires only that the nonce be unique per (key, message) pair; a simple counter suffices and is safe. CTR’s discipline is easier to satisfy correctly in practice.
(c) [4 marks] Recommend either CBC or CTR. Address each of the three system requirements.
Answer:
CTR.
Frequent writes / rare decryption. CTR encryption is fully parallelisable and operates as a stream cipher with no padding requirement. High write throughput is achievable with no per-record overhead beyond the nonce. CBC encryption is sequential within a record and requires PKCS#7 padding, adding up to 16 bytes per record.
Parallel batch decryption during an audit. CTR decryption is \(p_i = E_k(\text{nonce} \| i) \oplus c_i\) for each block independently. Both individual blocks and entire records can be decrypted in parallel across a batch with no ordering constraints.
Independent per-record decryption. Each CTR record is self-contained: decryption depends only on that record’s nonce and ciphertext blocks. A corrupt record has no effect on any other record. There is no inter-record chaining.
WR5 — Error Propagation Across Modes (10 marks)
Scenario: A three-block ciphertext \(c = (c_1, c_2, c_3)\) is transmitted over a noisy network. Exactly one bit flips inside block \(c_2\); \(c_1\), \(c_3\), and the IV (where present) arrive intact.
(a) [3 marks] ECB mode.
Answer:
Only \(p_2\) is corrupted. \(p_1\) and \(p_3\) are received intact.
The corruption in \(p_2\) is random-looking: the single bit flip in \(c_2\) produces a completely scrambled output from \(D_k\), not a single-bit flip. This is expected because AES behaves as a pseudorandom permutation; any change to the input diffuses unpredictably through the block.
ECB decrypts each block independently as \(p_i = D_k(c_i)\). Block \(i\) depends only on \(c_i\), so a flip in \(c_2\) cannot affect \(p_1\) or \(p_3\).
(b) [3 marks] CBC mode.
Answer:
- \(p_1\) is intact (it uses only the IV and \(c_1\), both undamaged).
- \(p_2\) is random-looking: the flipped \(c_2\) scrambles \(D_k(c_2)\) entirely, and \(p_2 = D_k(c_2) \oplus c_1\) inherits that randomness.
- \(p_3\) has exactly one bit flipped at the same position as the original flip in \(c_2\).
The CBC decryption formula is \(p_i = D_k(c_i) \oplus c_{i-1}\). The flip in \(c_2\) affects \(p_3 = D_k(c_3) \oplus c_2\) directly via the XOR: since \(c_3\) is intact, \(D_k(c_3)\) is correct, and the flip propagates unchanged from \(c_2\) into \(p_3\).
(c) [2 marks] CTR mode.
Answer:
Only \(p_2\) is affected. Exactly one bit is flipped in \(p_2\), at the same position as the original flip in \(c_2\). \(p_1\) and \(p_3\) are intact.
CTR decryption is \(p_i = E_k(\text{nonce} \| i) \oplus c_i\). The keystream \(E_k(\text{nonce} \| 2)\) is computed correctly regardless of \(c_2\); XORing with the flipped \(c_2\) flips exactly the same bit in \(p_2\).
(d) [2 marks] Which mode minimises the number of plaintext bits corrupted by a single-bit transmission error?
Answer:
CTR. A single ciphertext bit flip produces exactly one corrupted plaintext bit (same position, \(p_2\) only). This is strictly fewer than ECB, where the flip randomises all 128 bits of \(p_2\), and CBC, where the flip randomises all 128 bits of \(p_2\) and also flips one bit in \(p_3\) (approximately 129 bits corrupted total).