Not-So-Random Numbers in Virtualized Linux and the Whirlwind RNG
Adam Everspaugh, Yan Zhai, Robert Jellinek, Thomas Ristenpart, Michael Swift
Department of Computer Sciences
University of Wisconsin-Madison{ace, yanzhai, jellinek, rist, swift}@cs.wisc.edu
Abstract—Virtualized environments are widely thought tocause problems for software-based random number generators(RNGs), due to use of virtual machine (VM) snapshots aswell as fewer and believed-to-be lower quality entropy sources.
Despite this, we are unaware of any published analysis of the
security of critical RNGs when running in VMs. We ﬁll thisgap, using measurements of Linux’s RNG systems (without theaid of hardware RNGs, the most common use case today) on
Xen, VMware, and Amazon EC2. Despite CPU cycle countersproviding a signiﬁcant source of entropy, various deﬁciencies inthe design of the Linux RNG makes its ﬁrst output vulnerable
during VM boots and, more critically, makes it suffer fromcatastrophic reset vulnerabilities. We show cases in which the
RNG will output the exact same sequence of bits each time itis resumed from the same snapshot. This can compromise, forexample, cryptographic secrets generated after resumption. We
explore legacy-compatible countermeasures, as well as a cleanslate solution. The latter is a new RNG called Whirlwind thatprovides a simpler, more-secure solution for providing system
randomness.
Keywords-random number generator; virtualization

I. I NTRODUCTION
Linux and other operating systems provide random number generators (RNGs) that attempt to harvest entropy fromvarious sources such as interrupt timings, keyboard andmouse events, and ﬁle system activity. From descriptionsof events related to these sources, an RNG attempts to
extract (by way of cryptographic hashing) bit strings that are
indistinguishable from uniform for computationally boundedattackers. While recent system RNGs can make use of
hardware RNGs such as Intel’s rdrand instruction, security
still relies on software sources either exclusively (e.g., onolder CPUs) or in part (e.g., because of uncertainty about
the efﬁcacy of closed-source hardware RNGs [19]).
There exists signiﬁcant folklore [14,16,27] that system
RNGs such as Linux’s may provide poor security in virtualized settings, which are increasing in importance due
to adoption of cloud computing services such as Amazon’sEC2. Stamos, Becherer, and Wilcox [28] hypothesized that
the Linux RNG, when run within the Xen virtualization
platform on EC2, outputs predictable values very late in
the boot process. Garﬁnkel and Rosenblum [8] ﬁrst hypothesized vulnerabilities arising from the reuse of random
numbers when using virtual machine snapshots. Ristenpartand Yilek [26] were the ﬁrst to show evidence of theseand called them reset vulnerabilities. They demonstrated thatuser-level cryptographic processes such as Apache TLS cansuffer a catastrophic loss of security when run in a VM thatis resumed multiple times from the same snapshot. Left as anopen question in that work is whether reset vulnerabilities
also affect system RNGs. Finally, common folklore statesthat software entropy sources are inherently worse on virtualized platforms due to frequent lack of keyboard and mouse,interrupt coalescing by VM managers, and more. Despite
all this, to date there have been no published measurement
studies evaluating the security of Linux (or another common
system RNG) in modern virtualized environments.
Our ﬁrst contribution is to ﬁll this gap. We analyze arecent version of Linux and its two RNGs, the kernelonly RNG (used for stack canaries and address-space layout
randomization) as well as the more well-known RNG underlying the /dev/urandom and /dev/random devices. Via careful
instrumentation, we capture all inputs to these RNGs in avariety of virtualized settings, including on local Xen and
VMware platforms as well as on Amazon EC2 instances.
We then perform various analyses to estimate the securityof the RNGs. Our work reveals that:• Contrary to folklore, we estimate that software entropy
sources, in particular (virtualized or non-virtualized)
cycle counters provide signiﬁcant uncertainty from anadversary’s perspective during normal operation of thesystem (i.e., after it has booted).
• However, when booting a VM the ﬁrst use of the kernelonly RNG as well as the ﬁrst use of /dev/urandom areboth vulnerable. There exists a boot-time entropy hole,where insufﬁcient entropy has been collected before
use of the RNGs. Later outputs of the RNG, however,appear intractable to predict, suggesting the concerns of
Stamos et al. are unwarranted.
• Finally, the /dev/urandom RNG suffers from catastrophic snapshot reset vulnerabilities, which unfortunately answers the open question of [26] in the positive
and obviates a countermeasure suggested for the userlevel vulnerabilities previously discovered [26]. Weshow that resets can lead to exposure of secret keys
generated after snapshot resumption.
Our results are qualitatively the same across the different
VM management environments, though note that EC2 does
not currently support snapshots and therefore does not (yet)RNG
Linux GRI
Linux /dev/(u)random
FreeBSD /dev/random
Windows rand s()
Whirlwind

Reset
Security
No
No
No
No
Yes

Boot
SecurityNo
No
Unknown
Unknown
Yes

Tracking
SecurityNo
Yes
Yes
Unknown
Yes

Figure 1. Security comparison of system RNGs. Reset security refers
to safety upon VM snapshot resumption, boot security means sufﬁciententropy is generated prior to ﬁrst use, and tracking security is forward- andbackward-security in the face of compromise, and resistance to checkpointing attacks. See Section II-C for more details.

suffer from reset vulnerabilities.
We also perform limited experiments with FreeBSD andWindows, and speciﬁcally demonstrate that reset vulnerabilities affect FreeBSD’s /dev/random and Microsoft Windows
rand s() as well. This suggests that problems with virtualized deployments are not conﬁned to the Linux RNGs.
We move on to offer a new RNG design and implementation (for Linux), called Whirlwind. It directly addresses the
newly uncovered deﬁciencies, as well as other long-known
problems with the Linux RNG. Here we are motivated by,
and build off of, a long line of prior work: pointing out
the troubling complexity of the /dev/random and /dev/urandom RNG system [6,11,18]; showing theoretical weaknesses
in the entropy accumulation process [6]; designing multipool RNGs without explicit entropy counters [13,21]; andshowcasing the utility of instruction and operation timing toquickly build entropy [1,23,24].
Whirlwind combines a number of previously suggested
techniques in a new way, along with several new techniques. It serves as a drop-in replacement for both of theLinux RNGs, and provides better security (see Figure 1).
In addition to security, the design focuses on simplicity,
performance, theoretical soundness, and virtualization safety(though it will perform well for non-virtualized settings aswell). At its core is a new cryptographic hashing mode,
inspired by but different from the recent construction of
Dodis et al. [6], plus: a simple two-pool system, simpler interface, streamlined mostly-CPU-lock-free entropy addition,a method for bootstrapping entropy during boot and VM
resumption, direct compatibility with hypervisor-provided
randomness, and support for the rdrand instruction when it
is available. We emphasize that the security of Whirlwind
never relies on any one feature in particular (e.g., using
rdrand by itself), and instead uses multiple inputs sources
to ensure the highest possible uncertainty even in the faceof some entropy sources being compromised.
In terms of performance, Whirlwind matches the current
Linux /dev/urandom, and in some cases performs better.
We also show experimentally that it suffers from noneof the problems for virtualized settings that render thecurrent Linux RNG vulnerable. We do caution that more
analysis will be needed before widespread deployment, since

the Linux RNGs must work in diverse environments. For
example, future analysis will include low-end embedded
systems, another problematic setting [11,12,23]. Towards
this, we are in the process of making Whirlwind ready for
public, open-source release.
Finally, we explore hypervisor-based countermeasures forlegacy guest VMs with the old RNG. In particular, weinvestigate whether the hypervisor can defend against reset
vulnerabilities by injecting entropy into the guest RNG
via (artiﬁcially generated) interrupts during resumption. We
show that either a user-level guest daemon or the hypervisor
can force Linux /dev/random to refresh itself and reduce
the window of vulnerability from minutes to a few seconds.
While much better than current systems, this is still below
the security offered by Whirlwind. Due to space constraints,
we defer the details of these countermeasures to the fullversion of the paper, which will be available from theauthors’ websites.
II. BACKGROUND
A. The Linux RNGs
The Linux kernel provides three RNG interfaces which aredesigned to provide cryptographically strong random values:/dev/random, /dev/urandom, and get random int (GRI).
The /dev/(u)random RNG. The Linux kernel exposes two
pseudo-devices that implement interfaces to what we callthe /dev/(u)random RNG. The ﬁrst, /dev/random, may until
enough entropy is available, while the second, /dev/urandom,
is non-blocking. On the systems we examined, applications
and the Linux operating system itself use exclusively /dev/urandom and never read from /dev/random. The RNG
consists of (1) entropy gathering mechanisms that produce
descriptions of system events; (2) several entropy pools towhich these descriptions are mixed with a cryptographicallyweak generalized feedback shift register; (3) logic for how
and when entropy ﬂows between pools (described below);and (4) APIs for consumers to query to obtain randomness.
To retrieve random numbers, an application opens one of thedevice ﬁles, performs a read, and (presumed-to-be) random
bytes are returned. Additionally, an application may write toeither device, in which case the /dev/(u)random RNG mixes
the contents of the write buffer into both secondary entropy
pools (also described below) but does not update any entropy
estimates. For example, during boot a ﬁle containing output
from /dev/urandom during the preceding shutdown is written
back into the /dev/(u)random. Read and write requests arealways made in units of bytes. The /dev/urandom RNG also
has a kernel-only interface get random bytes() that does
not use the pseudo-device but is functionally identical to/dev/urandom.
An entropy pool is a ﬁxed-size buffer of random datastored in kernel memory along with associated state variables. These variables include the current mixing location

RP

disk, k/m

/dev/random
HV

IP
ints

IntP

Figure 2.

UP

P + J + CC

S

+

MD5

HV[0..32]/dev/urandom

The Linux RNGs. (Left) Data ﬂow through the /dev/(u)random RNG and (Right) the kernel-only RNG GRI.

