The 0.3% Key Failure Rate: A Crypto Audit Checklist
Archi4 min read
Contents
The 0.3 Percent Failure Line#
Every large public key audit finds the same fraction. Roughly 0.3 percent of keys fail a basic randomness or uniqueness test. That number appears in certificate transparency logs, in PGP key servers, and in firmware update images. It is small enough to ignore in a single deployment and large enough to become a quiet compromise when a product ships 10,000 units.
Thirty devices out of every ten thousand. A vendor that sends out a monthly update reaches that scale quickly. An operator running a 50,000 node mesh network sees 150 affected nodes. The failure is not in the algorithm, not in the chosen key size, and not in the protocol. It is in the random number generation and the way key material is handled.
1. Confirm the Entropy Source#
The operating system provides a random source. Use it. On Linux, that means getrandom or reading /dev/urandom. On Windows, BCryptGenRandom. On embedded targets, verify that the hardware random generator is actually attached to the system pool, not emulated by a linear feedback shift register.
A common mistake is to seed the generator once and then use a counter to produce successive keys. A counter is not random. If two devices start from the same seed, they produce the same key pair. The fix is to re-seed from the OS entropy pool before each signing operation. That is a one-line change in most libraries, and it removes the highest-cardinality failure.
2. Test Nonce Uniqueness for Signatures#
Elliptic curve signatures need a fresh nonce for every message. If two messages share the same nonce and the same private key, an observer can subtract the two signatures and solve for the private key. The math is public, straightforward, and often demonstrated in capture-the-flag exercises. The surprising part is that nonce reuse still appears in production systems.
The reliable way to avoid nonce reuse is deterministic signatures. RFC 6979 derives the nonce from the private key and the message hash. That removes the randomness requirement, but it also means the same message signed twice must produce the same signature. Some teams treat that as a problem and add a random input on top. If you do that, test that the random input is not time-of-day truncated to a 32 bit value.
An easy audit step: sign a fixed test message twice. If the signatures differ, the nonce is non-deterministic. If they match, deterministic. Neither case is wrong, but the non-deterministic path must draw from a generator that was independently verified in step 1.
3. Check for Shared Prime Factors#
RSA key generation works by selecting two large primes. A flawed random generator can produce the same prime in two different keys. When that happens, the GCD of the two public keys reveals both private keys. This is not theoretical. Registries of public keys have been scanned for shared factors since 2012, and the results consistently return that 0.3 percent figure.
For an individual deployment, you can run a quick test: gather all public RSA moduli in your inventory and compute pairwise GCDs. Any divisor greater than 1 means two keys share a factor. There are open source tools that do this on a reasonable database in minutes. If you find a shared factor, rotate both keys immediately and investigate the device that generated them.
4. Validate Curve and Subgroup Parameters#
Diffie-Hellman and elliptic curve operations require parameters that are not maliciously weak. For finite-field Diffie-Hellman, reject primes that are not safe primes and reject generator values that fall into small subgroups. The OpenSSL command line can print the group parameters; verify that the order is a large prime and that the generator is not 1 or -1.
For elliptic curves, stick to standard curves like P-256 or Curve25519. Do not accept custom curves from unknown sources. A custom curve can be constructed with a backdoor that only the author knows. This is not a risk in modern TLS if you use the named curve list. It becomes a risk when you import a hardware module that ships its own curve parameters without documentation.
5. Enforce Key Age Limits#
Even a key generated with perfect entropy can degrade through usage. A 2048-bit RSA key has a comfortable margin for a decade, but an ECDSA P-256 key gives away a few bits of bias with each signature. The math is safe for billions of signatures, but operational failings do not wait for math. A lost backup, a copied private key, or a side-channel leak all become worse with time.
Set a key rotation period based on the hardware and the threat model. For a public certificate, 90 days is a common upper bound. For a device attestation key, consider a year. The rotation itself should use the same entropy source and parameter checks from steps 1 through 4. Do not reuse the old key material as a seed for the new key.
The 0.3 Percent Is a Floor#
The audits that produce the 0.3 percent figure catch only the failures that appear as shared primes or repeated values. They do not catch a key pair that is mathematically correct but was generated on a compromised machine. That is why the checklist matters: each step removes a separate failure path. Entropy testing removes one. Nonce testing removes another. Prime GCD scanning removes a third.
Thirty devices per ten thousand is a small number. But in a fleet of 100,000, that is 300 breakable keys. Run the checklist once, then run it again after any firmware change. The number stays 0.3, but you want your devices in the other 99.7 percent.
More articles