Tuesday, February 26, 2008

Cell Index Translation

Throughout our previous discussions of registry keys, hives, and so on, we have run into the concept of a cell index several times. They appear in kernel memory in places such as the KeyCell member of the _CM_KEY_CONTROL_BLOCK structure; likewise, all of the structures representing portions of the hive itself (_CM_KEY_NODE, _CM_KEY_VALUE, and so on) have members that point to other structures by cell index rather than by virtual address.

The reason for this is that registry hives live two lives: one, as on-disk files, stored in %WINDIR%\system32\config\, and another, as an in-memory structure that the Configuration Manager uses in memory. In the former, cell indices can be thought of essentially as simple offsets from the start of the file; in the latter, however, the situation is more complicated. When registry hives are represented in memory, they must account for the fact that new keys and values may be added at any time. Since space for the hives is allocated out of paged pool, there is no way of guaranteeing that the memory allocated for the hive will continue to be contiguous.

To solve this problem, the Configuration Manager makes use of what Solomon and Russinovich (Windows Internals pp. 203-207) call cell maps. This is done in a very similar way to virtual to physical address translation on x86. Just as different portions of a virtual address on x86 are actually indices into different tables starting with the page directory, each portion of a cell index is an offset into several tables starting at the Storage.Map member of the appropriate _HHIVE.

Cell Index Translation in Memory

As mentioned before, there are several parts to the cell index: the type (1 bit, stable or volatile), the table index (10 bits), the entry index (9 bits), and finally the offset into the block (12 bits). The following diagram illustrates this layout:

1 10 bits 9 bits 12 bits
[V][ Table ][ Entry ][ Offset ]

Or, in terms of masks and shifts:

CI_TYPE_MASK = 0x80000000
CI_TABLE_MASK = 0x7FE00000

To translate a cell index to a virtual address, first start by selecting the appropriate storage map for the hive using the first bit of the cell index. Each cell index can refer to either the stable or volatile map for the hive, stored in the first and second elements of the Storage array of the _HHIVE, respectively. These elements are of type _DUAL and contain several fields:

lkd> dt nt!_DUAL
+0x000 Length : Uint4B
+0x004 Map : Ptr32 _HMAP_DIRECTORY
+0x008 SmallDir : Ptr32 _HMAP_TABLE
+0x00c Guard : Uint4B
+0x010 FreeDisplay : [24] _RTL_BITMAP
+0x0d0 FreeSummary : Uint4B
+0x0d4 FreeBins : _LIST_ENTRY

The one we care about here is the Map member. This plays a role analogous to the page directory in virtual to physical address mapping; it is the first table we will consult when translating an address, and we will always need to be able to locate it if we are to translate any cell index.

The next 10 bits of the cell index encode the table index; this refers to an entry in the _HMAP_DIRECTORY. The _HMAP_DIRECTORY is an array of 1024 (210) pointers to _HMAP_TABLEs; the table index lets us know which of these we want.

Next we have 9 bits that give the entry index, a value that selects a particular entry from the _HMAP_TABLE, which is an array of 512 (29) _HMAP_ENTRY structures. Finally, each _HMAP_ENTRY looks like:

lkd& dt nt!_HMAP_ENTRY
+0x000 BlockAddress : Uint4B
+0x004 BinAddress : Uint4B
+0x008 CmView : Ptr32 _CM_VIEW_OF_FILE
+0x00c MemAlloc : Uint4B

The BlockAddress member will give us the virtual address in memory of the hbin (remember that hives are structured into a series of bins, which in turn contain cells). At this point, we need only add to it offset (the final 12 bits) to get the address of the cell corresponding to the data we're looking for.

The only thing left to do before we can make use of the address we've computed is add 4. Why? As it turns out, the cell index actually points to a DWORD at the beginning of the cell that gives the length of the data. So, for example, the cell index of a key will point to the size of the key, rather than the start of the key itself. While this may be quite helpful in C (since you can just read that many bytes directly into the appropriate C struct), in higher level languages it's not necessary. So as the final step of the translation, we add 4 to the virtual address to get the actual start of the data.

On-Disk Cell Index Translation

When dealing with hive files on disk, things are much simpler. To translate a cell index into a file offset, we just use the following formula:

FileAddress = CellIndex + 0x1000 + 4

Adding 0x1000 is necessary because cell indexes are relative to the first hbin in the file; before the hbins there is an additional 0x1000 byte block known as the base block that contains metadata about the hive as a whole (the layout of this block can be seen by issuing the dd nt!_HBASE_BLOCK from within WinDbg). In addition, we add 4 to the address for precisely the same reasons we did when translating cell indexes in memory.

This simpler translation scheme is also used in memory if the Flat flag is set in the _HHIVE structure.

Notes on Implementation

