Mining Your Ps and Qs: Detection of

Widespread Weak Keys in Network Devices

Nadia Heninger†∗ Zakir Durumeric‡∗ Eric Wustrow‡ J. Alex Halderman‡

† University of California, San Diego ‡ The University of Michigan
nadiah@cs.ucsd.edu {zakir, ewust, jhalderm}@umich.edu

Abstract expect that today’s widely used operating systems and

RSA and DSA can fail catastrophically when used with server software generate random numbers securely. In this
malfunctioning random number generators, but the extent paper, we test that proposition empirically by examining
to which these problems arise in practice has never been the public keys in use on the Internet.
comprehensively studied at Internet scale. We perform The first component of our study is the most compre-
the largest ever network survey of TLS and SSH servers hensive Internet-wide survey to date of two of the most
and present evidence that vulnerable keys are surprisingly important cryptographic protocols, TLS and SSH (Sec-
widespread. We find that 0.75% of TLS certificates share tion 3.1). By scanning the public IPv4 address space,
keys due to insufficient entropy during key generation, we collected 5.8 million unique TLS certificates from
and we suspect that another 1.70% come from the same 12.8 million hosts and 6.2 million unique SSH host keys
faulty implementations and may be susceptible to com- from 10.2 million hosts. This is 67% more TLS hosts
promise. Even more alarmingly, we are able to obtain than the latest released EFF SSL Observatory dataset [18].
RSA private keys for 0.50% of TLS hosts and 0.03% of Our techniques take less than 24 hours to scan the entire
SSH hosts, because their public keys shared nontrivial address space for listening hosts and less than 96 hours
common factors due to entropy problems, and DSA pri- to retrieve keys from them. The results give us a macro-
vate keys for 1.03% of SSH hosts, because of insufficient scopic perspective of the universe of keys.
signature randomness. We cluster and investigate the vul- Next, we analyze this dataset to find evidence of several
nerable hosts, finding that the vast majority appear to be kinds of problems related to inadequate randomness. To
headless or embedded devices. In experiments with three our surprise, at least 5.57% of TLS hosts and 9.60% of
software components commonly used by these devices, SSH hosts use the same keys as other hosts in an appar-
we are able to reproduce the vulnerabilities and identify ently vulnerable manner (Section 4.1). In the case of TLS,
specific software behaviors that induce them, including at least 5.23% of hosts use manufacturer default keys that
a boot-time entropy hole in the Linux random number were never changed by the owner, and another 0.34%
generator. Finally, we suggest defenses and draw lessons appear to have generated the same keys as one or more
for developers, users, and the security community. other hosts due to malfunctioning random number gener-
ators. Only a handful of the vulnerable TLS certificates
are signed by browser-trusted certificate authorities.
1 Introduction and Roadmap Even more alarmingly, we are able to compute the
private keys for 64,000 (0.50%) of the TLS hosts and
Randomness is essential for modern cryptography, where
108,000 (1.06%) of the SSH hosts from our scan data
security often depends on keys being chosen uniformly at
alone by exploiting known weaknesses of RSA and DSA
random. Researchers have long studied random number
when used with insufficient randomness. In the case of
generation, from both practical and theoretical perspec-
RSA, distinct moduli that share exactly one prime factor
tives (e.g., [8, 13, 15, 17, 21, 23]), and a handful of major
will result in public keys that appear distinct but whose
vulnerabilities (e.g., [5, 19]) have attracted considerable
private keys are efficiently computable by calculating
scrutiny to some of the most critical implementations.
the greatest common divisor (GCD). We implemented
Given the importance of this problem and the effort and
an algorithm that can compute the GCDs of all pairs of
attention spent improving the state of the art, one might
11 million distinct public RSA moduli in less than 2 hours
∗ The first two authors both made substantial contributions. (Section 3.3). Using the resulting factors, we are able to
obtain the private keys for 0.50% of TLS hosts and 0.03% It is natural to wonder whether these results should
of SSH hosts (Section 4.2). In the case of DSA, if a DSA call into question the security of every RSA or DSA key.
key is used to sign two different messages with the same Based on our analysis, the margin of safety is slimmer
ephemeral key, an attacker can efficiently compute the than we might like, but we have no reason to doubt the
signer’s long-term private key. We find that our SSH scan security of most keys generated interactively by users on
data contain numerous DSA signatures that used the same traditional PCs. While we took advantage of the details
ephemeral keys during signing, allowing us to compute of specific cryptographic algorithms in this paper, we con-
the private keys for 1.6% of SSH DSA hosts (Section 4.3). clude that the blame for these vulnerabilities lies chiefly
To understand why these problem are occurring, we with the implementations. Ultimately, the results of our
manually investigated hundreds of the vulnerable hosts, study should serve as a wake-up call that secure random
which were representative of the most commonly repeated number generation continues to be an unsolved problem
keys as well as each of the private keys we obtained in important areas of practice.
(Section 3.2). Nearly all served information identifying
them as headless or embedded systems, including routers, Online resources For an extended version of this paper,
server management cards, firewalls, and other network de- partial source code, and our online key-check service, visit
vices. Such devices typically generate keys automatically https://factorable.net.
on first boot, and may have limited entropy sources com-
pared to traditional PCs. Furthermore, when we examined
clusters of hosts that shared a key or factor, in nearly all
2 Background
cases these appeared to be linked by a manufacturer or
In this section, we review the RSA and DSA public-key
device model. These observations lead us to conclude
cryptosystems and discuss the known weaknesses of each
that the problems are caused by specific defective imple-
that we used to compromise private keys. We then discuss
mentations that generate keys without having collected
how an adversary might exploit compromised keys to
sufficient entropy. We identified vulnerable devices and
attack SSH and TLS in practice.
software from dozens of manufacturers, including some of
the largest names in the technology industry, and worked
to notify the responsible parties. 2.1 RSA review
In the final component of our study, we experimen- An RSA [35] public key consists of two integers: an ex-
tally explore the root causes of these vulnerabilities by ponent e and a modulus N. The modulus N is the product
investigating several of the most common open-source of two randomly chosen prime numbers p and q. The
software components from the population of vulnerable private key is the decryption exponent
devices (Section 5). Based on the devices we identified, it
is clear that no one implementation is solely responsible, d = e−1 mod (p − 1)(q − 1).
but we are able to reproduce the vulnerabilities in plau-
sible software configurations. Every software package Anyone who knows the factorization of N can efficiently
we examined relies on /dev/urandom to generate cryp- compute the private key for any public key (e, N) using
tographic keys; however, we find that Linux’s random the preceding equation. When p and q are unknown, the
number generator (RNG) can exhibit a boot-time entropy most efficient known method to calculate the private key
hole that causes urandom to produce deterministic output is to factor N into p and q and use the above equation to
under conditions likely to occur in headless and embed- calculate d [9].
ded devices. In experiments with OpenSSL and Dropbear
SSH, we show how repeated output from the system RNG Factorable RSA keys No one has been publicly
can lead not only to repeated long-term keys but also to known to factor a well-generated 1024-bit RSA mod-
factorable RSA keys and repeated DSA ephemeral keys ulus; the largest known factored modulus is 768 bits,
due to the behavior of application-specific entropy pools. which was announced in December 2009 after a multi-
Given the diversity of the devices and software im- year distributed-computing effort [28]. In contrast, the
plementations involved, mitigating these problems will greatest common divisor (GCD) of two 1024-bit integers
require action by many different parties. We draw lessons can be computed in microseconds. This asymmetry leads
and recommendations for developers of operating sys- to a well-known vulnerability: if an attacker can find two
tems, cryptographic libraries, and applications, and for de- distinct RSA moduli N1 and N2 that share a prime factor
vice manufacturers, certificate authorities, end users, and p but have different second prime factors q1 and q2 , then
the security and cryptography communities (Section 7). the attacker can easily factor both moduli by computing
We have also created an online key-check service to allow their GCD, p, and dividing to find q1 and q2 . The attacker
users to test whether their keys are vulnerable. can then compute both private keys as explained above.
2.2 DSA review SSH In SSH, host keys allow a server to authenticate
itself to a client by providing a signature during the pro-
A DSA [32] public key consists of three so-called do-
tocol handshake. There are two major versions of the
main parameters (two prime moduli p and q and a gener-
protocol. In SSH-1 [38], the client encrypts session key
ator g of the subgroup of order q mod p) and an integer
material using the server’s public key. SSH-2 [39] uses a
y = gx mod p, where x is the private key. The domain
Diffie-Hellman key exchange to establish a session key.
parameters may be shared among multiple public keys
The user manually verifies the host key fingerprint the
without compromising security. A DSA signature con-
first time she connects to an SSH server. Most clients then
sists of a pair of integers (r, s): r = gk mod p mod q and
store the key locally in a known_hosts file and automati-
s = (k−1 (H(m) + xr)) mod q, where k is a randomly cho-
cally trust it for all subsequent connections.
sen ephemeral private key and H(m) is the hash of the
As in TLS, a passive eavesdropper with a server’s pri-
message.
vate key can decrypt an entire SSH-1 session. However,
Low-entropy DSA signatures DSA is known to fail because SSH-2 uses Diffie-Hellman, it is vulnerable only
catastrophically if the ephemeral key k used in the signing to an active man-in-the-middle attack. In the SSH user au-
operation is generated with insufficient entropy [4]. (El- thentication protocol, the user-supplied password is sent
liptic curve DSA (ECDSA) is similarly vulnerable. [11]) in plaintext over the encrypted channel. An attacker who
If k is known for a signature (r, s), then the private key knows a server’s private key can use the above attacks
x can be computed from the signature and public key as to learn a user’s password and escalate an attack to the
follows: system.
x = r−1 (ks − H(m)) mod q.
If a DSA private key is used to sign two different messages 3 Methodology
with the same k, then an attacker can efficiently compute
the value k from the public key and signatures and use In this section, we explain how we performed our Internet-
the above equation to compute the private key x [29]. If wide survey of public keys, how we attributed vulnerable
two messages m1 and m2 were signed using the same keys to devices, and how we efficiently factored poorly
ephemeral key k to obtain signatures (r1 , s1 ) and (r2 , s2 ), generated RSA keys.
then this will be immediately clear as r1 and r2 will be
equal. The ephemeral key k can be computed as: 3.1 Internet-wide scanning
k = (H(m1 ) − H(m2 ))(s1 − s2 )−1 mod q. We performed our data collection in three phases: dis-
covering IP addresses accepting connections on TCP
2.3 Attack scenarios port 443 (HTTPS) or 22 (SSH); performing a TLS or
SSH handshake and storing the presented certificate chain
The weak key vulnerabilities we describe in this paper can or host key; and parsing the collected certificates and
be exploited to compromise two of the most important host keys into a relational database. Table 1 summarizes
cryptographic transport protocols used on the Internet, the results.
TLS and SSH, both of which commonly use RSA or DSA
to authenticate servers to clients. Host discovery In the first phase, we scanned the
public IPv4 address space to find hosts with port 443
TLS In TLS [16], the server sends its public key in a or 22 open. We used the Nmap 5 network exploration
TLS certificate during the protocol handshake. The key tool [33]. We executed our first host discovery scan be-
is used either to provide a signature on the handshake ginning on October 6, 2011 from 25 Amazon EC2 Micro
(when Diffie-Hellman key exchange is negotiated) or to instances spread across five EC2 regions (Virginia, Cali-
encrypt session key material chosen by the client (when fornia, Japan, Singapore, and Ireland). The scan ran at an
RSA-encrypted key exchange is negotiated). average of 40,566 IPs/second and finished in 25 hours.
If the key exchange is RSA encrypted, a passive eaves-
dropper with the server’s private key can decrypt the mes- Certificate and host-key retrieval For TLS, we imple-
sage containing the session key material and use it to mented a certificate fetcher in Python using the Twisted
decrypt the entire session. If the session key is negoti- event-driven network framework. We fetched TLS cer-
ated using Diffie-Hellman key exchange, then a passive tificates using an EC2 Large instance with five processes
attacker will be unable to compromise the session key each maintaining 800 concurrent connections. We started
from just a connection transcript. However, in both cases, fetching certificates on October 11, 2011.
an active attacker who can intercept and modify traffic To efficiently collect SSH host keys, we implemented
between the client and server can man-in-the-middle the a simple SSH client in C, which is able to process up-
connection in order to decrypt or modify the traffic. wards of 1200 hosts/second by concurrently performing
 SSL Observatory Our TLS scan Our SSH scans
