This paper was released February 21, 2008 and published in Proc. 2008 USENIX Security Symposium. For the most
recent revision, related source code, and videos of demonstration attacks, visit http://citp.princeton.edu/memory.
Lest We Remember: Cold Boot Attacks on Encryption Keys
J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul,
Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten
Princeton University
Electronic Frontier Foundation
Wind River Systems
{jhalderm, nadiah, wclarkso, jcalandr, ajfeldma, felten}@cs.princeton.edu
schoen@eff.org, wpaul@windriver.com, jacob@appelbaum.net
Abstract
memory. They pose a particular threat to laptop users who
rely on disk encryption products, since an adversary who
Contrary to popular assumption, DRAMs used in most
steals a laptop while an encrypted disk is mounted could
modern computers retain their contents for several sec-
employ our attacks to access the contents, even if the com-
onds after power is lost, even at room temperature and
puter is screen-locked or suspended. We demonstrate this
even if removed from a motherboard. Although DRAMs
risk by defeating several popular disk encryption systems,
become less reliable when they are not refreshed, they
including BitLocker, TrueCrypt, and FileVault, and we
are not immediately erased, and their contents persist
expect many similar products are also vulnerable.
sufficiently for malicious (or forensic) acquisition of us-
While our principal focus is disk encryption, any sen-
able full-system memory images. We show that this phe-
sitive data present in memory when an attacker gains
nomenon limits the ability of an operating system to pro-
physical access to the system could be subject to attack.
tect cryptographic key material from an attacker with
Many other security systems are probably vulnerable. For
physical access. We use cold reboots to mount successful
example, we found that Mac OS X leaves the user's lo-
attacks on popular disk encryption systems using no spe-
gin password in memory, where we were able to recover
cial devices or materials. We experimentally characterize
it, and we have constructed attacks for extracting RSA
the extent and predictability of memory remanence and
private keys from Apache web servers.
report that remanence times can be increased dramatically
with simple cooling techniques. We offer new algorithms
As we discuss in Section 2, certain segments of the
for finding cryptographic keys in memory images and for
computer security and semiconductor physics communi-
correcting errors caused by bit decay. Though we discuss
ties have been conscious of DRAM remanence effects
several strategies for partially mitigating these risks, we
for some time, though strikingly little about them has
know of no simple remedy that would eliminate them.
been published. As a result, many who design, deploy, or
rely on secure systems are unaware of these phenomena
or the ease with which they can be exploited. To our
1
Introduction
knowledge, ours is the first comprehensive study of their
security consequences.
Most security experts assume that a computer's memory
is erased almost immediately when it loses power, or that
Highlights and roadmap
In Section 3, we describe
whatever data remains is difficult to retrieve without spe-
experiments that we conducted to characterize DRAM
cialized equipment. We show that these assumptions are
remanence in a variety of memory technologies. Contrary
incorrect. Ordinary DRAMs typically lose their contents
to the expectation that DRAM loses its state quickly if
gradually over a period of seconds, even at standard oper-
it is not regularly refreshed, we found that most DRAM
ating temperatures and even if the chips are removed from
modules retained much of their state without refresh, and
the motherboard, and data will persist for minutes or even
even without power, for periods lasting thousands of re-
hours if the chips are kept at low temperatures. Residual
fresh intervals. At normal operating temperatures, we
data can be recovered using simple, nondestructive tech-
generally saw a low rate of bit corruption for several sec-
niques that require only momentary physical access to the
onds, followed by a period of rapid decay. Newer memory
machine.
technologies, which use higher circuit densities, tended
We present a suite of attacks that exploit DRAM re-
to decay more quickly than older ones. In most cases, we
manence effects to recover cryptographic keys held in
observed that almost all bits decayed at predictable times

---

