Factoring “Short-Sleeve” RSA Keys with Polynomials

Executive Summary

What happens when an RSA modulus is generated from a private key whose bits are heavily biased toward zero? The bias survives into the public key, and Trail of Bits, working with Hanno Böck of the badkeys project, has demonstrated that you can spot the resulting moduli in the wild — and then factor them at speed. The paper reports two distinct “short-sleeve” bit patterns. Pattern 1 (still unattributed) showed up in expired CT-log certificates for several large organisations, including Yahoo and Verizon, and on some NetApp devices. Pattern 2 was traced to a type-mismatch bug in the big-integer RNG path used by old versions of EnterpriseDT’s CompleteFTP server. The team recovered 603 unique RSA private keys and 74 DSA private keys from internet scans of CompleteFTP hosts, plus 26 RSA keys matching the unidentified pattern 1.

The technical contribution is the factoring method. Rather than tackling integer factorisation directly, the short-sleeve structure lets you re-cast the modulus as a polynomial with small coefficients (treating the limb size of the big integer as a base), then factor that polynomial — a much easier problem. Re-evaluating the polynomial factors at the limb-size base recovers the prime factors of the modulus. The article walks through the discovery in the badkeys dataset, the polynomial trick, the reverse engineering of CompleteFTP’s decompiled .NET key-generation routine, the historical impact in SSH scans, and a list of guided questions for readers who want to implement the attack themselves. CompleteFTP shipped a detection tool in v26.1.0 (8 May 2026); badkeys now flags short-sleeve RSA moduli too.

How We Found the Weak Keys

The badkeys project is an open-source service that checks public keys against a catalogue of known vulnerabilities. As part of building it, Hanno Böck has accumulated a large corpus of real-world public keys harvested from Certificate Transparency logs, internet-wide TLS and SSH scans, PGP repositories, and other public sources. Searching this corpus for RSA moduli whose bit patterns looked unexpectedly sparse turned up a sizeable population matching the two patterns shown in Figure 1.

Both patterns share the same shape: regularly spaced runs of all-zero bits separated by short runs of pseudo-random data. Pattern 1 appears in expired CT-log certificates issued to several large organisations — Yahoo and Verizon among them — and on some hosts running NetApp software. The certificates are no longer valid; the affected organisations were notified, but the underlying product responsible for generating these keys has not been identified. Pattern 2 turned up on SSH servers whose banners advertise EnterpriseDT’s CompleteFTP. The vulnerable window is CompleteFTP v10.0.0–v12.0.0 for RSA (December 2016–March 2019) and v10.0.0–v23.0.4 for DSA (December 2016–December 2023).

The set of affected hosts is small compared to the broader internet. The point worth emphasising is structural: two independent cryptographic implementations failed in similar ways. Where one implementation leaks structure of this kind into its public output, others probably do too — which is reason enough to tune cryptanalytic algorithms specifically for this failure mode.

Factoring With Polynomials

Cryptographic code routinely needs to manipulate integers that are hundreds or thousands of bits long. These “big integers” are stored as arrays of smaller machine-sized values called limbs. Interpret pattern 1 as a sequence of 128-bit limbs (or pattern 2 as 32-bit limbs), and the regular zero blocks line up so that each limb contains one contiguous run of zeros. Only a short contiguous segment of each limb holds random bits, and the remainder is uncovered — hence the “short-sleeve” nickname.

The trick is to exploit this limb-level structure to swap a hard problem (factoring integers) for an easy one (factoring polynomials). Take a modulus n with unknown factors p and q, express it as a polynomial f_n(x) with small coefficients, factor f_n(x) into f_p(x) and f_q(x), and convert the polynomial factors back to integers to recover p and q. The integer↔polynomial bridge is used widely in numerical analysis — fast polynomial multiplication is the textbook example — but very little of the available literature spells out how to use it for fast factorisation.

Concretely, the base-B digits of an integer become the coefficients of the polynomial: an integer written as a = ∑_i a_i Bⁱ maps to the polynomial f_a(x) = ∑_i a_i xⁱ, and evaluating that polynomial at x = B recovers the integer. For short-sleeve keys you pick the base to match the limb size; the extra zero bits inside each limb then translate into polynomial coefficients that stay exceptionally small.