for new inputs and an entropy count measured in bits. There
are four pools as shown on Figure 2. In the below, we omit
details regarding the cryptographic extraction function andthe non-cryptographic mixing functions. Detailed descriptions appear in [6,18].
Interrupt pool (IntP): The kernel IRQ handler adds a description of each interrupt to a 128-bit interrupt pool (calleda “fast pool” in the source code). There is one IntP per
CPU to eliminate contention. Each interrupt delivery takes
a description (cycle counter xor’d with kernel timer, IRQ
number, instruction pointer that was interrupted) and mixes
it into the pool using a cryptographically weak function. The
entire contents of each IntP are mixed into the input pool IP
using another (more complex generalized feedback register)
mixing function every 64 interrupts or if a second has passed
since the last mixing into IP. At the same time, the input
pool entropy count denoted IP.ec is incremented (credited)by one (bit), which represents a conservative estimate .
Input pool (IP): The 4096-bit input pool has the interrupt
pool mixed into it as just mentioned, and as well has devicespeciﬁc event descriptions (kernel timer value, cycle counter,device-speciﬁc information) of keyboard, mouse, and disk
events mixed in using the more complex cryptographicallyweak function. We will only consider settings with no
keyboard or mouse (e.g., servers), and so only disk events
are relevant. (Network interrupts go to IntP.)
Non-blocking pool (UP): A 1024-bit pool isused for the non-blocking /dev/urandom interface.
Upon a request for 8n bits of randomness, let
αu = min(min(max(n, 8), 128), IP.ec/8 − 16). If
UP.ec < 8n and 8 ≤ αu the RNG transfers data from the
input pool IP to UP. Put another way, a transfer occurs only
if UP.ec < 8n and IP.ec ≥ 192. If a transfer is needed,
the RNG extracts αu bytes from IP and mixing the result
into UP, decrementing IP.ec by 8αu , and incrementing
UP.ec by 8αu . If a transfer is not needed or not possible(by the restrictions above), then UP is left alone. In theend, the RNG decrements UP.ec by 8n, extracts 8n bitsfrom UP, and return those bits to the calling process.
Blocking pool (RP): A 1024-bit pool is used for the blocking /dev/random interface. Upon a request for 8n bits of randomness, let αr = min(min(max(n, 8), 128), IP.ec/8).
If RP.ec ≥ 8n then it immediately extracts 8n bits fromRP, decrements RP.ec by 8n, and returns the extracted bits.
Otherwise it checks if αr ≥ 8 and, if so, transfers αr bytes

Transfer
IntP → IP

WhenInterrupt arrival

Condition
64 interrupts or 1 second

IP → UPn bytes requested
from /dev/urandom

UP.ec < 8nIP.ec ≥ 192

IP → RPn bytes requested
from /dev/random

RP.ec ≤ 8n
IP.ec ≥ 64

Figure 3.

Conditions for transfers between entropy pools.

from IP to RP, incrementing and decrementing entropy
counters appropriately by 8αr . It then immediately extracts
RP.ec/8 bytes fromRP, decrements RP.ec appropriately,
and returns the extracted bits to the calling process. If on
the other hand αr < 8, then it blocks until αr ≥ 8.
Figure 3 summarizes the conditions required for transferring data from one pool to the next. The design of/dev/(u)random intimately relies on ad-hoc entropy estimates, which may be poor. We will also see, looking ahead,that the entropy counters cause trouble due to their use
in deciding when to add entropy to the secondary pools.
For example, we observe that there exists a simple entropy
starvation attack against /dev/urandom by a malicious user
process that continuously consumes from /dev/random (e.g.,using the command dd if=/dev/random). In this case,reads from /dev/urandom will never trigger a transfer fromIP.
get random int: the kernel-only RNG. GRI is a simple
RNG that provides 32-bit values exclusively to callers inside
the kernel. GRI is primarily used for Address Space Layout
Randomization (ASLR) and StackProtector “canary” values
used to thwart stack-smashing attacks. The GRI RNG is
designed to be very fast and does not consume entropy fromthe pools in /dev/(u)random.
The GRI RNG uses two values stored in kernel memory:a per-CPU 512-bit hash value HV and a global 512-bit
secret value S, which is initially set to all zeros. During
the late_init phase of boot, the kernel sets the secretvalue S to 512-bits obtained from /dev/urandom is initially
set to all zeros. Late in the boot process, the kernel sets thesecret value S to 512-bits obtained from /dev/urandom.
Each time it is called, GRI adds the process ID (PID)
P of the current process, the current kernel timer value J(called jifﬁes), and the lower-32 bits of the timestamp cycle
counter CC into the ﬁrst 32-bit word of the hash value HV ,and then sets HV to the MD5 hash of HV and the secretvalue S. That is, it computes HV = H( (HV [1 .. 32] +P + J + CC) || HV [33 .. 512] || S) where “+” is integer
addition modulo 232 , || is concatenations, and H(·) is theMD5 hash. The ﬁrst 32 bits of HV are returned to the caller,
and the new HV value becomes the stored hash value forthe next call.
Use of hardware RNGs. If available, the /dev/(u)random
RNG uses architecture-speciﬁc hardware RNGs during initialization and output generation. During boot,/dev/(u)random reads enough bytes from the hardware RNG
to ﬁll each pool and uses the weak mixing function to mix
in these values. This is done for the input, nonblocking,and blocking pools, but not for the interrupt pool. During
output generation, /dev/(u)random XORs values from the
hardware RNG into each word of the output value prior to
the “folding” of the output that produces a 10-byte chunk.
GRI returns a 32-bit value from the hardware RNG in placeof the software implementation described above.
B. Virtualization
In this work, we focus on the efﬁcacy of the Linux RNGs
when operating in virtualized environments without the aidof a hardware RNG. In a virtualized environment, one ormore guest virtual machines (VMs) run on a single physicalhost, and the hypervisor mediates access to some hardware
components (e.g., the network interface, disks, etc.). Thereis a management component for starting, stopping, andconﬁguring virtual machines. In Xen, this is called Dom0,
while in hosted virtual machines (e.g., VMware Workstation)
this is the host operating system.
A VM can be started in one of three ways. First, it can
execute like a normal physical system by booting from avirtual disk. As it executes, it can update the state on thedisk, and its next boot reﬂects those changes. Second, a VM
can be repeatedly executed from a ﬁxed image, which is aﬁle that contains the persistent state of the guest OS. In thiscase, changes made to the OS state are discarded when the
VM shuts down, so the OS always boots from the same state.
This is the default case, for example, in infrastructure-as-aservice cloud computing systems including Amazon EC2.
Third, a VM can start from a snapshot, which is a ﬁle that
contains the entire state of a running VM at some point
in its execution. This includes not only the ﬁle system but
also memory contents and CPU registers. Both Xen and
VMware support pausing a running VM at an arbitrary point
in its execution and generating a snapshot. The VM can beresumed from that snapshot, which means it will continue
executing at the next instruction after being paused. If a
VM continues running after the snapshot, restarting from asnapshot effectively rolls back execution to the time when
the snapshot was taken.
It has long been the subject of folklore that RNGs,
and in particular, /dev/(u)random, may not perform as wellwhen run within a VM [14,16,27,28]. First, hypervisors
often coalesce interrupts into batches before forwarding
them to a given guest domain to improve performance.
Second, memory pages are typically zeroed (set to all zeroes
to erase any “dirty” data) by the hypervisor when newphysical memory pages are allocated to a guest VM. Zeroing
memory pages is required to ensure that dirty memory
does not leak information between different guests on thesame host machine. Third, several system events used for
entropy by /dev/(u)random are not relevant in popular usesof virtualization, in particular keyboard and mouse events
do not occur in virtualized servers.
C. RNG Threat Models
The Linux RNGs are used by a variety of securitycritical applications, including cryptographic algorithms andfor system security mechanisms. Should RNG values be
predictable to an adversary or the same (unknown) value
repeatedly used, the RNG-using applications become vulnerable to attack. As just a few examples, /dev/urandom
is used to seed initial TCP/IP sequence numbers and by
cryptographic libraries such as OpenSSL to generate secretkeys, while GRI is used as mentioned above for ASLR andstack canaries.
RNGs are therefore designed to face a variety of threats
from attackers both off-system and (unprivileged) local
attackers. We assume that the attacker always knows thesoftware and hardware stack in use (i.e., kernel versions,distribution, and underlying hypervisor). The threats to RNG
systems are:(1) State predictability: Should the entropy sources usedby the RNG not be sufﬁciently unpredictable from thepoint of view of the attacker, then the RNG state (andso its output) may be predictable. For example, a lowgranularity time stamp (e.g., seconds since the epoch)
is a bad entropy source because it is easily guessed[10].
(2) State compromise: The attacker gets access to the internal state of the RNG at some point in time and uses it tolearn future states or prior states (forward-tracking andback-tracking attacks respectively). Forward-tracking
attacks may use RNG outputs somehow obtained by
the attacker as checkpoints, which can help narrowa search allowing the attacker to check if guessedinternal states of the RNG are correct. VM snapshots
available to an attacker, for example, represent a statecompromise.
(3) State reuse: With full-memory VM snapshots, the same
RNG state may be reused multiple times and produce
identical RNG outputs. Since the security of a random
number is its unpredictability, this can eliminate thesecurity of the operation using a repeated RNG output.
(4) Denial-of-service: One process attempts to block another process from using the RNG properly.