(12/2010) (10/2011) (2-4/2012)
Hosts with open port 443 or 22 ≈16,200,000 28,923,800 23,237,081
Completed protocol handshakes 7,704,837 12,828,613 10,216,363
Distinct RSA public keys 3,933,366 5,656,519 3,821,639
Distinct DSA public keys 1,906 6,241 2,789,662
Distinct TLS certificates 4,021,766 5,847,957 —
Trusted by major browsers 1,455,391 1,956,267 —

Table 1: Internet-wide scan results — We exhaustively scanned the public IPv4 address space for TLS and SSH
servers listening on ports 443 and 22, respectively. Our results constitute the largest such network survey reported to
date. For comparison, we also show statistics for the EFF SSL Observatory’s most recent public dataset [18].

protocol handshakes using libevent. Initially, we ran the Identifying SSH devices was more problematic, as SSH
fetcher from an EC2 Large instance in a run that started keys do not include descriptive fields and the server iden-
on February 12, 2012. This run targeted only RSA-based tification string used in the protocol often indicated only
host keys. In two later runs, we targeted DSA-based host a common build of a popular SSH server. We were able
keys, and rescanned those hosts that had offered DSA to classify many of the vulnerable SSH hosts using a
keys in the first SSH scan. For these, we also stored the combination of TCP/IP fingerprinting and examination of
authentication signature provided by the server; we varied information served over HTTP and HTTPS.
the client string to ensure that each signature would be The device names and manufacturers that we report
distinct. The first DSA run started on March 26, 2012 here have been identified with moderate or high confi-
from a host at UCSD. The second run, from a host at the dence given the available information. However, because
University of Michigan, started on April 1, 2012; it took we do not have physical access to the hosts, we cannot
3 hours to complete. state with certainty that all our identifications are correct.
TLS certificate processing For TLS, we performed a
third processing stage in which we parsed the previously 3.3 Efficiently computing all-pairs GCDs
fetched certificate chains and generated a database from We now describe how we efficiently computed the pair-
the X.509 fields. We implemented a certificate parser in wise GCD of all distinct RSA moduli in our multimillion-
Python and C primarily based on the M2Crypto SWIG key dataset. This allowed us to calculate RSA private
interface to the OpenSSL library. keys for 66,540 vulnerable hosts that shared one of their
RSA prime factors with another host in our survey.
3.2 Identifying vulnerable device models The fastest known factoring method for general integers
We attempted to determine what hardware and software is the number field sieve, which has heuristic complex-
1/3 2/3
generated or served the weak keys we identified using ity O(2n (log n) ) for n-bit numbers [30]. In contrast
manual detective work. The most straightforward method to factoring, the greatest common divisor (GCD) of two
was based on TLS certificate information—predominately integers can be computed very efficiently using Euclid’s
the X.509 subject and issuer fields. In many cases, the algorithm. Using fast integer arithmetic, the complexity
certificate identified a specific manufacturer or device of GCD can be improved to O(n(lg n)2 lg lg n) [7]. Com-
model. Other certificates contained less information; we puting the GCD of two 1024-bit RSA moduli using the
attempted to identify these devices through Nmap host GMP library [20] takes approximately 15 µs on a current
detection or by inspecting the public contents of HTTPS mid-range computer.
sites or other IP services hosted on the IP addresses. The naïve way to compute the GCDs of every pair of
When we could identify a pattern in vulnerable TLS integers in a large set would be to apply a GCD algorithm
certificates that appeared to belong to a device model or to each pair individually. There are 6 × 1013 distinct
product line, we constructed regular expressions to find pairs of RSA moduli in our data; at 15 µs per pair, this
other similar devices in our scan results. Under the theory calculation would take 30 years. We can do much better
that the keys were vulnerable because of a problem with by using a more efficient algorithm.
the design of the devices (where they were most likely To accomplish this, we implemented a quasilinear-time
generated), this allows us to estimate the total population algorithm for factoring a collection of integers into co-
of devices that might be potentially vulnerable, beyond primes, based on Bernstein [6]. The relevant steps, illus-
those serving immediately compromised keys. trated in Figure 1, are as follows:
 N1 N2 N3 N4 4 Vulnerabilities

product We analyzed the data from our TLS and SSH scans and
× ×
tree identified several patterns of vulnerability that would have
been difficult to detect without a macroscopic view of
N1 N2 N3 N4 the Internet. This section discusses the details of these
problems, as summarized in Table 2.
mod N12 N22 mod N32 N42 remainder
tree 4.1 Repeated keys

