Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. Nadia Heninger and colleagues presented this work at USENIX Security in 2012. The problem is deceptively simple: can public keys gathered from Internet-facing TLS and SSH reveal devices whose randomness failed during key generation or signing? The team compared keys at enormous scale, then connected suspicious patterns with device and software clues. The practical interest is that public information can expose a private-key weakness across populations of deployed products.

Start with RSA key generation. If two public RSA values accidentally contain the same secret prime, calculating their greatest common divisor reveals that prime. Both values can then be factored and their private keys recovered. A different failure affects signatures: reusing the one-time secret number that should change for every signature can algebraically reveal the long-term signing key. These failures can emerge when random output is repeated or predictable. One hypothesis examined here was an early-boot window in which software requests random bytes before enough unpredictable input has reached the operating system’s generator.

The study had to separate several situations that look similar from outside. A manufacturer may install the same default key on many devices. Separate devices may instead generate repeated keys because they started with too little randomness. A signing device may repeat a supposedly one-time value. The question was therefore not merely whether keys were duplicated. It was whether patterns in public keys, signatures, service responses, and vendor artifacts could identify failures that permit private-key recovery and associate them with particular products or software families.

The collection contained 5.8 million unique TLS certificates and 6.2 million unique SSH host keys. The researchers used a batch greatest-common-divisor calculation to find RSA values sharing a prime. To group suspicious keys by device or software family, they combined certificate identities and service banners with clues from web responses, port behavior, and vendor artifacts. They also tested possible failure mechanisms under controlled conditions. A modified Linux boot experiment examined early-startup randomness, while constrained OpenSSL key generation tested how shared primes could arise. A separate analysis examined how Dropbear SSH could repeat one-time signing values.

Two results turn duplication into concrete private-key exposure. Shared primes let the team recover RSA private keys used by 0.50% of TLS hosts in the scan, with a smaller affected share among SSH hosts. Repeated one-time signing values exposed private keys for 1.03% of all scanned SSH hosts. The wider reuse problem was larger in both protocols. For TLS, the analysis attributed most apparently vulnerable reuse to manufacturer defaults rather than low-entropy generation. The analysis therefore distinguished copied defaults from broken random generation as separate sources of vulnerable key reuse across many devices.

Controlled startup testing makes one possible cause concrete. The team ran 1,000 unattended boots of a modified Linux system after disabling selected entropy sources. At the point when the SSH server would normally start, the experiment read 32 bytes from the random interface. Across those boots, the output was entirely predictable and repeatable under the deliberately constrained conditions. Instrumentation also found that SSH had seeded itself before the operating system estimated that enough entropy had reached its random generator. This establishes the mechanism in that setup; it does not show that every affected Internet device followed the same path.

The measurements covered publicly reachable IPv4 TLS and SSH endpoints on selected ports, not every device or every key. Product attribution was strongest where recognizable clusters supplied enough identifying evidence, so the resulting population estimates were described as conservative. Those sampling boundaries also limit whether the observed proportions carry into other networks. Duplication alone is not proof of failed randomness because manufacturer defaults produced a separate class of repeated keys. A 2016 follow-up added an operational warning: notifications and vendor advisories often did not translate into end-user patching, so successful detection and disclosure do not guarantee remediation.

For security architects and product teams, start with sequencing: block cryptographic key generation until the operating system’s random generator is ready, fail closed when trustworthy randomness is unavailable, and generate a separate key for each device. Factory or hardware entropy can help during provisioning. Certificate authorities can screen for known weak keys, but affected owners still need to regenerate them. Modern Linux and OpenSSL provide safer behavior when used correctly by waiting for initialization or returning an error when seeding fails. Callers must check that error. For cloned or rolled-back virtual machines, generation-change support lets the kernel reseed instead of continuing with copied random-generator state.

The contribution is a method and a warning. Comparing public keys at Internet scale can uncover certain correlated key-generation and signing failures, while public service metadata can help locate affected product families. Teams responsible for certificate infrastructure, SSH fleets, embedded provisioning, and incident response should combine screening with key regeneration and fixes to boot and provisioning. They should not treat every duplicate as evidence of weak randomness or assume notification causes remediation. Nor should they treat the RSA shared-prime test as universal: other algorithms need different checks for duplicated keys, repeated or biased signing values, and structured key patterns.