Type packetstorm
Reporter Todd Sabin
Modified 1999-12-17T00:00:00


                                            `BindView Security Advisory  
Windows NT's SYSKEY feature  
Issue date: December 16, 1999  
Contact: Todd Sabin <>  
Vulnerability in Windows NT's SYSKEY encryption  
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  
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  
obfusc. LMHash: ce28297dede40fab3a0f6436aff3881f  
obfusc. NTHash: xor 0edba3614fb6c22ae367e3eabad8807c  
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.  
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)  
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)))  
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)  
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.  
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  
Microsoft's SYSKEY page.  
Microsoft's security bulletin:  
Microsoft's hotfix page:  
Direct hotfix download links:  
Microsoft's knowledge base article:  
(may be a day or two before it appears)  
p.s. For the curious, the password in the above example is 'vmware3';  
the history is 'vmware3', 'vmware2', and 'vmware'