Finding Encryption Keys in Memory
Walkthrough of a few approaches using AES-256
Why this article?
The computer memory (RAM) can be thought of as a storehouse of secrets. These secrets can range from your instant messenger chats, sites visited in incognito mode, or the encryption keys used by programs to protect your data. The purpose of this article is to look at approaches for extracting AES encryption keys from RAM.
Next time you run a tool like bulk_extractor or aes_keyfind, you will have a better understanding of how it works under the hood.
Side Note: For acquiring memory in a Virtual Machine (VM) environment, you can refer to the instructions here for VMWare and VirtualBox. Alternately, tools like DumpIt can also be used.
What’s an AES Key?
Let’s start with some basics. Technically an encryption key is just a set of bits. For example, a 10-bit encryption key might look like 1011101011. The key, along with an encryption algorithm is used to convert plain text into ciphertext.
AES (Advanced Encryption Standard) is an encryption algorithm. It can work with key lengths of 128, 192, or 256 bits. AES is a symmetric algorithm, i.e. the same key can be used to retrieve the plain text back from the ciphertext.
From the operating system’s perspective, the keys must be loaded into the RAM in order to encrypt/decrypt the data. There is no other way. With that said, let’s look at approaches we can take to extract these loaded keys from a memory dump by using AES-256 keys as an example:
Approach 1: Bruteforce the Key
If you haven’t thought about this before, you might ask — why can’t we just try out every possible key? An AES-256 key has, well, 256 bits. The total number of possible keys here is 2²⁵⁶. This number, it seems, works out to 115 quattuorvigintillion (that’s 115 followed by 75 more digits!). To cover even 1% of the possible keys it might take many trillion years. Since we don’t have that kind of time at our disposal we generally don’t try to do this. Instead of bruteforcing the key, it is much wiser to bruteforce the memory regions where the key might be stored.
Approach 2: Bruteforce the Memory
When looking at memory it’s easier to think about it in bytes (rather than bits). An AES-256 key occupies 32-bytes of memory. So we can run through the memory dump one byte at a time (like sliding window) and pull out every possible 32-byte value. One of these values must be the encryption key!
While that is a very correct assumption, think about the number of keys you will generate. If you have 4GB of RAM, then the number of possible keys is 4GB–31 which is around 4.2 billion keys. To store these keys you need 128 GB of space and you will need to test each of these keys with a known ciphertext to see if you get back the plain text. So overall, while this method works, it is not scalable. Here is a simple brute-force Python script if you want to try.
Approach 3: Bruteforce Memory with Entropy checks
Is there a way we can brute-force more efficiently? Yes, we can. If you look at it, encryption keys are expected to be a random set of bytes. For example, this stream of bytes 0200001a000000006c006b3000ffa08e is unlikely to be an encryption key because the byte 00 repeats quite a few times. However, a value like 72031f503f46a08eb90c7a8d6ef7a05a can be a potential key (because it looks quite random).
How do we quantify something “looking random”? One approach is to count the number of distinct bytes. For example, in a 32-byte stream if there are fewer than say 10 distinct bytes then it is unlikely to be a key. A sample implementation is given in this Python script. Alternately, we can also use Shannon Entropy to evaluate the randomness/entropy of a byte stream.
Checking for randomness does reduce the number of keys when brute-forcing, but can leave us with several thousand potential keys. Can we do better?
Approach 4: Use your knowledge of AES to search
In order to go beyond brute-forcing, we need to be better informed about the system we are studying. Let’s start by getting into how AES encryption works under the hood.
AES is a pretty elaborate algorithm and we’ll only look at what’s relevant for us in terms of identifying keys. The AES algorithm consists of a phase called “Key Expansion” where the original key is taken and expanded into a number of Round Keys. In the case of AES-256, there are 15 Round keys generated. Each round key is 128 bits in size and the entire set of 15 round keys is called the Key Schedule.
Let’s take an example of an AES-256 Key: 4a404e635266556a586e3272357538782f4125442a472d4b6150645367566b59. The key schedule or the round keys will be:
15 Round Keys generated for our AES-256 bit key
RoundKey00 : 4a404e635266556a586e327235753878
RoundKey01 : 2f4125442a472d4b6150645367566b59
RoundKey02 : fa3f85e6a859d08cf037e2fec542da86
RoundKey03 : 896d7200a32a5f4bc27a3b18a52c5041
RoundKey04 : 896c06e02135d66cd10234921440ee14
RoundKey05 : 73645afad04e05b112343ea9b7186ee8
RoundKey06 : 20f39d4901c64b25d0c47fb7c48491a3
RoundKey07 : 6f3bdbf0bf75de41ad41e0e81a598e00
RoundKey08 : e3eafeebe22cb5ce32e8ca79f66c5bda
RoundKey09 : 2d6be2a7921e3ce63f5fdc0e2506520e
RoundKey10 : 9cea55d47ec6e01a4c2e2a63ba4271b9
RoundKey11 : d94741f14b597d177406a1195100f317
RoundKey12 : dfe7a505a121451fed0f6f7c574d1ec5
RoundKey13 : 82a43357c9fd4e40bdfbef59ecfb1c4e
RoundKey14 : 907b8acb315acfd4dc55a0a88b18be6dGenerated with AEScalc.jar downloaded from: http://lpb.canb.auug.org.au/adfa/src/AEScalc/index.html
As you can see above RoundKey00 and RoundKey01 are just our AES-256 key split into two halves. The rest of the 13 Round Keys are computed. Since the round keys need to be computed during every encryption/decryption, programs will usually generate the Key Schedule once and reuse it. In other words, the Key Schedule will be available in the program’s memory and we can use it to our benefit to extract valid AES keys. Let’s see what approach we can take:
- Use a sliding window to read 240 bytes from memory (size of the AES-256 key schedule). Check its randomness (as covered in approach 2). If we don’t see at least 10 distinct bytes let’s just discard this and move the sliding window to the next byte.
- Take the first 32-bytes (the supposed AES-256 key) and use it to calculate the round keys on your own. You can do this because the workings of the AES algorithm are publicly available.
- Match the round keys you generated with the values in the input byte stream. Calculating Hamming Distance is a great way to do this. It not only compares but also quantifies the degree of similarity between two byte streams. If there is a match then bingo, you have found an AES key!
The in-memory layout of the Key Schedule will be as shown below:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| AES-256-Key (RoundKeys 00 and 01) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RoundKey02 | RoundKey03 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RoundKey04 | RoundKey05 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RoundKey06 | RoundKey07 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RoundKey08 | RoundKey09 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RoundKey10 | RoundKey11 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RoundKey12 | RoundKey13 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RoundKey14 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Byte layout of AES-256 key schedule in memory.Generated with: https://github.com/luismartingarcia/protocol
Tools such as Bulk Extractor use this logic when scanning for AES keys. This approach is pretty neat but it’s also somewhat slow given the number of times you have to calculate key-schedule and validate it against the memory dump. Reference Python script. Is there even a better way?
Approach 5: Use your knowledge of the Application to search
When applications store AES keys in memory they might also store some metadata along with it. If we know the structure of the metadata then we might use that to look for a key.
Let’s take an example. The Windows operating system has a file encryption feature called EFS (Encrypting File System). EFS runs as a service inside lsass.exe process memory. When you open an EFS encrypted file it loads the file encryption key (FEK) into lsass.exe and stores it with some metadata. The in-memory layout is also documented by Microsoft (albeit in esoteric places). This is what the key structure will look like:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Key Len|Entropy| Algo |Reservd| Key (Variable) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+In-memory byte layout of AES-256 keys as used by Mircosoft's Encrypting File System.
We already know some values here. Note: the in-memory layout of bytes will usually be in little-endian. Let’s look at the key structure:
- Key Length — For AES-256 this is is 32 bytes or in hex 0x20. In memory this value will be stored as:
2000 0000. - Entropy — Same as Key Length.
- Algorithm — The algorithm ID for AES-256 is 0x6610. The in-memory layout will be
1066 0000. - Reserved — This will be all zeroes
0000 0000. - Key — These are the 32-bytes that we need.
So the approach for finding AES-256 EFS keys is — to look for the sequence of bytes 2000 0000 2000 0000 1066 0000 0000 0000. The 32-bytes following this sequence is a key! Example Python script.
This approach will be lightning-fast because you are just doing a byte search across the memory. You can further optimize this by looking only inside the lsass.exe process memory. Overall, this is the best way to identify keys in memory but it also requires you to deeply understand the system that is using these keys.
I found the key, now what?
If you are able to find AES keys then you have crossed a major hurdle to decrypting the data. However, it is not as simple as using the key, opening the door, and just barging in. Or in simpler words: finding the key does not equal successful decryption. You will need to solve a few more problems (which probably deserve their own articles):
- Get a copy of the plain text and the corresponding ciphertext. That is the only way you can know whether a key you have found is valid or not.
- Understand additional details about the algorithm. For AES, you need to figure out things like what is the mode of operation, initialization vector, etc.
- Understand additional details about the application — how it stores data, what assumptions it operates upon etc.
If you are interested, I have a walkthrough video of EFS showing how you can move from getting the key to successfully decrypting a file.
Thanks for reading!