ENTROPY SOURCES

Why correct cryptographic code can still generate weak keys at the moment a device first starts.

A key is not strong because it is long. It is strong because an adversary cannot narrow the set from which it was drawn.

That distinction is invisible in the artifact. A 2,048-bit RSA modulus generated from a weak source has the expected length, passes structural parsing and can be placed in a valid certificate. The defect is in the distribution, and the distribution cannot be reconstructed from one output.

This is why major failures of this kind have been found by collecting public keys and comparing populations.

The measurement that framed the problem

In 2012, Heninger, Durumeric, Wustrow and Halderman scanned the public IPv4 address space for TLS and SSH services. They collected 5.8 million unique TLS certificates from 12.8 million hosts and 6.2 million unique SSH host keys from 10.2 million hosts.

The aggregate revealed several distinct failures:

• 5.57 percent of TLS hosts and 9.60 percent of SSH hosts used keys repeated in an apparently vulnerable manner, including manufacturer defaults and low-entropy generation.
• Shared factors exposed RSA private keys for 0.50 percent of TLS hosts and 0.03 percent of SSH hosts.
• Repeated DSA signature randomness exposed keys used by 1.03 percent of SSH hosts in the principal scan results.
• Among 11,170,883 distinct RSA moduli, 2,314 distinct prime factors divided 16,717 public keys.
• One consumer-router model appeared 90,779 times with the same certificate.

The RSA attack is elementary. If two moduli share one prime, their greatest common divisor reveals it and both moduli factor. The difficult part is scale. A product-tree and remainder-tree batch GCD replaces a prohibitive pairwise comparison with a computation that the researchers completed across roughly eleven million moduli in less than two hours.

The failure is therefore a property of a population. One device cannot determine from its own public key that another unit generated a related key.

Boot is the dangerous moment

Many embedded products create a long-term host key on first boot or after a factory reset. At that instant, the units are most alike.

The firmware image may be byte-for-byte identical. The clock may not be set. Network interfaces have only just initialized. There may be no user input, persistent seed or useful timing variation. If thousands of devices request cryptographic output at the same point in the same startup sequence, the generator is being asked to distinguish units before the environment has done so.

Modern Linux offers a precise semantic distinction. A default call to getrandom() blocks until the urandom source has been initialized. A call with GRND_NONBLOCK returns an error instead. The current Linux manual still warns that an early read from /dev/urandom may return before pool initialization and recommends getrandom() when this matters.

The right behavior can look like an availability problem: key generation waits. The wrong behavior can look perfectly healthy: it returns immediately and creates a key that will fail only when compared with the rest of the fleet.

Two failures that look like bad randomness

Not every weak-key population originates in an empty entropy pool.

Debian OpenSSL, CVE-2008-0166. A Debian-specific change removed data from OpenSSL’s seeding path. Keys generated by affected packages came from a small, enumerable space dominated by the process identifier. The code returned correctly formed RSA and DSA keys, but an attacker could precompute the candidates and recognize them later.

ROCA, CVE-2017-15361. An Infineon RSA library generated primes with a detectable algebraic structure. Randomness was not the reported defect. The structure made selected 1,024-bit and 2,048-bit keys factorable from the public modulus alone. The disclosure estimated a worst-case 2,048-bit factorization at 140.8 CPU-years on its reference processor, with cloud cost between 20,000 and 40,000 US dollars at the time.

The ROCA team reported about 760,000 confirmed vulnerable keys across identity documents, authentication tokens, trusted-boot devices, package signatures, TLS and PGP. A fast public-key fingerprint allowed a defender, or an attacker, to select affected keys before paying the cost of factorization.

The affected library was present in products certified under FIPS 140-2 and Common Criteria EAL 5+. Certification did not prevent a key-generation method from violating the distribution assumed by ordinary RSA security arguments.

Signature randomness is secret-key material

For DSA and ECDSA, the per-signature nonce is part of the private computation. Reusing it for two different message hashes under the same key permits direct algebraic recovery of the long-term private key. Consistent partial bias can also be exploitable with lattice techniques.

RFC 6979 removes dependence on fresh environmental entropy for each DSA or ECDSA signature by deriving the nonce from the private key and message hash. Ed25519 uses deterministic derivation as part of its design.

This closes an important failure mode. It does not make signing independent of randomness throughout the key lifecycle, and it does not remove physical leakage or fault risks. Hedged signatures mix fresh randomness into deterministic derivation so that a weak fresh source does not become the only protection. We examine that distinction separately in Determinism is not a substitute for entropy.

The arithmetic of enough

Where random values cannot be removed, their collision probability can be bounded. For a uniformly random 96-bit nonce used under one key, the probability of at least one collision after n encryptions is approximately:

p = 1 - exp(-n(n - 1) / 2^97)

At 2³² encryptions, the probability is close to 2^-33. At 2⁴⁸ encryptions, it is about 0.39.

The calculation assumes independent samples. A restored virtual-machine snapshot, cloned generator state or repeated factory image can reproduce values deterministically. In that case, the birthday model is answering the wrong question.

What a device should do

• Provision per-device seed material. A unique secret can bootstrap a generator before environmental sources mature. It also turns the manufacturing system into a key-management boundary that must prevent duplication and disclosure.
• Do not silently generate long-term keys before initialization. Block, fail visibly or defer the operation until the platform can establish that its random source is ready.
• Use an interface with initialization semantics. On Linux, prefer getrandom() or a library that correctly wraps it, and check every return value.
• Test the noise source, not only DRBG output. NIST SP 800-90B defines repetition-count and adaptive-proportion health tests for raw noise-source samples. A cryptographic DRBG can conceal a failed physical source behind output that still looks random.
• Reseed deliberately. Define what happens after reset, suspend, clone, restore and extended operation.
• Use deterministic or hedged signing where specified. The choice should follow the signature standard and the device’s exposure to fault and side-channel attacks.
• Treat cloning and restore as key-lifecycle events. If generator state can be duplicated, keys and nonce sequences may need to be regenerated.

The audit that uses only public data

An operator with a deployed fleet can test several population properties without extracting one private key:

1. Collect every public key with device model, firmware version, manufacturing batch and provisioning date.
2. Detect exact duplicate public keys across all algorithms.
3. Run batch GCD across all RSA moduli.
4. Apply published algorithm-specific fingerprints, including the ROCA detector, where relevant.
5. Search collected DSA and ECDSA signatures for repeated nonce components under the same public key.
6. Repeat cold-start key generation on a sample of identical devices and compare the resulting population.

These tests do not prove that a generator is sound. They detect failure patterns that functional conformance and single-device inspection cannot see.

A property that leaves no local trace

The 2012 scan did not recover keys by defeating well-generated RSA. It placed millions of public values side by side and found relationships that should almost never exist.

Entropy quality is unusual because a single output can look exactly right. The evidence appears across devices, across signatures or across repeated lifecycle events.

A generator that has failed may continue to produce plausible bytes. The first observer able to see the population is the first one able to distinguish them from random.

---

References

1. Heninger, Durumeric, Wustrow and Halderman: Mining Your Ps and Qs
2. Linux manual: getrandom(2)
3. Linux manual: random(4)
4. Debian Security Advisory 1571: Predictable OpenSSL random number generator
5. ROCA: Vulnerable RSA Generation
6. NIST SP 800-90B: Recommendation for Entropy Sources Used for Random Bit Generation
7. RFC 6979: Deterministic Usage of DSA and ECDSA
8. RFC 8032: Edwards-Curve Digital Signature Algorithm
9. CFRG: Hedged ECDSA and EdDSA Signatures