the bits in the key schedule are in error, the probability that
we can correctly reconstruct the key without resorting to a
brute force search is more than 98%.
4. 2. Reconstructing aes keys
AES is a more modern cipher than DES, and it uses a key
schedule with a more complex structure, but nevertheless
we can efficiently reconstruct keys. For 128-bit keys, the AES
key schedule consists of 11 round keys, each made up of four
32-bit words. The first round key is equal to the key itself.
Each subsequent word of the key schedule is generated either
by XORing two earlier words, or by performing an operation
called the key schedule core (in which the bytes of a word are
rotated and each byte is mapped to a new value) on an earlier
word and XORing the result with another earlier word.
Instead of trying to correct an entire key at once, we can
examine a smaller set of the bits at a time and then combine
the results. This separability is enabled by the high amount
of linearity in the key schedule. Consider a “slice” of the first
two round keys consisting of byte i from words 1 to 3 of the
first two round keys, and byte i − 1 from word 4 of the first
round key (see Figure 6). This slice is 7 bytes long, but it is
uniquely determined by the 4 bytes from the first round key.
Our algorithm exploits this fact as follows. For each possible set of 4 key bytes, we generate the relevant 3 bytes of
the next round key, and we order these possibilities by the
likelihood that these 7 bytes might have decayed to the corresponding bytes extracted from memory. Now we may recombine four slices into a candidate key, in order of decreasing
likelihood. For each candidate key, we calculate the key
schedule. If the likelihood of this key schedule decaying to
the bytes we extracted from memory is sufficiently high, we
output the corresponding key.
When the decay is largely unidirectional, this algorithm
will almost certainly output a unique guess for the key. This
is because a single flipped bit in the key results in a cascade
of bit flips through the key schedule, half of which are likely
to flip in the “wrong” direction.
Our implementation of this algorithm is able to reconstruct keys with 7% of the bits decayed in a fraction of a second. It succeeds within 30 s for about half of keys with 15%
of bits decayed.
We have extended this idea to 256-bit AES keys and to
other ciphers. See the full paper for details.
figure 6: error correction for aes keys. in the aes-128 key schedule,
4 bytes from each round key completely determine 3 bytes of the
next round key, as shown here. our error correction algorithm
“slices” the key into four groups of bytes with this property. it
computes a list of likely candidate values for each slice, then
checks each combination to see if it is a plausible key.
Round Key 1
Round Key 2
4. 3. Reconstructing Rsa private keys
An RSA public key consists of the modulus N and the public
exponent e, while the private key consists of the private exponent d and several optional values: prime factors p and q of
N, d mod (p − 1), d mod (q − 1), and q− 1 mod p. Given N and e,
any of the private values is sufficient to efficiently generate
the others. In practice, RSA implementations store some or
all of these values to speed computation.
In this case, the structure of the key information is the
mathematical relationship between the fields of the public
and private key. It is possible to iteratively enumerate potential RSA private keys and prune those that do not satisfy
these relationships. Subsequent to our initial publication,
Heninger and Shacham11 showed that this leads to an algorithm that is able to recover in seconds an RSA key with all
optional fields when only 27% of the bits are known.
5. iDentif Ying ke Ys in memoRY
After extracting the memory from a running system, an
attacker needs some way to locate the cryptographic keys.
This is like finding a needle in a haystack, since the keys
might occupy only tens of bytes out of gigabytes of data.
Simple approaches, such as attempting decryption using
every block of memory as the key, are intractable if the memory contains even a small amount of decay.
We have developed fully automatic techniques for locating encryption keys in memory images, even in the presence
of errors. We target the key schedule instead of the key itself,
searching for blocks of memory that satisfy the properties of
a valid key schedule.
Although previous approaches to key recovery do not
require a key schedule to be present in memory, they have
other practical drawbacks that limit their usefulness for our
purposes. Shamir and van Someren16 conjecture that keys
have higher entropy than the other contents of memory and
claim that they should be distinguishable by a simple visual
test. However, even perfect copies of memory often contain
large blocks of random-looking data (e.g., compressed files).
Pettersson15 suggests locating program data structures containing key material based on the range of likely values for
each field. This approach requires the manual derivation of
search heuristics for each cryptographic application, and it
is not robust to memory errors.
We propose the following algorithm for locating scheduled AES keys in extracted memory:
1. Iteratethrougheachbyteofmemory. Treatthataddress
as the start of an AES key schedule.
2. Calculate the Hamming distance between each word
in the potential key schedule and the value that would
have been generated from the surrounding words in a
real, undecayed key schedule.
3. If the sum of the Hamming distances is sufficiently
low, the region is close to a correct key schedule; output the key.
We implemented this algorithm for 128- and 256-bit AES
keys in an application called keyfind. The program receives
extracted memory and outputs a list of likely keys. It assumes