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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.