and to predictable "ground states" rather than to random
struct nearly any 128-bit AES key within a few seconds.
values.
We have devised reconstruction techniques for AES, DES,
We also confirmed that decay rates vary dramatically
and RSA keys, and we expect that similar approaches
with temperature. We obtained surface temperatures of
will be possible for other cryptosystems. The vulnerabil-
approximately -50 C with a simple cooling technique:
ity of precomputation products to such attacks suggests
discharging inverted cans of "canned air" duster spray
an interesting trade-off between efficiency and security.
directly onto the chips. At these temperatures, we typi-
In Section 6, we present fully automatic techniques for
cally found that fewer than 1% of bits decayed even after
identifying such keys from memory images, even in the
10 minutes without power. To test the limits of this ef-
presence of bit errors.
fect, we submerged DRAM modules in liquid nitrogen
We demonstrate the effectiveness of these attacks in
(ca. -196 C) and saw decay of only 0.17% after 60 min-
Section 7 by attacking several widely used disk encryption
utes out of the computer.
products, including BitLocker, TrueCrypt, and FileVault.
In Section 4, we present several attacks that exploit
We have developed a fully automated demonstration at-
DRAM remanence to acquire memory images from which
tack against BitLocker that allows access to the contents
keys and other sensitive data can be extracted. Our attacks
of the disk with only a few minutes of computation. No-
come in three variants, of increasing resistance to coun-
tably, using BitLocker with a Trusted Platform Module
termeasures. The simplest is to reboot the machine and
(TPM) sometimes makes it less secure, allowing an at-
launch a custom kernel with a small memory footprint
tacker to gain access to the data even if the machine is
that gives the adversary access to the retained memory. A
stolen while it is completely powered off.
more advanced attack briefly cuts power to the machine,
It may be difficult to prevent all the attacks that we de-
then restores power and boots a custom kernel; this de-
scribe even with significant changes to the way encryption
prives the operating system of any opportunity to scrub
products are designed and used, but in practice there are a
memory before shutting down. An even stronger attack
number of safeguards that can provide partial resistance.
cuts the power and then transplants the DRAM modules
In Section 8, we suggest a variety of mitigation strategies
to a second PC prepared by the attacker, which extracts
ranging from methods that average users can apply to-
their state. This attack additionally deprives the original
day to long-term software and hardware changes. Each
BIOS and PC hardware of any chance to clear the memory
remedy has limitations and trade-offs. As we conclude
on boot. We have implemented imaging kernels for use
in Section 9, it seems there is no simple fix for DRAM
with network booting or a USB drive.
remanence vulnerabilities.
If the attacker is forced to cut power to the memory for
too long, the data will become corrupted. We propose
Online resources
A video demonstration of our attacks
three methods for reducing corruption and for correct-
and source code for some of our tools are available at
ing errors in recovered encryption keys. The first is to
http://citp.princeton.edu/memory.
cool the memory chips prior to cutting power, which dra-
matically reduces the error rate. The second is to apply
algorithms we have developed for correcting errors in
2
Previous Work
private and symmetric keys. The third is to replicate the
physical conditions under which the data was recovered
Previous researchers have suggested that data in DRAM
and experimentally measure the decay properties of each
might survive reboots, and that this fact might have se-
memory location; with this information, the attacker can
curity implications. To our knowledge, however, ours is
conduct an accelerated error correction procedure. These
the first security study to focus on this phenomenon, the
techniques can be used alone or in combination.
first to consider how to reconstruct symmetric keys in the
In Section 5, we explore the second error correction
presence of errors, the first to apply such attacks to real
method: novel algorithms that can reconstruct crypto-
disk encryption systems, and the first to offer a systematic
graphic keys even with relatively high bit-error rates.
discussion of countermeasures.
Rather than attacking the key directly, our methods con-
We owe the suggestion that modern DRAM contents
sider values derived from it, such as key schedules, that
can survive cold boot to Pettersson [33], who seems to
provide a higher degree of redundancy. For performance
have obtained it from Chow, Pfaff, Garfinkel, and Rosen-
reasons, many applications precompute these values and
blum [13]. Pettersson suggested that remanence across
keep them in memory for as long as the key itself is in
cold boot could be used to acquire forensic memory im-
use. To reconstruct an AES key, for example, we treat the
ages and obtain cryptographic keys, although he did not
decayed key schedule as an error correcting code and find
experiment with the possibility. Chow et al. discovered
the most likely values for the original key. Applying this
this property in the course of an experiment on data life-
method to keys with 10% of bits decayed, we can recon-
time in running systems. While they did not exploit the
2

---

