Trail of Bits Blog
Follow
Factoring "short-sleeve" RSA keys with polynomials
Researchers discovered that some RSA private keys have bits heavily biased toward 0, which can be detected and factored quickly. Along with Hanno Böck of the badkeys project, they found hundreds of unique keys with this property and analyzed historical data to track the issue over time. The pattern of 0 bits in these keys is often highly structured, allowing for the development of a polynomial-based cryptanalytic technique to exploit the pattern. The researchers identified two patterns of RSA moduli with repeated blocks of 0 bits, with one pattern remaining unexplained and the other traced 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 the researchers recovered 603 unique RSA private keys and 74 DSA keys from internet scans. The badkeys project is an open-source service that checks public keys for known vulnerabilities, and by searching a dataset of real-world keys, the researchers uncovered a large number of keys in the wild with the patterns. The researchers reverse-engineered the CompleteFTP vulnerability and found that it was caused by a mismatch between the size of the limbs and the size of the RNG output. The vulnerability was contained after the CompleteFTP team released an update that automatically checks for vulnerable keys and alerts the user if the key needs to be regenerated. The researchers also developed a technique for factoring integers by representing them as polynomials, which can be used to factor general RSA moduli. The discovery of these vulnerabilities highlights the importance of practical research and the need for continued monitoring of cryptographic implementations to identify and address potential weaknesses.
