The Lesson of Short-Sleeve RSA Is That Cryptography Fails in Shapes

Thesis

The Trail of Bits report on short-sleeve RSA keys is not merely a story about one flawed key generator; it is a reminder that cryptographic failure often has form. When randomness is absent in a repeated, structured way, the resulting public keys may carry a visible mathematical signature, and that signature can turn a problem designed to be computationally impossible into one that is almost routine.

Together with Hanno Böck of the badkeys project, Trail of Bits found hundreds of public keys whose RSA moduli contained repeated blocks of zero bits. These were not ordinary weak keys in the familiar sense of reused primes or insufficient bit length. They were keys whose internal representation had been starved of entropy in a regular pattern, creating what the researchers call “short-sleeve” keys, because only part of each big-integer limb was filled with random data while the rest remained uncovered by randomness.

The practical result was severe but bounded. The researchers recovered private keys for 603 unique RSA public keys and 74 DSA keys associated with vulnerable CompleteFTP versions, plus 26 RSA keys with a still-unidentified short-sleeve pattern. The more philosophically interesting result is broader: once implementation failure takes on structure, cryptanalysis can stop treating the key as a black box and start treating it as an artifact, something made by a flawed machine whose mistakes can be reverse-engineered.

Key Arguments

The flaw was visible in public keys

RSA security depends on the difficulty of factoring a large modulus, n, which is the product of two secret primes, p and q. Under normal generation, p and q should look random enough that their product also lacks exploitable structure. The public modulus is meant to reveal almost nothing useful about the private factors.

The keys in the Trail of Bits analysis violated that assumption in a way that could be detected at scale. In large datasets collected through Certificate Transparency logs, TLS and SSH scans, PGP keys, and other public sources, the researchers searched for RSA moduli with unusually sparse bit patterns. They found two recurring forms, both involving regularly spaced blocks of zero bits.

Pattern 1 appeared in expired certificates associated with large organizations, including Yahoo and Verizon, and in some devices running NetApp software. The generating product remains unidentified. Pattern 2 appeared in SSH hosts running CompleteFTP, a file transfer server from EnterpriseDT. That second pattern could be traced to old versions of CompleteFTP: RSA keys generated by versions 10.0.0 through 12.0.0, from December 2016 to March 2019, and DSA keys generated by versions 10.0.0 through 23.0.4, from December 2016 to December 2023.

The key observation is that a public key does not need to expose the private key directly to betray its origin. If many keys produced by the same implementation share a structural bias, the public key becomes evidence of the generator’s internal mistake. This is why projects such as badkeys matter: they treat the internet’s public keys as an empirical record of how cryptography is actually implemented, deployed, neglected, upgraded, and forgotten.

The mathematical shortcut came from changing the representation

The most elegant part of the research is the polynomial factorization technique. RSA asks an attacker to factor a large integer. For ordinary RSA moduli, that is precisely the hard problem. But these short-sleeve moduli were not ordinary integers in the practical sense; they were integers produced by a flawed limb-by-limb process.

Big integers are commonly represented as arrays of smaller machine-sized chunks called limbs. A 2048-bit integer, for example, may be stored as many 32-bit or 64-bit limbs. In correctly generated keys, each limb should contain enough random material. In the vulnerable CompleteFTP case, each 32-bit limb received only an 8-bit random value, leaving the rest of the limb mostly zero.

That repeated absence of entropy changes the problem. The researchers represent the integer in base B, where B corresponds to the limb size, and reinterpret the base-B digits as coefficients of a polynomial. In ordinary notation, an integer a written as a sum of digits ai times powers of B corresponds to a polynomial whose coefficients are those same digits, but with x replacing B. Evaluating the polynomial at B converts it back into the original integer.

This representation is always possible, but it is only useful for the attack when the coefficients are small. For normal RSA keys, the coefficients corresponding to p and q would be full-sized limb values, and polynomial factorization would not magically reveal the private factors. For short-sleeve keys, however, the missing entropy means the coefficients are unusually small, because the high bits of each limb are often zero. The modulus n can be converted into a polynomial fn(x), and, under the right alignment, factoring that polynomial can reveal polynomial forms corresponding to p and q. Evaluating those factors at the limb base yields the RSA private factors.

This is the conceptual pivot: the researchers did not break RSA as mathematics. They broke a family of RSA keys whose generation process accidentally moved them from the hard world of general integer factorization into the easier world of special-form polynomial factorization.

The implementation bug was ordinary, which makes it more instructive

The CompleteFTP vulnerability came from a type mismatch in custom big-integer code. The vulnerable function attempted to generate a random big integer of a requested bit length. It calculated the number of 32-bit limbs, allocated a byte array of that length, filled the byte array with nonzero random bytes, and then copied those bytes into an array of 32-bit limbs.

The intention was to fill each limb with randomness. The actual effect was to give each 32-bit limb only one byte of random data. The rest of each limb remained zero. In other words, the software confused a count of limbs with a count of bytes, and the key generator silently produced numbers with a regular entropy deficit.

That kind of bug is not exotic. It is not a failure of cryptographic theory. It is a failure at the boundary between representation and security, where a programmer’s mental model of a data structure drifts away from what the code actually does. This is why the report is valuable beyond CompleteFTP: it shows that cryptographic systems can fail because mundane software abstractions, array lengths, element sizes, implicit casts, and legacy code paths, interact with mathematical assumptions that are far less forgiving than ordinary application logic.

