Mining Your Ps and Qs: Discovering Massive Weak Cryptographic Keys in Network Devices

Based on the work of N. Heninger, Z. Durumeric, E. Wustrow, J. A. Halderman,
Proceedings of the 21st USENIX Security Symposium, pp. 205–220, 2012.
A scientific and analytical review for cryptographers and cryptanalysts.

Abstract. “Mining Your Ps and Qs” is a landmark empirical study in applied cryptography, demonstrating for the first time on an internet scale that flaws in pseudorandom number generators (PRNGs) in embedded and headless devices lead to the mass compromise of RSA and DSA keys. The authors scanned 12.8 million TLS hosts and 10.2 million SSH hosts, discovered repeating prime divisors of RSA moduluses and predictable ephemeral DSA nonces, and thus enabled the computation of private keys for tens and hundreds of thousands of devices without a single brute-force factorization—using solely the mathematical properties of the GCD algorithm and linear algebra over DSA signatures.

1. Introduction and historical significance of the work

Before this study, the problem of weak entropy in cryptographic systems was viewed primarily as a theoretical threat or a local incident (e.g., the 2008 Debian OpenSSL bug). Heninger and coauthors conducted the first complete scan of the IPv4 address space to statistically assess the scale of the problem, applying number theory methods (Bernstein’s algorithm for batch-based GCD computation) to real internet traffic.

Historical example: In 2004, Bauer and Laurie computed the pairwise GCD of 18,000 PGP keys from public servers and found several factorable pairs—a precursor to the technique that the authors of Mining Your Ps and Qs scaled to 11 million moduli.

2. Cryptanalytic Fundamentals: RSA

An RSA key consists of a modulus $N = p \cdot q$ and exhibitors $e$ The private exponent is calculated as: $d = e^{- 1} mod (p - 1) (q - 1)$

RSA’s security relies on the computational difficulty of factorization. $N$ . However, if two independently generated modules $N_{1} = p \cdot q_{1}$ And $N_{2} = p \cdot q_{2}$ have a common prime divisor $p$ , an attacker can immediately find both secret keys by computing: $p = gcd (N_{1}, N_{2}), q_{1} = N_{1} / p, q_{2} = N_{2} / p$

The complexity asymmetry is critical: factoring a single 1024-bit RSA modulus is considered computationally infeasible (the largest distributedly factored modulus at the time of publication was 768 bits, 2009), while the GCD of two 1024-bit numbers can be calculated by the Euclidean algorithm in microseconds.

A real-world example: Juniper Networks Branch SRX devices generated 46,993 keys, of which 12,688 (27%) were factorable via a common prime divisor—a classic illustration of a long-tailed distribution of repeating primes due to insufficient entropy at boot.

3. Cryptanalytic Foundations: DSA and the Nonce Replay Disaster

DSA message signature $m$ is a pair $(r, s)$ : $r = (g^{k} mod p) mod q, s = k^{- 1} (H (m) + x r) mod q$

Where $k$ — a random ephemeral number (nonce), and $x$ — a long-term private key. If it’s the same $k$ used to sign two different messages $m_{1}$ And $m_{2}$ , this is immediately revealed by the equality $r_{1} = r_{2}$ The attacker recovers $k$ : $k = \frac{H (m_{1}) - H (m_{2})}{s_{1} - s_{2}} mod q$

and then the private key: $x = r^{- 1} (k s - H (m)) mod q$

This class of attacks is identical in nature to the classic “gamma reuse” problem in stream ciphers and is known as a lattice/nonce-reuse attack , and is fully applicable to ECDSA as well.

Historical precedent: in 2010, the reuse of nonce $k$

in ECDSA signatures led to the compromise of the private key of the Sony PlayStation 3 (fail0verflow group), which became public evidence of the practical danger of this class of vulnerabilities long before the mass internet scanning by Heninger et al.

4. Methodology: Scale and Scan Engineering

Parameter	TLS scan (10/2011)	SSH scans (2–4/2012)
Hosts with an open port	28,923,800	23 237 081
Completed Handshakes	12 828 613	10 216 363
Unique RSA keys	5,656,519	3,821,639
Unique DSA keys	6 241	2,789,662
Unique TLS certificates	5 847 957	—

Data collection was performed in three phases: host discovery via SYN scan (Nmap, 40,566 IP/sec), certificate/key extraction (Python + Twisted for TLS, native C client with libevent for SSH), and parsing X.509 fields to attributing the device manufacturer.

4.1. Batch GCD Algorithm (Bernstein)

A naive pairwise GCD calculation for 11,170,883 modules would require $6 \times 10^{13}$ operations and ~30 years of computation. The authors used Bernstein’s quasilinear algorithm, based on a product tree and a remember tree: $P = \prod_{i = 1}^{m} N_{i} (product tree)$ for everyone $z_{i} = P mod N_{i}^{2} for everyone i (remainder tree)$ the sought common divisor $gcd (N_{i}, z_{i} / N_{i}) — the sought common divisor$

The asymptotic complexity was $O (m n (\lg n)^{2} \lg \lg n)$ , which made it possible to process the entire dataset in 5.5 hours on a single Intel Core i5 core, or in 1.3 hours when parallelized on a 16-core EC2 instance (the cost of the calculation was about 5 USD).

An example of practical significance: a similar method of batch factorization via GCD underlies modern tools for auditing Bitcoin blockchain transactions, where weak ECDSA nonces (analogous to DSA k) in secp256k1 signatures are identified—for example, the compromise of early Android Bitcoin wallets (2013, SecureRandom bug).

5. Results: Quantitative picture of vulnerabilities

