BindView Security Advisory -------- Windows NT's SYSKEY feature Issue date: December 16, 1999 Contact: Todd Sabin <tsabinat_private> Topic: Vulnerability in Windows NT's SYSKEY encryption Overview: SYSKEY does not fully protect the SAM from off-line attacks. Specifically, dictionary and brute-force password cracking are still possible, even when SYSKEY is enabled and the attacker is not in possession of the SystemKey. Affected Systems: All Windows NT 4.0 machines and pre-RC3 W2K machines with SYSKEY enabled. Details: SYSKEY is an optional Windows NT feature that was added in NT4.0 SP3. It adds further encryption to the password hashes in the SAM database. This encryption is meant to protect the SAM from 'off-line' attacks, where an attacker has gotten a copy of the SAM (e.g., by stealing a backup tape, repair disk, or the entire machine), but does not have the System Key. Without SYSKEY enabled, such an attacker would be able to directly recover all of the password hashes, and could then use them to authenticate on the network, or brute force them to obtain the plaintext passwords. Tools are currently available to do this. SYSKEY is supposed to defend against these attacks, but we have discovered that, due to implementation flaws, it falls well short. Effects of SYSKEY on registry: How does SYSKEY change what is stored in the SAM? Let's look at an example. Here's a (partial) hex dump of the registry value HKLM/SAM/SAM/Domains/Account/Users/000001F4/V: (before SYSKEY enabled) 000001f0: 6400 6f00 6d00 6100 6900 6e00 0102 0000 d.o.m.a.i.n..... 00000200: 0700 0000 0002 0000 0700 0000 ce28 297d .............()} 00000210: ede4 0fab 3a0f 6436 aff3 881f 0edb a361 ....:.d6.......a 00000220: 4fb6 c22a e367 e3ea bad8 807c 0edb a361 O..*.g.....|...a 00000230: 4fb6 c22a e367 e3ea bad8 807c 653c e4ff O..*.g.....|e<.. 00000240: 45a2 1ee6 b2db 5d9f 09fe f2fd 8fb8 9576 E.....]........v 00000250: 81a5 70e6 c83d 0be2 a7f1 4fcb ce28 297d ..p..=....O..()} 00000260: ede4 0fab 3a0f 6436 aff3 881f 339e 652f ....:.d6....3.e/ 00000270: be4f 2b9d 3a0f 6436 aff3 881f f42c 7909 .O+.:.d6.....,y. 00000280: 5604 6ea4 3a0f 6436 aff3 881f V.n.:.d6.... This is part of the SAM entry for the Administrator account on a test machine. The password hashes start at offset 0x20c. The first 16 bytes are the LMHash, the next 16 bytes are the NTHash, and the bytes after that are the hashes of the password history (including the current password), for both the NTHash and LMHash values. Actually, these are the obfuscated password hashes, although that's unimportant at this point. The data is roughly the real password hashes DES encrypted with the user's RID as the key. Code to undo the obfuscation can be found in pwdump. So, we know: obfusc. LMHash: ce28297dede40fab3a0f6436aff3881f obfusc. NTHash: 0edba3614fb6c22ae367e3eabad8807c After enabling SYSKEY, this changes to HKLM/SAM/SAM/Domains/Account/Users/000001F4/V: (after SYSKEY enabled) 000001f0: 6400 6f00 6d00 6100 6900 6e00 0102 0000 d.o.m.a.i.n..... 00000200: 0700 0000 0002 0000 0700 0000 0100 0000 ................ 00000210: 3e0e 0261 d2f5 f009 757c 7e7e 626a 78c1 >..a....u|~~bjx. 00000220: 0100 0000 fefd 887d 70a7 3d88 ac14 f9a2 .......}p.=..... 00000230: 7741 70a2 0100 0000 fefd 887d 70a7 3d88 wAp........}p.=. 00000240: ac14 f9a2 7741 70a2 96c6 794f 5959 0939 ....wAp...yOYY.9 00000250: c5a1 08d7 71e5 f60f 25e5 bc12 2a9f 1c4a ....q...%...*..J 00000260: 1b8c c152 6d04 6962 0100 0000 3e0e 0261 ...Rm.ib....>..a 00000270: d2f5 f009 757c 7e7e 626a 78c1 c064 f89f ....u|~~bjx..d.. 00000280: a2b4 3c42 4d75 317e d7e8 8ced 5e71 506d ..<BMu1~....^qPm 00000290: fd3e 0208 e9be ae86 6506 aeb6 .>......e... Now, aside from the insertion of '0100 0000' in front of each entry, we have the encrypted versions of the above. enc. obfusc. LMHash: 3e0e0261d2f5f009757c7e7e626a78c1 enc. obfusc. NTHash: fefd887d70a73d88ac14f9a2774170a2 Encryption Analysis: So, assuming all we have is the encrypted, obfuscated password hashes, what can we do? The more binary inclined may already see the punch line coming. It turns out that the hashes are encrypted with the same rc4 keystream, and consequently, that simply xoring them together will remove the encryption, and leave you with the xor of the obfuscated LM and NT hashes: enc. obfusc. LMHash: 3e0e0261d2f5f009757c7e7e626a78c1 enc. obfusc. NTHash: xor fefd887d70a73d88ac14f9a2774170a2 -------------------------------- c0f38a1ca252cd81d96887dc152b0863 and obfusc. LMHash: ce28297dede40fab3a0f6436aff3881f obfusc. NTHash: xor 0edba3614fb6c22ae367e3eabad8807c -------------------------------- c0f38a1ca252cd81d96887dc152b0863 Some work with a disassembler reveals the complete details of the encryption. For each user, the system uses a different key, which is computed by taking the MD5 sum of the global 128-bit encryption key (aka the password encryption key) concatenated with the user's 4-byte RID. However, this key is then used to rc4-encrypt the user's obfusc. LMHash, NTHash, and two password histories, all independently, using the same keystream. Attack: Due to this flawed implementation, it is possible to conduct dictionary and brute force attacks against a SYSKEY protected SAM. An initial attack would be as follows: For each candidate password { Compute LMHash(password) and NTHash(passwd) Obfuscate the hashes as they are stored in the registry Xor the two results Compare with the xor of the SYSKEY encrypted versions of same if they match, we've found the password. } Note that since the above calculation involves the user's RID, the attack must be done for one user at a time. However, this attack can be improved upon by taking a closer look at the details. Starting from the beginning, we know this: NTHash is MD4 of the user's unicode password. LMHash is the DES encryption of "KGS!@#$%", using the password as the key. Since DES keys are only 56 bits, the password is broken into two 7 byte halves, then each half is used as a key. This leaves us with two 128 bit hashes, NTHash, and LMHash. When stored in the registry, the hashes are further obfuscated by DES encrypting them, using a function of the user's RID as a key. Again, since the hashes are 128 bits, there are two DES encryptions done. The two halves are actually encrypted using different DES keys, but they're both functions of the RID. For details on this encryption, see Jeremy Allison's pwdump. So, what ends up in the registry is: des(k1,1st half lmhash), des(k2, 2nd half lmhash) and des(k1,1st half nthash), des(k2, 2nd half nthash) where k1 and k2 are known functions of the user's RID. Now, with syskey, there's a layer of rc4 encryption on top of that. Fortunately (for attackers), it reuses the keystream. So, stored in the registry is: rc4 (k3, (des(k1,1st half lmhash), des(k2, 2nd half lmhash))) and rc4 (k3, (des(k1,1st half nthash), des(k2, 2nd half nthash))) where k3 is unknown, and different for every user. Precisely, it's MD5 (<password encryption key> concatenated with the user's RID). Now, to attack, we xor out the rc4 encryption, giving: des(k1,1st half lmhash), des(k2, 2nd half lmhash) xored with des(k1,1st half nthash), des(k2, 2nd half nthash) or rewriting, des(k1,1st half lmhash) ^ des(k1,1st half nthash) and des(k2,2nd half lmhash) ^ des(k2,2nd half nthash) Again, we know k1 and k2. Now, if we assume for the moment that the passwords are <= 7 characters, then we can proceed as follows: since the LMHash is computed in halves, the second half will be fixed and known to us. Therefore, we can go through every user in the SAM and compute des(k2,2nd half lmhash), take that, xor it with des(k2,2nd half lmhash) ^ des(k2,2nd half nthash) to get des(k2,2nd half nthash), then take that, and decrypt it with k2 to get 2nd half nthash. We can then look that up in our dictionary. If we find a match, we can then verify that we have the correct password as in the first attack above. Since we've removed the user's RID through the above operations, we can conduct our attack against all users at once, for passwords which are <= 7 characters. Furthermore, we can precompute the dictionary; it will be good against all users on all machines. What about passwords that are longer than 7 characters? Taking 8 character passwords as an example, we can still precompute a dictionary of NTHashes of 8 char passwords, and keep it sorted by the eighth character. Or perhaps think of it as 256 (or less if you're narrowing the search space) separate dictionaries. One for each 8th char. Now you can go through all users and try each of the 256 dictionaries, again computing the known 2nd half of lmhash and going from there. So we've reduced the strength of 8 char passwords to the strength of 1 char passwords modulo lots of space, and perhaps a large constant. This can be extended to longer passwords as well. Note that it's also possible to attack the password histories, using the same technique. Recommendations: Follow Microsoft's instructions for installing the hotfix if you've enabled SYSKEY. Keep your backup tapes and repair disks safe, even if you've enabled SYSKEY. References: Microsoft's SYSKEY page. http://support.microsoft.com/support/kb/articles/q143/4/75.asp Microsoft's security bulletin: http://www.microsoft.com/security/bulletins/ms99-056.asp Microsoft's hotfix page: Intel: http://www.microsoft.com/Downloads/Release.asp?ReleaseID=16798 Alpha: http://www.microsoft.com/Downloads/Release.asp?ReleaseID=16799 Direct hotfix download links: Intel: http://download.microsoft.com/download/winntsp/Patch/syskey/NT4/EN-US/Q248183.exe Alpha: http://download.microsoft.com/download/winntsp/Patch/syskey/ALPHA/EN-US/Q248183.exe Microsoft's knowledge base article: http://support.microsoft.com/support/kb/articles/q248/1/83.asp (may be a day or two before it appears) pwdump http://us1.samba.org/samba/ftp/pwdump/ p.s. For the curious, the password in the above example is 'vmware3'; the history is 'vmware3', 'vmware2', and 'vmware'
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 15:21:32 PDT