Our focus will be on the design of the RNGs, and so wewill not attempt to exploit cryptanalytic weaknesses in theunderlying cryptographic primitives MD5 and SHA-1.
III. M EASUREMENT S TUDY OVERVIEW
In the following sections we report on measurements inorder to answer several questions about the security of theLinux RNGs when used on virtual platforms. In particular:• When booting from a VM image, how quickly is the
RNG state rendered unpredictable? (Section IV)• Does VM snapshot reuse lead to reset vulnerabilities?
(Section V)
Along the way we build a methodology for estimating
uncertainty about the RNG state, and, as a result, assessing
the suitability of various sources of entropy. Of course, one
cannot hope to fully characterize software entropy sources incomplex, modern systems, and instead we will use empiricalestimates as also done by prior RNG analyses [9,23]. Whenestimating complexity of attacking an RNG, we will beconservative whenever possible (letting the adversary know
more than realism would dictate). Where vulnerabilities
appear to arise, however, we will evidence the issues withreal attacks.
To accomplish this, we perform detailed measurements of
the Linux RNGs when rebooting a virtual machine and whenresuming from a snapshot. We produced an instrumented
version of the Linux kernel v3.2.35, which we refer toas the instrumented kernel. The instrumentation records
all inputs submitted to the RNGs, all calls made to the
RNGs to produce outputs, changes to the entropy counts
for each of /dev/(u)random’s pools, and any transfers of bits
between entropy pools. To avoid signiﬁcant overheads, theresulting logs are stored in a static buffer in memory, andare written to disk at the end of an experiment. Our changes
are restricted to the ﬁle: /drivers/char/random.c.
There were surprisingly non-trivial engineering challenges
in instrumenting the RNGs, as the breadth of entropy
sources, inherent non-determinism (e.g., event races), andthe potential for instrumentation to modify timing (recall thattime stamps are used as entropy sources) make instrumentation delicate. For brevity we omit the details. However, we
did validate the correctness of our instrumentation by building a user-level simulator of the RNGs. It accepts as input
log ﬁles as produced by the instrumented kernel, and uses
these to step through the evolution of the state of the RNGs.
This allowed us to verify that we had correctly accounted
for all sources of non-determinism in the RNG system, and,looking ahead, we use this simulator as a tool for mounting
attacks against the RNGs. For any computationally tractableattacks, we also verify their efﬁcacy in an unmodiﬁed Linuxkernel.
We will publicly release open-source versions of the
instrumented kernel as well as simulator so others canreproduce our results and/or perform their own analyses inother settings. Links to open-source code for this project canbe found on the author’s website.
We use the following experimental platforms. For local
experiments, we use a 4-core Intel Xeon E5430 2.67 GHz
CPU (64-bit ISA) with 13 GB of main memory. We use
Ubuntu Linux v12.10 in the Native setup, and we use thesame OS for host and guest VMs. The Xen setup uses Xen
v4.2.1, and the single Xen guest (domU) is conﬁgured with asingle CPU and 1 GB of main memory. The cycle counter is
not virtualized on Xen experiments (the default setting). The
VMware setup uses VMware Workstation 9.0.0 with guest
given a single CPU and 2 GB of main memory. On VMware
the cycle counter is virtualized (the default). Although we
performed experiments with Ubuntu, our results should
apply when other Linux distributions are used in either
the host and/or guest. Finally in our EC2 setup, we built
an Amazon Machine Image (AMI) with our instrumented
kernel running on Ubuntu Linux v12.04 (64-bit ISA). All
experiments launched the same AMI on a fresh EBS-backed
m1.small instance in the US East region. In our experimental
setups, there exist no keyboard or mouse inputs, which isconsistent with most VM deployment settings.
IV. B OOT- TIME RNG S ECURITY
We examine the behavior of the two Linux RNGs (GRIand /dev/(u)random) during boot, in particular seeking tounderstand the extent to which there exist boot-time entropy
holes (insufﬁcient entropy collection before the ﬁrst uses of
the RNGs). As mentioned, in the past concerns have beenraised that the Linux RNGs, when running on Amazon EC2,
are so entropy starved that cryptographic key generation
towards the end of boot could be compromised [28]. Our
results refute this, showing that uncertainty in the RNGs
is collected rather rapidly during boot across a variety ofsettings. We do, however, expose a boot-time entropy holefor the very ﬁrst uses of both GRI and /dev/(u)random. In
both cases the result is that stack canaries generated earlyin the boot process do not provide the uncertainty targeted(to 27 bits of uncertainty from 64 bits due to the weak RNG
output).
We examine the behavior of the two Linux RNGs (GRIand /dev/(u)random) during boot, in particular seeking tounderstand the extent to which there exist boot-time entropy
holes (insufﬁcient entropy collection before the ﬁrst uses of
the RNGs). As mentioned, in the past concerns have beenraised that the Linux RNGs, when running on Amazon EC2,
are so entropy starved that cryptographic key generation
towards the end of boot could be compromised [28]. Our
results suggest otherwise, showing that uncertainty in the
RNGs is collected rather rapidly during boot across a variety
of settings. We do, however, expose a boot-time entropy holefor the very ﬁrst uses of both GRI and /dev/(u)random. In
both cases the result is that stack canaries generated early

104

Disk
DeviceNetwork
Timer

Events

103

102

101

100

50

100

150

200

250

300

Time since boot (seconds)

Figure 4. The number of inputs to /dev/(u)random RNG by type of event
during boot on VMware. The y-axis contains number of events (logscale)bucketed into 3-second bins.

in the boot process do not provide the uncertainty targeted(from 64 bits of uncertainty to about 27 due to the weak
RNG output).
We perform analyses using the instrumented kernel in the
Native, Xen, VMware, and Amazon EC2 setups (describedin Section III). We perform 200 boots in each environment,
and analyze the resulting log ﬁles to assess the security of
the RNGs. After boot, the VM is left idle. We break down
our discussion by RNG, starting with /dev/(u)random.
A. /dev/(u)random boot-time analysis
The graph in Figure 4 displays the quantity and types of
inputs to the RNG for a single boot in the VMware setup(the other VMware traces are similar). The x-axis is divided
into 100 equal-sized buckets (3 seconds each) and the yaxis represents the number of occurrences of each input tothe RNG state observed during a single time bucket (on alogarithmic scale). The majority of RNG inputs during bootare from disk events and other device interrupts while timer
events are rare. The other platforms (Native, Xen, and EC2)
were qualitatively similar.
Estimating attack complexity. In order to estimate thesecurity of /dev/(u)random outputs, we seek a lower boundon the complexity of predicting the state of the RNG
by examining its inputs. Given that we target only lower
bounds, we are conservative and assume the attacker has asigniﬁcant amount of information about inputs and outputs
to the RNG. When these conservative estimates show apossible vulnerability, we check for attacks by a more
realistic attacker.
To establish a lower bound, we deﬁne the following conservative attack model. The attacker is assumed to know theinitial state of the RNG (this is trivially true when booting
VM images, due to zeroed memory) and the absolute cycle
counter at boot time (the exact value is not typically known).
To estimate the security of output i of /dev/(u)random, we

assume the attacker has access to all preceding RNG outputs
and the exact cycle counter for each output generation,
including the ith output. This means we are assessing a kindof checkpointing or tracking attack in which the attacker
can utilize knowledge of previous RNG outputs generated
by typical requests to reduce her search space.
We will additionally assume that the exact sequence of
RNG input types and the values of all event descriptions
except the cycle counter are known to the attacker. This
makes the cycle counter the only source of unpredictability
for the attacker. The reason we do this is that, in fact,
the other inputs included in event descriptions such as IRQ
appear to provide relatively little entropy. (Of course a real
attacker would need to predict these values as well, but again
we will be generous to the attacker.)
Input and output events. For a given platform (Xen,
VMware, EC2, or no-virtualization) we analyze the traces
of inputs and outputs of /dev/(u)random starting at boot andassign an identiﬁer to each input and output event so that
we can compare events across all t trials in each dataset.
We identify input events by the type of event (disk eventor interrupt by IRQ) and the index speciﬁc to that event
type in each trial. Grouping identiﬁers across all t trials, a
given identiﬁer, say (IRQ 16, 20), is a t-dimensional vectorof cycle counter values representing the cycle counters fromthe 20th occurrence of interrupts on IRQ 16 across all trials.
Similarly, we group output events by their sequence ina given trace. To analyze the security of output i, we ﬁrst
ﬁx a trial, then determine all the input events between the
output and the preceding output (i − 1). We call this input
sequence Si . Grouping inputs into sequences is critical to theanalysis: since we assume the only observable behavior of/dev/(u)random is the output, then an attacker must correctlypredict all inputs in a given sequence to guess the internal
state of the RNG. The complexity of this operation thengrows exponentially with the length of any input sequence.
We deﬁne α ≥ 0 as the number of lower bits of a groupof cycle counters that appear to be uniformly distributed forany given input event. For any input event, some number ofupper bits may provide some adversarial uncertainty, but for
simplicity we ignore these and focus only on the lowest α
bits.
Statistical test for uniformity. To determine how many
low bits appear to provide uncertainty, we use theKolmogorov-Smirnov (KS) 1-sample test [29]. The KS test
determines the maximum difference between the cumulative
distribution function of a set of samples compared to areference distribution. We proceed as follows for a candidate
α value and a particular input event which recall consists ofa t-dimensional vector of cycle counters. We mask the upper(64 − α) bits of each cycle counter value to produce a list oft α-bit values. We then compare these values to the uniform
distribution over [0, 2α − 1] using the KS test. The KS test

