The Electronic Frontier Foundation's SSL Observatory is a research project that gathers and analyzes the cryptographic certificates used to secure Internet connections, systematically cataloging them and exposing their database for other scientists, researchers and cryptographers to consult.
Now Arjen Lenstra of École polytechnique fédérale de Lausanne has used the SSL Observatory dataset to show that tens of thousands of SSL certificates "offer effectively no security due to weak random number generation algorithms." Lenstra's research means that much of what we think of as gold-standard, rock-solid network security is deeply flawed, but it also means that users and website operators can detect and repair these vulnerabilities.
While we have observed and warned about vulnerabilities due to insufficient randomness in the past, Lenstra's group was able to discover more subtle RNG bugs by searching not only for keys that were unexpectedly shared by multiple certificates, but for prime factors that were unexpectedly shared by multiple publicly visible public keys. This application of the 2,400-year-old Euclidean algorithm turned out to produce spectacular results.
In addition to TLS, the transport layer security mechanism underlying HTTPS, other types of public keys were investigated that did not use EFF's Observatory data set, most notably PGP. The cryptosystems that underlay the full set of public keys in the study included RSA (which is the most common class of cryptosystem behind TLS), ElGamal (which is the most common class of cryptosystem behind PGP), and several others in smaller quantities. Within each cryptosystem, various key strengths were also observed and investigated, for instance RSA 2048 bit as well as RSA 1024 bit keys. Beyond shared prime factors, there were other problems discovered with the keys, which all appear to stem from insufficient randomness in generating the keys. The most prominently affected keys were RSA 1024 bit moduli. This class of keys was deemed by the researchers to be only 99.8% secure, meaning that 2 out of every 1000 of these RSA public keys are insecure. Our first priority is handling this large set of tens of thousands of keys, though the problem is not limited to this set, or even to just HTTPS implementations.
We are very alarmed by this development. In addition to notifying website operators, Certificate Authorities, and browser vendors, we also hope that the full set of RNG bugs that are causing these problems can be quickly found and patched. Ensuring a secure and robust public key infrastructure is vital to the security and privacy of individuals and organizations everywhere.
Researchers Use EFF's SSL Observatory To Discover Widespread Cryptographic Vulnerabilities
