Factoring "short-sleeve" RSA keys with polynomials

What it is

Trail of Bits, working with Hanno Böck's badkeys project, identified "short-sleeve" RSA and DSA keys — moduli whose big-integer limbs contain structured blocks of zero bits, leaving only a small contiguous slice of each limb filled with random data. Such keys can be factored quickly using a polynomial technique. Two patterns emerged; pattern 2 was traced to a big-integer type-mismatch bug in EnterpriseDT's CompleteFTP file transfer software. Pattern 1 remains unexplained.

How it works

A big integer is stored as an array of machine-sized limbs. Reading the modulus $n$ in its base-$2^w$ representation (where $w$ is the limb width) turns each limb into a polynomial coefficient: $a = \sum_i a_i 2^{wi}$ becomes $f_n(x) = \sum_i a_i x^i$, with $f_n(2^w)=n$. Because evaluation commutes with multiplication and addition, if $p$ and $q$ also have small-coefficient polynomials then $f_n(x)=f_p(x)\cdot f_q(x)$. Factoring a polynomial is easy, so you factor $f_n(x)$, then evaluate the factors at $2^w$ to recover $p$ and $q$. This works only because the zero blocks force exceptionally small coefficients — correctly generated primes yield full $w$-bit coefficients, so the attack fails on normal keys. Pattern 1 reads as 128-bit limbs, pattern 2 as 32-bit limbs. The post notes it omits one key insight needed for the real-world moduli (full derivation at the end of the article).

Preconditions / Affected

The two patterns differ in origin and scope:

• Pattern 1 (128-bit limbs): seen in Certificate Transparency logs for certificates issued to large organizations including Yahoo and Verizon, and on some NetApp-running devices. Those certs have expired; the generating product is unidentified.
• Pattern 2 (32-bit limbs, CompleteFTP): note the version ranges differ by key type — RSA keys from v10.0.0–12.0.0 (Dec 2016–Mar 2019); DSA keys from v10.0.0–23.0.4 (Dec 2016–Dec 2023). (The existing summary's single 10.0.0–23.0.4 range applies to DSA; the RSA window is narrower.) Recovered: 603 unique RSA private keys, 74 DSA keys, from SSH host scans.

What to do

If you generated CompleteFTP host keys between December 2016 and December 2023, use CompleteFTP's released tool to check whether your keys need regenerating, and regenerate affected keys. More broadly, the authors suggest tailoring cryptanalytic checks for this failure mode, since independent implementations produced similar bugs — badkeys detection covers these patterns.

Caveats

Only a small minority of internet hosts are affected. Pattern 1's source was never confirmed — the contacted organizations did not respond. The blog deliberately omits one insight required to factor the real moduli, so the "basic version" described is not directly sufficient.