rejects any set of samples when the maximum differenceis above some predeﬁned threshold for a given signiﬁcancelevel. Typical signiﬁcance levels include 0.1, 0.05, 0.025,
and 0.001 [29]; we chose 0.1 which is most conservative(it favors smaller values for α). We ﬁnd the largest α thatpasses this KS test.
Any given event may be highly correlated with someprevious event and an attacker can use this correlation to
her advantage. To account for this, we also apply the above
tests to relative cycle counter values. That is, for an input
event E we compute, for a previous input or output eventE  , the relative cycle counter value obtained by subtractingfrom the cycle counter of E the cycle counter value of E (from the same trace). Then we compute the maximum αthat passes the KS test for uniformity using these relative
cycle counter values for E. We repeat this for every event E 
preceding E, and only keep the minimal α value computed.
We also experimented with using a χ2 test in place of KS
in the procedures just described. The results were largely
the same for equivalent signiﬁcance levels, with the KS test
being slightly more conservative (it chose smaller α values).
We therefore use KS and only report on it.
Computing complexity. For output i from /dev/(u)random,
let Si be sequence of input events that precede i (but occur
after i − 1) and let i be the length of Si (the number of
input events). Sequence lengths may vary from trial to trial
on the same platform, due to slight timing differences during
the boot sequence. Sequence length is a key component tothe complexity of predicting input values since each input
in a sequence increases the attacker’s search space by amultiplicative factor. So we compute the complexity of predicting a given sequence individually for each trial and weanalyze both the minimum and median values. We computethe complexity of predicting thecycle counters for the eventsin input sequence Si as: si = x∈Si minAlpha(x). This is
the same as computing the logarithm of the size of the searchtree for cycle counters when the attacker must only predictthe lower αj bits for each event j ∈ Si where the bits are
all independently chosen.
To determine the complexity of predicting output i, we
compute κi = max{s1 , s2 , . . . , si }. We use maximum
instead of sum for simplicity, since in general the cumulativecomplexity is dominated by the most complex sequence.
Again, we compute κi individually for each trial and thenexamine the minimum value across all trials.
To summarize, 2κi represents a lower bound on an adversary’s ability to predict the ith output of the RNG during bootassuming that the low α bits for each event (the α varies
between events) are uniform. Unless speciﬁed otherwise, thiswill be the standard method for computing lower-bounds on
attack complexity, and although it is a heuristic, we believe
it to be a good one.
Figure 5 shows the complexities for the platforms wetested during the ﬁrst few seconds of boot. These values
were computed using t = 200 boots on each platformusing our instrumented kernel. In all cases the ﬁrst output isvulnerable; see discussion below. Beyond that, our analysis
shows that the lower-bounds on attacks increase very rapidly,with Xen and the native platform exhibiting the smallest
complexity for the second output, an attack complexityof at least 2129 . The non-virtualized platform reaches amin κi = 1024 at output 140 which is generated 4.0 seconds
after boot (not shown). After 5 seconds on all platforms theattack complexity reaches the maximal value for this RNG:
1024 bits. Note that the times of outputs reported in thistable are relative to the time the Linux kernel is initialized,
which does not include the time in the VM manager’s startup
and guest boot loader (e.g., this is about ∼3.5 seconds in
VMware).
We observe that very long input sequences dominate thecumulative attack complexity κi , which is not surprising.
In all trials on all platforms, we observed max(i )) ≥ 395
in the ﬁrst 5 seconds after boot, that is, all boots have atleast one sequence of 395 or more inputs. This means thateach input cycle counter needs to carry only 2.6 bits ofuncertainty on average for κi to reach its maximum valueof 1024. On a platform with a 1.8 GHz clock (the slowest
platform we tested, EC2), this represents an average jitterfor input events of 2.9ns.
Note that this analysis assumes that the cycle counters of
input events are not under the control of an attacker and thatcycle counter values are not leaked to an attacker through aside channel. Although such attacks may be possible, theyrequire an attacker to control or inﬂuence nearly all inputs
to the RNG or gain knowledge of nearly all bits of each of
the tens of thousands of inputs that occur during boot.
First output entropy hole. Note that Figure 5 shows thatthe complexity of predicting the ﬁrst output is zero. The ﬁrst
output of /dev/(u)random always occurs before any inputs
are added to the RNG. Because the VM is supplied withzeroed memory pages, the Linux RNGs always start in a
predictable state and so this output is deterministic. We
observe this behavior on both VMware and Xen. The ﬁrst
output, always the 64-bit hexadecimal value 0x22DAE2A8
862AAA4E, is used by boot init stack protector. The current cycle counter is added to this RNG output (the canaryequals CC + (CC  32) where CC is cycle counter) toinitialize the stack canary of the init process. Fortunately, thecycle counter adds some unpredictability, but our analysis of
the ﬁrst GRI output (see Section IV-B) indicates that cycle
counters early in boot carry about 27 bits of uncertainty,
which is signiﬁcantly weaker than the ideal security of 64bits for a uniformly random stack canary.
B. GRI boot-time analysis
To predict the 32-bit output of the GRI RNG, an attacker
needs to know the state of the GRI before the call (HV and

i
1
2
5
10
15

Ti
0
0.9
1.0
1.2
3.6

Nativeisi
00
48 129
0
0
0
0
0
0

κi
0
129
129
129
129

Ti
0
0.1
0.2
2.1
2.1

i
0
9
0
3
1

Xen
si
0
129
0
24
0

κi
0
129
700
1024
1024

Ti
0
1.0
1.0
5.2
5.2

VMware
i
si
0
0
66
794
0
0
75 1024
0
0

κi
0
784
784
784
1024

Ti
0
1.1
1.1
1.4
2.6

i
0
15
0
0
1

EC2
si
0
216
0
0
0

κi
0
134
785
1024
1024

i
1
2
5
10

VMware GRI
Ti
κi
τi
0.3
22
27
0.3
33
44
0.4
76
94
0.4 109 171

Figure 5. (Left) Complexity estimates for predicting the ﬁrst /dev/(u)random outputs generated during boot. Ti is the maximum time in seconds (relative
to boot start) that output i was requested; i is median sequence length; si is the median sequence complexity; and κi is the minimum cumulativecomplexity across all trials on a given platform. (Right) Complexity estimates for GRI outputs. Here τi is the actual attack complexity (in bits) of theattack we implemented.

S, 128-bits and 512-bits, respectively) as well as the inputs
used (J, CC, and P ). When booting on a VM, the initialstate of HV and S are all zeroes. S remains zero until it
is initialized from /dev/(u)random (after approximately 100
calls to GRI in our observations). If the correlation between
the jifﬁes counter J and the cycle counter CC is known(they are based on the same underlying clock), then the
only unknown to an attacker is CC at the time each output
is generated. The worst case scenario occurs on VMware
where the cycle counter is virtualized by default, and so
begins at 0 each time a VM is booted. In our experimentswith VMware, we observed only 2 unique values of J at thetime the ﬁrst call to GRI is made. So if an attacker correctly
guesses the CC and it’s associated J value, then futures
values of J can be computed using the ratio of cycles totimer ticks. We therefore focus only on the cycle counter.
We use a complexity estimate similar to that in the lastsection, except that when bounding the complexity for output
i of the GRI RNG we do not assume the attacker knows theprior outputs. If we did, then each output would only have as
much uncertainty as a single cycle counter carries — the GRI
RNG does not attempt to deal with checkpointing attacks
and never adds entropy except during output generation.
For GRI, we deﬁne si to be the minimum number oflower bits α that appear uniformly distributed across thecycle counters used when output i is generated across allt trials. We use the same algorithm for computing α as
we use for /dev/(u)random. Our computation of κi for GRI
differs, we deﬁne κi as the sum of all preceding sj values:
κi =j∈[i] sj . Here we are excluding checkpointing
attacks.
Figure 5 (right table) shows the resulting complexity
estimates κi for the ﬁrst few outputs i of GRI from 200
boots on VMware (results on Xen and EC2 were similar).
If we exclude the secret value S from GRI, which is a known
value at the start of boot, then GRI has a maximal security
state of 128-bits (the size of its hash chaining variable). GRI
reaches this state after 10 calls, well before the secret value S
is initialized at approximately the 100th call. For the second
output and beyond, predicting the internal state by guessing
inputs is no easier than guessing any single 32-bit output
value. The ﬁrst value, however, shows less than ideal securityfor κ1 . We explore this next.
Predicting early GRI outputs. To conﬁrm that, in fact,
there is a vulnerability, we build an attack that works asfollows. First, we collect a dataset of multiple boots using
our instrumented kernel. From each of t traces, we group all
the cycle counters from the ﬁrst call to GRI, all the cycle
counters from the second, and so on as we did with previous
complexity estimates. Now, however, we select a range ofcycle counters at each depth to include in the attack. To makethe attack more efﬁcient, we search the smallest contiguous
range that covers a fraction (we use 80%) of the observed
cycle counters in the dataset. This excludes some outliers
and provides a moderate speedup of the attack time. We let
τi denote the logarithm of the search space resulting fromthis process. Figure 5 shows the values of τi for the ﬁrst few
outputs using our dataset of 200 boots on VMware with the
instrumented kernel. Again, only the ﬁrst output is weaker
than the desired 32-bits of security.
To evaluate this interpolated attack model we analyzed theﬁrst call to GRI from each of 100 boots on VMware. We
remove one trace from this dataset (the victim) and train
an attack on the remaining traces to identify a range ofpossible values for the cycle counter CC. The remaining
values (HV , J, P and S) are trivially known for the ﬁrst callon this platform. We use a GRI simulator and iterate over theidentiﬁed range of values for CC. The attack is successful
and we verify that we can produce the full internal state HV ,not just the output value. This is useful for validation sincecollisions are very likely when one tests up to 227 guesses
for a 32-bit number; the probability of a collision is 1 in 32.
A successful attack indicates that security is less than it
should be for the ﬁrst output. However, we note that taking
advantage of this would require the ability to test which of
the 227 values are correct. This value is the stack canary forthe kthreadd (kernel thread daemon) process. It is notclear that this weakness can be exploited, but this represents
a failure of the RNG.
V. S NAPSHOT R ESUMPTION RNG S ECURITY
Modern VM managers allow users to pause a running
VM, make a copy of the entire state (called a snapshot)of the VM including CPU registers, memory, and disk, andlater use that copy to restart the VM in the exact state atSituation(1) Cached entropy(2) Racing fast pool

Snapshot state
UP.ec ∈ [8, 56]
Any

Repeats until
UP.ec = 0
IntP overﬂow# bitsUP.ec∞(3) Transfer threshold

IP.ec < 192

IP.ec ≥ 192∞

Figure 6. Three situations leading to reset vulnerabilities with /dev/urandom. The symbol ∞ represents no limit on the number of repeated output
bits before the condition in the third column is met.

