[NT] The Feasibility of Attacking Windows 2000 Kerberos Passwords

From: support@securiteam.com
Date: 03/11/02 

From: support@securiteam.com
To: list@securiteam.com
Date: Mon, 11 Mar 2002 23:36:33 +0100 (CET)

The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com
- - promotion

When was the last time you checked your server's security?
How about a monthly report?
http://www.AutomatedScanning.com - Know that you're safe.
- - - - - - - - -

  The Feasibility of Attacking Windows 2000 Kerberos Passwords
------------------------------------------------------------------------

SUMMARY

It is well known that the LM and NTLM authentication schemes used by NT4
(and for backwards compatibility in Windows 2000) are very susceptible to
offline password guessing attacks. This has been ably demonstrated by
password-cracking tools such as l0phtcrack. However, the question of
whether it is feasible to adapt these techniques to attack the Kerberos 5
authentication scheme used by Windows 2000 does not appear to have
received the same level of public attention. It is also worrying that the
general presumption seems to be that Windows 2000 Kerberos 5 solves the
password cracking issue once for all, provided that Kerberos alone is used
in a domain.

In fact Kerberos 5, and consequently the Windows 2000 implementation, has
long been known to have vulnerabilities to offline password guessing
attacks. This paper investigates the feasibility of exploiting one of
these vulnerabilities to build a point-and-click 'l0phtcrack'-style
password cracking tool for Windows 2000 Kerberos. We do not go as far as
actually building this tool, but consider what would be involved in making
one, and how well and how fast it might work in recovering passwords.

To determine the performance that might be expected from a Windows 2000
Kerberos attack, a Windows 2000 Kerberos login exchange was captured from
the test network and decoded. This was done using only publicly available
specifications, APIs, and tools. Code to test passwords for correctness,
and to simulate a brute force attack against the captured Kerberos
pre-authentication data, was implemented. The results of this were used
to derive the estimated time to recover a user login password using the
principal attacks that might be used by a real-world password cracking
tool.

The Kerberos 5 vulnerability that this discussion utilizes is not new, and
is not secret. The code given here took less than a day to implement and
utilizes a design vulnerability in Kerberos that has been widely published
and known for many years. It is known that similar vulnerabilities have
been exploited in real attacks against the previous version of Kerberos,
V4. It is reasonable to presume that real-world tools already exist that
has been adapted to do the same for Windows 2000 and Kerberos 5 in
general.

The conclusion is that it would be straightforward to go further and to
implement a "point and click" Windows 2000 Kerberos cracking tool that
would require minimal knowledge on the part of the user, that would be
widely deployed, and that furthermore would not require administrative
access to a domain controller or indeed to any machine on the target
network. Such a tool can easily be assembled from public domain code and
specifications, and could automatically sniff exchanges between domain
controllers and users in order to harvest weak passwords, even in a pure
Windows 2000 Kerberos domain. We also conclude that such a tool would be
highly effective against dictionary-derived passwords, short passwords (<9
characters, depending on entropy and character set), and/or passwords
drawn from a restricted character set.

DETAILS

Background
"NTLMv2 is much stronger than NTLM or LANMAN protocols and is not
vulnerable to attacks on its encryption. It is however still subject to
dictionary/brute force attacks. Thus it is still only as strong as the
password. Kerberos is much, much stronger." [Typical comment from NT
security mailing list]

"The user password never leaves the local machine with Win2000 using
Kerberos security. It is never exposed to the network so it should not be
able to be sniffed" [typical comment from NT security site]

"By default the KDC requires all accounts to use pre-authentication. This
makes offline password-guessing attacks very difficult." [Microsoft
Kerberos white paper]

Wrong.

While Kerberos 5 is a considerable improvement over Kerberos 4, LM, NTLM
and its variants, it has long been known in the cryptographic community
that it too does not solve dictionary or brute force attacks against a
user's login password, even if pre-authentication is used. This is
explicitly stated in RFC1510:

"Password guessing" attacks are not solved by Kerberos. If a user chooses
a poor password, it is possible for an attacker to successfully mount an
offline dictionary attack by repeatedly attempting to decrypt, with
successive entries from a dictionary, messages obtained which are
encrypted under a key derived from the user's password. [RFC1510]

The RFC1510 statement is the correct one. The following is also worth
noting:

However, pre-authentication can be disabled for individual accounts when
necessary for compatibility with other implementations of the protocol.
[Microsoft Kerberos white paper]

If pre-authentication is disabled for a given Windows account, then
material for offline attack on that account can easily be obtained by a
remote user.

Vulnerability
In order to mount an offline dictionary or brute force attack, some data
that can be used to verify the user's password is needed. One way to
obtain this from Kerberos 5 is to capture a login exchange by sniffing
network traffic.

In Windows 2000, a Kerberos 5 login request contains pre-authentication
data that is used by the Kerberos AS to verify the user's credentials
before issuing a TGT. The basic pre-authentication scheme used by Windows
2000 contains an encrypted timestamp and a cryptographic checksum, both
using a key derived from the user's password.

