Entropy: measuring, estimating, and testing true randomness

The random number generation module covers Shannon entropy — the average amount of surprise across a whole distribution. For cryptography, that average is the wrong thing to optimize: an attacker doesn't need to guess the average outcome, they only need to guess the single most likely one. Min-entropy measures exactly that worst case — the unpredictability contributed by a source's most probable outcome — and it's always less than or equal to Shannon entropy for the same distribution, often substantially less.

A concrete example makes the gap obvious. Take a biased coin that lands heads 90% of the time and tails 10%. Its Shannon entropy is about 0.47 bits — already well below the 1 bit of a fair coin. Its min-entropy, though, is −log₂(0.9) ≈ 0.152 bits: more than three times lower, because min-entropy is driven entirely by the 90% outcome an attacker would simply guess every time. Cryptographic key material is sized against this stricter figure, not the Shannon average, precisely because an attacker plays the worst-case game, not the average-case one.

Knowing the formula for min-entropy doesn't tell you the min-entropy of a real physical noise source — you only have a finite sample of its output, never its true underlying probability distribution. NIST SP 800-90B (“Recommendation for the Entropy Sources Used for Random Bit Generation”) is the standard that defines how to estimate it anyway: a battery of statistical estimators, each designed to catch a different kind of weakness a noise source might have, with the final assessed min-entropy taken as the minimum across every estimator that runs — because any single estimator catching a problem is reason enough to distrust the source.

The standard's main “non-IID” track defines ten such estimators in total, covering everything from simple frequency bias to repeated substrings to how well a predictor algorithm can guess upcoming bits from past ones. The Entropy Testing Playground tool on this site implements three of them — Most Common Value, Collision, and Markov — ported directly from NIST's own reference source code rather than re-derived, so you can run real entropy estimators against either a bit string you type in or bits fetched live from a hardware quantum random number generator and watch the numbers move.

A CSPRNG (covered in the random number generation module) is fundamentally deterministic: given the same seed, it produces the same output forever — its security comes entirely from that seed being unpredictable and from the algorithm's output being computationally infeasible to distinguish from random. A true random number generator (TRNG) is a different kind of thing altogether: a physical process believed to be genuinely non-deterministic, sampled directly. Thermal (Johnson–Nyquist) noise in a resistor, jitter between unsynchronized ring oscillators, radioactive decay timing, and quantum vacuum fluctuations — the mechanism behind the ANU Quantum Random Numbers Server this site's Entropy Testing tool can pull live bits from — are all real TRNG entropy sources in production use today.

Raw TRNG output is almost never used directly, though, and this is exactly where SP 800-90B earns its keep: a physical noise source typically has some measurable bias or correlation (a resistor's thermal noise might run slightly warmer in one direction, say), so its raw bitstream needs testing — the whole point of the estimators above — and then conditioning through a cryptographic whitening step before it's trusted as a seed. The simplest such step is the von Neumann extractor: look at the input two bits at a time, output nothing for 00 or 11, output a 0 for 01, and a 1 for 10. It removes simple bias at the cost of throwing away roughly three-quarters of the raw bits, which is precisely the trade an assessed, tested min-entropy figure lets an engineer reason about instead of guessing at.

Operating systems maintain an internal entropy pool, fed by the physical sources covered above, and expose it to applications through platform APIs — the random number generation module covers calling them correctly. Linux historically offered two interfaces with different philosophies: /dev/random would block (pause the calling program) once its internal entropy estimate ran low, prioritizing never handing out output that might be guessable, while /dev/urandom would keep producing output from its CSPRNG regardless, on the reasoning that once properly seeded, a CSPRNG's output is cryptographically indistinguishable from true randomness. Since Linux 3.17 the getrandom() syscall largely resolved the debate: it blocks only once, until the pool has been seeded for the first time ever, then behaves like /dev/urandom from then on — a never-ending block was never actually buying extra security, just availability problems.

The real failure mode isn't the blocking-versus-non-blocking debate — it's boot-time entropy starvation on embedded and IoT devices. A device that generates its first SSH host key or TLS certificate moments after boot, before its entropy pool has gathered any real unpredictability from disk timing or network jitter (because it may have neither), can produce keys from a far smaller effective keyspace than its key size suggests. This is exactly the failure researchers found at internet scale in 2012: millions of embedded devices sharing RSA and DSA keys because they'd generated them from identical, barely-seeded entropy pools at first boot — a hardware-and-timing echo of the 2008 Debian OpenSSL bug covered in the random number generation module, but found in the wild rather than introduced by a single patch.

Entropy measurement isn't only for machines — it's exactly how to reason about passphrase strength honestly. Diceware generates a passphrase by rolling physical dice to pick words from a published 7,776-word list (7,776 = 6⁵, hence five dice rolls per word) and stringing several words together. Because each word is drawn uniformly from a fixed list, the entropy calculation is the same log₂(N) formula from the random number generation module — applied per word, then summed.

This is also a useful contrast with that module's 8-character password example: a passphrase built from real words looks far less random to a human eye than a string of mixed-case letters and symbols, yet can carry substantially more entropy, precisely because each unit (a word from 7,776 options) contributes far more bits than a single character from a 94-key keyboard — a direct illustration of why entropy, not apparent complexity, is the figure that actually matters.