Trail of Bits and Badkeys Discover Hundreds of Weak 'Short-Sleeve' RSA Keys Exploitable via Polynomial Factoring
Researchers at Trail of Bits and the badkeys project have identified hundreds of weak RSA and DSA keys in the wild, where private key bits are heavily biased toward zero, enabling a novel polynomial-based factoring attack.
Researchers at Trail of Bits, in collaboration with Hanno Böck of the badkeys project, have uncovered a significant cryptographic vulnerability affecting hundreds of RSA and DSA keys actively used on the internet. These so-called "short-sleeve" keys contain private key bits that are heavily biased toward zero, creating a detectable pattern in the public modulus. By exploiting this structured zero-bit pattern, the team developed a polynomial-based cryptanalytic technique that can factor these keys in seconds, effectively breaking the security they were meant to provide.
The discovery emerged from the badkeys project, an open-source service that checks public keys for known vulnerabilities. By scanning massive datasets—including Certificate Transparency logs, internet-wide TLS and SSH scans, and PGP key repositories—the researchers identified two distinct patterns of weak keys. Pattern 1 appeared in certificates issued to major organizations such as Yahoo, Verizon, and NetApp devices, though the root cause remains unexplained. Pattern 2 was traced to a type mismatch bug in the big-integer code of CompleteFTP (EnterpriseDT) software, affecting RSA keys generated with versions 10.0.0–12.0.0 (December 2016 to March 2019) and DSA keys generated with versions 10.0.0–23.0.4 (December 2016 to December 2023).
The technical mechanism behind the attack is elegant. RSA moduli are typically represented as arrays of smaller machine-sized values called limbs. In short-sleeve keys, each limb contains a block of zero bits, leaving only a small contiguous subset filled with random bits. By interpreting the modulus as a polynomial in base-2^w (where w is the limb size), the researchers could factor the polynomial—a computationally easy problem—rather than the integer itself. This converts the hard problem of integer factorization into a trivial polynomial factorization, yielding the private key factors p and q.
From internet scans, the team recovered 603 unique RSA private keys and 74 DSA keys that were vulnerable to this attack. While the affected hosts represent a small minority of internet-facing systems, the implications are broader. "The more interesting takeaway is that independent cryptographic implementations failed in similar ways," the researchers noted. "More implementations may include the same bugs, and so it's worth tailoring cryptanalytic algorithms for this particular type of failure."
EnterpriseDT has released a tool to help CompleteFTP users check whether their keys need to be regenerated. Users who generated host keys between December 2016 and December 2023 are advised to verify their keys immediately. For Pattern 1 keys, the affected certificates have already expired, but the researchers have shared their findings with Yahoo, Verizon, and NetApp.
This research highlights the dangers of flawed random number generation in cryptographic implementations. Even a subtle bias toward zero bits can completely undermine the security of RSA and DSA, turning a mathematically hard problem into one that can be solved with high school algebra. The findings serve as a cautionary tale for developers implementing cryptographic primitives and underscore the importance of rigorous testing and validation of key generation routines.