which it was paused. Both Xen and VMware support this,though Amazon EC2 does not, nor do any other clouds
to our knowledge. Nevertheless, snapshots are often usedin other settings such as backups, security against browser
compromise, and elsewhere [8,26].
We consider two threats related to VM snapshots. First,
we consider VM reset vulnerabilities [26], where resumingfrom a snapshot multiple times may lead to the RNG
outputting the same values over and over again. Second, we
consider an attacker that obtains a copy of the VM snapshot(e.g., if it is distributed publicly), meaning the attacker has
effectively compromised the state of the RNG at the timeof the snapshot. Here the question is whether the attacker
can predict outputs from the RNG or if, instead, the RNG
is able to build up sufﬁcient fresh entropy to recover fromthe compromise.
A. Reset vulnerabilities (/dev/(u)random)
We show that /dev/(u)random suffers from VM reset
vulnerabilities: the RNG will return the same output in two
different VM resumptions from the same snapshot. There areseveral different situations that give rise to this vulnerability,
all related to the values of the relative entropy countersand other state at the time the snapshot is taken. Figure 6
summarizes three situations that we have observed lead toreset vulnerabilities with regards to /dev/urandom. Note thatthese situations are not mutually exclusive, though we will
exercise them individually in our experiments. As discussed
below, these situations can also cause repeated outputs from/dev/random.
We use the following method to exhibit reset vulnerabilities. A guest VM boots under its default, unmodiﬁed kernel
and runs for 5 minutes to reach an idle state and starts auserland measurement process designed to: detect a VM
reset, capture the input pool entropy count (using /proc/fs)
upon resumption, and perform a series of 512-bit reads from/dev/urandom every 500 μs until the experiment completes.
To perform detection, the userland measurement process
runs a loop that samples the (non-virtualized) cycle counterusing the rdtsc instruction and then sleeps brieﬂy (100 μs).
When a sufﬁciently large discrepancy between subsequent
cycle counters is detected (we use 6.6 billion cycles, which
is about 2 seconds), the detection process exits the loop
and begins reading values from /dev/urandom. Thus we begin capturing outputs from /dev/urandom immediately aftersnapshot resumption. For each experiment, we captured 10

snapshots while the system is idle, performed 10 resets fromeach snapshot and examined the resulting RNG outputs.
We performed experiments on both Xen and VMware.
However, we experienced occasional errors when resumingfrom a snapshot on Xen: the guest would occasionallydeclare the ﬁlesystem readonly (presumably because of someerror upon resumption), and our measurement process wasthus unable to capture RNG outputs to a ﬁle. We experienced
no such errors using VMware.
For each 512-bit output produced by /dev/urandom, wedeclare an output a repeat if a full match of all 512 bits
occurs in any output from a different reset of the same
snapshot. Note that at 512 bits, a repeat can only occur if
the same RNG state was used (otherwise multiple collisions
against SHA-1 would have had to occur).
(1) Cached entropy. Recall that if the entropy estimate ofa secondary pool (UP or RP) has an entropy count greateror equal to the number of output bits requested, then the
output is generated directly from the secondary pool without
pulling fresh bits from the input pool IP. We also note thatno cycle counter (or other time stamp value) is added into
the hash at this point in time, which means that the output
of such calls after a reset are fully determined by the stateof the secondary pool at the time of the snapshot.
If the /dev/urandom entropy count has a value of UP.ec =8n for n > 0 at the time of snapshot, then the bits in the
non-blocking UP pool will be used to satisfy any requestof size ≤ 8n bits without transferring bits from the input
pool. Since the output generation algorithm is deterministic,
this results in repeated output of size ≤ 8n bits under these
conditions. UP.ec has a maximum value of 56 bits becauseof the internal mechanics of the RNG and so the maximum
repeated output length is n bytes where n ≤ UP.ec ≤ 7.
The conditions are the same for /dev/random.
(2) Racing the fast pool. Even if a transfer from the input
pool occurs after reset, this alone is does not prevent repeat
outputs. To generate unique outputs, the RNG requires atleast one new input in the input pool and a transfer fromthe input pool to the secondary pool (UP or RP). Aftera reset, the most likely addition to the input pool is fromthe function add interrupt randomness() as these accountfor an overwhelming majority of /dev/(u)random inputs. As
described earlier, these inputs are buffered in the interrupt
pool (also called the fast pool) until an overﬂow event occurs
and the contents of the interrupt pool are mixed into the input
pool. This creates a race condition between interrupt pool
overﬂow events and reads from /dev/(u)random. An overﬂow
event occurs every 64 interrupts or if 1 second has passed
since the last overﬂow when an interrupt input is received.
During this window, reads to /dev/urandom of arbitrary size
will produce repeated outputs.
For /dev/random, repeated outputs will occur during thesame window until /dev/random blocks for new entropy.

Thus the maximum number of repeated bits from /dev/random is 4088.
To exercise this situation for /dev/urandom we used theexperimental procedure above. Because we are comparing
512-bit output values, we can rule out repeats caused bysituation (1), discussed above. To exclude situation (3)discussed below (which doesn’t involve the input or fastpool), we want the input pool entropy count to be muchhigher than 192. We achieve this by downloading a large ﬁle(1GB) prior to capturing the snapshot. The inbound packets
from the download drive interrupts in the guest kernel which
increases the input pool entropy count. All resumption had
an initial input pool entropy count of at least 1,283 on both
Xen and VMware.
We were not able to exhibit this vulnerability on VMware
with the procedure above. On Xen, 2 snapshots experienced
errors on resumption and produced no usable output. Of theremaining 8 snapshots, one snapshot produced no repeatedoutputs (we didn’t win the race), and the remaining 7
snapshots exhibited at least one repeated 512-bit output(the ﬁrst output requested) after resumption. Of these themaximum duration for repeats was 1.7s after resumption.
This demonstrates that the RNG does a poor job of updating
its state after resumption, due to the (overly) complicatedpool structure and pool-transfer rules.
(3) Input pool entropy count below threshold. The input
pool entropy count IP.ec must reach the transfer thresholdof 192 bits before fresh inputs are transferred from the input
pool to the non-blocking pool UP. While the RNG is in thisstate, an unlimited quantity of repeatable output values canbe generated from /dev/urandom. For /dev/random of course,
this is not true, as repeat values will only be provided until
the entropy estimate for the blocking RP pool is exhausted(as per situation (1) above).
To arrange this situation, immediately before capturing thesnapshot, we execute a 10 second read from /dev/random toreduce the input pool entropy count below 64 and trigger
this condition.
On both VMware and Xen, the maximum value for IP.ec
upon resumption was 48 — sufﬁcient to put the RNG into
situation (3). On VMware, we observed that all snapshots
produced repeat outputs for the duration of the experiment(30 seconds). Results on Xen were similar (excluding failed
resumptions). This indicates that if IP.ec is very low whena snapshot is captured, it may take more than 30 seconds
for the /dev/random RNG to reach a secure state.
Entropy starvation attack for situation (3). In Section II
we observed that there exists a simple entropy starvation
attack against /dev/urandom, where a (malicious) user-levelprocess simply performs continuous reads from /dev/random. The internal logic of the RNG is such that in thiscase the input pool will always transfer to the blocking
RP pool, and never the UP pool. This can be used toextend the amount of time that /dev/urandom produces
repeated outputs in situation (3) where the input pool entropy
count is below the threshold to transfer bits from IP to
UP. An adversary with the ability to run an unprivileged
process on the system can easily engage this condition
by reading from /dev/random. If a remote attacker makes(legitimate) requests to a public interface that triggers largeof frequent reads from /dev/random, then the same effectmay be possible without requiring a local account.
The experimental procedure above was used with thefollowing deviations. We execute a continuous read from/dev/random (dd if=/dev/random) for the duration of
the experiment. After reset, the measurement process performs 512-bit reads from /dev/urandom every 1 second fora duration of 120 seconds. Upon resumption, all snapshots
exhibited repeated 512-bit outputs for the duration of theexperiment on both VMware and Xen (excluding failed
resumptions).
Impact on OpenSSL. The experiments above show that
reset vulnerabilities exist in /dev/(u)random, and give applications stale random values after resumption. We now brieﬂy
investigate the potential for this to lead to exploitable vulnerabilities against applications relying on /dev/urandom for
randomness after a VM resumption. We focus on OpenSSL
v1.0.1e and RSA key generation. When calling openssl
genrsa from the command line, OpenSSL seeds its internal
RNG with 32 bytes read from /dev/urandom as well as thecurrent system time, process ID, and dirty memory buffers.
We instrument this version of OpenSSL in order to observe
internal values of the key generation process. We then set up
a VM running an unmodiﬁed Linux kernel on VMware thatwill, immediately after being reset, execute the command
openssl genrsa from the shell. We observe that justconnecting to the VM via SSH to prepare it for a snapshot
typically drives the input pool entropy count below 192
before we take a snapshot. This is caused because a numberof processes are created during login and each new process
consumes many bytes from /dev/urandom to initialize stackcanaries and perform ASLR.
We captured 27 snapshots, performed 2 resets from eachsnapshot and then analyzed the resulting outputs from the
OpenSSL instrumentation and OpenSSL’s normal output.
A single snapshot produced an identical prime p in theprivate key in both resets, but other values in the private
key differed. Presumably, after the prime p was generated,differing dirty memory buffers caused the OpenSSL RNGs
to diverge. (Knowing one prime value of a private key
is sufﬁcient to derive the other and destroys the securityof an RSA private key.) Of the remaining 26 snapshots,
many had identical /dev/urandom output, but typically the
dirty memory buffers differed early enough in execution
to produce unique outputs. These dirty memory buffers
are likely different between resets because Address SpaceLayout Randomization (ASLR) (determined in part by GRI)
shifts around the OpenSSL memory layout.
To validate this hypothesis, we then disabled ASLR on
the guest VM prior to taking a snapshot by executing echo
0 > /proc/sys/kernel/randomize_va_spaceas root and repeat our experiment for 30 snapshots with 2
resets from each snapshot. Of these, 23 snapshots produced
repeated output from /dev/urandom and identical RSA
private keys. The other 7 snapshots had input at least
1 differing value into the OpenSSL RNG after reset —variously this differing value was one of /dev/urandom
output, PID, or system time.
We note that unlike prior reset vulnerabilities [26], these
are the ﬁrst to be shown in which the system RNG is invoked
after VM resumption. In [26], the authors ask whether
consuming fresh random bytes from the system RNG after
a reset is sufﬁcient to eliminate reset vulnerabilities inapplications. This answers that question in the negative, andhighlights clear problems with the /dev/(u)random design for
settings where snapshots are employed.
Reset vulnerabilities on FreeBSD. We also perform alimited set of experiments with snapshot resumptions using
an (uninstrumented) version of FreeBSD within VMware,to see if reset vulnerabilities affect other RNG designs (adescription of FreeBSD’s design is given in [13]). In eachof three resets using the same snapshot, we took 10 samples,
512 bits each, from /dev/random (same as /dev/urandom on
FreeBSD) one millisecond after reset. In all three resets thesame sequence of outputs were produced. This is a very
narrow window, and may not be practically exploitable, but
we admit that we did not test longer time windows.
Reset vulnerabilities on Windows. We perform similar
experiments on Microsoft Windows 7 running in VMware
using the rand s() random number generator interface. In
Windows, rand s() produces a single, 32-bit random output
value for each call. In all resets from 5 different snapshots
using various timings and number of samples, rand s()
reliably produced repeated 32-bit outputs multiple resets ofthe same snapshot. In all cases, at least 25% of outputs arerepeated. In a separate experiment, we perform 10 resets
from the same snapshot, and after reset we sample a single
32-bit output every 1s for a total of 2000 samples (collected
over more than 30 minutes). We found more than 500 (25%)
repeated outputs shared between each pair of resets, andsome pairs have 1000 (50%) repeated outputs. We also
observe that all 2000 outputs generated in the ﬁrst reset arefound in some combination of the following 9 trials. Thissecurity vulnerability has been reported to Microsoft.
Our experiments on FreeBSD and Windows were very
limited, but are sufﬁcient to demonstrate that the problem of
RNG reset vulnerabilities extends beyond the Linux RNGs.