Category	TLS hosts	SSH hosts
Duplicate keys (total)	60.50%	65.00%
Vulnerable duplicate keys	5.57%	9.60%
Default manufacturer certificates	5.23%	—
Repetitions due to low entropy	0.34%	—
RSA keys factored via GCD	0.50%	0.03%
DSA keys compromised via nonce-reuse	—	1.03%
Debian weak-key keys	0.03%	0.52% (RSA)
512-bit RSA keys	0.96%	0.08%

5.1. Default and weak manufacturer keys

670,391 TLS hosts (5.23%) used factory default certificates. Fifty-seven certificates in the database littleblackbox yielded private keys for 23,476 hosts. It was also discovered that 1,584 Citrix hosts (including Fortune 500 institutions, insurance companies, law firms, and the US Navy) used a shared default key.

Historical example: a database littleblackbox (2009)—a public archive of private keys for home router firmware, extracted through reverse engineering of firmware images; the work of Heninger et al. effectively confirmed the industrial scale of this problem using real traffic.

5.2 Factorizable RSA Keys

11,170,883 modules yielded 2,314 unique common prime factors, compromising 16,717 public keys—64,081 TLS hosts (0.50%) and 2,459 SSH hosts (0.03%). The most telling case was IBM’s Remote Server Administration (BladeCenter Management Module), which generated modules uniformly distributed among only 9 different prime factors—a unique pattern among all devices examined.

An analogy from blockchain cryptanalysis: a similar “small entropy space” problem was observed in attacks on Bitcoin Brainwallet’s weak keys, where ECDSA keys were generated from predictable human-readable phrases—compromise occurred not through factorization, but through dictionary entropy space searches, which is structurally related to the problem of device default keys.

5.3. DSA nonce-reyuz

The authors found numerous SSH-DSA signatures with identical $r$ , which allowed us to calculate private keys for 1.03% of SSH DSA hosts (105,728 hosts). This provides direct empirical confirmation of the theoretical attack previously described by Bleichenbacher and other DSA researchers.

6. Root Cause: Boot-time entropy hole in Linux RNG

The Linux kernel supports entropy pools ( Input, Blocking, Nonblocking). Reading from them /dev/urandom does not block even if the input pool lacks accumulated entropy—unlike /dev/random. The authors experimentally demonstrated that on headless devices during the first boot (no disk, keyboard, mouse, or significant interrupt timing jitter), the entropy pool can be nearly deterministic, creating a “window of vulnerability”—a boot-time entropy hole .

The OpenSSL library initializes its own entropy pool with 32 bytes of /dev/urandom PID, UID, and the current time in seconds. If the boot time is predictable (for example, the device turns on immediately after power-up), the space of possible seeds narrows sharply, making the second generated seed simpler. $q$ at fixed $p$ statistically repeatable between devices.

Replication example: The authors’ experiment with 14 million generated RSA keys under controlled entropy sources showed a sharp “phase transition” – the proportion of factorable keys increases abruptly in a narrow time window near the system clock second boundary, reproducing exactly the pattern observed in Juniper and Cisco devices “in the wild.”

7. Dropbear SSH and DSA Ephemeral Key Replay

Dropbear, a lightweight SSH implementation common on embedded devices, initializes its own entropy pool with 32 bytes of entropy /dev/urandom upon service startup. If the system PRNG hasn’t yet collected entropy (a typical situation when a headless device first boots), Dropbear generates identical values. $k$ for DSA signatures on different devices or sessions of the same device – a direct cause of the vulnerability category described in section 5.3.

8. Practical implications for cryptographers and developers

OS implementors should provide an explicit, guaranteed-to-lock entropy interface for cryptographic operations, rather than relying on /dev/urandom an unchecked pool state.
Library developers need to test PRNG behavior on headless/embedded platforms separately from desktop scenarios.
Device manufacturers are encouraged to use hardware random number generators (TRNGs) where possible, rather than software PRNGs that rely on predictable sources (time, PID).
Administrators should check their keys using services like factorable.net key-check and regularly rotate factory default keys.

9. Connection with modern cryptanalysis (2020s)

The methodology of Heninger et al. directly anticipated modern trends in cryptanalytic research, which are also relevant in the context of Bitcoin/ECDSA:

Bitcoin ECDSA nonce replay attacks are numerous instances of Bitcoin private keys being compromised due to weak or repeated nonces. $k$ in transactions (e.g. the well-known Android SecureRandom bugs of 2013), structurally identical to the attack from Section 3.
Batch-GCD blockchain address auditing : Researchers apply Bernstein’s algorithm to a mass search for common prime factors in historical RSA certificates and cryptographic artifacts common in domain name registries and Certificate Transparency certificate archives.
Wagner’s k-tree algorithm and related ECDLP methods , although formally related to a different class of problems (solving the generalized birthday problem), continue the same line of research: searching for structural weaknesses in implementations rather than in the algorithms themselves.

10. Conclusion

The paper “Mining Your Ps and Qs” remains a benchmark example of empirical cryptanalysis at internet-scale. Its key methodological lesson is that vulnerabilities often arise not in the mathematics of the algorithm (RSA and DSA are mathematically secure when implemented correctly), but in the infrastructure layer of randomness generation. For cryptanalysts, this study demonstrates the power of elementary number theory tools (the Euclidean algorithm, the residue tree) when applied to gigantic data—a methodological principle that remains relevant for modern cryptographic auditing of blockchain systems.

Mining Your Ps and Qs: Detecting massively weak cryptographic keys in network devices: https://lottox.ru/mining-your-ps-and-qs-detecting-massively-weak-cryptographic-keys-in-network-devices/ Original source: N. Heninger, Z. Durumeric, E. Wustrow, JA Halderman. “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices.” Proceedings of the 21st USENIX Security Symposium, 2012, pp. 205–220.