According to the article "Lest We Remember: Cold Boot Attacks on Encryption Keys" there is a quick and dirty entropy test that can help to find possible AES Key Schedules in memory dumps. Although there are references to this algorithm in blogs of other famouse cryptographers (for example, this post), I haven't been able to find any explanation why it works and why this algorithm is correct. Is there anybody who can provide me with a proof of correctness of this entropy test or can just explain me why it actually works?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ For a very graphic illustration of a cold boot attack, see there $\endgroup$– fgrieu ♦Apr 1, 2014 at 16:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The way you worded the question is misleading, as the entropy test is performed AFTER they have extracted an AES key from memory. The test is used to confirm whether it is a likely encryption key or an AES key used for benchmarking or algorithm verification.
The actual procedure involves cycling through the entire memory space, and examining each block of memory that could be the size of a computed key schedule, which may look daunting, but is actually quite fast, due to the simplicity of the key schedule. They cycle through the memory space in word increments and compute the first iteration of the key schedule. If it matches the next words in memory, the entire key schedule is performed and compared. This is about 134 million iterations in total on a 4GB memory space, which only takes a few minutes; it is especially if the testing system has AESNI instructions on multiple cores, the search may only take seconds. The full key schedule is 10 iterations for a 128-bit key.
Update:
It looks like they used an automated entropy test to eliminate memory blocks before the final (manual) entropy analysis of the key. This is done by cycling through memory blocks and counting duplicates. If any one byte value comprises 5% or more of the block, it is flagged as non-key. The block search size is 11 round keys or 176 bytes. This is faster than computing the key schedule in their code, but slower if you have code with AESNI instructions (3rd party code to perform the same search).
The only time this becomes slow is when there is memory corruption, such as in a cold boot attack. In that case, the missing bits need to be extrapolated, and a slower algorithm needs to be used to find candidate keys.
The key schedule only performs 4 operations on the master key, and these can be computed forward and reverse at almost any point in the key schedule. Additionally, 3 of the operations are not done on every word of the key. If memory corruption is present, a 4 word block is selected, and the key schedule is computed in both directions (128-bit key). If there are word matches in either direction, that area will be flagged for reconstruction of the entire key space.
Once AES keys are identified, an entropy analysis is performed to determine if it is a likely key for the application using AES. Then the various combinations of found keys are used with the application until a successful decryption is performed.
answered Mar 9, 2014 at 23:30
-
$\begingroup$
The way you worded the question is misleading, as the entropy test is performed AFTER they have extracted an AES key from memory.I don't think so. Take a look at the function "find_keys" in aeskeyfind. At first they run this simple entropy test. As for the other part of the answer - you are quite right. They use this test not to find but to reject possible false positives. Thank you! $\endgroup$ Mar 11, 2014 at 10:04 -
$\begingroup$ The code I have seen to do the same thing was more recent, and skipped that part of the search (it was not from the authors of the paper). I have updated my answer with how their entropy test eliminates memory blocks $\endgroup$ Mar 11, 2014 at 19:34