B. Reset vulnerabilities (GRI)
As described in Section II, the output of the GRI RNG
depends only on the state values HV and secret S and the
inputs cycle counter, jifﬁes and PID (CC, J, P ). Acrossmultiple resets from the same snapshot, it’s very plausible
for the same process (with same PID P ) to be the ﬁrst to
request an output. So the only new information after a snapshot resumption is the cycle counter value. For a virtualized
cycle counter, in which the cycle counter value will always
start from the same value (stored in the snapshot), we might
expect reset vulnerabilities. In fact we observe no repeatedvalues output by GRI across any of its invocations in any of
the 50 resets on VMware that we performed. This can likely
be attributed to small variations in timing between snapshot
resumption and the ﬁrst call to GRI. For 10,000 Xen resets,with the non-virtualized RDTSC, we did not see any repeats
as well.
C. Snapshot Compromise Vulnerabilities
If a snapshot is disclosed to an attacker, then one must
assume that all of the memory contents are available to them.
Not only is there likely to be data in memory of immediate
damage to an unwitting future user of the snapshot (e.g.,secret keys cached in memory), but the RNG state is
exposed. While we can’t hope to prevent cached secret keys
from leaking, we might hope that the RNG recovers fromthis state compromise when later run from the snapshot. As
we saw above, predicting future /dev/(u)random in various
situations is trivial since the attacker can often just run thesnapshot (on similar hardware). When not in these situations,however, and for GRI, we would like to estimate the thecomplexity of using the compromised state to attempt topredict outputs generated after a later snapshot resumption.
We use the same methodology as used above with Xen,
with the workload that reads from /dev/urandom repeatedly
after snapshot resumption. We then use our methodology
from Section IV to give lower-bound estimates on the complexity of predicting the very ﬁrst few outputs to /dev/urandom or GRI.
Figure 7 shows our estimated attack complexity after
reset. The complexity estimates for the /dev/urandom outputs
are much smaller than for their boot time counterparts(Figure 5 in Section IV). The security of the GRI outputs
is similar to boot because GRI security under our modelis driven only by the cumulative uncertainty of the cycle
counters from each output request. However, /dev/urandom
outputs have security dominated by the input sequencelength i . There are far fewer inputs during a resumption than at boot. This suggests possible vulnerability to
prediction attacks, but for brevity we do not pursue themfurther having already shown above that repeats give rise topredictable outputs.

i
1
2
5
10

/dev/(u)randomTi
iκi
0.7 ms20
1.4 ms2
20
4.1 ms2
27
7.1 ms
2
27

GRI
Ti
κi
21 s
22
21 s
33
21 s
66
21 s
105

Figure 7.
The minimum estimated complexity κi to predict the ﬁrst
few outputs of /dev/(u)random and GRI after a Xen guest is reset from asnapshot. Ti is the time that output i is generated (relative to resumption);i is the median sequence length.

VI. T HE W HIRLWIND RNG
In this section we detail the Whirlwind RNG, which
provides a simpler, faster, and more secure randomness
service. While our measurement study focused primarily
on virtual environments, the design of Whirlwind seeks toprovide security for a variety of settings and in general bea drop-in replacement for both /dev/(u)random and GRI. As
such, we must handle a variety of goals:• Simplicity: The current /dev/(u)random design is complex, requiring signiﬁcant effort to understand and audit
its design and implementation (with 1041 lines ofcode) [11]. In contrast, Whirlwind targets simplicity andrequires 676 lines of code.
• Virtualization security: Unlike all prior RNG designs
we are aware of, Whirlwind is explicitly designed toprovide security even in virtualized environments thatmight entail VM snapshot and image reuse.
• Fast entropy addition: Whirlwind uses a simple entropy gathering function designed to be fast, usually
it requires only 0.5 μs on our 2.67 GHz platform,
though 1/8 of the invocations it computes a single SHA512 compression. Despite using a slower hash function(SHA-512), we show it to be about as fast as entropy
addition in the current /dev/(u)random. Whirlwind uses
per-CPU input buffers to reduce lock contention andpermit the amount of buffered inputs to scale with thenumber of CPUs.
• Cryptographically sound: We propose a new design forthe cryptographic core of Whirlwind, inspired by the
recent work of [6]. Whirlwind dispenses with the linear
feedback shift registers of Linux /dev/(u)random, andachieves the robustness security goal detailed in [6].
• Immediately deployable: The basic Whirlwind design
is a drop-in replacement for Linux /dev/(u)random, andrequires no hypervisor support.
A. Whirlwind design
Figure 8 depicts the main components of Whirlwind. It
uses two entropy pools, a fast pool and a slow pool, as donein FreeBSD’s Yarrow RNG [13]. The fast pool consists of a
per-CPU input buffer If ast and a single (global) seed value
Sf ast for the fast pool. The slow pool consists of a per, and
CPU input buffer Islow , a private (internal) seed Sslow

Sf asth
If ast
Input

d
Islow

Sslow

h

p

Sslow

Figure 8. Block diagram of the Whirlwind RNG. Every dth input isdirected to the slow pool, and after p updates it is for use in output
generation. Here h is the SHA-512 compression function.

a public seed Sslow . In our implementation all input buffers
are 1024 bits in size which corresponds to one full message
block for SHA-512. All three seeds in our implementation
are 512 bits, which represents a chaining value for SHA-512.
We denote the SHA-512 compression function by h and the
SHA-512 hash function by H. Let n be the number of bitsof output for both h and H. We initialize the seeds values
as: Sf ast ← h(IV, 1) and Sf ast ← h(IV, 2) where IV is
the SHA-512 initialization vector and 1 and 2 are encodedin some unambiguous manner [25].
Inputs are written to the fast pool If ast by default andevery dth input is diverted to the slow pool Islow . In our
implementation d = 10 which ensures that the fast pool
receives the majority of inputs and thus changes rapidly
even in low-entropy conditions. Each input is 128-bits andconsists of the input source’s unique identiﬁer (created by
the GCC macro __COUNTER__ and encoded using 32 bits),
the lower 32 bits of the cycle counter (or jifﬁes on platforms
without a valid cycle counter), and 64 bits of optional,
source-provided information. Input buffers are per-CPU,
obviating the need for locking to process most inputs. We
denote the macro used for adding inputs by ww add input().
When an input pool is full (after 8 inputs are written
to a pool), a SHA-512 compression function applicationis performed, with the chaining variable equal to the pooland the message block equal toseed value Sf ast or Sslow
the input pool. The result becomes the new seed for thatpool. Locks are used to ensure that the compression function
is computed atomically. Thus, Whirlwind is computing ahash over the sequence of inputs in an online fashion. This
ensures the robustness security property introduced by Dodis
et al. [6] and which they showed Linux’s /dev/(u)random
fails to achieve. Robustness requires (informally speaking)that no matter where entropy resides in the sequence of
inputs to the RNG the RNG outputs always beneﬁt fromthe added entropy.
isIn the case of the slow pool, the internal seed Sslow
used as the hash chaining value and upon every pth hash theis copied to the public seed Sslow . This
internal seed Sslow
ensures that the slow pool represents a multiple of p times as

Algorithm 1 ww generate bytes(b)s1 ← Sf ast
s2 ← Sslowt ← 8b/n
ctr ← atomic inc(Ctr, t) − t
hw ← read hw random()
ww add input()
for i = 0 to t doCC ← get cycle counter()
output[i] ← H(3 || s1 || s2 || (ctr + i) || CC || P || hw )end forww add input()
Sf ast ← h(Sf ast , 01024 )return ﬁrst b bytes of output
Routine for generating b bytes of output from the Whirlwind RNG. The
variable Ctr is a global output counter.

