Entropy Starvation & Weak-Key Bugs

Entropy starvation occurs when a system lacks sufficient unpredictable input to seed its CSPRNG. This happens on newly booted embedded devices, virtualized servers, or systems with no user input. The RNG output becomes predictable.

In 2006, a Debian developer removed a line flagged by Valgrind: MD_Update(&m, buf, j). This line was the entropy source. The result: OpenSSL on Debian only seeded with the PID (max 32,768 values). All keys generated 2006-2008 are in a set of 32,768 possibilities.

RSA, DSA, and ECDSA keys, SSH host keys, TLS certificates, and SSL VPN keys generated on Debian/Ubuntu systems 2006-2008 were compromised. Affected systems: Debian Etch, Debian Lenny, Ubuntu 7.04-8.04. Blacklists were published; certificates revoked.

VMs can be cloned with identical disk state. If both VMs generate keys from the same CSPRNG state, they produce the same keys. Hypervisors now inject entropy via VirtIO RNG or ACPI tables, but poorly configured VMs still face this risk at boot.

IoT devices (routers, cameras) often generate SSH/TLS keys at first boot before accumulating entropy. Studies found millions of devices sharing a few thousand RSA key pairs because they all seeded from the same low-entropy boot state.

Lenstra et al. (2012) collected 11.7 million TLS certificates and computed pairwise GCDs. Found 12,720 RSA keys sharing a prime factor — meaning both keys could be fully factored. 0.2% of all public keys were broken. Cause: insufficient boot entropy.

ECDSA requires a unique random nonce k per signature. If k is reused (or weak), the private key is immediately recoverable: d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n. Sony's PS3 used k=constant — all games could be signed with the recovered key.

Java SecureRandom on Android 4.x was seeded with system time in certain conditions. Multiple Bitcoin wallet apps generated signatures with the same k nonce, leaking private keys. Millions of dollars were stolen. Google patched SecureRandom implementation.

Tools: ssh-vulnkey (checks against Debian weak key blacklist), badkeys (checks TLS certs for known-weak primes), GCD-batch algorithm for bulk RSA key auditing. Certificate Transparency logs enable population-scale analysis.

Use getrandom(GRND_RANDOM) at first key generation. Read from /dev/urandom after waiting for initial seeding (check /proc/sys/kernel/random/entropy_avail > 128). Use hardware RNG (RDRAND) as supplemental entropy. Never generate keys at first boot without delay.

Persist CSPRNG state across reboots: save 32 bytes from /dev/urandom to a seed file at shutdown; read and feed back at boot. This provides continuity of entropy across cold boots. Linux does this automatically; embedded systems often do not.

What was the root cause of the Debian OpenSSL entropy bug?

Entropy starvation causes predictable keys. Real breaks: Debian OpenSSL (PID-only seed), IoT GCD attacks, PS3 ECDSA nonce reuse, Android Bitcoin wallet. Always seed from OS entropy; audit embedded key generation carefully. Next: generating keys, nonces, and IVs safely.