The timestamp in the pre-authentication data is ASCII-encoded prior to
encryption, and is of the form YYYYMMDDHHMMSSZ (e.g. "20020304202823Z").
This provides a structured plaintext that can be used to verify a password
attempt - if the decryption result "looks like" a timestamp, then the
password attempt is almost certainly correct. A password attempt that
recovers a plausible timestamp can also be verified by computing the
cryptographic checksum and comparing it to that in the pre-authentication
data.

Experiment
Obtaining the password verification material
Using a test Windows 2000 domain, a login attempt for the user 'frank'
with the password 'frank' was made and the exchange was captured using the
freely available sniffing tool WinDump (a windows implementation of
tcpdump). This was then investigated using the freely available ASN.1
decoder dumpasn1 and the Kerberos V5 specification.

As expected, the capture contained the following pre-authentication data:

   2 30 72: SEQUENCE {
   4 A1 3: [1] {
   6 02 1: INTEGER 2
            : }
   9 A2 65: [2] {
  11 04 63: OCTET STRING, encapsulates {
  13 30 61: SEQUENCE {
  15 A0 3: [0] {
  17 02 1: INTEGER 23
            : }
  20 A2 54: [2] {
  22 04 52: OCTET STRING
            : F4 08 5B A4 58 B7 33 D8 09 2E 6B 34 8E 3E 39
90
            : 03 4A CF C7 0A FB A5 42 69 0B 8B C9 12 FC D7
FE
            : D6 A8 48 49 3A 3F F0 D7 AF 64 1A 26 3B 71 DC
C7
            : 29 02 99 5D
            : }
            : }
            : }
            : }
            : }

The second OCTET STRING contains the encrypted timestamp that can be used
to seed an offline attack. The etype 23 appears to be a Microsoft specific
etype, based on RC4-HMAC. The details of this are publicly documented in
the Internet Draft draft-brezak-win2k-krb-rc4-hmac-03.txt.

Decrypting the timestamp
The Brezak Internet draft also contains a detailed description of how the
RC4 key is derived from the user's password, as well as pseudo-code for
decrypting and verifying the timestamp. Implementing this is
straightforward (the code here used the OpenSSL cryptographic libraries)
and yields the necessary password test function for mounting an offline
attack.

As mentioned above, it is not necessary to compute the expensive embedded
cryptographic checksum in order to verify a password - one can simply
decrypt and look for an ASCII string that looks like a timestamp. If the
decryption does not recover a timestamp, the password tried is incorrect.
If the decryption does recover a timestamp, the password tried is almost
certainly correct, and if desired the cryptographic checksum in the
encrypted data can be used to further verify this. As most passwords tried
will be incorrect, the extra overhead involved in doing this extra
verification after the initial check for a recovered timestamp succeeds is
minimal.

