Weak Keys at Scale: Entropy Failures and Structured Primes

Every RSA key-strength table assumes something it never states: that the two secret primes were chosen uniformly at random from an enormous space, independently of every other key in the world. When that assumption holds, a 2,048-bit modulus is far beyond any known factoring capability. When it fails, the same key can fall in seconds, not because factoring got easier, but because the attacker no longer has to factor anything. The history of public-key deployment contains three distinct versions of that failure. In one, devices with too little randomness at boot generated primes that other devices also generated, so a simple greatest-common-divisor computation across a population exposed private keys. In another, a well-intentioned code change collapsed a widely used random number generator to a few tens of thousands of possible states, so every key it produced could be listed in advance. In the third, a chip vendor's library generated primes with a hidden algebraic structure that an old factoring technique could exploit. Each failure looks the same from the outside, a normal-looking RSA key, yet each needs a different test to find and a different response to fix. This article separates them, and argues that fleets of AI agents, created by the thousand from identical images, are rebuilding the conditions for the first two.

Three ways key generation fails

RSA key generation has three ingredients: a source of randomness, a procedure that turns random bits into candidate primes, and a primality test (Rivest, Shamir and Adleman, 1978). The security argument needs the output primes to be unpredictable and, crucially, unrelated to the primes of every other key. Failures in the first two ingredients produce three distinguishable classes, which this article names for clarity.

Shared factors arise when two independently generated keys end up containing the same prime, typically because both generators started from the same or overlapping random state. Enumerable keyspaces arise when the effective randomness is so small that every possible key can be generated in advance by anyone who knows the procedure. Structured primes arise when the prime-generation procedure itself produces primes with a mathematical shape that a specialised algorithm can exploit, even with plenty of randomness.

The classes differ in what an attacker needs. Shared factors require a large collection of public keys and an efficient way to compare them. Enumerable keyspaces require knowledge of the flawed generator and the patience to list its outputs once. Structured primes require a dedicated factoring method tuned to the structure. Because the requirements differ, so do the detection tests and the remediation duties, which is the organising idea of the rest of this article.

Shared factors: when two keys hold the same prime

If two RSA moduli share one prime factor, computing their greatest common divisor, an operation that takes microseconds even for very large numbers, reveals that prime, and dividing it out of each modulus reveals the other prime of each key. Both private keys are then fully exposed. Nothing about either key looks unusual in isolation; the weakness exists only in relation to another key.

Heninger, Durumeric, Wustrow and Halderman made the scale of this problem visible in their 2012 study Mining Your Ps and Qs. They collected public keys from TLS and SSH hosts across the internet and computed pairwise common divisors efficiently. They reported obtaining RSA private keys for 0.50 percent of TLS hosts and 0.03 percent of SSH hosts, and DSA private keys for 1.03 percent of SSH hosts, the last through repeated signature randomness. The vulnerable keys came overwhelmingly from headless and embedded network devices such as routers and firewalls.

Their analysis traced the root cause to what they described as a boot-time entropy hole. A freshly booted embedded device has collected little unpredictable input, from user activity, disks or network timing, when it generates its keys on first start. Devices of the same model therefore began from nearly identical random states. A characteristic pattern followed: when the generator's state diverged between choosing the first and second prime, devices produced moduli that shared one prime but not the other, which is precisely the case the common-divisor test exposes.

Finding shared factors across a population

Comparing every key with every other key one pair at a time grows with the square of the number of keys, which becomes expensive for millions of keys. The 2012 study used a batch technique that computes, for every modulus at once, its greatest common divisor with the product of all the others. It does this by building a product tree, multiplying moduli in pairs and then pairs of products up to a single root, and a remainder tree, which pushes that root back down and reduces it modulo each modulus squared. Each modulus then needs only one final common-divisor computation.

The defensive value of this method is that it works on public information only. An organisation can run it over the certificates and SSH host keys it already holds, or over keys gathered from its own device fleet, and any modulus with a nontrivial result is definitively compromised. There are no false positives: a shared prime is proof, not suspicion. Its blind spot is equally precise. It finds only keys that share a factor with another key in the dataset, so a weak key with no partner in the collection passes silently, and it says nothing about the other two failure classes.