mod N12 mod N22 mod N32 mod N42 We found that 7,770,232 of the TLS hosts (61%) and
6,642,222 of the SSH hosts (65%) served the same key
as another host in our scans. To understand why, we
/N1 /N2 /N3 /N4 clustered certificates and host keys that shared the same
public key and manually inspected representatives of the
gcd( · , N1 ) gcd( · , N2 )gcd( · , N3 ) gcd( · , N4 )
largest clusters. In all but a few cases, the TLS certificate
subjects, SSH version strings, or WHOIS information
Figure 1: Computing all-pairs GCDs efficiently — We
were identical within a cluster, or pointed to a single
computed the GCD of every pair of RSA moduli in our
manufacturer or organization. This sometimes suggested
dataset using an algorithm due to Bernstein [6].
an explanation for the shared keys.
Not all of the repeated keys were due to vulnerabili-
Algorithm 1 Quasilinear GCD finding ties. For instance, many of the most commonly repeated
keys appeared in shared hosting situations. Six of the ten
Input: N1 , . . . , Nm RSA moduli most common DSA host keys and three of the ten most
1: Compute P = ∏ Ni using a product tree. common RSA host keys were served by large hosting
2: Compute zi = (P mod Ni2 ) for all i providers (see Figure 2). Another frequent reason for
using a remainder tree. repeated keys was distinct TLS certificates all belonging
Output: gcd(Ni , zi /Ni ) for all i. to the same organization. For example, TLS hosts at
google.com, appspot.com, and doubleclick.net all served
A product tree computes the product of m numbers by distinct certificates with the same public key. We excluded
constructing a binary tree of products. A remainder tree these cases and attributed remaining clusters of shared
computes the remainder of an integer modulo many inte- keys to several classes of problems.
gers by successively computing remainders for each node
in their product tree. For further discussion, see [7]. Default keys A common reason for hosts to share
The final output of the algorithm is the GCD of each the same key that we do consider a vulnerability is
modulus with the product of all the other moduli. We
are interested in the moduli for which this GCD is not 1.
However, if a modulus shares both of its prime factors
with two other distinct moduli, then the GCD will be Devices
Number of repeats

the modulus itself rather than one of its prime factors. 105 Hosting providers
This occurred in a handful of instances in our dataset; we Unknown/other
factored these moduli using the naïve quadratic algorithm
for pairwise GCDs.
We implemented the algorithm in C using the GMP
104
library for the arithmetic operations and ran it on the
11,170,883 distinct RSA moduli from our TLS and SSH
datasets and the EFF SSL Observatory [18] dataset.
The entire computation finished in 5.5 hours using a 50 most repeated RSA SSH keys
single core on a machine with a 3.30 GHz Intel Core i5
processor and 32 GB of RAM. The remainder tree took Figure 2: Commonly repeated SSH keys — We investi-
approximately ten times as long to process as the product gated the 50 most repeated SSH host keys for both RSA
tree. Parallelized across sixteen cores on an EC2 Cluster and DSA. Nearly all of the repeats appeared to be due
Compute Eight Extra Large Instance with 60.5 GB of either to hosting providers using a single key on many IP
RAM and using EBS-backed storage for scratch data, the addresses or to devices that used a default key or gener-
same computation took 1.3 hours at a cost of about $5. ated keys using insufficient entropy. Note log scale.
 Our TLS Scan Our SSH Scans
Number of live hosts 12,828,613 (100.00%) 10,216,363 (100.00%)
. . . using repeated keys 7,770,232 (60.50%) 6,642,222 (65.00%)
. . . using vulnerable repeated keys 714,243 (5.57%) 981,166 (9.60%)
. . . using default certificates or default keys 670,391 (5.23%)
. . . using low-entropy repeated keys 43,852 (0.34%)
. . . using RSA keys we could factor 64,081 (0.50%) 2,459 (0.03%)
. . . using DSA keys we could compromise 105,728 (1.03%)
. . . using Debian weak keys 4,147 (0.03%) 53,141 (0.52%)
. . . using 512-bit RSA keys 123,038 (0.96%) 8,459 (0.08%)
. . . identified as a vulnerable device model 985,031 (7.68%) 1,070,522 (10.48%)
. . . model using low-entropy repeated keys 314,640 (2.45%)

Table 2: Summary of vulnerabilities — We analyzed our TLS and SSH scan results to measure the population of
hosts exhibiting several entropy-related vulnerabilities. These include use of repeated keys, use of RSA keys that were
factorable due to repeated primes, and use of DSA keys that were compromised by repeated signature randomness.
Under the theory that vulnerable repeated keys were generated by embedded or headless devices with defective designs,
we also report the number of hosts that we identified as these device models. Many of these hosts may be at risk even
though we did not specifically observe repeats of their keys.

manufacturer-default keys. These are preconfigured in distribution suggests that the key generation process may
the firmware of many devices, such that every device of be using insufficient entropy, with distinct keys due to
a given model shares the same key pair unless the user relatively rare events. For TLS, our investigations began
changes it. The private keys to these devices may be with the keys that occurred in at least 100 distinct self-
accessible through reverse engineering, and published signed certificates. For SSH, we started from the 50 most
databases of default keys such as littleblackbox [24] con- commonly repeated keys for each of RSA (appearing on
tain private keys for thousands of firmware releases. more than 8000 hosts) and DSA (more than 4000 hosts).
At least 670,391 (5.23%) of the TLS hosts appeared With this process, we identified 43,852 TLS hosts
to serve manufacturer-default certificates or keys. We (0.34%) that served repeated keys due apparently to low
classified a certificate as a manufacturer default if nearly entropy during key generation. 27,545 certificates (98%)
all the devices of a given model used identical certificates, containing these repeated keys were self-signed; all 577
or if the certificate was labeled as a default certificate. CA-signed certificates identified Iomega StorCenter net-
The most common default certificate that we could work storage devices. For most SSH hosts we were unable
ascribe to a particular device belonged to a model of to distinguish between default keys and keys repeated
consumer router. Our scan uncovered 90,779 instances due to entropy problems, but 981,166 of the SSH hosts
of this device model sharing a single certificate. We also (9.60%) served keys repeated for one of these reasons.
found a variety of enterprise products serving default keys, We used the techniques described in Section 3.2 to iden-
including server management devices, network storage tify apparently vulnerable devices from 27 manufacturers.
devices, routers, remote access devices, and VoIP devices. These include enterprise-grade routers from Cisco and
For most of the repeated SSH keys, the lack of uniquely Juniper; server management cards from Dell, Hewlett-
identifying host information prevents us from distinguish- Packard, and IBM; virtual-private-network (VPN) de-
ing default keys from keys generated with insufficient vices; building security systems; network attached storage
entropy, so we address these together in the next section. devices; and several kinds of consumer routers and VoIP
products.
Repeated keys due to low entropy Another common Duplicated keys are a red flag that calls the security
reason that hosts share the same key appears to be entropy of the device’s key generation process into question, and
problems during key generation. In these instances, when all keys generated with the same model device should be
we investigated a key cluster, we would typically see considered suspect. For 14 of the TLS devices generating
thousands of hosts across many address ranges, and, when repeated keys, we were able to infer a fingerprint for the
we checked the keys corresponding to other instances of device model and estimate the total population of the de-
the same model of device, we would see a long-tailed vice in our scan. The prevalence of duplicated keys varied
distribution in their frequencies. Intuitively, this type of greatly for different device models, from as low as 0.2%
 103
Modulus frequency

Modulus frequency
100

102

50
101

100 0
(a) Primes generated by Juniper SSG 20 firewall (b) Primes generated by IBM Remote Supervisor Adapter

Figure 3: Visualizing RSA common factors — Different implementations displayed different patterns of vulnerable
keys. These plots depict the distribution of vulnerable keys divisible by common factors generated by two different
device models. Each column represents a collection of RSA moduli divisible by a single prime factor p. The color
and internal rectangles show, for each p, the frequencies of each distinct prime factor q. The Juniper device (left; note
log-log scale) follows a long-tailed distribution that is typical of many of the devices we identified. In contrast, the IBM
remote access device (right) was unique among those we observed in that it generates RSA moduli roughly uniformly
distributed among nine distinct prime factors.