Memory Type
Chip Maker
Memory Density
Make/Model
Year
A
SDRAM
Infineon
128Mb
Dell Dimension 4100
1999
B
DDR
Samsung
512Mb
Toshiba Portege
2001
C
DDR
Micron
256Mb
Dell Inspiron 5100
2003
D
DDR2
Infineon
512Mb
IBM T43p
2006
E
DDR2
Elpida
512Mb
IBM x60
2007
F
DDR2
Samsung
512Mb
Lenovo 3000 N100
2007
Table 1: Test systems we used in our experiments
property, they remark on the negative security implica-
momentarily. These effects do not result from the kind
tions of relying on a reboot to clear memory.
of physical changes that Gutmann described, but rather
In a recent presentation, MacIver [31] stated that Mi-
from the capacitance of DRAM cells.
crosoft considered memory remanence attacks in design-
Other methods for obtaining memory images from live
ing its BitLocker disk encryption system. He acknowl-
systems include using privileged software running un-
edged that BitLocker is vulnerable to having keys ex-
der the host operating system [43], or using DMA trans-
tracted by cold-booting a machine when it is used in
fer on an external bus [19], such as PCI [12], mini-PCI,
"basic mode" (where the encrypted disk is mounted auto-
Firewire [8, 15, 16], or PC Card. Unlike these techniques,
matically without requiring a user to enter any secrets),
our attacks do not require access to a privileged account
but he asserted that BitLocker is not vulnerable in "ad-
on the target system, they do not require specialized hard-
vanced modes" (where a user must provide key material
ware, and they are resistant to operating system counter-
to access the volume). He also discussed cooling mem-
measures.
ory with dry ice to extend the retention time. MacIver
apparently has not published on this subject.
It has been known since the 1970s that DRAM cell
3
Characterizing Remanence Effects
contents survive to some extent even at room temperature
and that retention times can be increased by cooling. In
A DRAM cell is essentially a capacitor. Each cell encodes
a 1978 experiment [29], a DRAM showed no data loss
a single bit by either charging or not charging one of the
for a full week without refresh when cooled with liquid
capacitor's conductors. The other conductor is hard-wired
nitrogen. Anderson [2] briefly discusses remanence in his
either to power or to ground, depending on the cell's
2001 book:
address within the chip [37, 23].
[A]n attacker can . . . exploit . . . memory re-
Over time, charge will leak out of the capacitor, and the
manence, the fact that many kinds of computer
cell will lose its state or, more precisely, it will decay to its
memory retain some trace of data that have been
ground state, either zero or one depending on whether the
stored there. . . . [M]odern RAM chips exhibit
fixed conductor of the capacitor is hard-wired to ground or
a wide variety of memory remanence behaviors,
power. To forestall this decay, the cell must be refreshed,
with the worst of them keeping data for several
meaning that the capacitor must be re-charged to hold
seconds even at room temperature. . .
its value. Specifications for DRAM chips give a refresh
time, which is the maximum interval that is supposed to
Anderson cites Skorobogatov [40], who found signifi-
pass before a cell is refreshed. The standard refresh time
cant data retention times with static RAMs at room tem-
(usually on the order of milliseconds) is meant to achieve
perature. Our results for modern DRAMs show even
extremely high reliability for normal computer operations
longer retention in some cases.
where even infrequent bit errors could cause serious prob-
Anderson's main focus is on "burn-in" effects that oc-
lems; however, a failure to refresh any individual DRAM
cur when data is stored in RAM for an extended period.
cell within this time has only a tiny probability of actually
Gutmann [22, 23] also examines "burn-in," which he at-
destroying the cell's contents.
tributes to physical changes that occur in semiconductor
We conducted a series of experiments to characterize
memories when the same value is stored in a cell for
DRAM remanence effects and better understand the secu-
a long time. Accordingly, Gutmann suggests that keys
rity properties of modern memories. We performed trials
should not be stored in one memory location for longer
using PC systems with different memory technologies, as
than several minutes. Our findings concern a different
shown in Table 1. These systems included models from
phenomenon: the remanence effects we have studied oc-
several manufacturers and ranged in age from 9 years to
cur in modern DRAMs even when data is stored only
6 months.
3

---

3.1
Decay at operating temperature
50

Using a modified version of our PXE memory imaging
program (see Section 4.1), we filled representative mem-
45
ory regions with a pseudorandom pattern. We read back
40
these memory regions after varying periods of time with-
35
out refresh and under different temperature conditions,
30
and measured the error rate of each sample. The error
rate is the number of bit errors in each sample (the Ham-
25
% Decay
ming distance from the pattern we had written) divided by
20
the total number of bits we measured. Since our pseudo-
15
random test pattern contained roughly equal numbers of
A Data
10
A Fit
zeros and ones, we would expect fully decayed memory
C Data
5
to have an error rate of approximately 50% .
C Fit
Our first tests measured the decay rate of each mem-
0 0
50
100
150
Seconds without Power
ory module under normal operating temperature, which
ranged from 25.5 C to 44.1 C, depending on the ma-
chine (see Figures 1, 2, and 3). We found that the dimen-
Figure 1: Machines A and C
sions of the decay curves varied considerably between
machines, with the fastest exhibiting complete data loss
50

in approximately 2.5 seconds and the slowest taking an
average of 35 seconds. However, the decay curves all dis-
45
play a similar shape, with an initial period of slow decay,
40
followed by an intermediate period of rapid decay, and
35
then a final period of slow decay.
30
We calculated best fit curves to the data using the logis-
25
tic function because MOSFETs, the basic components of
% Decay
a DRAM cell, exhibit a logistic decay curve. We found
20
that machines using newer memory technologies tend to
15
exhibit a shorter time to total decay than machines using
B Data
10
B Fit
older memory technologies, but even the shorter times
F Data
5
are long enough to facilitate most of our attacks. We as-
F Fit
0
cribe this trend to the increasing density of the DRAM
0
1
2
3
4
5
6
7
8
9
10
Seconds without Power
cells as the technology improves; in general, memory
with higher densities have a shorter window where data
is recoverable. While this trend might make DRAM re-
Figure 2: Machines B and F
tention attacks more difficult in the future, manufacturers
also generally seek to increase retention times, because
50

DRAMs with long retention require less frequent refresh
and have lower power consumption.
45
40
3.2
Decay at reduced temperature
35
It has long been known that low temperatures can signifi-
30
cantly increase memory devices' retention times [29, 2,
25
% Decay
46, 23, 41, 40]. To measure this effect, we performed a
20
second series of tests using machines A-D.
15
In each trial, we loaded a pseudorandom test pattern
D Data
10
into memory, and, with the computer running, cooled
D Fit
E Data
the memory module to approximately -50 C. We then
5
E Fit
powered off the machine and maintained this temperature
0 0
0.5
1
1.5
2
2.5
until power was restored. We achieved these temperatures
Seconds without Power
using commonly available "canned air" duster products
(see Section 4.2), which we discharged, with the can
Figure 3: Machines D and E
inverted, directly onto the chips.
4

