Update (2012-02-17): After some investigation and facts that came to light as a result of a parallel experiment by researcher Nadia Heninger at UC San Diego and collaborators at the University of Michigan, it seems the scope of the problem with respect to keys associated with X.509 certificates is limited primarily to certificates that exist for embedded devices such as routers, firewalls, and VPN devices. The small number of vulnerable, valid CA-signed certificates have already been identified and the relevant parties have been notified. Nadia's excellent blog post provides a good overview of the situation right now. We are working with her on disclosure and to provide people with tools to audit against these types of vulnerabilities via the Decentralized SSL Observatory.

Using previously published and new data from EFF's SSL Observatory project, a team of researchers led by Arjen Lenstra at EPFL conducted an audit of the public keys used to protect HTTPS. Lenstra's team has discovered tens of thousands of keys that offer effectively no security due to weak random number generation algorithms.

The consequences of these vulnerabilities are extremely serious. In all cases, a weak key would allow an eavesdropper on the network to learn confidential information, such as passwords or the content of messages, exchanged with a vulnerable server. Secondly, unless servers were configured to use perfect forward secrecy, sophisticated attackers could extract passwords and data from stored copies of previous encrypted sessions. Thirdly, attackers could use man-in-the-middle or server impersonation attacks to inject malicious data into encrypted sessions. Given the seriousness of these problems, EFF will be working around the clock with the EPFL group to warn the operators of servers that are affected by this vulnerability, and encourage them to switch to new keys as soon as possible.

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.

Thanks to iSec Partners, the NLnet Foundation and SingleHop for supporting EFF's work on the Observatory.