Factoring "short-sleeve" RSA keys with polynomials
a day ago
- #vulnerability
- #cryptanalysis
- #RSA
- RSA private keys with bits heavily biased towards 0 can be detected and factored due to structured patterns of zeros, termed 'short-sleeve' keys.
- Two patterns were identified: Pattern 1 linked to unknown causes but found in certificates for companies like Yahoo and Verizon; Pattern 2 traced to a bug in CompleteFTP software from December 2016 to December 2023.
- A polynomial-based cryptanalytic method converts the integer factorization problem into polynomial factorization by exploiting the limb structure of big integers, making factoring easy for these keys.
- Reverse engineering revealed the CompleteFTP bug involved a mismatch in limb size and RNG output, causing repeated zero patterns in RSA and DSA keys.
- Historical data shows vulnerable keys increased until fixes were implemented, with automated tools now available to check and regenerate affected keys.
- The study recovered 603 unique RSA and 74 DSA private keys from scans, highlighting how cryptographic failures in independent implementations can lead to similar vulnerabilities.
- The research demonstrates a feedback loop where practical vulnerabilities inspire new algorithms, enhancing cryptanalysis and improving security understanding.