The Feasibility of Attacking Windows 2000 Kerberos Passwords
7 Mar. 2002
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.
"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]
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.
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:
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.
A precompiled Crack Estimator Executable can also be downloaded and run on your own hardware to estimate timings (requires MS VC++ runtime DLL).
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.
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
* 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