In summer 2012, a pair of academic papers appeared describing large-scale audits of RSA public keys obtained from the internet. The main technique used was to GCD all the keys together to detect moduli with shared factors: if you find two valid public keys sharing a prime factor, this is enough to calculate the private keys. Computing GCD of a large number of keys is quite efficient thanks to Bernstein’s algorithms.
Since then, so-called “batch GCD” has been used to factor moduli of Taiwanese smartcards, to make the FREAK attack even more powerful, and recently (by us) to factor public SSH keys of Github users. Given this widespread use, you might expect that factorable keys on the public Internet are becoming scarcer.
The 2012 papers, by Lenstra et al and Heninger et al, reported factoring rates of 12,934 out of 5,989,923 RSA keys (0.22%) and 16,717 out of 11,170,883 (0.15%) respectively. To see how things have changed three years on, we downloaded the latest zmap scan of RSA keys offered by public TLS servers and ran them through our OCaml batch GCD implementation. The result: 19,256 / 13,603,691 factored, which is about 0.14% – next to no improvement in three years!
Making “Bad key” detection easier
At Cryptosense we often come back from a security audit with a stack of RSA keys from internal SSH and TLS servers running on firewalls, routers etc. Running these through batch GCD against all the other pervious RSA keys we’ve encountered (including current and old zmap sets, the Github users set, etc.) is a standard test. To make it easier for administrators to detect weak RSA keys, we’ve put an interface to our tester online. You can submit a key and we’ll run it through batch GCD with all the keys in our our database (currently just over 20 million) and email you the result. We also check against a bunch of well-known blacklists, including the well-known Debian bug from 2008.
Should we factor the key, we’ll get in touch about sending you the factors securely.
Currently the front-end only parses SSH keys, but very shortly we’ll hook it up to our other parsers.