COMMAND
SYSKEY
SYSTEMS AFFECTED
WinNT 4.0 and pre-RC3 W2K machines with SYSKEY enabled
PROBLEM
Following is based on BindView Security Advisory. 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.
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.
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
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.
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.
p.s. For the curious, the password in the above example is
'vmware3'; the history is 'vmware3', 'vmware2', and 'vmware'
SOLUTION
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. 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