---

Seconds
Error % at
Error %
pattern. An even smaller number of cells decayed in dif-
w/o power
operating temp.
at -50 C
ferent directions across runs, with varying probabilities.
A
60
41
(no errors)
Apart from their eventual states, the order in which
300
50
0.000095
different cells decayed also appeared to be highly pre-
B
360
50
(no errors)
dictable. At a fixed temperature, each cell seems to decay
600
50
0.000036
after a consistent length of time without power. The rel-
C
120
41
0.00105
ative order in which the cells decayed was largely fixed,
360
42
0.00144
even as the decay times were changed by varying the
D
40
50
0.025
temperature. This may also be a result of manufacturing
80
50
0.18
variations, which result in some cells leaking charge faster
than others.
Table 2: Effect of cooling on error rates
To visualize this effect, we captured degraded memory
images, including those shown in Figure 4, after cutting
As expected, we observed a significantly lower rate
power for intervals ranging from 1 second to 5 minutes,
of decay under these reduced temperatures (see Table 2).
in 1 second increments. We combined the results into a
On all of our sample DRAMs, the decay rates were low
video (available on our web site). Each test interval began
enough that an attacker who cut power for 60 seconds
with the original image freshly loaded into memory. We
would recover 99.9% of bits correctly.
might have expected to see a large amount of variation
As an extreme test of memory cooling, we performed
between frames, but instead, most bits appear stable from
another experiment using liquid nitrogen as an additional
frame to frame, switching values only once, after the
cooling agent. We first cooled the memory module of
cell's decay interval. The video also shows that the decay
Machine A to -50 C using the "canned air" product.
intervals themselves follow higher order patterns, likely
We then cut power to the machine, and quickly removed
related to the physical geometry of the DRAM.
the DRAM module and placed it in a canister of liquid
nitrogen. We kept the memory module submerged in the
liquid nitrogen for 60 minutes, then returned it to the
machine. We measured only 14,000 bit errors within a 1
3.4
BIOS footprints and memory wiping
MB test region (0.17% decay). This suggests that, even
in modern memory modules, data may be recoverable for
Even if memory contents remain intact while power is
hours or days with sufficient cooling.
off, the system BIOS may overwrite portions of memory
when the machine boots. In the systems we tested, the
3.3
Decay patterns and predictability
BIOS overwrote only relatively small fractions of memory
with its own code and data, typically a few megabytes
We observed that the DRAMs we studied tended to decay
concentrated around the bottom of the address space.
in highly nonuniform patterns. While these patterns var-
On many machines, the BIOS can perform a destructive
ied from chip to chip, they were very predictable in most
memory check during its Power-On Self Test (POST).
of the systems we tested. Figure 4 shows the decay in
Most of the machines we examined allowed this test to be
one memory region from Machine A after progressively
disabled or bypassed (sometimes by enabling an option
longer intervals without power.
called "Quick Boot").
There seem to be several components to the decay
patterns. The most prominent is a gradual decay to the
On other machines, mainly high-end desktops and
"ground state" as charge leaks out of the memory cells. In
servers that support ECC memory, we found that the
the DRAM shown in Figure 4, blocks of cells alternate
BIOS cleared memory contents without any override op-
between a ground state of 0 and a ground state of 1, result-
tion. ECC memory must be set to a known state to avoid
ing in the series of horizontal bars. Other DRAM models
spurious errors if memory is read without being initial-
and other regions within this DRAM exhibited different
ized [6], and we believe many ECC-capable systems per-
ground states, depending on how the cells are wired.
form this wiping operation whether or not ECC memory
We observed a small number of cells that deviated from
is installed.
the "ground state" pattern, possibly due to manufacturing
ECC DRAMs are not immune to retention effects, and
variation. In experiments with 20 or 40 runs, a few "ret-
an attacker could transfer them to a non-ECC machine
rograde" cells (typically 0.05% of memory cells, but
that does not wipe its memory on boot. Indeed, ECC
larger in a few devices) always decayed to the opposite
memory could turn out to help the attacker by making
value of the one predicted by the surrounding ground state
DRAM more resistant to bit errors.
5

---

