March 5, 2002
Author: Frank O’Dwyer <fod@brd.ie fod AT opencycleroute DOT org>

Updated March 7, 2002 following feedback from readers.
Some discussion of this also exists in comp.protocols.kerberos

Contents

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

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 Kerberos 5 solves the password cracking issue once and for all, provided that Kerberos alone is used in a domain.

In fact Kerberos 5 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.

N.B.: Password-based login is not the only option in Kerberos 5, nor is it the only option in Windows 2000. It is also possible to login using a public key based scheme, PKINIT, that does not suffer from the problem outlined here. Windows 2000 includes support for this scheme too, with or without smartcard assistance. This entire discussion applies only to the option which is enabled by default, and which is most widely used, which is to use passwords to login. If PKI is not an option for you, there are other potential defenses and fixes that are also suggested in the conclusions section of the paper.

As an experiment 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 utilises is not new, and is not secret, nor is it unique to the Windows implementation. The code given here took less than a day to implement and utilises 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 have 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 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. The same tool could target logins directed at other Kerberos implementations as well, by implementing additional cryptographic methods.

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.

Background

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

“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.

The particular pre-authentication scheme used by default in Windows 2000 and by other Kerberos implementations does not in general make password-guessing attacks very difficult. Instead it can provide the very material that can be used to allow a password-guessing attack to occur.

While Kerberos 5 is a considerable improvement over Kerberos 4, LM, NTLM and its variants (and is generally and correctly regarded as a step forward) it has long been known in the cryptographic community that this issue exists. The following reference, which dates from 1993 (and is not the first mention of this) explicitly refers to the problem:

“This approach has many of the benefits needed to avoid password guessing attacks. It is, however, still vulnerable to attackers who can listen to network messages. This weakness is due to using the client’s password to encrypt verifiable plaintext [Loma 89]. An attacker can sniff the appropriate requests and replies on the network, and then attack them offline.” [DCE RFC 26, Joe Pato, referring to PADATA-ENC-TIMESTAMP]

This problem is also 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]

Vulnerability

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

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 Kerberos 5 a 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 that is used by Windows 2000 and other Kerberos implementations 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

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

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

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

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

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

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 Crack Estimator Source Code is available (requires an OpenSSL installation).

A precompiled Crack Estimator Executable can also be downloaded and run on your own hardware to estimate timings (requires MS VC++ runtime DLL).

Estimated Timings

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

The estimated timings given by the test program are summarised 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 realised using more or faster machines, and/or by optimising the RC4_set_key function (e.g. rewriting it in assembler). Speedups might also be realised using specialised 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 that passwords that are dictionary-derived are significantly easier to recover, as usual.

Conclusions

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

Overall Conclusion

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 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 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. The same tool could target logins directed at other Kerberos implementations as well, by implementing additional cryptographic methods.

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 or foreign KDC, 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 defences/fixes may be possible. Many of these are things that you can already do now, others require modifications to the Kerberos implementation. Like the vulnerability itself, these are not news either but bear repeating:

Fixes:

• Use other forms of initial Kerberos authentication and pre-authentication, e.g. tokens, public key based login, zero knowledge proofs, EKE, SPEKE, SRP, etc. W2K already includes support for public key based login with or without smartcard assistance, and those login methods do not suffer from the problem outlined here. I believe that HHAs are also supported, but the other schemes mentioned are not yet available (and may never be!). If you cannot use any of these suggestions for all accounts, then you might consider using them selectively for high importance accounts.
• (Kerberos implementation modification) Encrypt the pre-authentication data using the KDC’s public key (requires secure distribution of KDC public key). One way to achieve this would be run the existing login exchange over TCP and SSL. (This or something like SRP is my favorite option, as I believe people will want/need to use password based login for a while yet, for practical reasons.)

Other possible defences:

• (Kerberos implementation modification) Implement an iteration count in pre-authentication data to slow down exhaustive password testing. Only makes things N times harder though, and introduces more work for the KDC.
• If nothing in the ‘fix’ section above is available/suitable and you must use passwords, then implement a strong password policy. See references for a pointer to an example policy from SANS. This has to be balanced against the risk of users writing passwords down etc.. At minimum your policy should include:
  • minimum length requirements (anything less than 8 seems to be an obvious problem, and 9 with weak character sets, but you may want to require even longer passwords),
  • expiry requirements (your call, as often as possible and that you think your users will stand),
  • rejection of dictionary passwords and dictionary-derived passwords (use a large dictionary),
  • rejection of passwords derived from login name or login id,
  • requirements for complex passwords (e.g. require upper and lowercase and use of punctuation)
  • consider a more stringent policy (or different authentication method, e.g. HHA, smartcard, public key) for higher risk accounts such as admin accounts for the domain, databases, web services, etc.
• Enforce that password policy using filtering, e.g. on Domain Controllers.
• Audit network for weak passwords and change/remove them
• Implement password history
• Complicate network sniffing, e.g. by use of switched network topologies
• Physically secure machines (including workstations) that are “near” domain controller (in terms of network topology) to prevent booting alternative OS
• Install sniffer detectors

References

Summary | Background | Vulnerability | Experiment | Estimated Timings | Conclusions | References

RFC1510 – The Kerberos Network Authentication Service (V5)

Limitations of the Kerberos Authentication System (Steven M. Bellovin & Michael Merrit)

A Real-World Analysis of Kerberos Password Security (Tom Wu)

Using Pre-Authentication to avoid password-guessing attacks (DCE RFC 26, Joe Pato)

Encryption and Checksum Specifications for Kerberos 5 (Internet Draft)

RC4-HMAC (Internet Draft)

Kerberos White Paper (Microsoft)

IETF Kerberos WG home page

Alec Muffet’s “Crack”

WinDump

dumpasn1.c

OpenSSL

Trinux – A Linux Security Toolkit

SRP

Example strong password policy from SANS (you may wish to consider requiring even longer passwords and changing passwords more often than they suggest, though).