The researchers used ILSpy to inspect the .NET binary and eventually found the vulnerable function. They also discovered why newer dynamic testing did not reproduce the broken RSA keys: the flawed function still existed in the binary, but newer RSA generation no longer reached it. CompleteFTP had moved RSA generation to standard .NET cryptographic APIs, including RSACryptoServiceProvider, and later moved DSA generation to DSA.Create. That refactoring sharply limited the long-term blast radius.

The historical scan data tells a familiar operational story. Once the RSA generation code changed in March 2019, the creation of new vulnerable RSA keys appears to have stopped. Yet vulnerable keys remained visible because administrators often update software without regenerating long-lived host keys. Software moves, but cryptographic identity persists. A patched generator cannot repair keys that were already minted unless someone explicitly rotates them.

Implications

The first implication is practical: affected users should check and rotate keys. EnterpriseDT released CompleteFTP v26.1.0 on May 8, 2026, with automatic checks for vulnerable RSA and DSA keys, and the company also released a standalone checking tool. The badkeys website and standalone tooling can detect vulnerable short-sleeve RSA keys as well. Any organization that generated CompleteFTP host keys during the affected windows should treat this as a key hygiene event, not merely a software update.

The second implication is architectural: cryptographic implementations should avoid custom key generation whenever mature platform APIs exist. This is not because standard libraries are perfect, but because key generation is a place where tiny representational errors can have nonlocal consequences. The CompleteFTP case improved significantly when the product moved away from custom code and toward .NET’s maintained cryptographic interfaces. That decision did not erase already vulnerable keys, but it stopped the generator from continuing to produce them.

The third implication is methodological: cryptanalysis benefits from studying real failures, not only idealized constructions. The short-sleeve work sits in a lineage of attacks that exploit partial information about secret values, including known-bit attacks against RSA factors and hidden-number style attacks against DSA and ECDSA nonces. What makes short-sleeve keys distinctive is the regular spacing of the leakage. The missing bits are not a single contiguous wound; they are a repeating pattern across limbs, which invites algorithms that understand the manufacturing process of the number.

This matters because public-key cryptography is often described in terms of abstract hardness assumptions. RSA is secure because factoring is hard. DSA is secure because discrete logarithms are hard. Such statements are true only after the keys and nonces have been generated according to the assumptions required by the scheme. A biased generator creates mathematical objects that may no longer live inside the intended security argument. The proof did not fail; the object wandered out of the proof’s jurisdiction.

The fourth implication concerns measurement. Internet-wide scans, Certificate Transparency, and public key datasets are sometimes treated as passive observatories, useful for counting versions or finding exposed services. This research shows they can also function as a kind of cryptographic telescope. They reveal weak patterns that no single vendor, customer, or auditor would necessarily see alone. A key generated in isolation may look like a random accident. A thousand keys generated by related software can reveal the shape of the accident.

There is also a governance lesson. EnterpriseDT’s responsive disclosure handling and release of detection tooling limited user uncertainty. But the report also shows how difficult attribution can be. Pattern 1 remains unexplained despite appearing in real certificates and devices. Some certificates expired, some companies were notified, but the generating code path remains unknown. Vulnerabilities in cryptographic generation can outlive the product versions that created them, and they can remain partially anonymous even when their outputs are public.

Counter-Perspectives

A restrained reading of the report would say that the direct impact is limited. The number of recovered keys is not enormous relative to the internet. The known CompleteFTP RSA issue affected a specific historical version range. The vulnerable DSA issue persisted longer, but DSA itself is less central in many modern deployments. Pattern 1 certificates were already expired. From an incident response standpoint, this is not evidence that RSA is broadly unsafe.

That reading is correct, but incomplete. The point is not that every RSA key should now be suspected of polynomial factorization. The point is that real cryptographic systems fail through implementation-specific structure, and that structure can be detected only if researchers look for it. If two independent RSA-producing systems generated short-sleeve-like artifacts, then this family of mistakes is probably not exhausted.

Another counter-perspective is that standard libraries are sometimes treated too reverently. They can contain bugs, suffer from misuse, or lag behind best practice. That is true. But the lesson here is narrower and more concrete: key generation is a poor place for casual custom arithmetic. A custom implementation must correctly handle randomness, integer representation, bit length, primality testing, serialization, parameter selection, and edge cases across platforms. The burden is high because the cost of being slightly wrong is not a slightly degraded user experience; it can be private-key recovery.

A final counter-perspective concerns disclosure and public explanation. Publishing techniques for finding and factoring weak keys may seem dangerous. Yet obscurity would mostly protect the conditions under which vulnerable keys remain deployed. Once the pattern exists in public keys, capable attackers can independently search for it. Defensive publication changes the balance by giving vendors, scanners, and operators a shared vocabulary for detection and remediation.

The deeper lesson is that cryptography is not only a theory of hard problems. It is also a theory of how software creates mathematical objects under pressure from APIs, legacy code, platform differences, and maintenance habits. Short-sleeve RSA keys are weak because their limbs remember the bug that made them. The public modulus becomes a fossil of implementation error, and the polynomial attack is the instrument that reads it.