Entropy Sources and the Path from Randomness to a Key

A 128-bit key generated from a source with 30 bits of entropy is a 30-bit key. The bytes look random, they pass every statistical test applied to them, and they are enumerable by anyone willing to try a billion seeds. Nothing downstream — the cipher, the protocol, the hardware boundary — recovers the difference. Key generation is therefore a security boundary rather than a formatting step, and the engineering that matters sits in the entropy path, not in the key encoding.

A key inherits the strength of its seed

Entropy measures the number of equally likely states an attacker must consider. A source with H bits of entropy produces one of 2^H outcomes, so guessing costs on the order of 2^H trials. For a key, the security level is bounded by the smaller of the entropy and the key length: a 256-bit key drawn from 128 bits of entropy yields 128-bit security and no more.

The failure is invisible in the artifact. A key built from a process identifier, a millisecond timestamp, and a counter is 32 bytes long and has exactly the right shape. Its real uncertainty may be under 30 bits, which is a search a single machine completes quickly. Because the output is a valid key, no format check, length check, or statistical test flags it.

Two properties get conflated at this point. Unpredictability concerns the next output given everything observed so far. Uniformity concerns the distribution over the whole output space. A block cipher applied to an incrementing counter produces perfectly uniform-looking blocks that are entirely predictable. A generator seeded once at boot is unpredictable to an attacker who never learns the seed and completely transparent to one who reads it later, along with every output derived from it.

The practical consequence is that key generation has to draw from a source whose state is not derivable from observable values, and it has to do so close to the point of use. Keys generated elsewhere, or earlier, carry the assumptions of that other place and time.

From interrupt timing to a conditioned pool

A general-purpose operating system has no dedicated physical randomness device on most hardware, so it manufactures entropy from timing jitter: the low-order bits of interrupt arrival times, disk completion ordering, keyboard and mouse events, and differences between cycle counters on different cores. Each event contributes a small and unknown amount, typically a fraction of a bit to a few bits. The kernel credits these contributions against a target, mixes them into a pool, and only then allows the pool to seed a cryptographic generator.

On Linux the interface is getrandom(2), added in kernel 3.17. It blocks until the generator has been initialized, which the kernel allows once it has credited 256 bits of entropy. After initialization, calls return bytes from the ChaCha20-based generator without further blocking. The GRND_NONBLOCK flag turns the initial wait into an immediate EAGAIN failure, which lets a caller detect that the pool is not yet ready instead of stalling.

The historical split between /dev/random and /dev/urandom no longer reflects two different generators. Since Linux 5.6, /dev/random blocks only until initialization and thereafter behaves like /dev/urandom; the earlier behaviour, where reads from /dev/random could block for a long time once the entropy estimate was exhausted, was removed because the estimate was never a good predictor of output quality. The two device nodes now differ mainly in legacy semantics, not in cryptographic strength.

Virtual machines need explicit help. A guest has few physical interrupt sources and may boot from an image that many other guests also boot from, so paravirtualized random devices and host-supplied seed data are standard. A snapshot restore is the sharper case: the resumed guest continues from the generator state captured in the image, and if the same snapshot is resumed on several machines, each starts from the same state. The kernel mixes in fresh data on resume, but the ordering guarantee is weak, and any key generated in the first moments after a resume deserves suspicion.

The same hazard exists inside a single process. A userspace generator seeded once and then copied by fork(2) produces identical streams in parent and child. Libraries that keep a global random state without an explicit reseed hook on fork are a recurring source of duplicated keys, and the fix is to draw from the kernel per use rather than to maintain private state.

Deterministic generators do not add entropy

Once seeded, a deterministic random bit generator expands the seed into arbitrarily many bytes. NIST SP 800-90A specifies three families — hash-based, HMAC-based, and counter-mode — with a common lifecycle: instantiate with a seed, generate output, reseed at intervals, and optionally re-instantiate. The seed length is fixed per mechanism, and the standard caps the number of requests between reseeds at 2^48. That cap is not a performance limit; it bounds the amount of output an attacker can collect under one seed.

The standard distinguishes two resistance properties. Prediction resistance means an attacker who compromises the internal state cannot predict subsequent output, which requires a reseed from a fresh entropy source before each request. Backtracking resistance means an attacker who compromises the state cannot recover earlier output, which is achieved by discarding or overwriting state as it is used. A generator can provide the second without the first, and most operating system generators do exactly that: they rekey the underlying stream cipher after producing output, so past bytes stay hidden, while new entropy arrives slowly from the environment.

The distinction matters when choosing a generator for a long-lived service. A generator that reseeds only on a timer is vulnerable for the whole interval after a state compromise. A generator that reseeds per request pays a syscall or a hardware read each time. The trade is latency and complexity against the window of exposure.

Sampling a uniform value from uniform bytes

Uniform bytes do not directly give uniform values in an arbitrary range. Mapping an 8-bit value onto three outcomes by taking the remainder modulo 3 produces counts of 86, 86, and 84 out of 256: the first two outcomes are each more likely by 2/256. The bias is small, and it is exactly the kind of small bias that breaks a scheme whose security argument assumes uniformity, particularly when many values are sampled, as in prime generation or nonce selection.

Rejection sampling removes the bias at the cost of discarding some output. Draw enough bits to cover the range, and retry when the value falls outside it:

import secrets

def uniform_below(n: int) -> int:
    """Uniform integer in [0, n) with no modulo bias."""
    bits = n.bit_length()
    while True:
        candidate = secrets.randbits(bits)   # bits of fresh randomness
        if candidate < n:                    # reject the partial top slice
            return candidate

The expected number of iterations is below two whenever n is more than half of 2^bits, so the cost is bounded and small. The alternative — multiply-and-shift or floating-point scaling — reintroduces bias at a finer granularity and is harder to reason about.

The same principle governs structured keys. Generating an RSA prime means sampling a candidate of the correct bit length with the top bits set, testing for primality, and retrying; generating an elliptic curve scalar means sampling below the group order, not truncating a longer value. In both cases the sampling routine, not the generator, decides whether the resulting key is uniformly distributed over the intended set.

Where generation breaks

The failures cluster into four patterns. The first is a source with no real uncertainty: an embedded device that boots deterministically, has no interrupt jitter worth the name, and seeds its generator from a fixed constant. Devices manufactured from the same image then produce the same keys, and a single recovered key exposes every device of that build.

The second is state duplication. Snapshots, cloned disks, and forked processes copy generator state along with everything else. The keys are different only if something forces new entropy into the copy before the first draw.

The third is insufficient input. A routine that asks for 16 bytes and receives 16 bytes is fine; one that asks for 16 and silently accepts a short read, or ignores a negative return value, may proceed with uninitialized or partially filled buffers. Checking the return value and the byte count is the entire defence, and it is routinely omitted.

The fourth is a non-cryptographic generator used because it was nearby. Language-level random functions are built for simulation and games: their state is small, their output is predictable from a few observations, and their seeding is often derived from the clock. None of them is a substitute for the operating system generator.

A workable rule is to obtain key material from the kernel interface at the moment of use, request exactly the number of bytes needed, verify that the call succeeded and filled the buffer, and treat the availability of entropy as a dependency to be monitored rather than assumed. Keys derived from a seed rather than drawn directly — the case for password-derived keys and for keys expanded from a master secret — are covered in password-based key derivation and in envelope encryption, where the seed itself becomes the object that must be protected.