Short-Sleeve RSA: How Zero-Block Prime Structure Exposed 603 Private Keys in the Wild

A joint research effort by Trail of Bits and the badkeys project has characterised a previously unnamed class of weak RSA key: moduli whose prime factors contain large, regularly spaced blocks of unset bits. Dubbed short-sleeve keys for the visual pattern those zero-blocks create, 603 unique RSA private keys and 74 DSA keys carrying this defect were recovered from Certificate Transparency logs, internet-wide TLS and SSH scans, and PGP keyservers — all without access to the corresponding private key material.

Why These Keys Factor

Standard RSA security rests on the assumption that factoring a large modulus N = p × q is computationally infeasible. Short-sleeve keys violate a subtler assumption: that p and q carry no exploitable internal structure. When the prime factors contain evenly spaced zero-bit blocks, the modulus can be expressed as a polynomial with unusually small coefficients in a base-2^w representation. Factoring that polynomial — using lattice-based techniques in the spirit of Coppersmith's method — is dramatically cheaper than general-purpose integer factorisation and yields the primes directly. The practical result: an RSA private key is recoverable from its public modulus alone.

What the Scans Revealed

Searching the badkeys dataset — aggregated from CT logs, internet-wide TLS and SSH scans, and PGP dumps — the researchers isolated two distinct zero-block patterns in deployed keys:

• Pattern 1: Appeared in TLS certificates issued to Yahoo and Verizon domains, and in NetApp appliance certificates. All certificates from this pattern have since expired, closing the TLS impersonation window.
• Pattern 2: Found on live SSH hosts running CompleteFTP software — RSA host keys generated by versions 10.0.0–12.0.0 (December 2016 – March 2019), and DSA host keys generated by versions 10.0.0–23.0.4 (December 2016 – December 2023).
• A further 26 RSA keys matched a third, as-yet-unidentified pattern, suggesting additional affected codebases remain undiscovered.

While the number of vulnerable CompleteFTP installations has declined over time, the researchers confirmed that a significant fraction still serve SSH connections with broken host keys as of publication. Any live SSH host presenting such a key is exposed to a practical private-key recovery attack.

Remediation Steps

CompleteFTP released version 26.1.0 on 8 May 2026, adding automated detection of vulnerable keys at startup and forcing key regeneration. Enterprisedt also published a standalone KeyChecker tool for administrators who cannot immediately upgrade. For everyone else:

• Run the open-source badkeys CLI or use the web interface at badkeys.info against your full key inventory — TLS, SSH host keys, and PGP.
• CompleteFTP administrators: upgrade to v26.1.0 or later immediately and regenerate all RSA and DSA host keys.
• Do not limit the audit to currently active keys — keys generated in the 2016–2023 window may have been reused or archived; treat any match as a confirmed private-key compromise.
• If a key matches, rotate and revoke; do not rely on the assumption that the key was never targeted.

Wider Implications for PKI Hygiene

This research demonstrates that key-generation flaws do not require a broken PRNG to produce factorable output — subtle structural bias in prime selection is sufficient. The pattern surfaced independently in at least two unrelated codebases, which is a meaningful signal that the same flaw may exist in other cryptographic libraries, embedded TLS stacks, or network appliances that have not yet been audited. Defenders running automated PKI or SSH hygiene checks should add sparse-modulus detection to their existing controls — alongside checks for short key lengths and known-bad public exponents — rather than treating key length alone as a proxy for strength.