Questions: Random Number Generation in Cryptography

Question 1

The Debian OpenSSL bug (2006-2008) commented out a line that mixed process memory into the random seed, reducing the effective entropy to the process ID (~15 bits). What was the practical impact?

Model answer: With only ~32,768 possible seeds (2^15 process IDs), all SSH and TLS keys generated on affected Debian/Ubuntu systems came from a set of ~32,768 possible keys per key type and size. An attacker could pre-compute all possible keys and test each against any target server in seconds. Every key generated during the affected period had to be revoked and regenerated. This demonstrated that a single line of code affecting randomness can compromise millions of systems.

The bug persisted for nearly two years because the code change appeared to fix a Valgrind warning — it was a plausible maintenance commit. No one noticed the catastrophic security impact until a researcher generated all possible keys and found matches on production servers. The lesson: randomness is a single point of failure, and its correctness is not visible from the outside.

Question 2

A developer seeds a PRNG with the current time in seconds. Why is this insecure even if the PRNG algorithm itself is cryptographically strong?

• A. The current time changes too fast for the PRNG to process
• B. Time in seconds provides at most ~20-30 bits of entropy (the attacker can estimate when the key was generated to within a plausible time window). A CSPRNG cannot create entropy — it can only expand existing entropy. If the seed has 30 bits of entropy, the output has 30 bits of entropy regardless of the PRNG quality
• C. Time-based seeds cause the PRNG to produce negative numbers
• D. The PRNG algorithm needs at least 256 bits of input to function

Answer: (B)

Entropy is a property of the seed, not the algorithm. A CSPRNG with a 128-bit truly random seed produces output that is computationally indistinguishable from random. The same CSPRNG with a predictable seed produces predictable output. If the attacker knows the key was generated sometime in 2024, that's about 31.5 million seconds — roughly 25 bits of entropy. They can try all possible seeds in seconds. This is why entropy sources must be genuinely unpredictable physical processes.

Question 3

Why should developers use OS-provided CSPRNGs (/dev/urandom on Linux, BCryptGenRandom on Windows) rather than implementing their own?

• A. OS CSPRNGs are faster than user-space implementations
• B. OS CSPRNGs continuously mix entropy from multiple hardware sources, are maintained by security experts, are hardened against state compromise, and have been extensively audited. Custom implementations are likely to have entropy collection bugs, reseeding failures, or state leakage that the developer won't detect
• C. User-space PRNGs are illegal in most jurisdictions
• D. OS CSPRNGs use quantum random number generators

Answer: (B)

Randomness is one of the hardest things to get right in cryptography because failures are silent — weak randomness produces output that looks random to the developer but is predictable to an attacker. OS CSPRNGs have been battle-tested, receive continuous security patches, and integrate with hardware random number generators when available. The Dual_EC_DRBG scandal showed that even NIST-standardized PRNGs can contain backdoors, but OS-level implementations are the most scrutinized option available.

Question 4

/dev/random and /dev/urandom on Linux differ in that /dev/random blocks when the entropy pool is estimated to be depleted, while /dev/urandom never blocks. For cryptographic key generation, /dev/urandom is the correct choice.

• T. True
• F. False

Answer: True

This is counterintuitive — it seems like /dev/random should be 'more secure' because it waits for entropy. But the entropy estimation is unreliable, and once a CSPRNG is properly seeded (which happens early in boot), its output is computationally indistinguishable from true randomness regardless of the estimated entropy level. /dev/random's blocking causes availability issues (programs hang waiting for entropy) without providing meaningful additional security. The Linux kernel developers explicitly recommend /dev/urandom for all purposes except very early boot randomness.

Question 5

Dual_EC_DRBG was standardized by NIST in 2006 and later revealed to contain a likely NSA backdoor. What made the backdoor possible?

Model answer: Dual_EC_DRBG uses two elliptic curve points P and Q. If the relationship between P and Q is known (specifically, if someone knows the discrete logarithm e such that Q = eP), the holder of e can predict all future outputs from a short observation of the generator's output. NIST specified particular P and Q values without justifying their choice. If NSA generated Q = eP for a known e, they could predict any Dual_EC_DRBG output. The design also had an output truncation that was shorter than necessary, making the backdoor exploitable from observing just 32 bytes of output.

The mathematical backdoor was identified by Shumow and Ferguson in 2007, but NIST did not withdraw the standard. The Snowden leaks (2013) confirmed NSA had paid RSA Security $10 million to make Dual_EC_DRBG the default in their BSAFE library. This episode permanently damaged trust in government-standardized cryptographic algorithms and motivated the development of fully transparent standards processes.