In Volatility, the super-cool memory analysis framework from Volatile Systems, we have the concept of stackable address spaces. The "address space" part means that we have can have objects that represent various types of memory spaces (such as standard x86 memory space, PAE memory space, and so on); these objects have, at a minimum, read(), vtop(), and is_valid_address() methods that handle reading from the memory space, translating virtual to physical addresses (whatever virtual and physical mean in that space's context), and checking to see if a given address is valid in that space.

The "stackable" part means that address spaces can be layered, with on address space calling on another to actually read the data. One example in Volatility is the IA32PagedMemory class, which deals with virtual addresses, but relies on having some base address space (in most cases, a FileAddressSpace, which just treats any address as an offset in the underlying file) available to read data from.

In the same way, we can see each hive as its own space, with cell indexes playing the same role as virtual addresses in memory. I have implemented two address spaces within Volatility that demonstrate this: HiveAddressSpace, which uses a virtual memory space like IA32PagedMemory and does cell map translation, and HiveFileAddressSpace, which uses simpler file-based translation method and works with spaces like the FileAddressSpace.

There are several benefits to this approach. First, all of the interfaces used in Volatility to deal with structures (read_obj, read_value, and so on) will work with the new address spaces we have defined. So, for example, assuming we have defined _CM_KEY_NODE, _CHILD_LIST, and _CM_KEY_VALUE in our vtypes.py, the following code will get us the name of the first value of a given key:

val_count = read_obj(hive_space, types,
["_CM_KEY_NODE", "ValueList", "Count"], key_addr)
val_list_ptr = read_obj(hive_space, types,
["_CM_KEY_NODE", "ValueList", "List"], key_addr)
val_ptr = read_value(hive_space, "pointer",
name_len = read_obj(hive_space, types,
["_CM_KEY_VALUE", "NameLength"], val_ptr)
name = read_string(hive_space, types,
["_CM_KEY_VALUE", "Name"], val_ptr, name_len)

The other benefit to implementing the translation as an address space is that the code above will work equally well with a HiveAddressSpace or a HiveFileAddressSpace -- meaning we can deal with hives in memory exactly as we do on-disk hives. To cite a relevant example, all of the code in CredDump works perfectly with a HiveAddressSpace object in place of the HiveFileAddressSpace. This means we can seamlessly extract password hashes and other credentials directly from memory! Cool!

What Can be Done Now

At this point, we can locate hives in memory, find open keys, and make sense of the cell indexes that point into the raw hive data in memory. But how can we actually now traverse the keys and values in the registry? It turns out this is actually not a big problem; many people have already done work on parsing raw registry hives, and we can apply these techniques to memory as well. Samba's regfio library and Tim Morgan's RegLookup are good places to start.

Aside from looking at open source projects, I have also discovered that a large amount of information on internal registry structures already exists in the public symbols distributed by Microsoft. Here are the types I know of that correspond to hive data structures:







Using these types and Volatility's built-in data access functions, it is pretty simple to write code that can traverse the registry hive in memory or on disk. A very simple implementation that can traverse key nodes and values can be found in framework/win32/rawreg.py in the CredDump source.

One word of caution, though. As with all tools that work with memory, we must be able to deal with the fact that the data we're looking for may not be there. This is a very real danger with hive files in memory; not only can portions of memory be paged out as usual, but the part of the hive we're looking for may not have ever been loaded into memory at all! Windows XP and above only map in small views of each hive that correspond to the pieces of data they need to access. So while, in general, every key that has a Key Control Block will be mapped in, for any other keys there is no guarantee that the data will be there. Still, with a little bit of careful programming it's not too hard to avoid getting into trouble.

The End

With what we know now about the registry and how it is stored in Windows memory, we should have no trouble extracting all the registry data we can get our hands on from a memory dump. Of course, this is not really the end -- there are still many, many tools that can be developed that examine specific parts of the registry in memory; CredDump is just one small example. However, I believe that all the significant technical challenges involved in accessing registry data in Windows XP memory dumps have been resolved, and so I will leave it to others to make the most of this new capability.

Friday, February 22, 2008

Cached Domain Credentials

When a Windows computer is joined to a domain, authentication of users is performed not against the local SAM database, but by querying the domain controller. From this description, we might be tempted to conclude that there won't be any useful credentials stored in the registry on a machine that is part of a domain; the users and their hashes don't actually exist on the local machine but rather on the domain controller.

As it turns out, however, by default Windows does store domain credentials on client machines. The reason for this is simple: if the domain controller is unavailable for some reason, users would still like to be able to log into their machines using their credentials; for this reason Windows caches domain credentials of the last (by default) 10 users to log on to the machine. The exact number of cached logons is controlled by the value "CachedLogonCount" of HKLM\Software\Microsoft\Windows NT\CurrentVersion\WinLogon.

Cached Credentials in the Registry

The cached credentials are stored in the SECURITY hive, as with LSA secrets; specifically, they can be found in the values of HKLM\Security\Cache. This key has a number of values, named NL$1 for the first cached account, NL$2 for the second, and so on. However, as we have come to expect in these matters, the data there is not immediately usable.

The first public tool capable of dumping these credentials was CacheDump, by Arnaud Pilon. He was also kind enough to provide a pretty decent explanation of how the whole process worked, in addition to the code, which makes our job at this point much easier.

As Pilon explains, the data in the NL$?? keys is formatted as follows:

[ metadata ][ CH ][ T ][ Encrypted Data ]
64 bytes 16 16 > 100 bytes

The metadata section is cleartext, and contains such information as:

  • Length of the username

  • Length of the domain

  • Length of the full domain name

The actual username, domain name, and hash data are all stored in the encrypted data block. The CH portion of the data is an apparently random 16 byte key that is used to generate the decryption key for the encrypted data.

Decrypting the Cached Data

The decryption process is actually quite simple. First, we obtain the value of NL$KM from the LSA secrets database and decrypt it, as described in an earlier article. Then we generate an RC4 key by taking the HMAC of CH and use NL$KM as the key for the hash function. In Python this looks like:

hmac_md5 = HMAC.new(nlkm,ch)
rc4key = hmac_md5.digest()

The key is then used to decrypt the data in the NL$?? key. (As an aside, this may be the simplest of the obfuscation techniques we have looked at so far.

Once we have the data decrypted, we can find the domain cached password as the first 16 bytes of the encrypted data. The username, domain, and domain name then appear in a contiguous block starting at offset 72 in the encrypted data. We can use the lengths of these fields from the metadata block to extract the strings; note however that they are aligned to 4 bytes, so if the length is not a multiple of 4, it will be padded with nulls.

Wasn't that easy?

And that's really all that there is to it. For the record, the hash algorithm used on the plaintext password is:

MD4(MD4(password) + username)

where both password and username are little-endian UTF-16 strings.

This concludes our brief tour of the various mechanisms used to obscure credentials in Windows. As we have seen, all of the algorithms, once reverse engineered, can be implemented offline; this is precisely what CredDump does. If you have any lingering questions about how all this works, feel free to check out the code, or shoot me an e-mail. Next time we'll be diving right back into memory analysis, and I'll describe how these same techniques we've explored in the past few articles can be used on what portions of the hive remain in memory on Windows systems.

Decrypting LSA Secrets

The LSA secrets store is a protected storage area used the the Local Security Authority (LSA) system in Windows to keep important pieces of information safe from prying eyes. As with Syskey, however, we will see that these secrets are only obfuscated, and once the mechanism is known, we can extract them from the registry with ease. Even without knowing the obfuscation algorithm, however, it is possible to read the values of this data using the LsarQuerySecret function exported by lsasrv.dll, but only if one has the LocalSystem privilege (for example, if the process is running under the SYSTEM account).

What kind of data is stored in these secrets? Here are a few that I've come across:

  • $MACHINE.ACC: has to do with domain authentication, see KB175468

  • DefaultPassword: password used to logon to Windows if auto-logon is enabled

  • NL$KM: secret key used to encrypt cached domain passwords

  • L$RTMTIMEBOMB_[...]: FILETIME giving the date when an unactivated copy of Windows will stop working

So it could clearly be of great use in some cases to be able to read these secrets. To take one example, if one wanted to know when the system was installed, one could look at the value of L$RTMTIMEBOMB, and then subtract 30 days (Windows gives you 30 days from the time you installed to activate the product before it stops working). And, of course, dumping the cached domain logon credentials requires us to be able to get the value of NL$KM.

LSA Secrets in the Registry

LSA secrets are stored in the SECURITY hive of the registry, in the key SECURITY\Policy\Secrets. Under that key, each secret has its own key, so NL$KM can be found at SECURITY\Policy\Secrets\NL$KM. Each secret key then has several subkeys associated with it: CurrVal, CupdTime, OldVal, OupdTime, and SecDesc. CurrVal and Oldval are the current and previous values of the secret, and CupdTime and OupdTime are the respective timestamps when the values were updated, as 64-bit FILETIMEs. SecDesc is assumed to be a security descriptor for the secret, but I have not verified this empirically.

The values of the CurrVal and OldVal keys are unnamed, and displayed as "(Default)" in regedit. Even once you obtain the values, however, you won't be able to make much sense of them. The reason for this is that as with the hashes in the SAM, LSA secrets are encrypted with a key that is specific to each machine (in fact, as we will see, it is based on the boot key used in SysKey encryption).

Decrypting the Secrets

The encrypted data of each secret has the following form:

12 bytes Variable len
[ Metadata ][ Encrypted Data ]

The initial metadata portion does not contain much of interest to us (among other things, it has the size of the block of data, which we already know, since it is specified in the key value data structure). In my code, I ignore it and only deal with the data from offset 0xC (decimal 12) onwards.

So to decrypt the secret's information, we will need two things: an encryption key, and knowledge of which algorithm was used. Luckily, a Chinese reverse engineer known to me only as Eyas[at]xfocus.org has done much of this work for us, and written about the process in an article on XFocus. Unfortunately, the article is in Chinese, but Google Translate does a reasonable job on it, and the included x_dialupass2.cpp is happily quite universal.

Perusing this code shows that the author obtained the secret decryption key by searching the memory space of lsass.exe for the string "\x10\x00\x00\x00\x10\x00\x00\x00"; this is because the key was known to be 16 bytes, and it is contained in a data structure whose first two fields are little-endian integers giving the current and maximum size of the contained data. Crude as this method is, it has worked in every case I have tried it, and it works well enough that the author of CacheDump uses it in his utility to decrypt the value of NL$KM.

The encryption algorithm used, however, is still somewhat mysterious. Both x_dialupass2.cpp and CacheDump both rely on a function named SystemFunction005 in advapi32 do perform the actual decryption, and this function is (naturally) entirely undocumented by Microsoft. So we will have to do a bit of work if we want to really understand how this works, and produce our own implementation of it.


Some Googling and poking through the Wine source code gives us some initial information: SystemFucntion005 apparently decrypts a variable-length block of data using DES in ECB mode (the relevant code can be found in dlls/advapi32/crypt_lmhash.c.

This description initially seems promising, and, indeed, if we decrypt the first 8 bytes of the secret data using the first 7 bytes of the LSA key, we get sensible-looking data that appears to be two little-endian integers that describe the length of the encrypted data. Unfortunately, past that, using that 7-byte key produces gibberish.

What went wrong? Well, notice that in our first attempt, we only used the first 7 bytes of a 16 byte key. As it turns out, although the Wine implementation does not support this, SystemFunction005 can use keys longer than 7 bytes. The first 7 bytes of the key decrypt the first 8-byte block of data, the next 7 bytes (key[7:14]) decrypt the second 8-byte block, and so on.

When we there are fewer than 7 bytes left in the key data, we start again at the beginning of the key, plus the number of bytes of key data we had left over. So for example, with the 16 byte LSA key, we use the following keys: key[0:7], key[7:14], key[2:9], key[9:16], key[0:7], ... and so on. The function that moves through the key data in advapi32 is called AdvanceKeyData, if you are inclined to verify that I've gotten everything correct.

The only other small wrinkle is that the decrypted data is actually an LSA_BLOB data structure:

typedef struct _LSA_BLOB {
DWORD cbData;
DWORD cbMaxData;
BYTE * szData;

Thus, the data returned to the user does not include the first 8 bytes, and will be cbData bytes long.

Obtaining the LSA key

Although searching for the LSA key in memory works, it's a bit crude, and it leaves us with an incomplete picture of how the obfuscation algorithm works. Moreover, it won't work if we don't have access to the original system the secrets were stored on (e.g., if we only have access to the on-disk hives from the system). With the help of some information from Massimiliano Montoro (mao), author of Cain & Abel, we can do better.

As mao describes in a post to the Cain & Abel forums, the LSA key is derived from the registry key SECURITY\Policy\PolSecretEncryptionKey and the boot key used in SysKey. To calculate it, we first obtain an RC4 key from the MD5 hash of the boot key followed by 1000 instances of bytes 60 to 76 of the data in PolSecretEncryptionKey. In Python This looks like:

md5 = MD5.new()
for i in range(1000):
rc4key = md5.digest()

We then use this key to decrypt 48 bytes of data from PolSecretEncryptionKey starting at offset 12 (that is, RC4(rc4key, pol_sec_key[12:60])). Bytes 0x10 through 0x20 of the resulting string are precisely the value of the LSA key we need! Using this key, we can decrypt all the LSA secrets as described above.

Final Words

The code that implements the algorithms described here is part of CredDump, and can be found in framework/win32/lsasecrets.py. I hope you've enjoyed this look at another obfuscation algorithm. In the next article, we'll be making use of the knowledge we gained here to tackle the problem of dumping the domain password hashes from a local client.

Thursday, February 21, 2008

SysKey and the SAM

The Security Accounts Manager

The Security Accounts Manager, or SAM, has been used by Windows since the days of NT to store information on local user accounts (or, in the case of a domain controller, the accounts for all users on the domain). It takes the form of a registry hive, and is stored in %WINDIR%\system32\config. Generally, two types of hash are stored in the SAM: the LanMan hash and the NT hash.

The LanMan hash has many flaws:

  1. It is not salted, and is thus vulnerable to precomputed dictionary attacks such as rainbow tables.

  2. The hash is split into two 7-byte pieces, which allows attacks to be performed against each piece at the same time. This also means that if the password is shorter than 7 characters, the last half of the hash will be a constant value.

  3. The password is converted to uppercase before hashing, which reduces the keyspace.

The LM hash is computed by padding or truncating the password to 14 characters, splitting it into two halves, and then using each half as a 56-bit DES key to encrypt the fixed string "KGS!@#$%"

The NT hash, by contrast, is simply the MD4 hash of the password (encoded as UTF-16 little endian). Although it is still unsalted and therefore vulnerable to precomputed dictionary attacks, it is much more secure than the LM hash, as it allows mixed case passwords up to 128 characters.

The SAM before Windows 2000

In the registry, the hashes for each user are stored under SAM\SAM\Domains\Account\Users\[RID], where RID is the numeric user ID of the user as an 8 digit hex string. Inside this key, the V value is a binary data structure that stores the account information, including the password hashes. The various pieces of information can be found from the following calculations (Python syntax):

hash_offset = unpack("<L", V[0x9c:0xA0])[0] + 0xCC
name_offset = unpack("<L", V[0x0c:0x10])[0] + 0xCC
name_length = unpack("<L", V[0x10:0x14])[0]

Once the raw hashes are obtained, they still need one last step of de-obfuscation before they can be fed to a password-cracking program like Ophcrack. Each hash must be decrypted using a key based on the user ID, using the following algorithm:

def sid_to_key(sid):
s1 = ""
s1 += chr(sid & 0xFF)
s1 += chr((sid>>8) & 0xFF)
s1 += chr((sid>>16) & 0xFF)
s1 += chr((sid>>24) & 0xFF)
s1 += s1[0];
s1 += s1[1];
s1 += s1[2];
s2 = s1[3] + s1[0] + s1[1] + s1[2]
s2 += s2[0] + s2[1] + s2[2]

return str_to_key(s1),str_to_key(s2)

The str_to_key function just converts a 7 byte string to an 8 byte DES key with odd parity.

The two keys are used to decrypt the two halves of the password hashes, so:

k1,k2 = sid_to_key(sid)
lmhash = DES(k1,enc_lmhash[:8])+DES(k2,enc_lmhash[8:])
lmhash = DES(k1,enc_lmhash[:8])+DES(k2,enc_lmhash[8:])

And in Windows NT, this is all we need to do to get the hashes. Note that only the SAM hive was necessary to fully decrypt the hashes.


To make the hashes harder to decrypt, Microsoft introduced SysKey, an additional layer of obfuscation SysKey is on by default in Windows 2000 and above, and can be enabled in Windows NT 4.0 using the SysKey utility. In this scheme, a key stored in the system hive is used to further encrypt the hashes in the SAM.

The key, known as the boot key is taken from four separate keys: SYSTEM\CurrentControlSet\Control\Lsa\{JD,Skew1,GBG,Data}. However, the actual data needed is stored in a hidden field of the key that cannot be seen using tools like regedit. Specifically, each part of the key is stored in the key's Class attribute, and is stored as a Unicode string giving the hex value of that piece of the key.

Once we have obtained the 16-byte boot key, it must be descrambled. It is permuted according to:

p = [ 0x8, 0x5, 0x4, 0x2,
0xb, 0x9, 0xd, 0x3,
0x0, 0x6, 0x1, 0xc,
0xe, 0xa, 0xf, 0x7 ]
for i in range(len(key)):
key[i] = scrambled_key[p[i]]

This gives us the final value of the boot key, and is all the information we need from the system hive. This boot key is used for several other things aside from just decrypting the SAM -- it is also used to decrypt LSA secrets and cached domain passwords, as we will see.

Turning now to the SAM, our first task is to generate the hashed boot key, which we will then use to derive the encryption key for the individual hashes. To get the hashed boot key, we first go to SAM\SAM\Domains\Account and read the value of F there. Next, we generate an RC4 key as:

rc4_key = MD5(F[0x70:0x80] + aqwerty + bootkey + anum)

where aqwerty and anum are the constant strings:

aqwerty =
anum = "0123456789012345678901234567890123456789\0"

Finally, the key is used to decrypt the 32 bytes at F[0x80:0xA0]. The resulting value is the hashed boot key.

At this point we're almost done. To decrypt the actual hashes for each user, we follow essentially the same procedure as in Windows NT: we go to SAM\SAM\Domains\Account\Users\[RID], and read the encrypted hashes from the V value of that key.

However, we must now apply one additional stage of decryption to the hashes. Once again we must generate the an RC4 key to decrypt the hashes; as before, it will be created from the MD5 of several strings. Specifically, the RC4 key is the MD5 of the first 16 bytes of the hashed boot key, the user ID (as a 32-bit little-endian integer), and the string "LMPASSWORD\0" or "NTPASSWORD\0" (depending on whether the key will be used to decrypt a LanMan or NT hash).

If you find code easier to read than English, here's the specific process:

antpassword = "NTPASSWORD\0"
almpassword = "LMPASSWORD\0"
rc4_key_lm = MD5(hbootkey[:0x10] +
pack("&L",rid) +
rc4_key_nt = MD5(hbootkey[:0x10] +
pack("&L",rid) +

And, at last, we can decrypt the LM and NT hashes with RC4 using their respective keys. This will give us the same kind of hashes we found in Windows NT -- that is, they still need to be decrypted using DES and the sid_to_key function. This will give us the hashes in a form that we can attempt to break.


Although this process certainly is complicated, in the end, it is no more than an obfuscation technique. An attacker can still easily extract the hashes if he can steal the system and SAM hives, or even just the SAM hive if he has some other means of obtaining the boot key. Moreover, the obfuscation mechanism only has to be reverse engineered once, but the entire protection mechanism will then be useless until the algorithm is changed.

Up next, we'll give LSA secrets the same treatment we gave SysKey. LSA secrets are a protected data store that can store several interesting pieces of information, such as the default password for systems that have auto-logon enabled, the timestamp used by Windows to decide when to stop working if it has not been activated, and an encryption key used to encrypt cached domain credentials.

As a final note, if you'd like to just look at some code implementing this, have a peek at framework/win32/hashdump.py in the CredDump distribution.

Wednesday, February 20, 2008

CredDump: Extract Credentials from Windows Registry Hives

This is just a short post to talk about a new tool I've developed, called CredDump. CredDump is a pure-Python implementation of the bkhive/samdump2, lsadump2, and cachedump utilities commonly used to audit Windows password security.

Why re-implement these tools? Well, for one thing, I like Python, and wanted to learn the details of how they all worked. Much more importantly though, this tool is completely cross-platform and requires only the registry hives recovered from the system to operate. Most other tools currently available rely on some aspect of Windows to provide their functionality. For example:

  • lsadump2 calls advapi32.LsarQuerySecret to obtain the unencrypted LSA secrets.

  • cachedump searches through the address space of lsass.exe to obtain the unencrypted LSA key, and uses advapi32.SystemFunction005 to decrypt the value of NL$KM with it.

  • Cain & Abel is the closest to operating entirely offline, but still uses advapi32.SystemFunction005 to do the decryption. Also, it's closed source and Windows-only.

So the hope was to build something in the spirit of Nicola Cuomo's bkhive and samdump2, that could work without requiring Windows at all.

It turned out that almost all of the pieces were already publicly available in various forms. The only truly original work I ended up having to do was reverse engineering SystemFunction005 to re-implement it in Python (and even there, the Wine folks had already done most of the work, they just didn't account for keys longer than 7 bytes).

You can find the project's home page here, or download it directly here.

But wait, I hear you cry, how do I get these hives in the first place? You extract them from a Windows system. Unfortunately, it's not as easy as just copying them out of c:\windows\system32\config, because the files are always open. To get around this, you can either boot into Knoppix, or use the Volume Shadow Copy trick.

In the next few articles, I'll be discussing in detail how these programs work. The first article will cover Syskey encryption and how to dump the SAM database, the next will explore the extraction of LSA secrets, and the final one will talk about cached domain passwords. Of course, if you don't want to wait, there's always the code, which should be pretty readable Python. After that, it's back to memory analysis; now that we have a sense of some of the things in the registry, I'll show you how we can access large portions of the registry directly from Windows memory dumps.

Wednesday, February 13, 2008

Keys Open by Hive

Quick addendum: I thought it might also be fun to post how many keys were open in each hive (this is for xp-laptop-2005-07-04-1430.img -- and sorry for the huge amount of space, Blogger's auto-formatting seems to get confused around tables):

HiveKey Count
[...]ts and Settings\Sarah\NTUSER.DAT147

Reading Open Keys

Last time, we found out how to find information about loaded registry hives in Windows memory dumps. However, just knowing what hives are loaded may not be particularly useful. To fill out our view of the state of the system's registry, we will also want to get information about registry keys currently open in the Configuration Manager. To start, though, we will need to know a little bit more about how the Configuration Manager represents keys in memory.

Each open key is represented by a Key Control Block. Key Control Blocks, or KCBs, store a number of pieces of metadata about the key, such as the name, last write time, pointers to the cached values contained in the key (recall that the registry is essentially a filesystem, where keys act as folders and values are the files). To see precisely what information we can get about a key from its KCB, we can look at the _CM_KEY_CONTROL_BLOCK structure in Windbg:

+0x000 RefCount : Uint2B
+0x002 Flags : Uint2B
+0x004 ExtFlags : Pos 0, 8 Bits
+0x004 PrivateAlloc : Pos 8, 1 Bit
+0x004 Delete : Pos 9, 1 Bit
+0x004 DelayedCloseIndex : Pos 10, 12 Bits
+0x004 TotalLevels : Pos 22, 10 Bits
+0x008 KeyHash : _CM_KEY_HASH
+0x008 ConvKey : Uint4B
+0x00c NextHash : Ptr32 _CM_KEY_HASH
+0x010 KeyHive : Ptr32 _HHIVE
+0x014 KeyCell : Uint4B
+0x018 ParentKcb : Ptr32 _CM_KEY_CONTROL_BLOCK
+0x01c NameBlock : Ptr32 _CM_NAME_CONTROL_BLOCK
+0x020 CachedSecurity : Ptr32 _CM_KEY_SECURITY_CACHE
+0x024 ValueCache : _CACHED_CHILD_LIST
+0x02c IndexHint : Ptr32 _CM_INDEX_HINT_BLOCK
+0x02c HashKey : Uint4B
+0x02c SubKeyCount : Uint4B
+0x030 KeyBodyListHead : _LIST_ENTRY
+0x030 FreeListEntry : _LIST_ENTRY
+0x038 KcbLastWriteTime : _LARGE_INTEGER
+0x040 KcbMaxNameLen : Uint2B
+0x042 KcbMaxValueNameLen : Uint2B
+0x044 KcbMaxValueDataLen : Uint4B

So to find out what keys are open, we will be looking for a list of key control blocks in memory. To figure out where to look, I turned to the kernel debugging extensions. After all, Windbg's !reg openkeys command is able to get a list of all open keys and their KCBs, so by reverse engineering that command we can figure out how to extract the same information from a memory dump.

Luckily, the kernel debugging extensions disassemble easily, and debug information for them is available from the Microsoft symbol server, so we get information on function names and so on for free (for anyone wishing to try this at home, the appropriate file is in winxp\kdexts.dll in the Debugging Tools for Windows program directory). In general, this can actually be an excellent technique for finding out about Windows internals -- any information you get a Windbg extension can be extracted from live memory with a little effort, and since the intention is to display the information to the user, there are a lot of useful markers in the code like print statements that help you understand what particular data structures and fields mean.

By reverse engineering the regopenkeys() function, we find that it uses the unexported kernel global variables CmpCacheTable and CmpHashTableSize. CmpCacheTable points to a hash table that is used by the Configuration Manager to provide fast lookups for open keys. Each entry in the table points to a _CM_KEY_HASH structure, shown below:

lkd> dt nt!_CM_KEY_HASH
+0x000 ConvKey : Uint4B
+0x004 NextHash : Ptr32 _CM_KEY_HASH
+0x008 KeyHive : Ptr32 _HHIVE
+0x00c KeyCell : Uint4B

The NextHash member points to the next entry in the given hash bucket. To read the entire table, we just read CmpHashTableSize pointers at CmpCacheTable, and then for each of those, read in all the entries in that bucket using the NextHash field (the last entry in a given bucket will have its NextHash set to 0).

However, the !reg openkeys command gives much more information about each key than we find in a _CM_KEY_HASH structure -- it also lists the KCB, name, and cell. Digging a little deeper, we discover the secret to how it does this: each _CM_KEY_HASH is in fact embedded in its corresponding _CM_KEY_CONTROL_BLOCK (see the KeyHash member at offset 0x8 up there?). By subtracting 8 from the address of the _CM_KEY_HASH, we get the address of the KCB, which in turn gives us all the information we could want: last write time, name, cell index, and pointers to parent KCBs.

Throughout this discussion, you may have noticed that unlike the debugger, we don't know in what value CmpCacheTable has. Unfortunately, the location of this variable changes with each version of Windows and even each service pack or hotfix. Was all our hard work figuring this out for naught, then, since we can't implement it in an offline analysis framework like Volatility?

Well, not really. Just as we came up with a signature for the registry hive data structure in the last post, we can come up with a heuristic for determining the address of CmpCacheTable in memory as well. Since the hash table is just a big list of pointers, however, a static signature probably won't work. So let's look at the things we know about CmpCacheTable:

  1. It's a kernel global variable, so it should reside inside the mapped executable image for ntoskrnl.exe.

  2. It points to a list of pointers, and each of those points to a _CM_KEY_HASH structure.

  3. The _CM_KEY_HASH structure has a pointer to a the hive the key belongs to at offset 0x8.

Point (3) is the critical one, because we already know how to identify valid _HHIVE structures! We can leverage this to find the table of cached registry keys.

Our algorithm for finding this table is going to look something like this, then:

  1. Find the base address of the kernel in memory. This can be done using the KPCR trick.

  2. Parse the PE header to get the offset (RVA) of each section, and add that to the kernel base address to get its virtual address. (I find pefile quite useful for this.)

  3. Loop over each section, and treat each dword in that section as a potential pointer.

  4. At the pointed-to memory location, treat each dword as a pointer to a _CM_KEY_HASH.
  5. Follow the KeyHive pointer to the _HHIVE candidate, and check that it matches the signature we developed earlier.

  6. As a bonus, once we've found CmpCacheTable this way, CmpHashTableSize is the next dword after it, at least on XP SP2 (the variables are most likely declared next to each other in the Windows kernel source.)

If you want to cheat a bit, the variable is in the PAGEDATA section, which should simplify your search. It is up to you how many entries in the candidate hash table you want to check; checking more will take longer, but should reduce the chance of false positives. Also, some entries will be 0 (if that hash bucket is not filled), so don't throw out a candidate just because some of its entries are null.

Armed with this information, you should now be able to read the full list of registry keys opened by the configuration manager. So how many keys can you expect to find using this method? Here are some quick stats from some images I have (the first two are publicly available test images, the third is just an image I took with dd from my own XP SP2 machine):

Image# keys

Although we have now looked pretty deeply into the internals of the Configuration Manager and figured out how to extract several important pieces of information about the registry from memory, we aren't quite done with the topic yet. For one thing, we've so far only really dealt with metadata, rather than the registry data itself. In addition to things like key key names and timestamps, we may want to pull out as much information as possible about each key and its values. To do this, we will have to start looking at the pieces of the raw hive itself that are mapped into memory, which will involve finally figuring out how to make use of cell indexes and where they fit into virtual address space. Stay tuned!

Friday, February 8, 2008

Enumerating Registry Hives

The Windows registry can be an important forensic resource. Harlan Carvey has written extensively on various aspects of registry analysis, and is even considering writing a book on the topic. I have already written about attempting to extract hives from memory; in this post, we will again look at registry hives in Windows memory, but this time in a more top-down fashion, by examining the data structures used to represent hives by the Configuration Manager.

A hive is represented by the Windows Configuration Manager using the _CMHIVE data structure. You can examine this structure in detail using the dt command in Windbg:

lkd> dt nt!_CMHIVE
+0x000 Hive : _HHIVE
+0x210 FileHandles : [3] Ptr32 Void
+0x21c NotifyList : _LIST_ENTRY
+0x224 HiveList : _LIST_ENTRY
+0x22c HiveLock : Ptr32 _FAST_MUTEX
+0x230 ViewLock : Ptr32 _FAST_MUTEX
+0x234 LRUViewListHead : _LIST_ENTRY
+0x23c PinViewListHead : _LIST_ENTRY
+0x244 FileObject : Ptr32 _FILE_OBJECT
+0x248 FileFullPath : _UNICODE_STRING
+0x250 FileUserName : _UNICODE_STRING
+0x258 MappedViews : Uint2B
+0x25a PinnedViews : Uint2B
+0x25c UseCount : Uint4B
+0x260 SecurityCount : Uint4B
+0x264 SecurityCacheSize : Uint4B
+0x268 SecurityHitHint : Int4B
+0x26c SecurityCache : Ptr32 _CM_KEY_SECURITY_CACHE_ENTRY
+0x270 SecurityHash : [64] _LIST_ENTRY
+0x470 UnloadEvent : Ptr32 _KEVENT
+0x474 RootKcb : Ptr32 _CM_KEY_CONTROL_BLOCK
+0x478 Frozen : UChar
+0x47c UnloadWorkItem : Ptr32 _WORK_QUEUE_ITEM
+0x480 GrowOnlyMode : UChar
+0x484 GrowOffset : Uint4B
+0x488 KcbConvertListHead : _LIST_ENTRY
+0x490 KnodeConvertListHead : _LIST_ENTRY
+0x498 CellRemapArray : Ptr32 _CM_CELL_REMAP_BLOCK

Some interesting things jump out to start with. First, two _UNICODE_STRINGs. These are always good as they will provide us with a human-readable name for the hive. We also notice that the very first field, Hive, is 0x210 bytes long! So let's look at its structure, _HHIVE:

lkd> dt -r1 nt!_HHIVE
+0x000 Signature : Uint4B
+0x004 GetCellRoutine : Ptr32 _CELL_DATA*
+0x008 ReleaseCellRoutine : Ptr32 void
+0x00c Allocate : Ptr32 void*
+0x010 Free : Ptr32 void
+0x014 FileSetSize : Ptr32 unsigned char
+0x018 FileWrite : Ptr32 unsigned char
+0x01c FileRead : Ptr32 unsigned char
+0x020 FileFlush : Ptr32 unsigned char
+0x024 BaseBlock : Ptr32 _HBASE_BLOCK
+0x000 Signature : Uint4B
+0x004 Sequence1 : Uint4B
+0x008 Sequence2 : Uint4B
+0x00c TimeStamp : _LARGE_INTEGER
+0x014 Major : Uint4B
+0x018 Minor : Uint4B
+0x01c Type : Uint4B
+0x020 Format : Uint4B
+0x024 RootCell : Uint4B
+0x028 Length : Uint4B
+0x02c Cluster : Uint4B
+0x030 FileName : [64] UChar
+0x070 Reserved1 : [99] Uint4B
+0x1fc CheckSum : Uint4B
+0x200 Reserved2 : [894] Uint4B
+0xff8 BootType : Uint4B
+0xffc BootRecover : Uint4B
+0x028 DirtyVector : _RTL_BITMAP
+0x000 SizeOfBitMap : Uint4B
+0x004 Buffer : Ptr32 Uint4B
+0x030 DirtyCount : Uint4B
+0x034 DirtyAlloc : Uint4B
+0x038 RealWrites : UChar
+0x03c Cluster : Uint4B
+0x040 Flat : UChar
+0x041 ReadOnly : UChar
+0x042 Log : UChar
+0x044 HiveFlags : Uint4B
+0x048 LogSize : Uint4B
+0x04c RefreshCount : Uint4B
+0x050 StorageTypeCount : Uint4B
+0x054 Version : Uint4B
+0x058 Storage : [2] _DUAL
+0x000 Length : Uint4B
+0x004 Map : Ptr32 _HMAP_DIRECTORY
+0x008 SmallDir : Ptr32 _HMAP_TABLE
+0x00c Guard : Uint4B
+0x010 FreeDisplay : [24] _RTL_BITMAP
+0x0d0 FreeSummary : Uint4B
+0x0d4 FreeBins : _LIST_ENTRY

Once again we notice a few fields that might be of interest to us. The Storage member contains information that the configuration manager uses to translate cell indices (see my earlier article for more details on cell indices) into virtual addresses in memory. The BaseBlock member gives us a direct pointer to the base block structure of the registry file, as it exists in memory. Reading memory there shows us exactly what we expect; the usual registry file signature "regf" followed by the timestamp, filename, etc.

Knowing what the structure looks like is all well and good, but how do we actually find them in memory? It turns out that we can create a highly effective signature by noting two facts. First, the _CMHIVE data structure is allocated in paged pool, and thus has a pool tag: "CM10" (listed in pooltag.txt as "Internal Configuration manager allocations"). We also know from the the structure listing above that it is 0x49c bytes long; by including the pool header (8 bytes) and padding it out to an 8 byte alignment, we get a total size of 0x4a8 for the whole pool block. This will appear in the pool header as 0x95 (since the size is listed as the number of 8-byte blocks in the allocation, and 0x95 * 0x8 = 0x4a8). Finally, the pool type (paged pool) is encoded as 0x0c.

So we can already create a signature for the pool header (regular expression notation): "..\x95\x0cCM10" that should be fairly accurate in finding the pool allocations we want. But we can do even better! Notice the first field of the _HHIVE structure -- Signature. Each _HHIVE, and therefore each _CMHIVE, begins with a constant signature, 0xbee0bee0 as a little-endian integer. So armed with this knowledge, we can build the full signature for use with something like FTimes:


Once we have found just a single hive, we can use it to find all of the others in virtual memory. Each _CMHIVE has a member HiveList. This _LIST_ENTRY links together all the hives in the kernel address space. We can traverse this linked list to find all the hives currently loaded by the configuration manager (remember that each _LIST_ENTRY will point to the HiveList member of the _CMHIVE, not the beginning of the structure -- you will have to subtract 0x224 from the value of the Flink or Blink to obtain the correct value). Note that the addresses given by the HiveList member are virtual addresses; you will need a page directory to translate them. Luckily, all Configuration Manager structures live in kernel space, so the page directory of any process will do -- I generally use the Idle process.

As you traverse this list, you may notice a couple oddities. First, there will be one entry in the list that doesn't seem to match the others. Its address will be somewhere around 0x8067b3a8, and its signature won't be 0xbee0bee0. This is because it actually isn't a hive at all! Rather, this is actually the list head. It exists as a global variable within the NT kernel; you can get its value by issuing ? CmpHiveListHead from within Windbg. If all you want is a list of the hives, though, it's save to just skip over it as you traverse the list.

The other slightly strange thing you will encounter is that there are many more hive structures found in the physical memory dump than can be found by traversing the linked list. Upon closer inspection, this is because there are actually a number of duplicate structures in physical memory -- they have exactly the same data as other entries that can be found in the linked list. A similar phenomenon can be seen when searching for process structures in physical memory; ptfinder calculates the MD5 of the structures to avoid such duplicates. It is probably safe to ignore such duplicates and focus only on the entries that are in the in-memory list.

Hopefully this article has given you a taste for what kinds of information about the registry can be extracted from Windows memory dumps. But perhaps you feel let down -- after all, a simple list of the hives loaded into memory doesn't tell you much that's forensically useful. Sure, you might be able to say when the hive was last modified by looking at the timestamp in the base block, or find out who was logged in by looking at what ntuser.dat hives were open, but that's not that exciting. What you'd really like to do is get information about actual registry keys that are currently open. This can also be accomplished using memory analysis, and we'll see how in an upcoming article.