Figure 4: We loaded a bitmap image into memory on Machine A, then cut power for varying lengths of time. After 5
seconds (left), the image is indistinguishable from the original. It gradually becomes more degraded, as shown after
30 seconds, 60 seconds, and 5 minutes.
4
Imaging Residual Memory
connected to the target machine via an Ethernet crossover
cable runs DHCP and TFTP servers as well as a simple
Imaging residual memory contents requires no special
client application for receiving the memory data. We have
equipment. When the system boots, the memory con-
extracted memory images at rates up to 300 Mb/s (around
troller begins refreshing the DRAM, reading and rewriting
30 seconds for a 1 GB RAM) with gigabit Ethernet cards.
each bit value. At this point, the values are fixed, decay
halts, and programs running on the system can read any
USB drives
Alternatively, most PCs can boot from an
data present using normal memory-access instructions.
external USB device such as a USB hard drive or flash
device. We implemented a small (10 KB) plug-in for the
SYSLINUX bootloader [3] that can be booted from an
4.1
Imaging tools
external USB device or a regular hard disk. It saves the
One challenge is that booting the system will necessarily
contents of system RAM into a designated data partition
overwrite some portions of memory. Loading a full oper-
on this device. We succeeded in dumping 1 GB of RAM
ating system would be very destructive. Our approach is
to a flash drive in approximately 4 minutes.
to use tiny special-purpose programs that, when booted
EFI boot
Some recent computers, including all Intel-
from either a warm or cold reset state, produce accurate
based Macintosh computers, implement the Extensible
dumps of memory contents to some external medium.
Firmware Interface (EFI) instead of a PC BIOS. We have
These programs use only trivial amounts of RAM, and
also implemented a memory dumper as an EFI netboot
their memory offsets used can be adjusted to some extent
application. We have achieved memory extraction speeds
to ensure that data structures of interest are unaffected.
up to 136 Mb/s, and we expect it will be possible to
Our memory-imaging tools make use of several differ-
increase this throughput with further optimizations.
ent attack vectors to boot a system and extract the contents
of its memory. For simplicity, each saves memory images
iPods
We have installed memory imaging tools on an
to the medium from which it was booted.
Apple iPod so that it can be used to covertly capture
memory dumps without impacting its functionality as a
PXE network boot
Most modern PCs support net-
music player. This provides a plausible way to conceal
work booting via Intel's Preboot Execution Environment
the attack in the wild.
(PXE) [25], which provides rudimentary startup and net-
work services. We implemented a tiny (9 KB) standalone
application that can be booted via PXE and whose only
4.2
Imaging attacks
function is streaming the contents of system RAM via
a UDP-based protocol. Since PXE provides a universal
An attacker could use imaging tools like ours in a number
API for accessing the underlying network hardware, the
of ways, depending on his level of access to the system
same binary image will work unmodified on any PC sys-
and the countermeasures employed by hardware and soft-
tem with PXE support. In a typical attack setup, a laptop
ware.
6

---

Figure 5: Before powering off the computer, we spray an upside-down canister of multipurpose duster directly onto the
memory chips, cooling them to -50 C. At this temperature, the data will persist for several minutes after power loss
with minimal error, even if we remove the DIMM from the computer.
Simple reboots
The simplest attack is to reboot the
the target machine and place it into the secondary DIMM
machine and configure the BIOS to boot the imaging
slot (in the same machine or another machine), effectively
tool. A warm boot, invoked with the operating system's
remapping the data to be imaged into a different part of
restart procedure, will normally ensure that the memory
the address space.
has no chance to decay, though software will have an
opportunity to wipe sensitive data prior to shutdown. A
cold boot, initiated using the system's restart switch or by
5
Key Reconstruction
briefly removing and restoring power, will result in little
or no decay depending on the memory's retention time.
Our experiments (see Section 3) show that it is possible
Restarting the system in this way denies the operating
to recover memory contents with few bit errors even af-
system and applications any chance to scrub memory
ter cutting power to the system for a brief time, but the
before shutting down.
presence of even a small amount of error complicates
the process of extracting correct cryptographic keys. In
Transferring DRAM modules
Even if an attacker can-
this section we present algorithms for correcting errors
not force a target system to boot memory-imaging tools,
in symmetric and private keys. These algorithms can cor-
or if the target employs countermeasures that erase mem-
rect most errors quickly even in the presence of relatively
ory contents during boot, DIMM modules can be phys-
high bit error probabilities in the range of 5% to 50%,
ically removed and their contents imaged using another
depending on the type of key.
computer selected by the attacker.
A naive approach to key error correction is to brute-
Some memory modules exhibit far faster decay than
force search over keys with a low Hamming distance from
others, but as we discuss in Section 3.2 above, cooling a
the decayed key that was retrieved from memory, but this
module before powering it off can slow decay sufficiently
is computationally burdensome even with a moderate
to allow it to be transferred to another machine with mini-
amount of unidirectional error. As an example, if only
mal decay. Widely-available "canned air" dusters, usually
10% of the ones have decayed to zeros in our memory
containing a compressed fluorohydrocarbon refrigerant,
image, the data recovered from a 256-bit key with an equal
can easily be used for this purpose. When the can is dis-
number of ones and zeroes has an expected Hamming
charged in an inverted position, as shown in Figure 5, it
distance of 12 from the actual key, and the number of
dispenses its contents in liquid form instead of as a gas.
such keys is 128+12 > 256.
12
The rapid drop in pressure inside the can lowers the tem-
Our algorithms achieve significantly better perfor-
perature of the discharge, and the subsequent evaporation
mance by considering data other than the raw form of
of the refrigerant causes a further chilling. By spraying
the key. Most encryption programs speed up computation
the contents directly onto memory chips, we can cool their
by storing data precomputed from the encryption keys--
surfaces to -50 C and below. If the DRAM is cooled to
for block ciphers, this is most often a key schedule, with
this temperature before power is cut and kept cold, we
subkeys for each round; for RSA, this is an extended form
can achieve nearly lossless data recovery even after the
of the private key which includes the primes p and q and
chip is out of the computer for several minutes.
several other values derived from d. This data contains
Removing the memory modules can also allow the
much more structure than the key itself, and we can use
attacker to image memory in address regions where stan-
this structure to efficiently reconstruct the original key
dards BIOSes load their own code during boot. The at-
even in the presence of errors.
tacker could remove the primary memory module from
These results imply an interesting trade-off between
7

