What happens when the bits of an RSA private key are heavily biased toward 0 instead of being randomly generated? The public key’s bits could be biased enough for us to detect these incorrectly generated keys in the wild. Together with Hanno Böck of the badkeys project, we found hundreds of unique keys that not only have this property, but can be quickly factored. We also found the bug that led to many of these keys and analyzed historical data to track the issue over time. Surprisingly, the pattern of 0 bits is often highly structured, allowing us to develop a powerful polynomial-based cryptanalytic technique that exploits the pattern.

These “short-sleeve” keys, named for how the 0 bits don’t fully cover the limbs of the big integers, largely fell into two patterns. Pattern 1 remains unexplained, but we traced pattern 2 to a type mismatch in big-integer code from old versions of the CompleteFTP file transfer software. The CompleteFTP bug also generated vulnerable short-sleeve DSA keys, and we recovered 603 unique RSA private keys and 74 DSA keys from internet scans. If you used CompleteFTP to generate host keys between December 2016 and December 2023, CompleteFTP has released a tool to check whether your keys need to be regenerated.

How we found the weak keys

The badkeys project is an open-source service that checks public keys for known vulnerabilities. While developing this tool, Hanno collected a massive number of real-world keys from public sources, including Certificate Transparency logs, internet-wide TLS and SSH scans, PGP keys, and many others. By searching this dataset for unexpectedly sparse RSA moduli, we uncovered a large number of keys in the wild with the patterns in Figure 1.

Both patterns include several regularly spaced blocks of all zeros interleaved with seemingly random data. Pattern 1 appears in CT logs for certificates issued to several large organizations, including Yahoo and Verizon, and on some devices running NetApp software. Fortunately, these certificates have already expired, but we still shared our findings with these companies. We wanted to learn more about which product could be responsible for generating these keys, but we did not hear back. Pattern 2 appears on SSH hosts running the CompleteFTP software from EnterpriseDT. The underlying vulnerability affects RSA keys generated using versions 10.0.0–12.0.0 (Dec 2016–Mar 2019) and DSA keys generated with v10.0.0–23.0.4 (Dec 2016–Dec 2023).

These vulnerabilities affect a small minority of hosts on the internet, but the more interesting takeaway is that independent cryptographic implementations failed in similar ways. More implementations may include the same bugs, and so it’s worth tailoring cryptanalytic algorithms for this particular type of failure.

Cryptographic algorithms often need integers hundreds or thousands of bits long, and they represent these “big integers” using an array of smaller machine-sized values, called limbs. If we interpret pattern 1 as a sequence of 128-bit limbs, or 32-bit limbs in pattern 2, the repeated blocks of zeros correspond to a single block of zeros in each limb. Only a small contiguous subset of the limb is filled with random bits, and the rest of the limb is uncovered, hence the nickname “short-sleeve keys.”

By exploiting this mathematical structure in the limbs of these moduli, we replace the hard problem of factoring integers with the easy problem of factoring polynomials. That is, we take the 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 these factors into $p$ and $q$. The technique of converting between integers and polynomials is common, including doing fast polynomial multiplication, but sadly, few resources describe how to use it for fast integer factorization.

In particular, we use the digits in the base-$B$ representation of the integer to set the coefficients of the polynomial. In the normal base-10 representation, this involves replacing powers of 10 with powers of $x$, and then converting a polynomial back to an integer involves replacing powers of $x$ with powers of 10. Mathematically, the base-$B$ representation of an integer $a = \sum_i a_i B^i$ corresponds to the polynomial $f_a(x) = \sum_i a_i x^i$, and the polynomial evaluation $a = f_a(B)$ converts back to an integer. For short-sleeve keys, the base corresponds to the limb size, and the extra zero bits in each limb will lead to polynomials with exceptionally small coefficients.

This method of representing integers with polynomials is useful because the product of evaluations $f_a(B) * f_c(B)$ equals the evaluation of the product $(f_a*f_c)(B)$. All evaluation does is replace $x$ with $B$, so it doesn’t matter if this happens before or after multiplication. The same is true of addition.¹