many inputs as the fast pool. In our implementation p = 50,
which, combined with d = 10, means the public slow seedis updated every 500 inputs.
Consumers within the kernel request random values from
Whirlwind using get random int() or get random bytes().
From user mode, processes read random values via the existing /dev/random or /dev/urandom read interfaces. Whirlwind
handles all such requests in the same manner and, in particular, we have completely removed the GRI RNG and we
do not differentiate between /dev/random and /dev/urandom.
The current implementation does not support writing to the
RNG from user-level processes, though it would be easy to
add.
Algorithm 1 describes output generation in pseudocode.
When Whirlwind receives an output request for b bytes,
the RNG ﬁrst copies the slow and fast pool seeds fromstatic (global) memory into local memory on the stack.
Whirlwind then prepares a response by computing a SHA512 hash over the concatenation of: (1) the local copy ofthe slow pool seed; (2) the local copy of the fast pool
seed; (3) a 64-bit request counter Ctr; (4) the current cycle
counter CC; and (5) 64-bits read from a CPU hardware
RNG (e.g., RDRAND), if available. The request counterCtr is atomically pre-incremented for the number of blocks
requested (to reserve counter values for output generation)and is incremented locally for each block of output. This
ensures that even if concurrent requests have identical values(seeds, P, CC) the outputs are guaranteed to be unique. Two
inputs are fed back into the RNG for each output requested.
Finally, a single application of h is used to ensure forward
security.
Initializing Whirlwind. We also include one special mechanism for quickly initializing (or refreshing) the entropy ofWhirlwind, which is needed to prevent a boot-time entropy
hole (like the ones in the legacy RNG, see Section IV) andto recover from a VM reset. For boot time, we would have
liked to use the recent suggestion of Mowery et al. [23]Algorithm 2

ww bootstrap()

for i ← 0 to  doCC ← get cycle counter()
ww add input()k ← CC mod max
for j ← 0 to k doa ← (j/(CC + 1)) − (a ∗ i)end forend for
The Whirlwind entropy bootstrapping mechanism used during boot andsnapshot resumption. The values  and max are conﬁgured parameters(default 100, 1024).

to quickly generate entropy in the initial stages of boot via
timing of functions in the kernel init function. Unfortunately,
this is not fast enough for us, since we observe reads to the
RNG early in init. We therefore use an approach based ontiming of instructions that may take a variable number ofcycles, which has been suggested and used previously [1,24].
This provides nondeterminism (by way of contention andraces within the CPU state), as shown in prior studies [20].
Pseudocode is shown in Algorithm 2. In our implementation
we have  = 100 and max = 1024.
Whirlwind calls this entropy timing loop before the ﬁrst
use of the RNG during boot, and at the start of resumption
from a snapshot. The latter takes advantage of Xen’s resume
callback, which is a virtual interrupt delivered to the guest
OS when it ﬁrst starts following a snapshot resumption.
Similar facilities exist in other hypervisors.
Entropy sources. It is easy to add entropy sources toWhirlwind, by simply inserting ww add input() in appropriate places. This requires no understanding of RNG internals(such as the role of entropy estimates), unlike in the existingLinux /dev/(u)random. In terms of performance, submitting
an input to the RNG is fast, but may still require a single
SHA-512 compression function call on the critical path.
While we expect that, in deployment, Whirlwind might use
a wider set of entropy sources, for comparison purposes, we
restrict our experiments here to use only the same set of entropy sources as used by the current /dev/(u)random implementation in Linux as well as those called in ww bootstrap()
and ww generate bytes().
Hypervisor-provided entropy. As we show below, thealready-mentioned software-based sources are already sufﬁcient to provide security during boots and resets. Some users
may nevertheless desire (for defense-in-depth) support for
the Xen management Dom0 VM (also running Whirlwind)
to provide an additional entropy source for a guest VM’s
Whirlwind RNG. In current practice, host-to-guest entropy
injection is facilitated via virtual hardware RNGs, that then
are fed into the Linux /dev/(u)random by way of a user-level
daemon (rngd). Unlike these systems, we will ensure hostprovided entropy is inserted into Whirlwind immediately
after a VM resumption, before any outputs are generated.

To do so, we pass additional entropy with the Xenstore
facility in Xen, which uses shared memory pages between
Dom0 (the management VM) and the guest VM to provide ahierarchical key-value store. We modiﬁed Dom0 to read 128
bytes from /dev/urandom and write the value to Xenstore.
During a resume callback, Whirlwind detects that a reset
occurred, reads the value from Xenstore and adds the value
to the RNG via repeated input events. All this requires lessthan 30 lines of modiﬁcation to Xen’s operation librarylibxl. The entire operation requires 75 ms on average, andthe rareness of the operation (once per resumption) makes
this tolerable.
Other instantiations. For concreteness, we chose several
suggested values of (sometimes implicit) parameters, but it
is easy to modify the Whirlwind implementation to support
different choices. For instance, instead of letting h be the
SHA-512 compression function, one could use the fullSHA-512 (or some other secure hash, such as SHA-3),
which leads to the RNG computing a hash chain. The
approach detailed is faster because it reduces the number ofcompression function calls. One might also use SHA-256,
smaller or larger seed values (to trigger hashing more or lessfrequently), and the like. Additionally, we choose the output
generation hash H as the full SHA-512. Again, this can be
replaced with any suitable hash function or even AES in aone-way mode such as Davies-Meyer mode [31].
B. Security evaluation
We evaluate the boot-time and reset security of Whirlwind. We perform 50 reboots in Xen from a particularusing an instrumented version of the Linux kernel using
Whirlwind. We also perform 50 resets from a single Xensnapshot captured while idling (5 minutes after boot); a userlevel process requests 512-bit outputs from the RNG every
500 μs after resumption. As before, the instrumentation
records all inputs and outputs to the Whirlwind RNG. We
then perform complexity analysis as done for the legacy/dev/(u)random (see Section IV), which again ignores all
input sources except the cycle counter. This provides aconservative estimate of unpredictability from the attacker’s
perspective. As intended, the adversarial uncertainty regarding the Whirlwind internal state hits 1024 (the maximal
amount) before the ﬁrst use of the RNG either during bootor after a reset. An immediate implication is that reset
vulnerabilities are avoided: the probability of repeated output
arising from reuse of the same snapshot is negligible.
We have not yet evaluated Whirlwind’s entropy accumulation on low-end systems, such as embedded systems [12,23].
In particular, here the cycle timing loop may provide lessuncertainty because embedded system CPUs themselves
have less non-determinism. In these settings, however, we
do not expect to be using VM snapshots (making this usemoot) and for generating entropy at boot we can use thetechniques of [23].

Block size
4 bytes
16 bytes
64 bytes
256 bytes

Throughput (/dev/urandom)
Whirlwind (MB/s)
Legacy (MB/s)
0.6
1.6
2.3
4.9
9.3
9.0
21.8
12.0

Figure 9. Comparing performance of the Whirlwind and legacy /dev/urandom implementations using dd to read 10,000 blocks of various sizes.

C. Performance evaluation
We turn to evaluating the performance of Whirlwind,particularly in comparison to the existing /dev/(u)random
and GRI RNGs. Our Whirlwind implementation uses SHA512 as opposed to SHA-1 (resp. MD5 for GRI), so we
expect to see a performance penalty from the use of stronger
cryptography. To compare, we evaluated the throughput of
reading from /dev/urandom and GRI for both Whirlwind
and the legacy RNGs. While the system is otherwise idle,
we execute reads of 10,000 blocks on the /dev/urandom
interface for various block sizes using dd. We repeat this 100
times for each block size and report the average throughput
in Figure 9. As expected, the legacy RNG performs slightly
better at smaller block sizes (≤ 16 byte), but is outperformed
by Whirlwind at 64 and 256 byte block sizes.
We also compare measured performance of adding inputs
to the new and legacy RNGs. We add minimal instrumentation to time these operations and measure performance
during VM boots, resets, and during idle time. We also use
these runs to measure performance of reading from GRI. The
resulting performance data indicate the various functions
were timed more than 100,000 times for each RNG. The
results are that while input processing for /dev/(u)random is
as fast in Whirlwind as in the legacy RNG, the GRI output
interface requires 10.3 μs (one standard deviation is ±1.8)
for Whirlwind but the legacy RNG requires only 1.0 μs(±0.5).
To the best of our knowledge GRI is only used during
process creation. In order to understand whether the GRI
slowdown will cause problems in applications, we run thefork benchmark from LMbench [22] 100 times. The averagelatency of fork is 414 μs (with standard deviation ±5 μs)for the legacy RNG, and 418 μs (±5 μs) for kernel with
Whirlwind. Thus Whirlwind incurs only 1% overhead in
this (worst-case) benchmark, and so we believe this is not a
problem for practical use.
Lastly, we evaluate the overhead of ww bootstrap()(Algorithm 2) used at boot and snapshot resumption. The
time to execute the timing loops has a mean of 0.7 ms over
50 runs. Boot and snapshot resumption are rare operations,suggesting this level of overhead will not impact deployments.
Overall we conclude that Whirlwind has performanceclosely matching the existing RNGs, and in some caseseven better despite using more expensive (and more secure!)cryptographic primitives. For this, we get a signiﬁcantly
simpliﬁed design and improved security.
VII. R ELATED W ORK
Many high proﬁle RNG failures have been reported over
the years, including ones leading to: attacks against the
Secure Socket Layer (SSL) implementation of an early
Netscape web browser [10]; the ability to cheat cheat atonline poker [2]; insecure random values in Microsoft Windows [7]; predictable host keys in Debian OpenSSL [32];jailbreaks against the Sony’s PlayStation 3 [4]; factorizable
RSA private keys generated on embedded systems [12];predictable outputs in the OpenSSL RNG on Android [17];and factoring RSA private keys that protect digital IDs on
government-issued smart cards in Taiwan [5].
Several previous papers analyzed the Linux/dev/(u)random RNG. Gutterman et al. [11] provided
the ﬁrst: they reverse-engineer the design of the RNG fromthe source code (attesting to its complexity!); highlightproblems in the hashing steps (that were subsequently
ﬁxed and the version we analyze includes these ﬁxes);
and point out that in some constrained environments suchas embedded systems or network routers there might beinsufﬁcient entropy provided to the RNG. Heninger et
al. [12] show that embedded Linux systems suffer froma boot-time entropy hole which leads to exposure of
cryptographic secret keys generated on affected devices.
Mowery et al. [23] look to ﬁll this boot-time entropy
hole by way of timing functions in kernel initialization.
Vuillemin et al. [9] perform an in-depth, empirical analysisof entropy transfers in Linux /dev/(u)random, and showthat most consumers are in the kernel.
Dodis et al. [6], building off earlier work by Barakand Halevi [3], suggest that the cryptographic extraction
component of RNGs should be robust, meaning an RNG
should guarantee entropy is collected no matter the rate ofentropy in the input stream. They show that /dev/(u)random
is not robust, but do not show attacks that would affectpractice. Part of the Whirlwind design is inspired by their
online hashing based extractor, though they use universal
hash functions and we use cryptographic ones.
None of the above consider RNG performance in modern
virtualized environments. We also do not know of any
analyses of the GRI RNG before our work.
Turning to virtualized settings, Garﬁnkel and Rosenblum [8] hypothesized that VM reset vulnerabilities may exist when reusing VM snapshots, and analyses by Ristenpartand Yilek [26], uncovered actual vulnerabilities in user-levelprocesses such as Apache mod ssl that cache randomness inmemory before use. In these settings, the user-level process
never invoked /dev/urandom (or /dev/random) after VM
resumption, and in particular they left as an open question
whether system RNGs suffer from reset vulnerabilities aswell. We answer this question, unfortunately, in the positive,

