Short-Sleeve RSA Keys: Weak Keys from Biased Bits in Cryptographic Implementations
Researchers from the badkeys project and technical experts discovered hundreds of RSA and DSA private keys with a unique vulnerability: their bits are heavily biased toward 0, forming regular blocks of zeros in the modulus. This pattern, termed 'short-sleeve keys,' weakens the cryptographic strength, allowing quick factorization using polynomial techniques. Two patterns emerged: Pattern 1 affects keys from large organizations including Yahoo and Verizon (all certificates expired), and Pattern 2, traced to a type mismatch bug in CompleteFTP software (versions 10.0.0–23.0.4). The bug caused big integer generation to use incorrect limb sizes, resulting in repeated zero blocks. They recovered 603 RSA and 74 DSA private keys from internet scans. This attack leverages polynomial representation to convert integer factorization into easy polynomial factorization. The discovery highlights the importance of correct cryptographic implementation, especially for big integer handling, and serves as a reminder that independent implementations can fail in similar ways.
Key facts
- Hundreds of RSA and DSA keys found with heavily biased bits toward 0.
- Patterns involve regular blocks of zeros in the modulus (short-sleeve keys).
- Bug in CompleteFTP (v10.0.0–23.0.4) caused type mismatch in big integer generation.
- Polynomial factoring technique exploits zero patterns to factor keys quickly.
- 603 RSA and 74 DSA private keys recovered from internet scans.