Mining ' and Minding ' Her Ps and Qs

Aug 10, 2012
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.

( -- 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 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.”

Explore further: EU open source software project receives green light

More information: Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices, Nadia Heninger, Zakir Durumeric, Eric Wustrow, J. Alex Halderman, Proc. 21st USENIX Security Symposium, August 2012.

Related Stories

Flaw found in securing online transactions

Feb 16, 2012

Researchers on Wednesday revealed a flaw in the way data is scrambled to protect the privacy of online banking, shopping and other kinds of sensitive exchanges.

Improving the security of Internet exchanges

Mar 20, 2009

( -- TLS is the main protocol used today to secure exchanges over the Internet. The protocol has been subject to attacks in recent years, resulting in identity theft and data tampering. To address these problems, ...

Recommended for you

EU open source software project receives green light

Jul 01, 2015

An open source software project involving the University of Southampton to extend the capacity of computational mathematics and interactive computing environments has received over seven million euros in EU funding.

Can computers be creative?

Jul 01, 2015

The EU-funded 'What-if Machine' (WHIM) project not only generates fictional storylines but also judges their potential usefulness and appeal. It represents a major advance in the field of computational creativity.

Algorithm detects nudity in images, offers demo page

Jul 01, 2015

An algorithm has been designed to tell if somebody in a color photo is naked. launched earlier this month; its demo page invites you to try it out to test its power in nudity detection. You ...

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet Aug 12, 2012
Picking a good "random" public key has always been a problem for public-key encryption. The software just isn't being written well enough, and Nadia has found out who's software is the worst.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.