---

efficiency and security. All of the disk encryption systems
For simplicity and generality, we will analyze the algo-
we studied (see Section 7) precompute key schedules and
rithms assuming no knowledge of this decay order.
keep them in memory for as long as the encrypted disk is
mounted. While this practice saves some computation for
5.1
Reconstructing DES keys
each disk block that needs to be encrypted or decrypted,
we find that it greatly simplifies key recovery attacks.
We first apply these methods to develop an error correc-
Our approach to key reconstruction has the advantage
tion technique for DES. The DES key schedule algorithm
that it is completely self-contained, in that we can recover
produces 16 subkeys, each a permutation of a 48-bit sub-
the key without having to test the decryption of cipher-
set of bits from the original 56-bit key. Every bit from the
text. The data derived from the key, and not the decoded
original key is repeated in about 14 of the 16 subkeys.
plaintext, provides a certificate of the likelihood that we
In coding theory terms, we can treat the DES key sched-
have found the correct key.
ule as a repetition code: the message is a single bit, and
We have found it useful to adopt terminology from
the corresponding codeword is a sequence of n copies of
coding theory. We may imagine that the expanded key
this bit. If 0 = 1 < 1 , the optimal decoding of such an
2
schedule forms a sort of error correcting code for the key,
n-bit codeword is 0 if more than n/2 of the recovered bits
and the problem of reconstructing a key from memory
are 0, and 1 otherwise. For 0 = 1, the optimal decod-
may be recast as the problem of finding the closest code
ing is 0 if more than nr of the recovered bits are 0 and 1
word (valid key schedule) to the data once it has been
otherwise, where
passed through a channel that has introduced bit errors.
log(1 - 0) - log 1
r =
.
Modeling the decay
Our experiments showed that al-
log(1 - 0) + log(1 - 1) - log 1 - log 0
most all memory bits tend to decay to predictable ground
states, with only a tiny fraction flipping in the opposite
For 0 = .1 and 1 = .001 (that is, we are in a block
direction. In describing our algorithms, we assume, for
with ground state 0), r = .75 and this approach will fail to
simplicity, that all bits decay to the same ground state.
correctly decode a bit only if more than 3 of the 14 copies
(They can be implemented without this requirement, as-
of a 0 decay to a 1, or more than 11 of the 14 copies of
suming that the ground state of each bit is known.)
a 1 decay to 0. The probability of this event is less than
If we assume we have no knowledge of the decay pat-
10-9. Applying the union bound, the probability that any
terns other than the ground state, we can model the de-
of the 56 key bits will be incorrectly decoded is at most
cay with the binary asymmetric channel, in which the
56 x 10-9 < 6 x 10-8; even at 50% error, the probability
probability of a 1 flipping to 0 is some fixed
that the key can be correctly decoded without resorting to
0 and the
probability of a 0 flipping to a 1 is some fixed
brute force search is more than 98%.
1.
In practice, the probability of decaying to the ground
This technique can be trivially extended to correct er-
state approaches 1 as time goes on, while the probabil-
rors in Triple DES keys. Since Triple DES applies the
ity of flipping in the opposite direction remains relatively
same key schedule algorithm to two or three 56-bit key
constant and tiny (less than 0.1% in our tests). The ground
components (depending on the version of Triple DES),
state decay probability can be approximated from recov-
the probability of correctly decoding each key bit is the
ered key data by counting the fraction of 1s and 0s, as-
same as for regular DES. With a decay rate of 0 = .5 and
suming that the original key data contained roughly equal
probability 1 = .001 of bit flips in the opposite direction,
proportions of each value.
we can correctly decode a 112-bit Triple DES key with at
We also observed that bits tended to decay in a pre-
least 97% probability and a 168-bit key with at least 96%
dictable order that could be learned over a series of timed
probability.
decay trials, although the actual order of decay appeared
fairly random with respect to location. An attacker with
5.2
Reconstructing AES keys
the time and physical access to run such a series of tests
could easily adapt any of the approaches in this section to
The AES key schedule has a more complex structure than
take this order into account and improve the performance
the DES key schedule, but we can still use it to efficiently
of the error-correction. Ideally such tests would be able to
reconstruct a key in the presence of errors.
replicate the conditions of the memory extraction exactly,
A seemingly reasonable approach to this problem
but knowledge of the decay order combined with an esti-
would be to search keys in order of distance to the recov-
mate of the fraction of bit flips is enough to give a very
ered key and output any key whose schedule is sufficiently
good estimate of an individual decay probability of each
close to the recovered schedule. Our implementation of
bit. This probability can be used in our reconstruction
this algorithm took twenty minutes to search 109 candi-
algorithms to prioritize guesses.
date keys in order to reconstruct a key in which 7 zeros
8