in the case of one router to 98% for one thin client. The a browser trusted authority and both have expired. Some
total population of these identified, potentially vulnerable devices generated factorable keys both for TLS and SSH,
TLS devices was 314,640 hosts, which represents 2.45% and a handful of devices shared common factors across
of the TLS hosts in our scan. SSH and TLS keys.
In the above analyses, we excluded repeated keys that We classified these factorable keys in a similar manner
were due to the infamous Debian weak-key vulnerabil- to the repeated keys. We found that, in all but a small
ity [5, 37], which we report separately in Table 2. number of cases, the TLS certificates and SSH host keys
divisible by a common factor all belonged to a particular
4.2 Factorable RSA keys manufacturer, which we were able to identify in most
cases using the techniques described in Section 3.2.
A second way that entropy problems might manifest them- We identified devices from 41 manufacturers in this
selves during key generation is if an RSA modulus shares way, which constituted 99% of the hosts that generated
one of its prime factors p or q with another key. As ex- RSA keys we could factor. The devices range from 100%
plained in Section 2.1, finding such a pair immediately (576 of 576 devices) vulnerable to 0.01% vulnerable
allows an adversary to efficiently factor both moduli and (2 out of 10,932). As with repeated keys, we would
obtain their private keys. In order to find such keys, we not expect to see well-generated cofactorable keys; any
computed the GCD of all pairs of distinct RSA moduli by device model observed generating factorable keys should
applying the algorithm described in Section 3.3. be treated as potentially vulnerable.
The 11,170,883 distinct RSA moduli yielded 2,314 The majority of the devices serving factorable keys
distinct prime divisors, which divided 16,717 distinct were Juniper firewalls. We identified 46,993 of these
public keys. This allowed us to obtain private keys for devices in our dataset, and we factored the keys for 12,688
23,576 (0.40%) of the TLS certificates in our scan data, (27%). Of these keys, 7,510 (59%) share a single common
which were served on 64,081 (0.50%) of the TLS hosts, divisor. The distribution of common factors among its
and 1,013 (0.02%) of the RSA SSH host keys, which were moduli is shown in Figure 3a.
served on 2,459 (0.027%) of the RSA SSH hosts. The most remarkable devices were IBM Remote Server
The vast majority of the vulnerable keys appeared to be Administration cards and BladeCenter devices, which
system-generated certificates and SSH host keys used by displayed a distribution of factors unlike any of the other
routers, firewalls, remote administration cards, and other vulnerable devices we found. There were only 9 distinct
types of headless or embedded network devices. Only prime factors that had been used to generate the keys for
two of the factorable TLS certificates had been signed by 576 devices. Each device’s key was the product of two
 104 ture collisions appeared to be from ADTran Total Access
Keys compromised by business-grade phone/network routers and revealed pri-
repeated signature randomness vate keys for 62,807 (73%) out of 86,301 such hosts. Sev-
Frequency

eral vulnerable device models, including the IBM RSA II

102 remote administration cards and Juniper NetScreen, also
generated factorable RSA keys.
While we collected multiple signatures from some SSH
hosts, 3,917 (89.7%) out of 4,365 of the collisions were
100 from different hosts that had generated the same long-
100 101 102 103 term key and also used the same ephemeral key during
Private key index the key exchange protocol. This problem compounds the
danger of the repeated key vulnerability: a single signa-
Figure 4: Vulnerable DSA keys for one SSH device — ture collision between any pair of hosts sharing the same
We identified 18,684 SSH DSA keys that appeared to key at any point during runtime reveals the private key for
have been generated by Gigaset DSL routers, of which every host using that key. In our dataset we observed tens
16,575 were repeated at least once. Shown in red in this of thousands of hosts using the same public key. While a
log-log plot are 12,378 keys further compromised due to single host may never repeat an ephemeral key, two hosts
repeated DSA signature values. sharing a private key due to poor entropy can put each
others’ keys at risk.
We note that any estimation of vulnerability based on
different primes from this list. The 36 possible moduli our data is an extreme lower bound, as we gathered at
that could be generated with this process were roughly most two signatures from each host in our scans. It is
uniformly distributed, as shown in Figure 3b. In addition, likely that many more private keys would be revealed if
this was the only device we observed to generate RSA we collected additional signatures.
moduli where both prime factors were shared with other
keys.
5 Experimental Investigation
4.3 DSA signature weaknesses
Based on the results the previous section, we conjectured
The third class of entropy-related vulnerability that we that the problems we observed were an implementational
searched for was repeated ephemeral keys in DSA signa- phenomenon. To more deeply understand the causes, we
tures. As explained in Section 2.2, if a DSA key is used augmented our data analysis with experimental investiga-
to sign two different messages using the same ephemeral tion of specific implementations. While there are many
key, then the long-term private key is immediately com- independently vulnerable implementations, we chose to
putable from the public key and the signatures. The pres- examine three open-source cryptographic software com-
ence of this vulnerability indicates entropy problems at ponents that appeared frequently in the vulnerable popu-
later phases of operation, after initial key generation. We lations.
searched for signatures from identical keys containing re-
peated r values. Then we used the method in Section 2.2 5.1 Weak entropy and the Linux RNG
to compute the corresponding private keys.
Our combined SSH DSA scans collected 9,114,925 We conjectured that the cause for many of the entropy
signatures (in most cases, two from each SSH host serving problems we observed began with insufficient random-
a DSA-based key) of which 4,365 (0.05%) contained the ness provided by the operating system. This led us to take
same r value as at least one other signature. 4,094 of an in-depth look at the Linux random number generator
these signatures (94%) used the same r value and the (RNG). We note that not every vulnerable key was gen-
same public key. This allowed us to compute the 281 erated on Linux; we also observed vulnerable keys on
distinct private keys used to generate these signatures. FreeBSD and Windows systems, and similar vulnerabil-
These compromised keys were served by 105,728 (1.6%) ities to those we describe here have been reported with
of the SSH DSA hosts in our combined scans. BSD’s arc4random [36].
We clustered the vulnerable signatures by r values The Linux RNG maintains three entropy pools, each
and manufacturer. 2,026 (46%) of the colliding r val- with an associated counter that estimates how much
ues appeared to have been generated by Gigaset SX762 fresh entropy it has available. Fresh entropy from un-
consumer-grade DSL routers and revealed private keys predictable kernel sources is periodically mixed into the
for 17,349 (66%) of the 26,374 hosts we identified as Input pool. When processes read from /dev/random or
this device model (see Figure 4). Another 934 signa- /dev/urandom, the kernel extracts the requested amount
 SSH urandom read(32)

250 25,000

Bytes read from nonblocking pool

200 20,000
Input pool entropy (bits)

150 15,000

100 Input pool entropy estimate 10,000

Input threshold to update entropy pool
50 Bytes read from nonblocking pool 5,000
SSH process seeds from /dev/urandom

0 0
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70
Time since boot (s)

Figure 5: Linux urandom boot-time entropy hole — We instrumented an Ubuntu Server 10.04 system to record its
estimate of the entropy contained in the Input entropy pool during a typical boot. Linux does not mix Input pool
entropy into the Nonblocking pool that supplies /dev/urandom until the Input pool exceeds a threshold of 192 bits
(blue horizontal line), which occurs here at 66 seconds post-boot. For comparison, we show the cumulative number
of bytes generated from the Nonblocking entropy pool; the vertical red line marks the time when OpenSSH seeds its
internal PRNG by reading from urandom, well before this facility is ready for secure use.

of entropy from the Input pool and mixes it into the Block- Experiment To test whether Linux’s /dev/urandom
ing or Nonblocking pool, respectively, and then extracts can produce repeatable output in conditions resembling
bytes from the respective pool to return. If the input pool the initial boot of a headless or embedded networked de-
does not contain enough entropy to satisfy the request, vice, we modified the 2.6.35 kernel to add instrumentation
the read from the Blocking pool blocks; the Nonblocking to the RNG and disable certain entropy sources to simu-
pool read is satisfied immediately. late a cold boot on a low-end machine without a working
clock.
Entropy sources We experimented with the Linux We experimented with this kernel on a Dell Optiplex
2.6.35 kernel to exhaustively determine the sources of 980 system using a fresh installation of Ubuntu server
entropy used by the RNG. To do this, we traced through 10.04.4. The machine was configured with a Core i7 CPU,
the kernel source code and systematically disabled en- 4 GB RAM, a 32 GB SSD, and a USB keyboard. It was
tropy sources until the RNG output was repeatable. All of attached to a university office LAN and obtained an IP ad-
the entropy sources we found are greatly weakened under dress using DHCP. With this configuration, we performed
certain operating conditions. 1,000 unattended boots. Each time, we read 32 bytes
The explicit entropy sources we observed are the unini- from urandom at the point in the initialization process
tialized contents of the pool buffers when the kernel starts, where the SSH server would normally start. Under these
the startup clock time in nanosecond resolution, input conditions, we found that the output of /dev/urandom
event and disk access timings, and entropy saved across was entirely predictable and repeatable.
boots to a local file. Surprisingly, modern Linux systems The kernel maintains a reserve threshold for the Input
no longer collect entropy from IRQ timings. pool, and no data is copied into the Nonblocking pool un-
The final and most interesting entropy source was one til the Input pool has been credited with at least that much
that we have not seen documented elsewhere. The devel- entropy (192 bits, for our kernel). Figure 5 shows the
opers chose not to put a lock around the mixing procedure cumulative amount of entropy credited to the Input pool
when entropy is extracted from the pool, and, as a re- during a typical bootup from our tests. (Note that none
sult, if two threads extract entropy concurrently, the pool of the entropy sources we disabled would have resulted
contents may change anywhere in the middle of the hash in more entropy being credited to the pool.) The credited
computation, resulting in the introduction of significant entropy does not cross this reserve threshold until more
(but uncredited) entropy to the pool. than a minute after boot, well after the SSH server and
The removal of IRQs as an entropy source has likely other startup processes have launched. Although Ubuntu
exacerbated RNG problems in headless and embedded tries to restore entropy saved during the last shutdown,
devices, which often lack human input devices, disks, and this happens slightly after the point when sshd first reads
multiple cores. If they do, the only source of entropy—if from urandom. With no entropic inputs, urandom pro-
there are any at all—may be the time of boot. duces a deterministic output stream.
 Fraction of keys generated that we could factor
