Factoring "short-sleeve" RSA keys with polynomials - The Trail of Bits BlogPage content

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.<br>Figure 1: Two patterns of RSA moduli with repeated blocks of 0 bits seen in real-world examples.<br>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.<br>How we found the weak keys<br>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.<br>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).<br>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&rsquo;s worth tailoring cryptanalytic algorithms for this particular type of failure.<br>Factoring with polynomials<br>Cryptographic algorithms often need integers hundreds or thousands of bits long, and they represent these &ldquo;big integers&rdquo; 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 &ldquo;short-sleeve keys.&rdquo;<br>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.<br>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.<br>Figure 2: Integers with blocks of 0 bits can be represented as polynomials with small coefficients.<br>This method of representing integers with polynomials is useful because the product of...