Factoring RSA Keys with Many Zeros
Researchers have identified a new class of weak RSA encryption keys that contain numerous zeros in their structure. These keys, found in real-world deployments, could potentially be factored more easily than standard RSA keys. The discovery was made by analyzing a large dataset of public keys collected from various sources, including Certificate Transparency logs, internet-wide scans for TLS and SSH, and PGP keys.
The identified weak keys exhibit specific patterns of regularly spaced blocks of zeros interspersed with seemingly random data. One such pattern was observed in certificates issued to major organizations like Yahoo and Verizon, as well as on some NetApp devices. While the affected certificates have already expired, the findings were shared with the organizations. Efforts to determine the product responsible for generating these keys were unsuccessful.
A second pattern of weak keys was found on SSH hosts running EnterpriseDT's CompleteFTP software. The vulnerability impacts RSA keys generated by versions 10.0.0 through 12.0.0 of the software, released between December 2016 and March 2019. Additionally, DSA keys generated by the same software, specifically versions 10.0.0 through 23.0.4 (December 2016 to December 2023), are also affected.
While these vulnerabilities affect a relatively small number of internet hosts, the research highlights a concerning trend of similar cryptographic implementation failures occurring independently. This suggests that other cryptographic implementations might harbor similar weaknesses, warranting the development of specialized cryptanalytic algorithms tailored to detect and exploit this particular type of key generation flaw.
The discovery raises questions about the origin of these weak keys. While the research itself does not speculate, the potential for deliberately designed backdoors cannot be entirely dismissed. Such backdoors could theoretically be implemented to allow specific entities to break these classes of RSA keys, potentially with the cooperation of software providers.
The badkeys project, an open-source service that checks public keys for known vulnerabilities, was instrumental in this discovery. The extensive collection of real-world keys provided a unique dataset for identifying these anomalies. The researchers emphasize the importance of continued vigilance and tailored cryptanalytic approaches to address such specific weaknesses in cryptographic implementations.
