Contact Us

Entropy (Cryptography)

Field: Security · Also called: cryptographic entropy, randomness, entropy source, min-entropy

In cryptography, entropy is a measure of the disorder, randomness, or variability in a closed system, usually stated in bits: a value with n bits of entropy is as unpredictable as a uniformly random n-bit value.

Why it matters

Encryption keys, the random values in a salt, session tokens, and the nonces used in protocols such as TLS are only as strong as they are unpredictable. NIST’s random bit generation standards, SP 800-90A and SP 800-90B, define entropy as “a measure of the disorder, randomness or variability in a closed system.” NIST’s digital identity guidelines, SP 800-63-4, state the same idea from the attacker’s side: “the amount of uncertainty that an attacker faces to determine the value of a secret.” A 128-bit key generated with 128 bits of entropy leaves an attacker 2128 equally likely possibilities. The same key generated from a predictable seed, such as the time of day, has far less entropy than its length suggests, however random its bytes look.

Entropy sources and random bit generators

Computers are deterministic, so the uncertainty has to come from outside the program: an entropy source, such as electrical noise in hardware, timing variations, or noise in a camera’s image sensor. NIST SP 800-90B specifies how entropy sources for random bit generation are designed and tested, and says they are intended to be combined with the deterministic random bit generator (DRBG) mechanisms of NIST SP 800-90A. The entropy source provides a seed; the DRBG, a cryptographically secure pseudorandom number generator, stretches it into as many random bits as are needed.

LavaRand is a well-known example of a physical entropy source: camera images of lava lamps and other chaotic motion, hashed to seed a generator.

Min-entropy

Because an attacker guesses the most likely value first, cryptography measures entropy by the worst case. NIST SP 800-90B uses min-entropy, which it describes as “a lower bound on its entropy” and “often used as a worst-case measure of the unpredictability of a random variable.” For a source whose most likely output has probability p, the min-entropy is −log2 p bits. A source that produces one value half of the time has at most 1 bit of min-entropy per sample, however many bits each sample contains.

Physical computers vs. virtual machines

An operating system gathers entropy from the physical world around it. Human interaction is one of the richest sources: the Linux kernel’s random number generator has long listed “inter-keyboard timings” and “inter-interrupt timings from some interrupts” among its sources, and it feeds in the timing of events from the input layer, which carries keystrokes and mouse movement. A headless server or a virtual machine usually has no one typing or moving a mouse, so it has fewer of those sources to gather from, especially right after it boots. In 2012, Heninger, Durumeric, Wustrow, and Halderman found they could remotely recover the private RSA keys of 0.50% of the TLS hosts they scanned, because the keys shared prime factors. Nearly all of the affected machines were headless embedded devices, such as routers and server management cards, that generated keys on first boot and lacked the physical entropy sources that PCs use.

Virtual machines add a problem of their own: a snapshot copies the state of the guest’s random number generator along with everything else. In 2010, Ristenpart and Yilek showed that resuming a virtual machine from the same snapshot more than once can make it reuse the same “random” values, and demonstrated attacks on widely used TLS clients and servers, including recovering a server’s DSA signing key.

The usual remedy is to seed the guest from the host, which has the physical sources. A virtio random number generator device, supported by QEMU and libvirt, “allows the host to pass through entropy to guest operating systems.”

History

  • 1948: Claude Shannon’s paper A Mathematical Theory of Communication uses entropy as a measure of information and uncertainty, the sense in which cryptography uses the word.
  • 2010: Ristenpart and Yilek’s NDSS paper When Good Randomness Goes Bad describes virtual machine reset vulnerabilities.
  • 2012: Heninger, Durumeric, Wustrow, and Halderman’s USENIX Security paper Mining Your Ps and Qs reports weak keys generated at first boot on embedded devices.
  • 2018: NIST published SP 800-90B, Recommendation for the Entropy Sources Used for Random Bit Generation.
  • 2025: NIST SP 800-63-4 gives the attacker-side definition quoted above.

Sources

See also