603 unique RSA private keys and 74 DSA keys — all with zero-bit patterns in their limbs — fell to a polynomial factoring trick that turns RSA moduli into easy-to-factor polynomials. Hanno Böck and the Trail of Bits team found these keys in Certificate Transparency logs, internet-wide TLS/SSH scans, and PGP key servers. The real surprise: the zero bits weren't random noise but regularly spaced blocks, giving the keys a "short-sleeve" look.
How the Short-Sleeve Pattern Emerges
RSA moduli are big integers stored as arrays of 32-bit or 128-bit limbs. In correctly generated keys, each limb is full of random bits. Short-sleeve keys have limbs where only a small contiguous chunk is random; the rest is zero. Two patterns emerged. Pattern 1 showed up in certificates for Yahoo and Verizon (now expired). Pattern 2 appeared on SSH hosts running CompleteFTP from EnterpriseDT. The regularity of the zero blocks is what made the polynomial attack possible.
From Moduli to Polynomials
The key insight: represent the modulus $n$ as a polynomial $f_n(x)$ using the base-$2^w$ representation, where $w$ is the limb size. Because the zero bits cause most coefficients to be tiny (much smaller than $2^w$), $f_n(x)$ factors into $f_p(x) * f_q(x)$ just like $n = p \cdot q$. Factoring polynomials is trivial, so evaluating the polynomial factors at $x = 2^w$ recovers $p$ and $q$. This doesn't work on well-generated keys because their coefficients are full-width. The short-sleeve structure makes the polynomial coefficients small enough that standard factorization algorithms split them instantly.
The CompleteFTP Bug That Leaked Bits
Reverse-engineering a trial version of CompleteFTP revealed the culprit. The genRandomBits function in the .NET code allocates an array of bytes for random data, then copies it directly into the big-integer's limbs. But each limb is 32 bits, and Array.Copy treats each 8-bit byte as a separate 32-bit element — so each limb gets only 8 bits of entropy, with the upper 24 bits forced to zero. The decompiled code is a textbook type mismatch:
byte[] array = new byte[numLimbs];
rngProvider.GetNonZeroBytes(array);
Array.Copy(array, 0, bignumLimbs, 0, numLimbs);
bignumLimbs[numLimbs - 1] |= 0x80000000;
Every limb ends up with a single byte of randomness and a block of zeros. RSA keys generated this way between December 2016 and March 2019 were vulnerable; DSA keys generated with the same bug persisted until December 2023.
Scope and Mitigation
EnterpriseDT refactored key generation to use .NET's RSACryptoServiceProvider and DSA.Create in later versions. The team was responsive during disclosure and shipped v26.1.0 with a detection tool that checks whether existing keys are vulnerable and alerts users to regenerate them. The badkeys project now also detects short-sleeve RSA keys. Historical SSH scans show the number of affected hosts peaked around 2019 and has since plateaued — most users who generated keys once never rotated them.
This attack is a textbook example of how specific implementation bugs can be exploited by adapting number-theoretic algorithms to real-world patterns. The polynomial technique works here precisely because the zero bits are structured. The same trick won't break general RSA, but the feedback loop between vulnerability research and cryptanalytic algorithm design will keep turning up more edge cases where cryptographic primitives are botched at the implementation level.
Source: Factoring "short-sleeve" RSA keys with polynomials
Domain: blog.trailofbits.com
Comments load interactively on the live page.