For a short-sleeve RSA modulus $n$ with $w$-bit limbs, we can use the base-$2^w$ representation to find 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)$. Note that for correctly generated prime factors, $f_p(x)$ and $f_q(x)$ will typically have $w$-bit coefficients; that’s why this attack doesn’t work in general.

Factoring polynomials is easy, so we can factor $f_n(x)$ to get $f_p(x)$ and $f_q(x)$, then evaluate these factors at $2^w$ to get $p$ and $q$. This is the basic version of the attack, but I’m intentionally omitting a key insight needed to factor these real-world moduli. A full explanation is at the end of this blog.

The correspondence between integers and polynomials makes it easy to factor these special form moduli, but interestingly, it helps factor general RSA moduli as well. The General Number Field Sieve (GNFS) algorithm has the best known asymptotic performance, and the first step is defining a number field by selecting a polynomial $f_n(x)$ and evaluation point $m$ such that $f_n(m) = n$.²

Reverse engineering the CompleteFTP vulnerability

After applying this technique to the keys that Hanno found, we found that the private factors are indeed short-sleeved: the prime factors have large, regularly spaced blocks of unset bits. The SSH banners for the hosts with the second pattern indicate they use the CompleteFTP software, so we reverse-engineered a trial version to determine what caused the vulnerable keys.

Dynamically generated RSA keys did not have the short-sleeve pattern³, so we used the ILSpy tool to decompile the .NET code in the demo binary. After some reverse engineering, we found the bug that generated the short-sleeve keys. The following function fills the big integer represented by bignumLimbs with a randomly generated value of the desired bit length. See if you can spot the problem.

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;
}

There’s a mismatch between the size of the limbs and the size of the RNG output! Each limb requires 32 bits of random material, but Array.Copy implicitly casts each 8-bit element of the RNG output to its own element of the big-integer limbs. The repeating structure in the short-sleeve keys is because the issue affects each limb, and the 0 bits are because too small of a value is copied to each limb. This exactly matches the pattern of the cryptanalyzed keys.

We also figured out why our dynamic testing did not generate broken keys: the genRandomBits function was compiled in but unreachable in the latest version. Older versions used custom-written key-generation code that called this vulnerable function, which was later refactored to use standard .NET crypto APIs.

We reverse-engineered an older version of the CompleteFTP software to look for other calls to genRandomBits and found that DSA key generation was also affected. The 160-bit DSA private key $x$ was previously generated by this function, and the public key and parameters include a generator $g$ and target $y = g^x$. The private key is easily recoverable, and once we knew what to look for, we found vulnerable DSA keys in the wild as well.⁴

Since v12.1.0, CompleteFTP generates RSA keys using .NET’s RSACryptoServiceProvider, and since v23.1.0, it generates DSA keys using the DSA.Create API.

How the vulnerability spread, and how it was contained

The decision to refactor key-generation code to use standard libraries significantly mitigated the scope of the impact. This is actually reflected in the data. Prof. Nadia Heninger has a large collection of historical and contemporary SSH scans that we used to find broken SSH RSA signatures, so I checked to see whether it included CompleteFTP hosts. There were typically hundreds of CompleteFTP hosts in each IPv4-wide scan, and after aligning the historical scans to the release history, the trend is clear.

Starting with the introduction of the RSA vulnerability in December 2016, there was a consistent increase in the number of hosts with vulnerable keys, and once the rewritten RSA code was released in March 2019, this trend immediately stopped. However, even though the number of hosts running an affected version has steadily decreased since then, the proportion of affected keys has plateaued, consistent with customers who regularly update their software but generate their keys only once.

The EnterpriseDT team was very responsive throughout disclosure. To help these users, EnterpriseDT released v26.1.0 of CompleteFTP on May 8, 2026; this update automatically checks if the system is using a vulnerable RSA or DSA key and alerts the user if the key needs to be regenerated. They also released a standalone tool that does the same. In addition, the badkeys website and standalone tool now support the detection of vulnerable short-sleeve RSA keys.

In total, we recovered private keys for 603 unique RSA public keys and 74 DSA keys generated by vulnerable versions of CompleteFTP, and 26 RSA keys with the unidentified short-sleeve pattern. Our data sources are heavily biased toward RSA SSH keys, so these numbers do not reflect the actual prevalence.

