BindView Security Advisory: Vulnerability in Windows NT's SYSKEY feature

[advisory+syskey () BOS BINDVIEW COM (BindView Security Advisory)]

BindView Security Advisory
--------

Windows NT's SYSKEY feature
Issue date: December 16, 1999
Contact:  Todd Sabin <tsabin () bos bindview com>

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'