The integer↔polynomial map is multiplicative: f_a(B) · f_c(B) = (f_a · f_c)(B). Evaluation is just substitution, so it doesn’t matter whether you multiply first and evaluate after or the other way around. The same identity holds for addition. (Mathematically, the evaluation map is a ring homomorphism.)

For a short-sleeve RSA modulus n with w-bit limbs, base-2^w gives a polynomial f_n(x) with exceptionally small coefficients. If f_p(x) and f_q(x) also have exceptionally small coefficients, then f_n(x) = f_p(x) · f_q(x) over the integers, and polynomial factorisation pulls them apart.

This is closely related to the number-field-sieve worldview — modern factoring implementations work with a polynomial f₀ together with a linear polynomial f₁ such that Resultant(f₀, f₁) is a small multiple of n. In the special case where f₁ is monic, Resultant(f₀, x − m) = n ↔ f₀(m) = n. The short-sleeve attack is the (rare, fortunate) case where the polynomial reflecting the modulus has small enough coefficients to be factored directly.

Reverse Engineering the CompleteFTP Vulnerability

Applying the polynomial method to the pattern-2 keys recovered prime factors that are themselves short-sleeved — the primes have the same regularly spaced runs of unset bits. The SSH banners on the hosts producing pattern 2 pointed at CompleteFTP, so the team grabbed a trial copy and reverse-engineered the key-generation path.

Dynamically generated RSA keys from the latest version did not show the short-sleeve pattern, which forced static analysis. The team used ILSpy to decompile the .NET demo binary. After some digging they found the offending routine. It fills a big-integer represented by bignumLimbs with a random value of a given bit length — see if you can spot the problem before reading on:

public void genRandomBits(int bits) {
    // Calculate the number of limbs
    int numLimbs = bits / 32;
    // Allocate space for the RNG output
    byte[] array = new byte[numLimbs];
    // Call the system RNG
    rngProvider.GetNonZeroBytes(array);
    // Copy to the limbs of the big number
    Array.Copy(array, 0, bignumLimbs, 0, numLimbs);
    // Set the top bit to ensure proper bit length
    bignumLimbs[numLimbs - 1] |= 0x80000000;
    // Store the length
    dataLength = numLimbs;
}

Figure 4: Decompiled code for the vulnerable genRandomBits in CompleteFTP. Several branches have been removed for clarity, and comments are added. Source: original Trail of Bits article.

The bug is a size mismatch between the limb array and the RNG buffer. Each limb wants 32 bits of randomness, but Array.Copy implicitly casts each 8-bit element of the byte array into one element of the 32-bit limb array. The repeating structure observed in short-sleeve keys comes straight from this: every limb gets the same treatment, and each one gets too little entropy — exactly the “sparse coefficients” the cryptanalysis predicted.

The reason dynamic testing missed the bug is that genRandomBits is compiled in but unreachable in current versions. Older builds used custom key-generation code that funnelled through this function. Later refactors swapped it for standard .NET crypto APIs. Older CompleteFTP versions also routed DSA key generation through genRandomBits: the 160-bit DSA private key x came from this function, and the corresponding public key includes the generator g and the value y = g^x. Once you know what to look for, the same scan recovers vulnerable DSA keys in the wild.

From v12.1.0 onward, RSA generation uses .NET’s RSACryptoServiceProvider; from v23.1.0 onward, DSA generation uses the DSA.Create API. Diffie–Hellman key exchange also called the vulnerable routine but with a 2048-bit exponent, which keeps it cryptographically safe.

How the Vulnerability Spread, and How It Was Contained

Refactoring the key-generation code to use standard libraries mattered. Nadia Heninger’s historical and contemporary SSH scan archive — the same dataset used to find broken SSH RSA signatures — was queried for CompleteFTP banners. The IPv4-wide scans typically contained several hundred CompleteFTP hosts at any given time. Lining the scans up with CompleteFTP’s release timeline tells a clean story:

From the introduction of the RSA-side bug in December 2016, vulnerable hosts increased steadily. The trend reversed the moment the rewritten RSA code shipped in March 2019. Since then, the number of hosts running an affected version has dropped — but the proportion of vulnerable keys has plateaued. That is consistent with customers who patch the software regularly but generate their host keys exactly once.

EnterpriseDT was responsive throughout disclosure. On 8 May 2026 they released CompleteFTP v26.1.0, which automatically checks the host’s active RSA and DSA keys and warns when regeneration is required, plus a standalone tool that performs the same check. badkeys’s website and command-line tool now detect short-sleeve RSA keys as well.

Final counts: 603 unique RSA public keys and 74 DSA keys recovered from vulnerable CompleteFTP installations, plus 26 RSA keys matching the still-unattributed pattern 1. The underlying SSH-scan corpus is heavily RSA-leaning, so these numbers should be read as a lower bound rather than a population estimate.

The Search for More Short-Sleeve Keys

Pattern 1 remains a mystery, and there is no guarantee that the vulnerability is restricted to RSA. Existing cryptanalytic literature exploits irregularly spaced runs of known bits — Extended Hidden Number Problem and Its Cryptanalytic Applications by Hlaváč and Rosa handles the (EC)DSA case where nonces have multiple blocks of unknown bits at arbitrary positions, and Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits by Herrmann and May handles the RSA case where one factor has multiple contiguous blocks of unknown bits. The short-sleeve structure adds regular spacing, which is more information than either of those papers exploits, and there are almost certainly stronger variants of these algorithms tuned for this property. When the same kind of leakage appears in two unrelated RSA implementations, it is reasonable to expect a third.

The high-level lesson is the practical-research feedback loop: known vulnerabilities motivate sharper cryptanalysis, which then uncovers more vulnerabilities. The only way to understand how cryptographic systems fail under real-world implementation choices is to keep watching them break.

Appendix — Synthetic Moduli for Practice

The original article ships two synthetic moduli that follow the same pattern as the in-the-wild keys, plus a series of guided questions for readers who want to implement the attack. The factors of n₂ were generated by calling genRandomBits(1024) in a loop until the result was prime. Reproduced verbatim:

n_1=0xc889f7ef523b08e400000000000000014d2ee8284c7a03c000000000000000012c16eeaeab96ddc8000000000000000201036d671407a06600000000000000022f743377005a840d0000000000000001e8e3c0efdd8054ba000000000000000306ee98c677dfdf190000000000000002de525d2b1011ceae0000000000000424455c59eec3a0654500000000000003f8d762d68bcbe8cc3a00000000000000d31291f9aaa7e9a7d60000000000000337a82a59342aadff570000000000000295c495b3690a69b66c00000000000000d9c5e55654e9b14cba000000000000040f0f0f7d3bfdce03d6000000000000026b89ac77db000000000000000000036a77
n_2=0x40000049000014ac8000900e00010ec58000b17b8001e0720001be890002169f80029cd5000349190003cd4480037c8c000397660003b28300041021000418cb00058a210004c2708004924980053b8780051cbd8005ebe80006bb27800765e6800651478007f62300073949800860950008614d800863988008d103800884c100099a260009a6d90009578f0007e84300080db800072e59000724f10007c0ec0006ec6600062231000605930005ca4c000566cc0005da92000574dd00040bf1000457dc0004cfbe0004c5640003fe6d0003ada60002de110002cbb30002d5a6000243840001cdf40001a8a9000151be000113f4000101070000acdf000029e5

Guided questions from the original article, paraphrased:

• Computing f_n2(x) with B = 2³² produces some unexpectedly large coefficients — why? Are f_p(x) and f_q(x) still small in every coefficient?
• Is there a bit shift p << i such that f_2ⁱp(x) has small coefficients? This is the key trick that maps arbitrary short-sleeve values onto small-coefficient polynomials.
• If f_2ⁱp(x) and f_2^jq(x) have small coefficients, can you compute their product purely from public information? Can you still recover p and q?
• If polynomial factorisation worked for every p and q, RSA would be broken. Why is the short-sleeve property essential, and where does the method fail in the general case?
• The short-sleeve property lets you build the product f_2ⁱp(x) · f_2^jq(x), but unless the factors are irreducible the polynomial factorisation may split it into more than two terms. Prove that there is always an efficient way to recover p and q from the polynomial factorisation.