Simulating an attack
Given the above password test function, and some captured
pre-authentication data to verify passwords against, then implementing a
password cracker is straightforward. We have not done this, but the
obvious approach is to use existing well-known techniques (e.g. as used by
Alec Muffet's Crack program, and l0phtcrack), and indeed it is easy to
adapt existing code by replacing the password testing component. It is not
much of an additional step to automatically capture the pre-authentication
data, resulting in a point and click 'script kiddie' tool.

The code given here does not go as far as implementing a full-blown
password cracker of any kind. Instead it implements the password test
function from the Brezak Internet draft, and iterates it in a simulation
of 1,000,000 brute force trials against the example pre-authentication
capture shown above. This yields timing information which can be used to
estimate the efficiency of a real world attack program.

The <http://www.brd.ie/papers/w2kkrb/crackestimate.htm> Crack Estimator
Source Code is available (requires an OpenSSL installation).

A precompiled <http://www.brd.ie/papers/w2kkrb/crackestimate.exe> Crack
Estimator Executable can also be downloaded and run on your own hardware
to estimate timings (requires MS VC++ runtime DLL).

Estimated Timings
The estimated timings given by the test program are summarized in the
table below.

To generate the timings the program was compiled with MS Visual C++ 6.0,
using the assembler versions of the relevant OpenSSL libraries, and run on
a low end Pentium machine. Figures for more powerful hardware and for a
distributed attack using 100 machines have been extrapolated from this.
These are only ballpark figures, but they give a feel for what is and is
not within easy reach of an attack.

Further speed improvements could be realized using more or faster
machines, and/or by optimizing the RC4_set_key function (e.g. rewriting it
in assembler). Speedups might also be realized using specialized hardware
to implement some or all of the password test function. Also, apart from
the dictionary attack figures these numbers take no account of lack of
password entropy, therefore it would be wise to treat these numbers very
conservatively (e.g. divide by at least an order of magnitude or two).

It can be seen from this table that even relatively long and "complex"
passwords are easily within reach of a brute force attack using only a
single high-end Pentium machine. It can also be seen passwords that are
dictionary-derived are significantly easier to recover, as usual.

A table is available at:
 
<http://www.brd.ie/papers/w2kkrb/feasibility_of_w2k_kerberos_attack.htm#ESTIMATED_TIMINGS> http://www.brd.ie/papers/w2kkrb/feasibility_of_w2k_kerberos_attack.htm#ESTIMATED_TIMINGS

Conclusions:
It would be straightforward to implement a "point and click" Windows 2000
Kerberos cracking tool that would require minimal knowledge on the part of
the attacker, and that furthermore would not require administrative access
to a domain controller or indeed to any machine on the target network.

Such a tool can easily be assembled from publicly available code and
specifications, and could automatically sniff exchanges between domain
controllers and users in order to harvest weak Windows 2000 passwords,
even in a pure Windows 2000 domain.

We also conclude that such a tool would be highly effective against
dictionary-derived passwords, short passwords (<9 characters, depending on
entropy and character set), and/or passwords drawn from a restricted
character set.

Some other points worth noting are:
 * This attack requires LAN access near the user being attacked, and/or
near the Windows 2000 domain controller, in order to sniff the network
traffic between the two. In many circumstances this is easy or trivial to
arrange, though some network topologies complicate it.
 * The attack cannot be directly performed remotely from the target
network. (It can however be indirectly performed, e.g. by subverting a
machine that is on a target LAN, and using that to sniff the login
exchanges and ship the material elsewhere for offline attack.)
 * It is possible to detect machines that have been placed into
'promiscuous' mode for the purposes of sniffing network traffic, as
"sniffer detectors" exist. Thus the attacker risks detection, but this is
not much of a risk for the attacker if the attacker is using someone
else's machine.
 * Another route to sniffing the pre-authentication material is to reboot
a machine on the LAN into another OS, such as Trinux, a Linux distribution
that can be booted from 3 floppy disks. It would be feasible to rig such
an OS so that it did not appear on the radar of sniffer detectors (e.g. it
could be made to appear as an inactive IP address).
 * If a user inadvertently typed in a password that was not valid for the
domain but was important somewhere else, it might be recovered by the
attacker.

What can be done
The following defenses/fixes may be possible. Like the vulnerability
itself, these are not news either but bear repeating:
 * Use other forms of initial Kerberos authentication and
pre-authentication, e.g. tokens, public key based login, zero knowledge
proofs, EKE, SPEKE, SRP, etc.
 * Encrypt the pre-authentication data using the KDC's public key
(requires secure distribution of KDC public key)
 * Implement an iteration count in pre-authentication data to slow down
exhaustive password testing

Other defenses:
 * Use "strong" passwords/implement a strong password policy
 * Increase minimum password length
 * Expire passwords more frequently
 * Implement password history
 * Complicate network sniffing, e.g. by use of switched network topologies

 * Physically secure machines that are "near" domain controller to prevent
booting alternative OS
 * Install sniffer detectors

ADDITIONAL INFORMATION

References
 <http://www.ietf.org/rfc/rfc1510.txt?number=1510> RFC1510 - The Kerberos
Network Authentication Service (V5)
 <http://www.research.att.com/~smb/papers/kerblimit.usenix.pdf>
Limitations of the Kerberos Authentication System (Steven M. Bellovin &
Michael Merrit)
 <http://www.ietf.org/html.charters/krb-wg-charter.html> Encryption and
Checksum Specifications for Kerberos 5 (Internet Draft)
 
<http://www.ietf.org/internet-drafts/draft-brezak-win2k-krb-rc4-hmac-03.txt> RC4-HMAC (Internet Draft)
 
<http://www.microsoft.com/technet/treeview/default.asp?url=/technet/prodtechnol/windows2000serv/deploy/confeat/kerberos.asp> Kerberos White Paper (Microsoft)
 <http://www.ietf.org/html.charters/krb-wg-charter.html> IETF Kerberos WG
home page
 <http://www.users.dircon.co.uk/~crypto/> Alec Muffet's "Crack"
 <http://netgroup-serv.polito.it/windump/> WinDump
 <http://www.cs.auckland.ac.nz/~pgut001/dumpasn1.c> dumpasn1.c
 <http://www.openssl.org/> OpenSSL
 <http://trinux.sourceforge.net/> Trinux - A Linux Security Toolkit
 <http://www-cs-students.stanford.edu/~tjw/srp/doc.html#drafts> SRP

The information has been provided by <mailto:fod@BRD.IE> Frank O'Dwyer.

========================================

This bulletin is sent to members of the SecuriTeam mailing list.
To unsubscribe from the list, send mail with an empty subject line and body to: list-unsubscribe@securiteam.com
In order to subscribe to the mailing list, simply forward this email to: list-subscribe@securiteam.com

====================
====================

DISCLAIMER:
The information in this bulletin is provided "AS IS" without warranty of any kind.
In no event shall we be liable for any damages whatsoever including direct, indirect, incidental, consequential, loss of business profits or special damages.

Relevant Pages