---

round key 1
candidate contains a value for each slice of bytes. We
consider the candidates in order of decreasing total like-
lihood as calculated above. For each candidate key we
Core




consider, we calculate the expanded key schedule and ask
if the likelihood of that expanded key schedule decaying
round key 2
to our recovered key schedule is sufficiently high. If so,
then we output the corresponding key as a guess.
When one of 0 or 1 is very small, this algorithm will
Figure 6: In the 128-bit AES key schedule, three bytes of
almost certainly output a unique guess for the key. To see
each round key are entirely determined by four bytes of
this, observe that a single bit flipped in the key results in
the preceding round key.
a cascade of bit flips through the key schedule, half of
which are likely to flip in the "wrong" direction.
had flipped to ones. At this rate it would take ten days to
Our implementation of this algorithm is able to re-
reconstruct a key with 11 bits flipped.
construct keys with 15% error (that is, 0 = .15 and
We can do significantly better by taking advantage of
1 = .001) in a fraction of a second, and about half of
the structure of the AES key schedule. Instead of trying
keys with 30% error within 30 seconds.
to correct an entire key at once, we can examine a smaller
This idea can be extended to 256-bit keys by dividing
set of bytes at a time. The high amount of linearity in the
the words of the key into two sections--words 1-3 and 8,
key schedule is what permits this separability--we can
and words 4-7, for example--then comparing the words
take advantage of pieces that are small enough to brute
of the third and fourth round keys generated by the bytes
force optimal decodings for, yet large enough that these
of these words and combining the result into candidate
decodings are useful to reconstruct the overall key. Once
round keys to check.
we have a list of possible decodings for these smaller
pieces of the key in order of likelihood, we can combine
5.3
Reconstructing tweak keys
them into a full key to check against the key schedule.
Since each of the decoding steps is quite fast, the run-
The same methods can be applied to reconstruct keys for
ning time of the entire algorithm is ultimately limited
tweakable encryption modes [30], which are commonly
by the number of combinations we need to check. The
used in disk encryption systems.
number of combinations is still roughly exponential in the
number of errors, but it is a vast improvement over brute
LRW
LRW augments a block cipher E (and key K1) by
force searching and is practical in many realistic cases.
computing a "tweak" X for each data block and encrypt-
ing the block using the formula EK (P X) X. A tweak
1
Overview of the algorithm
For 128-bit keys, an AES
key K2 is used to compute the tweak, X = K2 I, where
key expansion consists of 11 four-word (128-bit) round
I is the logical block identifier. The operations and
keys. The first round key is equal to the key itself. Each
are performed in the finite field GF(2128).
remaining word of the key schedule is generated either
In order to speed tweak computations, implementations
by XORing two words of the key schedule together, or by
commonly precompute multiplication tables of the values
performing the key schedule core (in which the bytes of a
K2xi mod P, where x is the primitive element and P is an
word are rotated and each byte is mapped to a new value)
irreducible polynomial over GF(2128) [26]. In practice,
on a word of the key schedule and XORing the result with
Qx mod P is computed by shifting the bits of Q left by
another word of the key schedule.
one and possibly XORing with P.
Consider a "slice" of the first two round keys consisting
Given a value K2xi, we can recover nearly all of the
of byte i from words 1-3 of the first two round keys, and
bits of K2 simply by shifting right by i. The number of
byte i - 1 from word 4 of the first round key (as shown
bits lost depends on i and the nonzero elements of P. An
in Figure 6). This slice is 7 bytes long, but is uniquely
entire multiplication table will contain many copies of
determined by the four bytes from the key. In theory,
nearly all of the bits of K2, allowing us to reconstruct the
there are still 232 possibilities to examine for each slice,
key in much the same way as the DES key schedule.
but we can do quite well by examining them in order of
As an example, we apply this method to reconstruct the
distance to the recovered key. For each possible set of 4
LRW key used by the TrueCrypt 4 disk encryption system.
key bytes, we generate the relevant three bytes of the next
TrueCrypt 4 precomputes a 4048-byte multiplication table
round key and calculate the probability, given estimates
consisting of 16 blocks of 16 lines of 4 words of 4 bytes
of 0 and 1, that these seven bytes might have decayed
each. Line 0 of block 14 contains the tweak key.
to the corresponding bytes of the recovered round keys.
The multiplication table is generated line by line from
Now we proceed to guess candidate keys, where a
the LRW key by iteratively applying the shift-and-XOR
9

---