suggesting that using /dev/urandom right before randomness
use is not a valid countermeasure with the existing design,
though it will be with Whirlwind.
In [28], the authors hypothesize that booting multiple
times from the same VM image in an infrastructure-as-aservice (IaaS) setting such as Amazon’s EC2 may enableattackers to predict /dev/(u)random RNG outputs that canlead to SSH host key compromises. Our analyses suggestthat such an attack is infeasible for all uses of the LinuxRNGs beyond the ﬁrst during boot.
Thompson et al. [30] point out the potential for a malicious hypervisor to snoop on the entropy pools of a guest
VM. Kerrigan et al. [15] investigate entropy pool poisoning
attacks, where one guest VM in a cloud setting attempts
to interfere with another’s entropy pool by (say) sending
interrupts at a known frequency to the guest. Theirs isa negative result, with their experiments showing that theattack fails. Our measurements corroborate this: even justa few bits of uncertainty about cycle counters leads to an
unpredictable RNG state even in the current /dev/(u)random
implementation. We also investigate using such interrupt
injection as a defense.
Finally, we use CPU timing jitter as an entropy source asused in other systems, such as the haveged entropy daemon
and the CPU jitter RNG [1,24].

VIII. C ONCLUSIONSIn this work, we performed the ﬁrst analysis of the security of the Linux system random number generators (RNGs)
when operating in virtualized environments including Xen,
VMware, and Amazon EC2. While our empirical measurements estimate that cycle counters in these settings (whether
virtualized or not) provide a ready source of uncertainty froman attacker’s point of view, deﬁciencies in the design ofthe /dev/(u)random RNG make it vulnerable to VM reset
vulnerabilities which cause catastrophic reuse of internal
state values when generating supposedly “random” outputs.
Both the /dev/(u)random and kernel-only GRI RNGs also
suffer from a small boot-time entropy hole in which the veryﬁrst output from either is more predictable than it should be.
Our second main contribution is a new design for system
RNGs called Whirlwind. It rectiﬁes the problems of theexisting Linux RNGs, while being simpler, faster, and using
a sound cryptographic extraction process. We have implemented and tested Whirlwind in virtualized environments.
Our results showed that Whirlwind enjoys performanceequal (and sometimes even better) than the previous RNG.

R EFERENCES[1] Haveged entropy gatherer.
haveged/.

http://www.issihosts.com/[2] B. Arkin, F. Hill, S. Marks, M. Schmid, T. J. Walls, and
G. Mc-Graw. How we learned to cheat at online poker: A
study in software security. The developer.com Journal, 1999.
[3] B. Barak and S. Halevi. A model and architecture for pseudorandom generation with applications to /dev/random. In
Computer and Communications Security – CCS, pages 203–
212. ACM, 2005.
[4] M. Bendel. Hackers Describe PS3 Security As Epic Fail,
Gain Unrestricted Access, 2010.
[5] D. J. Bernstein, Y.-A. Chang, C.-M. Cheng, L.-P. Chou,
N. Heninger, T. Lange, and N. van Someren. Factoring rsa
keys from certiﬁed smart cards: Coppersmith in the wild. In
Advances in Cryptology – ASIACRYPT 2013, pages 341–360.
Springer, 2013.
[6] Y. Dodis, D. Pointcheval, S. Ruhault, D. Vergnaud, and
D. Wichs. Security analysis of pseudo-random number
generators with input: /dev/random is not robust. In Computerand Communications Security – CCS. ACM, 2013.
[7] L. Dorrendorf, Z. Gutterman, and B. Pinkas. Cryptanalysisof the random number generator of the Windows operating
system. ACM Transactions on Information and System
Security (TISSEC), 13(1):10, 2009.

[16] M. Kerrisk. LCE: Don’t play dice with random numbers,
2012. https://lwn.net/Articles/525459/.
[17] S. H. Kim, D. Han, and D. H. Lee. Predictability of Android
OpenSSL’s Pseudo Random Number Generator. In Computerand Communications Security – CCS, pages 659–668. ACM,
2013.
[18] P. Lacharme, A. Rck, V. Strubel, and M. Videau. The linux
pseudorandom number generator revisited. Cryptology ePrint
Archive, Report 2012/251, 2012. http://eprint.iacr.org/.
[19] E. Leitl. Intel In Bed with NSA. cryptome mailing list, 2013.
http://cryptome.org/2013/07/intel-bed-nsa.htm.
[20] N. Mc Guire, P. O. Okech, and Q. Zhou. Analysis ofinherent randomness of the Linux kernel. In Real Time Linux
Workshop, 2009.
[21] R. McEvoy, J. Curran, P. Cotter, and C. Murphy. Fortuna:
cryptographically secure pseudo-random number generation
in software and hardware. 2006.
[22] L. W. McVoy, C. Staelin, et al. lmbench: Portable tools
for performance analysis. In USENIX Annual TechnicalConference, pages 279–294. San Diego, CA, USA, 1996.
[23] K. Mowery, M. Wei, D. Kohlbrenner, H. Shacham, and
S. Swanson. Welcome to the Entropics: Boot-Time Entropy
in Embedded Devices. pages 589–603. IEEE, 2013.
[24] S. Müller. CPU Time Jitter Based Non-Physical True Random
Number Generator, 2013.

[8] T. Garﬁnkel and M. Rosenblum. When virtual is harder thanreal: Security challenges in virtual machine based computing
environments. In Workshop on Hot Topics in Operating
Systems – HotOS-X, May 2005.

[25] National Institute of Standards and Technology. Federal
Information Processing Standards Publication 180-2: Secure
Hash Standard, 2002. http://csrc.nist.gov/publications/ﬁps/
ﬁps180-2/ﬁps180-2withchangenotice.pdf.

[9] F. Goichon, C. Lauradoux, G. Salagnac, and T. Vuillemin.
Entropy transfers in the Linux Random Number Generator.
Research Report RR-8060, INRIA, Sept. 2012.

[26] T. Ristenpart and S. Yilek. When good randomness goes bad:
Virtual machine reset vulnerabilities and hedging deployed
cryptography. In NDSS. ISOC, 2010.

[10] I. Goldberg and D. Wagner. Randomness and the Netscapebrowser. Dr Dobb’s Journal-Software Tools for the Professional Programmer, 21(1):66–71, 1996.
[11] Z. Gutterman, B. Pinkas, and T. Reinman. Analysis of theLinux random number generator. In IEEE Symposium on
Security and Privacy, pages 371–385. IEEE, 2006.
[12] N. Heninger, Z. Durumeric, E. Wustrow, and J. A. Halderman.
Mining Your Ps and Qs: Detection of Widespread Weak Keysin Network Devices. 2012.
[13] J. Kelsey, B. Schneier, and N. Ferguson. Yarrow-160: Notes
on the design and analysis of the yarrow cryptographic
pseudorandom number generator. In Selected Areas in Cryptography, pages 13–33. Springer, 2000.
[14] B. Kerrigan and Y. Chen. A study of entropy sources in cloudcomputers: random number generation on cloud hosts. In
Computer Network Security, pages 286–298. Springer, 2012.
[15] B. Kerrigan and Y. Chen. A study of entropy sources in cloudcomputers: random number generation on cloud hosts. In
Computer Network Security, pages 286–298. Springer, 2012.

[27] A. Shah.
About random numbers and virtual
machines,2013.
http://log.amitshah.net/2013/01/
about-random-numbers-and-virtual-machines/.
[28] A. Stamos, A. Becherer, and N. Wilcox. Cloud computing
models and vulnerabilities: Raining on the trendy new parade.
BlackHat USA, 2009.
[29] M. A. Stephens. Use of the Kolmogorov-Smirnov, CramérVon Mises and related statistics without extensive tables.
Journal of the Royal Statistical Society. Series B (Methodological), pages 115–122, 1970.
[30] C. J. Thompson, I. J. De Silva, M. D. Manner, M. T. Foley,
and P. E. Baxter. Randomness exposed–an attack on hosted
virtual machines, 2011.
[31] R. S. Winternitz. A secure one-way hash function built fromdes. In IEEE Symposium on Security and Privacy, pages 88–
90, 1984.
[32] S. Yilek, E. Rescorla, H. Shacham, B. Enright, and S. Savage.
When private keys are public: results from the 2008 Debian
OpenSSL vulnerability. In SIGCOMM Conference on Internet
Measurement, pages 15–27. ACM, 2009.