32 0.6
Time dilation factor (slower →)

24
0.4

16

0.2
8

0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Starting clock time t0 (seconds)
clock tick
Figure 6: OpenSSL generating factorable keys — We hypothesized that OpenSSL can generate factorable keys under
low-entropy conditions due to slight asynchronicity between the key generation process and the real-time clock, we
generated 14 million RSA keys using controlled entropy sources for a range of starting clock times. Each square in the
plot indicates the fraction of 100 generated keys that could we could factor. In many cases (white), keys are repeated
but never share primes. After a sudden phase change, factorable keys occur during a range leading up to the second
boundary, and that range increases as we simulate machines with slower execution speeds.

Boot-time entropy hole The entropy sources we dis- 5.2 Factorable RSA keys and OpenSSL
abled would likely be missing in some headless and em-
One interesting question raised by our vulnerability re-
bedded systems, particularly on first boot. This means that
sults is why factorable RSA keys occur at all. A naïve
there is a window of vulnerability—a boot-time entropy
implementation of RSA key generation would simply
hole—during which Linux’s urandom may be entirely
seed a PRNG from the operating system’s entropy pool
predictable, at least for single-core systems. If processes
and then use it to generate p and q. In this approach, we
generate long-term cryptographic keys or maintain their
would expect to see duplicate keys if the OS provided
own entropy pools seeded only with entropy gathered
the same seed, but factorable keys would be extremely
during this window, those keys are likely to be vulnerable.
unlikely. What we see instead is that some devices seem
The risk is particularly high for unattended systems that
prone to generating keys with common factors. Another
ship with preconfigured operating systems and generate
curious feature is that although some of the most common
SSH or TLS keys the first time the respective daemons
prime factors divided hundreds of different moduli, in
start during the initial boot.
nearly all of these cases the second prime factor did not
On stock Ubuntu systems, these risks are somewhat
divide any other keys.
mitigated: TLS keys must be generated manually, and
One explanation for this pattern is that implementa-
OpenSSH host keys are generated during package installa-
tions updated their entropy pools in the middle of key
tion, which is likely to be late in the install process, giving
generation. In this case, the entropy pool states might
the system time to collect sufficient entropy. However, on
be identical as distinct key generation processes generate
the Fedora, Red Hat Enterprise Linux (RHEL), and Cen-
the first prime p and diverge while generating the second
tOS Linux distributions, OpenSSH is installed by default,
prime q. In order to explore this theory, we studied the
and host keys are generated on first boot. We experi-
source code of OpenSSL [14], one of the most widely
mented further with RHEL 5 and 6 to determine whether
used open-source cryptographic libraries. OpenSSL is not
host keys on these systems might be compromised, and
the only software library responsible for the problems we
observed that sufficient entropy had been collected at the
observed, but we chose to examine it because the source
time of key generation by a slim margin. We believe
code is freely available and because of its popularity.
that most server systems running these distributions are
safe, particularly since they likely have multiple cores OpenSSL RSA key generation OpenSSL’s built-in
and gather additional entropy from physical concurrency. RSA key generator relies on an internal entropy pool main-
However, it is possible that other distributions and cus- tained by OpenSSL. The entropy pool is seeded on first
tomized installations do not collect sufficient entropy on use with (on Linux) 32 bytes read from /dev/urandom,
startup and generate weak keys on first boot. the process ID, user ID, and the current time in seconds.
OpenSSL provides a function named bnrand() to gen- 5.3 DSA signature weaknesses and Dropbear
erate cryptographically-sized integers from the entropy
pool, which, on each call, mixes into the entropy pool the The DSA signature vulnerabilities we observed indicate
current time in seconds, the process ID, and the possibly that entropy problems impact not only key generation but
uninitialized contents of a destination buffer. also the continued runtime behavior of server software
during normal usage. This is somewhat surprising, since
The RSA key generation algorithm generates the
we might expect the operating system to collect suffi-
primes p and q using a randomized algorithm. During this
cient entropy eventually, even in embedded devices. We
process, OpenSSL extracts entropy from the entropy pool
investigated Dropbear, a popular light-weight SSH imple-
dozens to hundreds of times. Since we observed many
mentation. It maintains its own entropy pools seeded from
keys with one prime factor in common, we can conjecture
the operating system at launch, on Linux with 32 bytes
that multiple systems are starting with urandom and the
read from urandom. This suggests a possible explanation
time in the same state and that the entropy pool states
for the observed problems: the operating system had not
diverge due to the addition of time during intermediate
collected enough entropy when the SSH server started,
steps of the key generation process.
and, from then on, even though the system entropy pool
We hypothesized that this process is hypersensitive to may have had further entropy, the running SSH daemon
small variations in where the boundary between seconds did not.
falls. Slight variations in execution speed might cause the
To better understand why these programs produce vul-
wall clock tick to fall between different calls to bnrand(),
nerable DSA signatures, we examined the source code
resulting in different execution paths. This can result in
for the current version of Dropbear, 0.55. The ephemeral
several different behaviors, with three simple cases:
key is generated as output from an internal entropy pool.
If the second never changes while Whenever Dropbear extracts data from its entropy pool, it
computing p and q, every execu- p q increments a static counter and hashes the result into the
tion will generate identical keys. t t+1 pool state. No additional randomness is added until the
counter (a 32-bit integer) overflows. This implies that, if
If the clock ticks while generating two Dropbear servers are initially seeded with the same
p, both p and q diverge, yielding p q value from urandom, they will provide identical signature
distinct keys with no shared factors. t t+1 randomness as long as their counters remain synchronized
and do not overflow.
If instead the clock advances to the next second during the (We note that Dropbear contains a routine to generate k
generation of the second prime q, then two executions will in a manner dependent on the message to be signed, which
generate identical primes p but can would ensure that distinct messages are always signed
generate distinct primes q based on p q
with distinct k values and protect against the vulnerability
exactly when the second changes. t t+1
that we explore here. However, that code is disabled by
default.)
Experiment To test our hypothesis, we modified We looked for evidence of synchronized sequences
OpenSSL 1.0.0g to control all the entropy inputs used of ephemeral keys in the wild by making further SSH
during key generation, generated a large number of RSA requests to a handful of the Dropbear hosts from our
keys, and determined how many were identical or fac- scan. We chose two hosts with the SSH version string
torable. To simulate the effects of slower clock speeds, dropbear-0.39 that had used identical DSA public keys
we dilated the clock time returned by time() and re- and r values and found that the signatures followed an
peated the experiment using dilation multipliers of 1–32. identical sequence of r values. We could advance the
In all, we generated 14 million keys. We checked for sequence of one host by making several SSH requests,
common factors within each batch of 100 keys. then cause the other host to catch up by making the same
The results we obtained, illustrated in Figure 6, are number of requests. When probed again an hour later,
consistent with our hypothesis. No factorable keys are both hosts remained in sync. This suggests that the Drop-
generated for low starting offsets, as both p and q are bear code is causing vulnerabilities on real hosts in the
generated before the second changes. As the initial off- manner we predicted.
set increases, there is a rapid phase change to generat- Several other implementations, including hosts identify-
ing factorable keys, as generation of q values begins to ing OpenSSH and the Siemens Gigaset routers displayed
overlap the second boundary. Eventually, the fraction of similar behavior when rescanned. Because OpenSSL adds
factorable keys falls as the second boundary occurs dur- the current clock time to the entropy pool before extract-
ing the generation of more p values, resulting in distinct ing these random values, this suggests that some of these
moduli with no common factors. devices do not have a working clock at all.
6 Discussion As others have noted, Linux is very conservative at
crediting randomness added to the entropy pool [23],
6.1 RSA vs. DSA in the face of low entropy and random further insists on using freshly collected ran-
domness that has not already been mixed into the output
We believe that the DSA signature vulnerabilities pose
PRNG. The blocking behavior means that applications
more cause for concern than the RSA factorization vul-
that read from random can hang unpredictably, and, in
nerability. The RSA key factorization vulnerability that
a headless device without human input or disk entropy,
we investigated occurs only for certain patterns of key
there may never be enough input for a read to complete.
generation implementations in the presence of low en-
While blocking is intended to be an indicator that the sys-
tropy. In contrast, the DSA signature vulnerability can
tem is running low on entropy, random often blocks even
compromise any DSA private key—no matter how well
though the system has collected more than enough entropy
generated—if there is ever insufficient entropy at the time
to produce cryptographically strong PRNG output—in a
the key is used for signing. It is not necessary to search for
sense, random is often “crying wolf” when it blocks.
a collision, as we did; it suffices for an attacker to be able
Our experiments suggest that many of the vulnerabil-
to guess the ephemeral private key k. The most analogous
ities we observed may be due to the output of urandom
attacks against RSA of which we are aware show that
being used to seed entropy pools before any entropic
some types of padding schemes can allow an attacker to
inputs have been mixed in. Unfortunately, the existing in-
discover the encrypted plaintext or forge signatures [10].
terface to urandom gives the operating system no means
We are unaware of any attacks that use compromised RSA
of alerting applications to this dangerous condition. Our
signatures to recover the private key.
recommendation is that Linux should add a secure RNG
We note that our findings show a larger fraction of
that blocks until it has collected adequate seed entropy
SSH hosts are compromised by the DSA vulnerability
and thereafter behaves like urandom.
than by factorable RSA keys, even though our scanning
techniques have likely only revealed a small fraction of
the hosts prone to repeating DSA signature randomness. 6.3 Are we seeing only the tip of the iceberg?
In contrast, the factoring algorithm we used has found all
Nearly all of the vulnerable hosts that we were able to
of the repeated RSA primes in our sample of keys.
identify were headless or embedded devices. This raises
There are specific countermeasures that implementa-
the question of whether the problems we found appear
tions can use to protect against these attacks. If both
only in these types of devices, or if instead we are merely
prime factors of an RSA modulus are generated from a
seeing the tip of a much larger iceberg.
PRNG without adding additional randomness during key
Based on the experiments described in Section 5.1, we
generation, then low entropy would result in repeated but
conjecture that there may exist further classes of vulnera-
not factorable keys. These are more readily observable,
ble keys that were not visible to our methods, but could be
but may be trickier to exploit, because they do not imme-
compromised with targeted attacks. The first class is com-
diately reveal the private key to a remote attacker. To pre-
posed of embedded or headless devices with an accurate
vent DSA randomness collisions, the randomness for each
real-time clock. In these cases, keys generated during the
signature can be generated as a function of the message
boot-time entropy hole may appear distinct, but depend
and the pseudorandom input. (It is very important to use
only on a configuration-specific state and the boot time.
a cryptographically secure PRNG for this process [4].) Of
These keys would not appear vulnerable in our scanning,
course, the most important countermeasure is for imple-
but an attacker may be able to enumerate some or all of
mentations to use sufficient entropy during cryptographic
such a reduced key space for targeted implementations.
operations that require randomness, but defense-in-depth
remains the prudent course. A more speculative class of potential vulnerability con-
sists of traditional PC systems that automatically generate
cryptographic keys on first boot. We observed in Sec-
6.2 /dev/(u)random as a usability failure
tion 5.1 that an experimental machine running RHEL 5
The Linux documentation states that “[a]s a general rule, and 6 did collect sufficient entropy in time for SSH key
urandom should be used for everything except long-lived generation, but that the margin of safety was slim. It is
GPG/SSL/SSH keys” [1]. However, all the open-source conceivable that some lower-resource systems may be
implementations we examined used urandom to generate vulnerable.
keys by default. Based on a survey of developer mailing Finally, our study was only able to detect vulnerable
lists and forums, it appears that this choice is motivated by DSA ephemeral keys under specific circumstances where
two factors: random’s extremely conservative behavior a large number of systems shared the same long-term key
and the mistaken perception that urandom’s output is and were choosing ephemeral keys from the same small
secure enough. set. There may be a larger set of hosts using ephemeral
keys that do not repeat across different systems but are of true randomness and is continually seeded with fresh
nonetheless vulnerable to a targeted attack. entropy collected during operation.
We found no evidence suggesting that RSA keys from
Communicate entropy conditions to applications. The
standard implementations that were generated interac-
problem with /dev/urandom is that it can return data
tively or subsequent to initial boot are vulnerable.
even before it has been seeded with any entropy. The OS
should provide an interface to indicate how much entropy
6.4 Directions for future work
it has mixed into its PRNG, so that applications can gauge
In this work, we examined keys from two cryptographic whether the state is sufficiently secure for their needs.
algorithms on two protocols visible via Internet-wide
Test RNGs thoroughly on diverse platforms. Many of the
scans of two ports . A natural direction for future work
entropy sources that Linux supports are not available on
is to broaden the scope of all of these choices. Entropy
headless or embedded devices. These behaviors may not
problems can also affect the choice of Diffie-Hellman key
be apparent to OS developers unless they routinely test
parameters and keying material for symmetric ciphers. In
the internals of the entropy collection subsystem across
addition, there are many more subtle attacks against RSA,
the full spectrum on platforms the system supports.
DSA, and ECDSA that we did not search for. We focused
on keys, but one might also try to search for evidence of For library developers:
repeated randomness in initialization vectors in ciphertext
or salts in cryptographic hashes. Default to the most secure configuration. Both OpenSSL
We also focused solely on services visible to our scans and Dropbear default to using /dev/urandom instead
of the public Internet. Similar vulnerabilities might be of /dev/random, and Dropbear defaults to using a less
found by applying this methodology to keys or other cryp- secure DSA signature randomness technique even though
tographic data obtained from other resource-constrained a more secure technique is available as an option. In
devices that perform cryptographic operations, such as general, cryptographic libraries should default to using
smart cards or mobile phones. the most secure mechanisms available.
The observation that urandom can produce predictable Use RSA and DSA defensively. Crypto libraries can
output on some types of systems at boot may lead to at- take specific steps to prevent weak entropy from resulting
tacks on other services that automatically begin at boot in the immediate leak of private keys due to co-factorable
and depend on good randomness from the kernel. It war- RSA moduli and repeated DSA signature randomness
rants investigation to determine whether this behavior (see Section 6.1).
may undermine other security mechanisms such as ad-
dress space layout randomization or TCP initial sequence For application developers:
numbers. Generate keys on first use, not on install or first boot. If
keys must be generated automatically, it may be better to
7 Defenses and Lessons defer generation until the keys are needed.
Heed warnings from below. If the OS or cryptography
The vulnerabilities we have identified are a reminder that library being used raises a signal that insufficient entropy
secure random number generation continues to be a chal- is available (such as blocking), applications should de-
lenging problem. There is a tendency for developers at tect this signal and refuse to perform security-critical
each layer of the software stack to silently shift respon- operations until the system recovers from this potentially
sibility to other layers; a far better practice would be vulnerable state. Developers have been known to work
a defense-in-depth approach where developers at every around low-entropy states by ignoring or disabling such
layer apply careful security design and testing and make warnings, with extremely dangerous results [22].
assumptions clear. We suggest defensive strategies and
lessons for several important groups of stakeholders. For device manufacturers:
For OS developers: Avoid factory-default keys or certificates. While some
defense is better than nothing, default keys and certificates
Provide the RNG interface applications need. Typi-
provide only minimal protection.
cal security applications require a source of randomness
that is guaranteed to be of high quality and has pre- Seed entropy at the factory. Devices could be initialized
dictable performance; neither Linux’s /dev/random nor with truly random seeds at the factory. Sometimes it is al-
/dev/urandom strikes this balance. The operating sys- ready necessary to configure unique state on the assembly
tem should maintain a secure PRNG that refuses to return line (such as to set MAC addresses), and entropy could
data until it has been seeded with a minimum amount be added at the same time.
Ensure entropy sources are effective. Embedded or head- 8 Related Work
less devices may not have access to sources of randomness
assumed by the operating system, such as user-input de-
HTTPS surveys The HTTPS public-key infrastruc-
vices or disk timing. Device makers should ensure that
ture has been a focus of attention in recent years, and
effective entropy sources are present, and that these are
researchers have performed several large-scale scans to
being harvested in advance of cryptographic operations.
measure TLS usage and CA behavior. In contrast, our
Use hardware random number generators when possible. study addresses problems that are mostly separate from
Security-critical devices should use a hardware random the CA ecosystem.
number generator for cryptographic randomness when- In 2010, the Electronic Frontier Foundation (EFF) and
ever possible. iSEC Partners debuted the SSL Observatory project [18]
For certificate authorities: and released the largest public repository of TLS certifi-
cates. The authors used their data to analyze the CA
Check for repeated, weak, and factorable keys Certifi-
infrastructure and noted several vulnerabilities. We owe
cate authorities have a uniquely broad view of keys con-
the inspiration for our work to their fascinating dataset, in
tained in TLS certificates. We recommend that they repeat
which we first identified several of the entropy problems
our work against their certificate databases and take steps
we describe; however, we ultimately performed our own
to protect their customers by alerting them to potentially
scans to have more up-to-date and complete data.
weak keys.
In 2011, Holz et al. [26] scanned the Alexa top 1 mil-
For end users: lion domains and observed TLS sessions passing through
Regenerate default or automatically generated keys. the Munich Scientific Research Network (MWN). Their
Cryptographic keys and certificates that were shipped study recorded 960,000 certificates and was the largest
with the device or automatically generated at first boot academic study of TLS data at the time. They report many
should be manually regenerated. Ideally, certificates and statistics gathered from their survey, mainly focusing on
keys should be generated on another device (such as a the state of the CA infrastructure. We note that they ex-
desktop system) with access to adequate entropy. amined repeated keys and dismissed them as “curious,
but not very frequent.” Yilek et al. [37] performed daily
Check for known weak keys. We have created a key- scans of 50,000 TLS servers over several months to track
check service that individuals can use to check their TLS replacement time for certificates affected by the Debian
certificates and SSH host keys against our database of weak key bug. Our count of Debian certificates provides
keys we have identified as vulnerable. another data point on this subject.
For security and crypto researchers:
Problems with random number generation Several
Secure randomness remains unsolved in practice. The significant vulnerabilities relating to weak random num-
fact that all major operating systems now provide cryp- ber generation have been found in widely used software.
tographic RNGs might lead security experts to believe In 1996, the Netscape browser’s SSL implementation
that any entropy problems that still occur are the fault was found to use fewer than a million possible seeds for
of developers taking foolish shortcuts. Our findings sug- its PRNG [19]. In May 2008, Bello discovered that the
gest otherwise: entropy-related vulnerabilities can result version of OpenSSL included in the Debian Linux distri-
from complex interaction between hardware, operating bution contained a bug that caused keys to be generated
systems, applications, and cryptographic primitives. We with only 15 bits of entropy [5]. The problem caused only
have yet to develop the engineering practices and princi- 294,912 distinct keys to be generated per key size during
ples necessary to make predictably secure use of unpre- a two year period before the error was found [37].
dictable randomness across the diverse variety of systems Gutmann [22] draws lessons about secure software
where it is required. design from the example of developer responses to an
Primitives should fail gracefully under weak entropy. OpenSSL update intended to ensure that the entropy
Cryptographic primitives are usually designed to be se- pool was properly seeded before use. He observes that
cure under ideal conditions, but practice will subject them many developers responded by working around the safety
to conditions that are less than idea. We find that RSA checks in ways that supplied no randomness whatso-
and DSA, with surprising frequency, are used in practice ever. The root cause, according to Gutmann, was that
under weak entropy scenarios where, due to the design the OpenSSL design left the difficult job of supplying suf-
of these cryptosystems, the private keys are totally com- ficient entropy to library users. He concludes that PRNGs
promised. More attention is needed to ensure that future should handle entropy-gathering themselves.
primitives degrade gracefully under likely failure modes Gutterman, Pinkas, and Reinmann analyzed the Linux
such as this. random number generator in 2006 [23]. In contrast to
our analysis, which focuses on empirical measurement of Furthermore, the authors of the concurrent work state
an instrumented Linux kernel, theirs was based mainly that they “cannot explain the relative frequencies and
on a review of the LRNG design. They point out several appearance” of the weak keys they observed and report
weaknesses from a cryptographic perspective, some of no attempt to determine their source. In this work, we
which have since been remedied. In a brief experimental performed extensive investigation to trace the vulnerable
section, they observe that the only entropy source used by keys back to specific devices and software implementa-
the OpenWRT Linux distribution was network interrupts.. tions, and we have notified the responsible developers
Weak entropy and cryptography In 2004, Bauer and and manufacturers. We find that the weak keys can be ex-
Laurie [2] computed the pairwise GCDs of 18,000 RSA plained by specific design and implementation failures at
keys from the PGP web of trust and discovered a pair with various levels of the software stack, and we make detailed
a common factor of 9, demonstrating that the keys had recommendations to developers and users that we hope
been generated with broken (or omitted) primality testing. will lessen the occurrence of these problems in the future.
The DSA signature weakness we investigate is well
known and appears to be folklore. In 2010, the hacking 9 Conclusion
group fail0verflow computed the ECDSA private key used
for code signing on the Sony PS3 after observing that the In this work, we investigated the security of random num-
signatures used repeated ephemeral keys [12]. Several ber generation on a broad scale by performing and an-
more sophisticated attacks against DSA exist: Bellare, alyzing the most comprehensive Internet-wide scans of
Goldwasser, and Miccancio [4] show that the private key TLS certificates and SSH host keys to date. Using the
is revealed if the ephemeral key is generated using a lin- global view provided by our data, we discovered that inse-
ear congruential generator, and Howgrave-Graham and cure RNGs are in widespread use, leading to a significant
Smart [27] give a method to compute the private key from number of vulnerable RSA and DSA keys.
a fraction of the bits of the ephemeral key. Our experiences suggest that the type of scanning and
Ristenpart and Yilek [34] developed “virtual ma- analysis we performed can be a useful tool for finding sub-
chine reset” attacks in 2010 that induce repeated DSA tle flaws in cryptographic implementations, and we hope
ephemeral keys after a VM reset, and they implement it will be applied more broadly in future work. Previous
“hedged” cryptography to protect against this type of ran- examples of random number generation flaws were found
domness failure. Hedged public key encryption was intro- by painstakingly reverse engineering individual devices
duced by Bellare et al. in 2009 and is designed to fail as or implementations, or through luck when a collision was
gracefully as possible in the face of bad randomness [3]. observed by a single user. Our scan data allowed us to
As we were preparing this paper for submission, an in- essentially mine for vulnerabilities and detect problems
dependent group of researchers uploaded a preprint [31] in dozens of different devices and implementations in a
reporting that they had computed the pairwise GCD of single shot. Many of the collisions we found were too rare
RSA moduli from the EFF SSL Observatory dataset and to ever have been observed by a single user but quickly
a database of PGP keys. Their work is concurrent and in- became apparent with a near-global view of the universe
dependent to our own; we were unaware of these authors’ of public keys. The results are a reminder to all that
efforts before their work was made public. They declined vulnerabilities can sometimes be hiding in plain sight.
to report the GCD computation method they used. We
responded by publishing a blog post [25] describing our
GCD computation approach and summarizing some of Acknowledgments
the key findings we detail in this paper.
The authors of the concurrent work report similar re- The authors thank Dan Bernstein and Tanja Lange for dis-
sults to our own on the fraction of keys that were able to cussion of batch factorization and OpenSSL, and Hovav
be factored, and thus the two results provide validation for Shacham for advice on many aspects of this work. We
each other. In their paper, however, the authors draw very also thank Jake Appelbaum, Michael Bailey, Kevin Bor-
different conclusions than we do. They do not analyze the ders, Keith Brautigam, Ransom Briggs, Jesse Burns, Alek-
source of these entropy failures, and they conclude that sander Durumeric, Prabal Dutta, Peter Eckersley, Andy
RSA is “significantly riskier” than DSA. In contrast, we Isaacson, James Kasten, Ben Laurie, Stephen Schultze,
performed original scans that targeted SSH as well as TLS, Ron Rivest, and David Robinson.
and we looked for DSA repeated signature weaknesses as This material is based upon work supported by the
well as cofactorable RSA keys. We find that SSH DSA National Science Foundation under Award No. DMS-
private keys are compromised at a higher rate than RSA 1103803, the MURI program under AFOSR Grant No.
keys, and we conclude that the fundamental problem is an FA9550-08-1-0352, and a National Science Foundation
implementational issue rather than a cryptographic one. Graduate Research Fellowship.
References [21] G UTMANN , P. Software generation of random numbers for cryp-
tographic purposes. In Proc. 7th USENIX Security Symposium
[1] random(4) Linux manual page. http://www.kernel.org/doc/man- (1998), pp. 243–257.
pages/online/pages/man4/random.4.html. [22] G UTMANN , P. Lessons learned in implementing and deploying
[2] BAUER , M., AND L AURIE , B. Factoring silly keys from crypto software. In Proc. 11th USENIX Security Symposium
the keyservers. In The Shoestring Foundation Weblog (July (2002), pp. 315–325.
2004). http://shoestringfoundation.org/cgi-bin/blosxom.cgi/2004/ [23] G UTTERMAN , Z., P INKAS , B., AND R EINMAN , T. Analysis
07/01#non-pgp-key. of the Linux random number generator. In Proc. 2006 IEEE
[3] B ELLARE , M., B RAKERSKI , Z., NAOR , M., R ISTENPART, T., Symposium on Security and Privacy (May 2006), pp. 371–385.
S EGEV, G., S HACHAM , H., AND Y ILEK , S. Hedged public-key [24] H EFFNER , C., ET AL . LittleBlackBox: Database of private SS-
encryption: How to protect against bad randomness. In Proc. L/SSH keys for embedded devices. http://code.google.com/p/
Asiacrypt 2009 (Dec. 2009), M. Matsui, Ed., pp. 232–249. littleblackbox/.
[4] B ELLARE , M., G OLDWASSER , S., AND M ICCIANCIO , D. [25] H ENINGER , N., ET AL . There’s no need to panic over factorable
“Pseudo-random” generators within cryptographic applications: keys–just mind your Ps and Qs. Freedom to Tinker weblog (2012).
the DSS case. In Advances in Cryptology—CRYPTO ’97 (Aug. https://freedom-to-tinker.com/blog/nadiah/new-research-theres-
1997), B. S. Kaliski Jr., Ed., pp. 277–291. no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs.
[26] H OLZ , R., B RAUN , L., K AMMENHUBER , N., AND C ARLE , G.
[5] B ELLO , L. DSA-1571-1 OpenSSL—Predictable random number The SSL landscape—A thorough analysis of the X. 509 PKI using
generator, 2008. Debian Security Advisory. http://www.debian. active and passive measurements. In Proc. 2011 ACM SIGCOMM
org/security/2008/dsa-1571. Internet Measurement Conference (2011), pp. 427–444.
[6] B ERNSTEIN , D. J. How to find the smooth parts of integers. [27] H OWGRAVE -G RAHAM , N., AND S MART, N. Lattice attacks on
http://cr.yp.to/papers.html#smoothparts. digital signature schemes. Designs, Codes and Cryptography 23,
[7] B ERNSTEIN , D. J. Fast multiplication and its applications. Algo- 3 (2001), 283–290.
rithmic Number Theory (May 2008), 325–384. [28] K LEINJUNG , T., AOKI , K., F RANKE , J., L ENSTRA , A., T HOMÉ ,
E., B OS , J., G AUDRY, P., K RUPPA , A., M ONTGOMERY, P.,
[8] B LUM , M., AND M ICALI , S. How to generate cryptographically
O SVIK , D., TE R IELE , H., T IMOFEEV, A., AND Z IMMERMANN ,
strong sequences of pseudo-random bits. SIAM J. Comput. 13, 4
P. Factorization of a 768-bit RSA modulus. In Advances in
(1984), 850–864.
Cryptology—CRYPTO 2010 (2010), T. Rabin, Ed., pp. 333–350.
[9] B ONEH , D. Twenty years of attacks on the RSA cryptosystem. [29] L AWSON , N. DSA requirements for random k value,
Notices of the AMS 46, 2 (1999), 203–213. 2010. http://rdist.root.org/2010/11/19/dsa-requirements-for-
[10] B RIER , E., C LAVIER , C., C ORON , J., AND NACCACHE , D. random-k-value/.
Cryptanalysis of RSA signatures with fixed-pattern padding. In [30] L ENSTRA , A., L ENSTRA , H., M ANASSE , M., AND P OLLARD , J.
Advances in Cryptology—Crypto 2001, pp. 433–439. The number field sieve. In The development of the number field
sieve, A. Lenstra and H. Lenstra, Eds., vol. 1554 of Lecture Notes
[11] B ROWN , D. R. L. Standards for efficient cryptography 1: Elliptic
in Mathematics. 1993, pp. 11–42.
curve cryptography, 2009. http://www.secg.org/download/aid-
780/sec1-v2.pdf. [31] L ENSTRA , A. K., H UGHES , J. P., AUGIER , M., B OS , J. W.,
K LEINJUNG , T., AND WACHTER , C. Ron was wrong, Whit is
[12] BUSHING , MARCAN , SEGHER , AND SVEN. Console hacking right. Cryptology ePrint Archive, Report 2012/064, 2012. http://
2010: PS3 epic fail. Talk at 27th Chaos Communication Congress eprint.iacr.org/2012/064.pdf.
(2010). http://events.ccc.de/congress/2010/Fahrplan/attachments/
[32] L OCKE , G., AND G ALLAGHER , P. FIPS PUB 186-3: Digital Sig-
1780_27c3_console_hacking_2010.pdf.
nature Standard (DSS). Federal Information Processing Standards
[13] C HOR , B., AND G OLDREICH , O. Unbiased bits from sources of Publication (2009).
weak randomness and probabilistic communication complexity. In [33] LYON , G. F. Nmap Network Scanning: The Official Nmap Project
Proc. 26th IEEE Symposium on Foundations of Computer Science Guide to Network Discovery and Security Scanning. Insecure,
(1985), pp. 429–442. USA, 2009.
[14] C OX , M., E NGELSCHALL , R., H ENSON , S., L AURIE , B., ET AL . [34] R ISTENPART, T., AND Y ILEK , S. When good randomness goes
The OpenSSL project. http://www.openssl.org. bad: Virtual machine reset vulnerabilities and hedging deployed
[15] DAVIS , D., I HAKA , R., AND F ENSTERMACHER , P. Crypto- cryptography. In Proc. ISOC Network and Distributed Security
graphic randomness from air turbulence in disk drives. In Ad- Symposium (2010).
vances in Cryptology—CRYPTO ’94 (1994), pp. 114–120. [35] R IVEST, R. L., S HAMIR , A., AND A DLEMAN , L. A method for
obtaining digital signatures and public-key cryptosystems. Com-
[16] D IERKS , T., AND R ESCORLA , E. The Transport Layer Security mun. ACM 21 (Feb. 1978), 120–126.
(TLS) Protocol, Version 1.2. RFC 5246.
[36] W OOLLEY, R., M URRAY, M., D OUNIN , M., AND E R -
[17] D ORRENDORF, L., G UTTERMAN , Z., AND P INKAS , B. Crypt- MILOV, R. FreeBSD security advisory FreeBSD-SA-
analysis of the Windows random number generator. In Proc. 14th 08:11.arc4random, 2008. http://lists.freebsd.org/pipermail/
ACM Conference on Computer and Communications Security freebsd-security-notifications/2008-November/000117.html.
(2007), CCS ’07, pp. 476–485. [37] Y ILEK , S., R ESCORLA , E., S HACHAM , H., E NRIGHT, B., AND
[18] E CKERSLEY, P., AND B URNS , J. An observatory for the S AVAGE , S. When private keys are public: Results from the 2008
SSLiverse. Talk at Defcon 18 (2010). https://www.eff.org/files/ Debian OpenSSL vulnerability. In Proc. 2009 ACM SIGCOMM
DefconSSLiverse.pdf. Internet Measurement Conference, pp. 15–27.
[19] G OLDBERG , I., AND WAGNER , D. Randomness and the Netscape [38] Y LONEN , T. SSH—secure login connections over the internet. In
browser. Dr. Dobb’s Journal 21, 1 (1996), 66–70. Proc. 6th USENIX Security Symposium (1996), pp. 37–42.
[39] Y LÖNEN , T., AND L ONVICK , C. The secure shell (SSH) protocol
[20] G RANLUND , T., ET AL . The GNU multiple precision arithmetic
architecture. http://merlot.tools.ietf.org/html/rfc4251.
library. http://gmplib.org/.