multiply function to generate four new values, and then
Combined with a few heuristics--for example, choose
XORing all combinations of these four values to create
the most likely state first, prune nodes by bounds on the
16 more lines of the table. The shift-and-XOR operation
solution, and iteratively increase the bit flips allowed--
is performed 64 times to generate the table, using the
this results in a practical algorithm for reasonable error
irreducible polynomial P = x128 + x7 + x2 + x + 1. For any
rates. This process can likely be improved substantially
of these 64 values, we can shift right i times to recover
using additional data recovered from the private key.
128 - (8 + i) of the bits of K2, and use these recovered
We tested an implementation of the algorithm on a fast
values to reconstruct K2 with high probability.
modern machine. For fifty trials with 1024-bit primes
(2048-bit keys) and = 4%, the median reconstruction
XEX and XTS
For XEX [35] and XTS [24] modes, the
time was 4.5 seconds. The median number of nodes vis-
tweak for block j in sector I is X = EK (I) x j, where
2
ited was 16,499, the mean was 621,707, and the standard
I is encrypted with AES and x is the primitive element
deviation was 2,136,870. For = 6%, reconstruction re-
of GF(2128). Assuming the key schedule for K2 is kept
quired a median of 2.5 minutes, or 227,763 nodes visited.
in memory, we can use the AES key reconstruction tech-
For 512-bit primes and = 10%, reconstruction re-
niques to reconstruct the tweak key.
quired a median of 1 minute, or 188,702 nodes visited.
For larger error rates, we can attempt to reconstruct
5.4
Reconstructing RSA private keys
only the first n/4 bits of the key using this process and
use the lattice techniques to reconstruct the rest of the
An RSA public key consists of the modulus N and the
key; these computations generally take several hours in
public exponent e, while the private key consists of the
practice. For a 1024-bit RSA key, we would need to
private exponent d and several optional values: prime fac-
recover 256 bits of a factor. The expected depth of the
tors p and q of N, d mod (p - 1), d mod (q - 1), and
tree from our branching reconstruction process would be
q-1 mod p. Given N and e, any of the private values is
( 1 +
2
)2256 (assuming an even distribution of 0s and 1s)
sufficient to generate the others using the Chinese remain-
and the expected fraction of branches that would need to
der theorem and greatest common divisor algorithms. In
be examined is 1/2 + 2
.
practice, RSA implementations store some or all optional
values to speed up computation.
6
Identifying Keys in Memory
There have been a number of results on efficiently re-
constructing RSA private keys given a fraction of the bits
Extracting encryption keys from memory images requires
of private key data. Let n = lg N. N can be factored in
a mechanism for locating the target keys. A simple ap-
polynomial time given the n/4 least significant bits of p
proach is to test every sequence of bytes to see whether it
(Coppersmith [14]), given the n/4 least significant bits of
correctly decrypts some known plaintext. Applying this
d (Boneh, Durfee, and Frankel [9]), or given the n/4 least
method to a 1 GB memory image known to contain a 128-
significant bits of d mod (p - 1) (Blomer and May [7]).
bit symmetric key aligned to some 4-byte machine word
These previous results are all based on Coppersmith's
implies at most 228 possible key values. However, this is
method of finding bounded solutions to polynomial equa-
only the case if the memory image is perfectly accurate.
tions using lattice basis reduction; the number of contigu-
If there are bit errors in the portion of memory containing
ous bits recovered from the most or least significant bits of
the key, the search quickly becomes intractable.
the private key data determines the additive error tolerated
We have developed fully automatic techniques for locat-
in the solution. In our case, the errors may be distributed
ing symmetric encryption keys in memory images, even
across all bits of the key data, so we are searching for
in the presence of bit errors. Our approach is similar to
solutions with low Hamming weight, and these previous
the one we used to correct key bit errors in Section 5. We
approaches do not seem to be directly applicable.
target the key schedule instead of the key itself, searching
Given the public modulus N and the values
p and
q
for blocks of memory that satisfy (or are close to satisfy-
recovered from memory, we can deduce values for the
ing) the combinatorial properties of a valid key schedule.
original p and q by iteratively reconstructing them from
Using these methods we have been able to recover keys
the least-significant bits. For unidirectional decay with
from closed-source encryption programs without having
probability , bits pi and qi are uniquely determined by
to disassemble them and reconstruct their key data struc-
Ni and our guesses for the i - 1 lower-order bits of p and q
tures, and we have even recovered partial key schedules
(observe that p0 = q0 = 1), except in the case when
pi and
that had been overwritten by another program when the

qi are both in the ground state. This yields a branching
memory was reallocated.
(
process with expected degree 3+ )2 . If decay is not
Although previous approaches to key recovery do not
8
unidirectional, we may use the estimated probabilities to
require a scheduled key to be present in memory, they
weight the branches at each bit.
have other practical drawbacks that limit their usefulness
10

---

Document Outline

• Introduction
• Previous Work
• Characterizing Remanence Effects
  • Decay at operating temperature
  • Decay at reduced temperature
  • Decay patterns and predictability
  • BIOS footprints and memory wiping
• Imaging Residual Memory
  • Imaging tools
  • Imaging attacks
• Key Reconstruction
  • Reconstructing DES keys
  • Reconstructing AES keys
  • Reconstructing tweak keys
  • Reconstructing RSA private keys
• Identifying Keys in Memory
  • Identifying AES keys
  • Identifying RSA keys
• Attacking Encrypted Disks
• Countermeasures and their Limitations
• Conclusions

---