moduli   = public_moduli(inventory)            # your own certificates and host keys
products = build_product_tree(moduli)          # pairwise products up to one root
rems     = build_remainder_tree(products, moduli)  # root reduced modulo each modulus squared
for n, r in zip(moduli, rems):
    g = gcd(n, r // n)
    if g != 1:
        flag(n, reason='shares a prime with another key in inventory')
# A flag is proof of compromise: revoke and regenerate on a healthy generator.

Enumerable keyspaces: the Debian generator collapse

The second class is not about pairs of keys but about a generator whose effective randomness collapsed. In May 2008 the Debian security advisory DSA-1571 announced that a change made in September 2006 to Debian's packaged OpenSSL, intended to silence warnings from a memory-checking tool, had removed nearly all of the entropy feeding OpenSSL's random number generator. The remaining variation came essentially from the process identifier, of which there were only tens of thousands of possible values on typical systems.

The consequence was stark. For a given key type, size and processor architecture, the generator could produce only a small, enumerable set of keys. Anyone who regenerated that set, a modest computation, could match any affected public key to its private key by lookup. Every SSH host key, TLS server key and other key generated with the affected packages during roughly twenty months was predictable. Worse, the advisory noted that DSA keys were at risk even if they had been generated on an unaffected system, if they were ever used to sign on an affected one, because DSA signatures also depend on fresh randomness.

Detection for this class is a lookup rather than a computation: compare the fingerprint of each public key against a published list of every key the broken generator could produce. Debian shipped such blacklists and tools to check keys. Remediation required regenerating every key created on affected systems and replacing every certificate issued for them, an operational burden that, in this article's assessment, mattered more in practice than the cryptographic analysis.

Structured primes: the ROCA case

The third class arises even with good randomness. In 2017 Nemec, Sýs, Švenda, Klinec and Matyáš published The Return of Coppersmith's Attack, describing RSA keys generated by a widely deployed library in Infineon security chips, used in smart cards, Trusted Platform Modules and hardware tokens. To speed up prime generation, the library built each prime from a small random part combined with a fixed multiplicative structure. That structure drastically reduced the set of primes the library could ever produce.

The researchers showed that this structure allowed a variant of Coppersmith's method, a technique for finding small solutions to certain polynomial equations, to factor the resulting moduli far faster than general-purpose factoring. They reported practical factoring for 1,024-bit keys and an expensive but feasible computation for 2,048-bit keys, and estimated that very large numbers of affected keys existed in national identity cards, authentication tokens and computers with the affected chips.

Two properties make this class distinctive. First, the same structure that weakened the keys also made them detectable: the paper described a fast fingerprinting test, applicable to the public key alone, that identifies affected moduli with essentially no false negatives. Second, remediation could not be done by software updates to existing keys, because the weakness lives in the keys themselves. Firmware updates fixed future generation; every existing key had to be regenerated with the fixed firmware or off the chip, and devices that could not be updated had to be replaced.

Different classes, different duties

Put side by side, the three classes call for three different detection tests and three different remediation duties, and confusing them leads to false confidence. A clean shared-factor screen says nothing about whether keys came from a collapsed generator or a structured-prime library. A clean blacklist check says nothing about entropy holes on other devices. A clean structural fingerprint says nothing about shared primes. Each test answers only its own question.

The remediation duties differ in scope as well. Shared factors implicate a device model's boot process and demand that every key generated under the same conditions be treated as suspect, not only those found in the screen, because the screen only finds keys with a partner in the dataset. Enumerable keyspaces implicate every key generated on affected software during a time window. Structured primes implicate every key generated by a particular component, regardless of time, and may require hardware replacement.

The synthesis offered here is a triage order that runs the cheapest definitive tests first and maps each finding to its full remediation scope rather than to the single key that triggered it.

AI agent fleets recreate the entropy hole

The conditions behind the first two classes are not historical curiosities. They describe, in this article's analysis, how many AI agent platforms provision identities today. Agents are frequently created by the thousand from identical container images or virtual machine snapshots, often in short-lived environments, and some platforms generate a key pair for each agent at start-up. A freshly started container or a restored snapshot can begin with random-generator state that is identical, or nearly so, across instances, unless the platform ensures fresh seeding from the host. That is a close analogue of the boot-time entropy hole that produced shared primes in embedded devices.

Two further patterns echo the enumerable-keyspace class. Keys baked into an image are shared by every agent built from it, the degenerate case of a keyspace of size one. And key-generation code written quickly, sometimes by code assistants, may seed a general-purpose random generator from the clock or process identifier rather than calling the operating system's cryptographic generator, recreating the Debian failure in miniature.

The remedies follow from the classes. Agent identities should be issued by a central key service or hardware security module rather than generated inside agent environments. Where local generation is unavoidable, it must use the operating system's cryptographic generator through an interface that blocks until seeded, and must never run in a cloned snapshot before reseeding. Platforms should run shared-factor screening and blacklist checks over all agent public keys continuously, because a fleet is exactly the kind of population in which shared factors reveal themselves.

Limitations

This article synthesises three primary cases rather than reporting new measurements. Percentages and timelines are taken from the cited sources and describe the conditions at the time of those studies, not the present prevalence of weak keys. Shared-factor screening finds only keys whose partners are present in the same dataset, so a clean result is weaker evidence than it appears. The agent-platform analysis is a reasoned extrapolation from the mechanisms in the cited cases, not a measurement of any particular platform. Finally, the three-class taxonomy is a practical organising tool and not exhaustive; other generation failures, such as primes that are too close together, call for their own tests.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

agent_identity_keys:
  issued_by: central_key_service     # never generated in the agent image
  generation_in_container: forbidden
  keys_in_images: forbidden            # scan images on build
  local_generation_exception:
    rng: os_csprng_blocking_until_seeded
    forbidden_seeds: [clock, pid, fixed]
    snapshot_rule: reseed_before_any_key_generation
  screening:
    shared_factor_scan: daily
    blacklist_check: on_issue

Glossary

Entropy

Unpredictable input collected by a system to seed its random number generator.

Boot-time entropy hole

The period after a device starts when it has gathered too little entropy to generate secure keys.

Greatest common divisor

The largest number dividing two integers, which exposes a prime shared by two RSA moduli.

Product tree

A tree formed by multiplying numbers in pairs repeatedly up to a single product.

Remainder tree

A tree that reduces a large product modulo each leaf value, enabling batch divisor computation.

Enumerable keyspace

A set of possible keys small enough to be generated and listed in full by an attacker.

Coppersmith's method

A lattice-based technique for finding small solutions to polynomial equations, used to factor structured moduli.

Key fingerprint

A short hash of a public key used to identify it, for example against a blacklist.

References

1. N. Heninger, Z. Durumeric, E. Wustrow, J. A. Halderman, Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices, USENIX Security 2012
2. Debian Security Advisory DSA-1571-1: openssl, predictable random number generator (2008)
3. M. Nemec, M. Sýs, P. Švenda, D. Klinec, V. Matyáš, The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli, ACM CCS 2017
4. R. L. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, 1978
5. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2 (IETF)