ISE Cryptography — Quiz Solutions
L02: Stream Ciphers
10 questions · 1 mark each · 10 marks total.
Q01: PRG definition
Which of the following correctly describes a pseudo-random generator (PRG) as defined in the lecture?
Answer:
An efficient, deterministic algorithm that maps a seed to an output.
Q02: 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.
Q03: Stream cipher construction
A stream cipher built from a PRG \(G\) is defined by \(E(s, m) = G(s) \oplus m\). Which statement best explains why the security of this construction depends 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.
Q04: Nonce purpose
A stream cipher \(E(s, m) = G(s) \oplus m\) 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.
Q05: Why RC4 is deprecated
The lecture identified several concrete weaknesses in RC4 that led to its deprecation from TLS. Which statement best describes the primary reason RC4 is unsuitable for modern cryptographic use?
Answer:
The keystream it produces has statistical biases, particularly in the early bytes, which leak information about the plaintext.
Q06: Stream cipher XOR
You are using a toy stream cipher \(E(s, m) = G(s) \oplus m\). For your chosen seed \(s\), the PRG produces the keystream \(G(s) = 11010110\). You want to encrypt the plaintext \(m = 10011100\). What is the resulting ciphertext?
Answer:
\(01001010\)
Working: \(11010110 \oplus 10011100 = 01001010\).
Q07: Proof by reduction
Suppose someone gives a reduction showing that any adversary who wins the semantic security game against a stream cipher \(\mathcal{E}\) built from a PRG \(G\) can be converted into an adversary that distinguishes \(G(s)\) from a truly random string with the same advantage. Assuming \(G\) is a secure PRG, what does this proof let us conclude about \(\mathcal{E}\)?
Answer:
It is semantically secure, because an attack on the cipher would contradict the assumption that \(G\) is a secure PRG.
Why: The reduction is a contrapositive argument. If \(\mathcal{E}\) were not semantically secure, there would exist an adversary with non-negligible advantage against \(\mathcal{E}\), which the reduction converts into a distinguisher against \(G\) with the same advantage — contradicting \(G\)’s security.
Q08: Bit commitment hiding
In the PRG-based bit commitment scheme from the lecture, Bob commits to a bit \(b_0\) by sending \(c \leftarrow \text{com}(s, r, b_0)\), where \(\text{com}(s, r, 0) = G(s)\) and \(\text{com}(s, r, 1) = G(s) \oplus r\). Which property follows directly from \(G\) being a secure PRG?
Answer:
Hiding: Alice cannot learn anything about \(b_0\) from \(c\) alone.
Why: If \(G\) is a secure PRG, \(G(s)\) is indistinguishable from a uniform random string. Whether \(b_0 = 0\) (so \(c = G(s)\)) or \(b_0 = 1\) (so \(c = G(s) \oplus r\), which is also uniform since \(r\) is random), Alice sees a uniformly distributed string in either case.
Q09: Mersenne Twister
A developer chooses the Mersenne Twister as the random number generator for a cryptographic key derivation routine. Why is this choice insecure, even though the Mersenne Twister has a very long period and passes most standard statistical test suites?
Answer:
After observing enough consecutive outputs, an adversary can reconstruct the internal state and predict every future output.
Why: 624 consecutive 32-bit outputs are sufficient to reconstruct the full 19937-bit MT state. Statistical tests measure properties of the output distribution, not an adversary’s ability to predict from observed outputs — these are different things.
Q10: PRG composition tradeoff
The lecture compared \(n\)-wise parallel composition and \(n\)-wise sequential composition of a PRG. Both achieve the same security bound, but they differ in seed cost. Which of the following correctly identifies that difference?
Answer:
Sequential composition uses a single seed of length \(\lambda\), while parallel composition uses \(n\) independent seeds each of length \(\lambda\).