Key Takeaways

• An RSA modulus that inherits per-limb structure from a buggy RNG path is detectable from the public key alone — no oracle, no side channel.
• The CompleteFTP bug is a textbook size mismatch: byte[] array = new byte[numLimbs] is sized in limb count, then Array.Copy widens each byte into a 32-bit limb, leaking 24 zero bits per limb.
• The cryptanalytic move is to swap factoring integers for factoring polynomials: pick base 2^w to match the limb width, and the short-sleeve gaps become small polynomial coefficients you can factor with classical algorithms.
• 603 RSA keys, 74 DSA keys, plus 26 RSA keys from an unidentified second implementation — small numbers in absolute terms, but the structural lesson is that the same failure shape appeared in two independent codebases.
• Affected CompleteFTP versions: RSA on v10.0.0–v12.0.0 (Dec 2016–Mar 2019), DSA on v10.0.0–v23.0.4 (Dec 2016–Dec 2023). v26.1.0 ships a detection tool.
• The Diffie–Hellman path also called genRandomBits but with a 2048-bit exponent, which keeps DH safe.
• Cryptanalytic algorithms tuned for regularly spaced known-bit blocks are an under-explored area. If two independent implementations leak this way, expect more.

Defensive Recommendations

• If you used CompleteFTP between Dec 2016 and Dec 2023, regenerate host keys. Run EnterpriseDT’s v26.1.0 detection tool against the active RSA and DSA keys; if a key was generated on an affected version, replace it and rotate any downstream credentials that trusted the host key.
• Scan your own fleet with badkeys. The CLI and website now flag short-sleeve RSA moduli alongside the existing checks — useful both for inventoried hosts and for inbound certificates / SSH keys you accept from third parties.
• Audit any in-house big-integer code for byte/word size mismatches. The bug pattern (RNG buffer sized in elements, copy widens each element) is shallow and survives in legacy code well past the point when the original author leaves the project. Add a unit test that asserts the entropy density of a generated big integer.
• Prefer platform crypto APIs over hand-rolled key generation. The CompleteFTP regression vanished once key generation moved to RSACryptoServiceProvider / DSA.Create. The same is true everywhere — crypto/rand readers, EVP_RAND_*, OS CSPRNG wrappers exist for a reason.
• Treat long-lived host keys as a separate risk class. Customers patched CompleteFTP but kept the same keys; that is why the chart plateaus rather than tailing to zero. Document a key-rotation cadence even when the software is current.
• Watch CT logs for biased moduli. If you operate a CA or run subdomain monitoring, a regularly-spaced zero-bit pattern in a submitted public key is a high-signal alert — it almost always means a broken RNG.
• Don’t assume PRNG bugs are detectable only via timing or side channels. The short-sleeve case is a reminder that pure inspection of the public output can be enough when the bug imposes structure on it.
• Constrain trust on stored / cached SSH and TLS public keys. Many of the affected hosts will outlive the affected operator; pin algorithms and key-strength policies that fail closed when a clearly malformed modulus appears.

Conclusion

The short-sleeve disclosure is small in numbers but large in structure. A single type mismatch in a forgotten code path generated hundreds of RSA and DSA keys whose private factors are extractable from the public modulus alone, in seconds, by anyone who notices the right pattern. The polynomial factorisation trick — treating the limb size as a base, mapping the modulus to a small-coefficient polynomial, then factoring that — is the kind of technique that gets sharper every time another buggy RNG produces an exotic public-key shape. The under-reported point is that two independent implementations leaked in essentially the same way; pattern 1 remains unattributed, and there is no reason to expect it to be the last.

Original text: “Factoring “short-sleeve” RSA keys with polynomials” by Keegan Ryan at The Trail of Bits Blog.