The search for more short-sleeve keys

Unfortunately, we do not have more information about short-sleeve pattern 1, nor do we know whether that vulnerability extends to other key types. It’s common for cryptanalytic algorithms to exploit knowledge of irregularly spaced blocks of known bits (including ECDSA⁵ and RSA⁶), but the regular spacing of short-sleeve leakage adds new structure, and there may be powerful variants of these algorithms that can exploit this property. If this type of leakage appears in two independent implementations of RSA, there are likely to be even more examples of short-sleeve keys out there.

In this instance, the impact of the vulnerabilities is fortunately limited, but it illustrates the power of practical research. The process of using known vulnerabilities to inspire more capable algorithms and using these algorithms to uncover new vulnerabilities generates a powerful feedback loop in cryptanalysis. It helps us understand how real cryptographic systems fail in practice, and it is only by observing how systems break that we learn how to make them more secure.

Acknowledgments

Thank you to Nadia Heninger for introducing me to Hanno and for letting me use the SSH scans for this project. Those scans consist of historical data from Censys and the University of Michigan provided by Zakir Durumeric and contemporary data and analysis scripts from Kevin He and George Sullivan.

Appendix

This final section is intended for those who want to implement the attack or write a proof that the attack works. I left out key details from the main post, but the following guided questions will help you close that gap. First, here are the full moduli for you to factorize. They are synthetically generated, but follow the same pattern as keys in the wild. The factors of $n_2$ were generated by calling genRandomBits(1024) in a loop until the result was prime.

n_1=0xc889f7ef523b08e400000000000000014d2ee8284c7a03c000000000000000012c16eeaeab96ddc8000000000000000201036d671407a06600000000000000022f743377005a840d0000000000000001e8e3c0efdd8054ba000000000000000306ee98c677dfdf190000000000000002de525d2b1011ceae0000000000000424455c59eec3a0654500000000000003f8d762d68bcbe8cc3a00000000000000d31291f9aaa7e9a7d60000000000000337a82a59342aadff570000000000000295c495b3690a69b66c00000000000000d9c5e55654e9b14cba000000000000040f0f0f7d3bfdce03d6000000000000026b89ac77db000000000000000000036a77
n_2=0x40000049000014ac8000900e00010ec58000b17b8001e0720001be890002169f80029cd5000349190003cd4480037c8c000397660003b28300041021000418cb00058a210004c2708004924980053b8780051cbd8005ebe80006bb27800765e6800651478007f62300073949800860950008614d800863988008d103800884c100099a260009a6d90009578f0007e84300080db800072e59000724f10007c0ec0006ec6600062231000605930005ca4c000566cc0005da92000574dd00040bf1000457dc0004cfbe0004c5640003fe6d0003ada60002de110002cbb30002d5a6000243840001cdf40001a8a9000151be000113f4000101070000acdf000029e5

1. If you compute $f_{n_2}(x)$ using $B=2^{32}$, some of the coefficients are large. Why is that? Is it true that all of the coefficients of $f_p(x)$ and $f_q(x)$ are small?
2. Is there a bit shift $p \ll i$ such that $f_{2^i p}(x)$ has small coefficients? This is the key trick needed to turn arbitrary short-sleeve values into polynomials with small coefficients.
3. If $f_{2^i p}(x)$ and $f_{2^j q}(x)$ have small coefficients, can you still compute $f_{2^i p}(x)*f_{2^j q}(x)$ from public information? Can you still recover $p$ and $q$?
4. If this polynomial factorization technique worked for every $p$ and $q$, then RSA would be broken. Why is the short-sleeve property important, and why doesn’t this factorization method work in general? What are the limits?
5. The short-sleeve property allows us to construct the product $f_{2^i p}(x)*f_{2^j q}(x)$, but unless $f_{2^i p}(x)$ and $f_{2^j q}(x)$ are irreducible, factorization may split this into more than two terms. Prove that there is always an efficient way to recover $p$ and $q$ from the polynomial factorization.