Mining ' and Minding ' Her Ps and Qs

(Phys.org) -- Each time you connect to a secure website (say a bank’s website), you begin by downloading a certificate published by the site, which asserts that its Web address is legitimate. It also contains a public key that your computer can use to establish a secure connection, and this public key, ostensibly, prevents anyone else from spying on your connection.

Nadia Heninger, winner of the best paper award at this week's USENIX Security Symposium, scanned the entire Internet and found hundreds of thousands of instances of insecure Internet connections.

But according to the paper presented at the 21st USENIX Security Symposium Aug. 9 in Bellevue, Wash., vulnerable public keys are “surprisingly widespread” on the Internet, especially for certain types of devices such as routers and firewalls. The paper, “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices,” won the conference’s Best Paper award Aug. 8.

UC San Diego postdoctoral researcher Nadia Heninger co-authored the paper with Zakir Durumeric, Eric Wustrow and J. Alex Halderman of the University of Michigan. To pursue their research, Heninger and her colleagues scanned the entire Internet in 24 hours and collected public keys from 22 million hosts, which were using them to secure Web and SSH connections.

The researchers found evidence that public keys for hundreds of thousands of devices were insecure because they had been generated in a way that would allow anyone to easily calculate the private keys. Further, devices from dozens of manufacturers – 54 cited in the paper – proved vulnerable, and the researchers informed all of them prior to publishing their results.

Two cryptographic algorithms have been the de facto standards used for these public keys: RSA, an acronym that derives from the last names of inventors Ronald Rivest, Adi Shamir and Leonard Adleman; and DSA, the U.S. federal standard Digital Signature Algorithm.

The problem, says Heninger, is that some of these public keys are not sufficiently random. “These public-key algorithms are supposed to be designed so that it is impossible for someone to figure out the private key just by looking at a public key,” she explained. “But because these keys were not truly random, we were able to use mathematical relationships between pairs of keys to calculate their private keys.”

If two different devices have the same public key, they also have the same private key, which means that malicious users could gain access to restricted content in one location if they merely decode the public key for the other.

Heninger says her team was able “to remotely compromise about 0.4 percent of all the public keys used for SSL [Secure Socket Layer] Web site security.” The SSL ‘handshake’ protocol typically uses RSA encryption, which consists of two numbers – one of which is the product of two randomly chosen prime numbers, p and q, which are produced by the RSA key-generation algorithm.

Fortunately, servers and most large websites were in the clear: all of the compromised keys were “for various kinds of routers and firewalls and VPN servers – no banks,” said Heninger. These ’unsigned’ certificates had been automatically generated by ‘headless’ devices and were not sufficiently random, whereas the vast majority of certificates that were signed by a certificate authority (and most likely had been generated by humans) appear secure.

Among other results, the researchers found that 5.57 percent of TLS (HTTPS) hosts and 9.6 percent of SSH hosts share public keys in an apparently vulnerable manner due to either insufficient randomness during key generation or device default keys. They were also able to obtain remotely the RSA private keys for 0.5 percent of TLS hosts and 0.03 percent of SSH hosts because their public keys shared nontrivial common factors due to poor randomness. In addition, they were able to obtain remotely the DSA private keys for just over 1 percent of SSH hosts due to repeated signature randomness.

The only fix, according to Heninger, is for device manufacturers and software developers to “make sure they generate their keys with good randomness.” She and her colleagues have developed an online service that lists all of the compromised keys they discovered, so users can check keys against them. [Go to factorable.net and click on “Check Your Key.”]

“This is a wake-up call to the security community,” concluded Heninger. “It’s a reminder to all of how security vulnerabilities can sometimes be hiding in plain sight.”