What Administrators Need to Know About Passwords

What Administrators Need to Know About Passwords

The things administrators need to know about passwords fall into three categories: how they are stored, how they are used, and how they are attacked . Understanding those three areas is fundamental to understanding what to tell users about passwords and implementing a password policy.

How Passwords Are Stored on Windows

Windows stores passwords several different ways, generally speaking, by replacing characters chosen by a user for the password using some form of transformation.

NOTE: In the remainder of this chapter, the term character is used to denote any symbol that can be used to construct a password, including numbers , letters , and nonalphanumeric symbols. A character set is the set of all characters used or possible in a password, as evident by context. The letters of the alphabet are referred to as letters .

Some of the stored passwords are used for authenticating local and remote users, one is used to authenticate domain users locally, and there are several different ways that applications may store passwords. The following sections examine each in turn .

The LM "Hash"

The LAN Manager, or LM, "hash" is not a hash at all, although it is the output of an OWF, and as such, cannot be reversed . Unfortunately, many years ago it became common to refer to the output of the LM OWF as the "LM hash." Much as we would like to change the world and get people to refer to it properly, we do not see that happening. Therefore, we, unwillingly, bow to common usage and refer to it as the LM hash from now on.

The LM hash was originally invented for use in the LAN Manager operating system designed by IBM. When Windows NT was designed in the early 1990s, it was imperative that it interoperate with LAN Manager, and therefore that it supported the LM hash, in spite of the fact that Windows NT also supported a more secure password storage algorithm, the NT hash. This interoperability was exploited for other purposes by developers both at Microsoft and elsewhere and has resulted in the fact that today, more than 10 years after Windows NT first came out, we still have to support the LM hash in many environments. Even the most recent version of Windows NTWindows Server 2003generates the LM hash by default. The next version of Windows will almost certainly also support LM hashes, although they may not be generated by default. This truly highlights how difficult it is to replace authentication systems in a widely deployed operating system.

The LM hash is computed as follows :

1.	The password is padded with nulls to exactly 14 characters. The current implementations will not generate an LM hash for passwords longer than 14 characters.
2.	All lowercase letters are converted to uppercase.
3.	The password is split into two 7-byte chunks , and each chunk is used to generate an 8-byte odd-parity DES key.
4.	Each 8-byte key is used in a DES encryption of a fixed string. The fixed string is calculated by decrypting the value 0xaad3b435b51404ee using a null key.
5.	The two cipher- texts are concatenated and stored.

This computation, shown in Figure 11-1, raises several interesting concerns. First, it is trivial to tell whether a user has an LM hash at all and whether the password underlying it is shorter than 8 characters. This is because passwords are padded with nulls to make them exactly 14 characters. If a password is only 7 characters long, for example, the second half is null. Encrypting the fixed value with a null key yields 0xaad3b435b51404ee. In other words, if that string forms one or both halves of the password hash, that part of the password is null.

Figure 11-1. The LM hash computation.

The second concern is that the character set allowed in an LM hash is very limited. First, all the lowercase letters are replaced with uppercase letters. Second, the character set is limited to 142 characters, although only 99 of them are printable, and ordinarily the characters used in a password are picked from the ones on a keyboard, and is case insensitive. For a U.S. English system, that includes only 68 characters. (There are 94 characters on the keyboard, but if you ignore case you lose 26 of them.) Table 11-1 shows the entire 99-character printable LM character set.

Table 11-1. The Entire Printable LM Hash Character Set

Character Code	Character	Character Code	Character
0032	(space)	0063	?
0033	!	0064	@
0034	"	0065	A
0035	#	0066	B
0036	$	0067	C
0037	%	0068	D
0038	&	0069	E
0039	'	0070	F
0040	(	0071	G
0041	)	0072	H
0042	*	0073	I
0043	+	0074	J
0044	,	0075	K
0045	-	0076	L
0046	.	0077	M
0047	/	0078	N
0048		0079	O
0049	1	0080	P
0050	2	0081	Q
0051	3	0082	R
0052	4	0083	S
0053	5	0084	T
0054	6	0085	U
0055	7	0086	V
0056	8	0087	W
0057	9	0088	X
0058	:	0089	Y
0059	;	0090	Z
0060	<	0091	[
0061	=	0092	\
0062	>	0093	]
0094	^	0181	µ
0095	_	0182
0096	`	0183	·
0123	{	0186
0124		0187	»
0125	}	0188	¼
0126	~	0189	½
0161		0191
0162		0196
0163	& pound ;	0197
0165		0198
0166		0199
0167	§	0201
0170		0209	‘
0171	«	0214
0172		0220
0176	°	0223
0177	±	0247	·
0178	2

In addition, many characters used in a password are actually converted into a different character by the OWF, with the result that all those characters generate the same output. Table 11-2 shows some of the character conversions in the character set below character code 1024.

Table 11-2. List of Characters That Generate Identical LM Hashes

0175
0190	¾	0192
0222		0193
0254		0194	‚
Converted into		0195	ƒ
0095	_	0224
		0225
0101	e	0226
0200	ˆ	0227
0202		0097	a
0203	‹	Converted into
0232		0065	A
0234
0235	«	0114	r
Converted into		0174
0069	E	Converted into
		0082	R
0100	d
0208		0121	y
0240		0221
Converted into		0253
0068	D	0255
		Converted into
0117	u	0089	Y
0217
0218		0120	x
0219		0215	x
0249	¹	Converted into
0250		0088	X
0251	»
Converted into
0085	U
0111	o	0105	i
0210	’	0204
0211	“	0205
0212	”	0206
0213		0207
0216	˜	0236
0242	²	0237	­
0243	³	0238
0244		0239
0245	µ	Converted into
0248		0073	I
Converted into
0079	O	0169
		0099	c
		Converted into
		0067	C

You may think these tables are not that interesting, and in all honesty, they are not. We do include them for a reason though. Many people we have met will use certain characters in their passwords with the intent to cause the LM hash not to be generated. Unfortunately, far too often the characters they use do indeed result in an LM hash. If you want to prevent one from being stored, see the later discussion on that topic, and make sure you do not pick characters from Tables 11-1 or 11-2.

The most commonly used character set for passwords consists of the alphanumeric characters on the keyboard, plus the 14 symbols above the numbers. Although there are only 50 case-insensitive characters in that set, let us consider all characters on a U.S. English keyboard. There are 68 characters in that set, giving us only 6.8 x 10 ¹² different passwords less than or equal to 7 characters in length. That may sound like a lot, but it is actually not. Because the second half of the LM hash generates the same hash as the first, the number of possible passwords does not increase by going beyond 7 characters. Note, however, and this is important, that there is still value in creating a password longer than 7 characters . The cracker still has to compare two halves, instead of just one as in the case of a <= 7-character password. Although this does not increase the strength of the password in a theoretical sense, it still takes marginally longer to crack both halves, particularly if there are a lot of accounts that are being cracked. We have noticed increases in crack time on the order of hours for relatively large sets of passwords.

One final thing to know about the LM hash is that it is unsalted. With Windows, there was never any reason to salt the passwords because arbitrary users could not access the password database. Recall that salting was used to prevent a user from discovering other users with the same password.

The NT Hash

When Windows NT was designed, the LM hash was already considered relatively weak. Consequently, a new mechanism for storing passwords was needed. The new mechanism, dubbed the NT hash, was much simpler than the LM hash, as Figure 11-2 shows. The algorithm simply takes the password, hashes it, and stores it.

Figure 11-2. The NT hash algorithm.

Several items are of note in Figure 11-2. First, notice that this time the algorithm is a true hashMD4. Although MD4 is not used for new implementations today, in the early 1990s it was deemed one of the stronger hashes, and it made sense to use it. Second, notice that the result is called the unicodePwd. That happens to be the name of the attribute in Active Directory (AD) used to store the NT hash.

The NT hash is considerably more difficult to crack than the LM hash due both to its significantly greater character set and to the greater potential length. Theoretically, the NT hash supports the entire Unicode double-byte character set of 65,535 characters (NULL is not allowed). That theoretically gives us 4.9 x 10 ⁶¹¹ different passwords. Limiting ourselves to only passwords less than or equal to 14 characters, we get 2.7 x 10 ⁶⁷ possible passwords. Neither of those numbers is really comparable to the numbers we had for LM hashes, however, because users typically do not use the entire Unicode character set in their passwords. As mentioned before, passwords are typically constructed from the 68 keys on the keyboard. Adjusting for the fact that the NT hash, contrary to the LM hash, is case sensitive, that means the comparable character set for NT hashes has 94 characters in it. This gives us 4.3 x 10 ²⁷ possible 14-character passwords, a very significant improvement of 15 orders of magnitude over the LM hashes. Using only 7 characters in the passwords we would get 6.6 x 10 ¹³ possible, because of the addition of case sensitivity. That still represents a respectable order-of-magnitude improvement over the LM hash.

It is important to keep in mind here that the full character set and password length generates many more possible passwords than the MD4 hash can ever represent. There may be hash collisions (two or more plain texts that generate the same hash). Because the comparison at logon is between hashes, not the passwords that generated them, any password that generates a particular hash is going to result in a successful logon. In addition, in late 2004, a paper was published describing how to create collisions in MD4, using pen and paper! Clearly, MD4 is no longer a secure algorithm. This does not mean that all systems using MD4 as a password storage algorithm should be changed. We need to take into account what it takes to get password hashes on those systems first. The best protection against password attacks is, and always has been, to stop attackers from getting your hashes. We return to this in a few pages.

Cached Credentials

Cached credentials are used to authenticate against when you are authenticating using domain credentials to a system that is not connected to a domain controller. Each time a domain user logs on, the OS generates the cached credentials and stores them in the Security hive of the operating systemnot in the LSA Secrets as commonly assumed.

Note that cached credentials have nothing to do with storing passwords after you get authenticated. For instance, Internet Explorer, virtually all mail clients , Red Hat, SuSe, and Debian Linuxes, Windows Explorer, and many other applications and operating systems all have the capability to "remember" the passwords you use to access some resource. Those are not cached credentials. They are stored usernames and passwords, and the storage facility is entirely different. Cached credentials is a term describing only the process of storing the domain logon credentials so that you can log on to a domain member without being connected to a domain controller.

The cached credentials are actually a function of the NT hash. Figure 11-3 shows the computation.

Figure 11-3. The cached credentials generation process.

As Figure 11-3 shows, the cached credentials are very different from your normal password hashes. First, they are salted using the username. Second, they are a hash of a hash. Basically, the NT hash is salted and then hashed again. This means that to crack the cached credentials, you would have to brute force a hash of a hash, a process that is extremely time-consuming . Finally, you have to be able to execute code as the LocalSystem account to get to them. This means that the claim advanced by some people and organizationsthat cached credentials represents a huge security problemis probably a bit blown out of proportion. Weak passwords will certainly be cracked through cached credentials, but only if the attacker already has complete control over the machine, in which case you have a lot of other things to worry about. Strong passwords are extremely hard to crack using cached credentials.

Other Stored Usernames and Passwords

Most operating systems also store passwords for ease of use, such as to remember the password you used to connect to a network resource, or to run a program as a different user. In addition, Windows operating systems have a few other password stores. There are various forms of digest credentials stored in Active Directory, for instance. There is also the LSA Secrets, where the Local System Authority (LSA) stores information it needs, such as service account credentials. The process of storing credentials for accessing network resources and for use by applications is handled in Windows by the credential manager (credman) set of APIs. The credman APIs are designed for use by applications, such as Internet Explorer, as well as the OS itself, to help store credentials as well as can be done in software. The credman APIs do not themselves store credentials. They merely are used to encrypt or decrypt them. The application passes in the credentials and receives an encrypted blob in return, which can now be stored anywhere . For instance, this is the functionality used by the Stored Usernames and Passwords tool to store credentials used to access other systems. Those particular credentials are stored in the user's profile.

How Passwords Are Used

Passwords are obviously used for authentication. Windows supports many different kinds of authentication. The four main protocols are LM authentication, which uses the LM hash, NTLM (sometimes referred to as NTLMv1), NTLMv2, and Kerberos, all of which use the NT hash. Kerberos is well documented in RFCs 1510 (http://www.ietf.org/rfc/rfc1510.txt?number=1510) and 1964 ( http://www.ietf.org/rfc/rfc1964.txt?number=1964), and therefore we do not deal with it further here. The other three are interesting, however.

LM authentication is designed primarily for backward compatibility. It is used to authenticate access from Windows 3.11, Windows 95, and Windows 98. If Windows 95 or 98 has the Directory Services Client (see KB 323466), they can use some version of NTLM instead. LM authentication is also used to authenticate to servers running Windows 95 and 98 if they are using share-level passwords. If they can pass the authentication through to a domain controller, NTLM can be used instead. In addition, LM authentication is used with some third-party products, such as certain network-attached storage devices. Finally, LM authentication is used in some situations by services such as the Clustering Service and Real Time Communication Server (RTC). These services use UDP-based RPC, which by default uses only LM authentication. To change how RPC over UDP works, set the NtlmMinClientSec value as we discuss in the "Password Best Practices" section later in this chapter.

NTLM authentication has been the default authentication protocol in Windows NT since NT 3.1. It was only replaced by Kerberos in Windows 2000. It is still used in many situations, such as when authenticating in a Windows NT 4.0 domain or in a workgroup and when authenticating between systems in a Windows 2000 or higher domain and systems outside the domain or that have no trust relationship with the domain. Within a Windows 2000 or higher domain and between systems that have trust relationships based on such domains, such as within a forest, Kerberos is always usedexcept in one situation. The exception is when a resource is accessed using an IP address rather than a host name. Kerberos is based on host names. Because Windows DNS does not create reverse lookup zones by default, the protocol cannot rely on a way to resolve IP addresses to host names . Therefore, it always falls back to either NTLM or NTLMv2 in that situation. As described earlier, the choice of NTLM or NTLMv2 depends on the configuration of the client.

Figure 11-4 shows the authentication flow in NTLM and LM authentication.

Figure 11-4. LM and NTLM authentication.

There are several very important points to be made about Figure 11-4. First, the client always sends both authentication protocols, regardless of whether the server supports them. While the client is processing the challenge, the server does the same, using the stored hashes discussed earlier. Upon receipt of the response from the client, the server compares the NTLM result it calculated to the result the client sent. If the two match, the client is authenticated. If not, it compares the LM result it calculated to the one the client sent. If neither the NTLM nor the LM results match, the server generates an authentication failure message.

Notice that the algorithm used is DES. Because DES is no longer considered cryptographically secure, neither is the authentication sequence. If an attacker manages to sniff both the challenge and the response off the wire, the password can be brute forced from the authentication sequence. It is just one additional encryption operation. Tools such as LC5 (the latest version of the popular password cracker L0phtCrack) can sniff these sequences off the wire and crack them.

Take another look at Figure 11-4. Pay attention to the secret data used in the authentication process. The only secret used is the hash . The actual response is computed as follows:

1.	Take the 8-byte challenge.
2.	Pad the relevant hash with 5 nulls, making it 168 bits.
3.	Split the hash+nulls into three chunks and use each as a key to encrypt the challenge.
4.	Concatenate the results from Step 3.

As this description shows, the security of the entire authentication algorithm is based on the protection of the hash. In other words, if an attacker has access to the hash, he has everything he needs to authenticate as that user. The hashes are plaintext equivalent . An attacker simply needs a tool that can compute and transmit the response based on an arbitrary hash. This is known as a pass-the-hash attack. Put another way, if bad guys have your password hashes, cracking is unnecessary. You have already been hacked!

NOTE: Password hashes are plaintext equivalent in challenge-response protocols. In other words, if a bad guy has the password hashes, there is no need to crack them. All that is needed is a tool that can generate responses based on arbitrary hashes. This means that hashes must be very well protected. To prevent this type of attack the only solution is to not not let bad guys get to your password hashes.

This does not apply to cached credentials, however. Cached credentials cannot be used for a network authentication. In their raw, uncracked form, they can be used only to authenticate to the system they came from. To be used on other systems, they must be cracked.

The pass-the-hash attack is one of the primary reasons you cannot access the password hashes unless you have the ability to run code as the LocalSystem or an administrator on the server where the hashes are stored. (This is not true on some UNIX variants, by the way. Some of them still give untrusted users access to hashes if they know how to ask properly.) If an attacker can do that, the network has already been compromised. This is, however, not the case with other operating systems that sometimes volunteer hashes to anyone who asks. Note also that salting does nothing to solve this problem. If the hashes are salted, the challenge-response is simply calculated using the salted hash. Salted hashes can still be used in a pass-the-hash attack.

NTLMv2

The most misunderstood authentication protocol in Windows is NTLMv2. NTLMv2 first appeared in Windows NT 4.0 Service Pack 4 and was designed to combat certain weaknesses such as replay vulnerabilities and the weak DES encryption in NTLM. Although NTLMv2 is technically considered a trade secret, certain facts are well known. Consider Figure 11-5.

Figure 11-5. NTLMv2 authentication.

As Figure 11-5 shows, the NTLMv2 protocol takes the place of the NTLM protocol in the authentication messages. A server that is NTLMv2 capable first checks whether the client's response could be an NTLMv2 response. This is done by comparing the length of the response, because the NTLM response is fixed-length and the NTLMv2 response is variable length, but always longer than the NTLM response. If the client's response is not an NTLMv2 response, or if it did not match the NTLMv2 response the server calculated, the server falls back to the same behavior as a non-NTLMv2-compatible server. If all three checks fail, the server generates a failed authentication message. This means that if the client does not support NTLMv2 but the server requires it, the only error message the client will see is "bad username or password." Because there is no negotiation of the authentication protocols, there is no way for the client to know why it failed. Also notice that the NTLMv2 protocol uses the NT hash. There is no separate NTLMv2 hash .

To turn on NTLMv2, you need to tweak the Registry. You must consider three values:

• LMCompatibilityLevel Exposed in Group Policy as Network Security: LAN manager authentication level

• NtlmMinClientSec Exposed in Group Policy as Network security: Minimum session security for NTLM SSP based (including secure RPC) clients

• NtlmMinServerSec Exposed in Group Policy as Network security: Minimum session security for NTLM SSP based (including secure RPC) servers

To keep things concise , we do not discuss NtlmMinClientSec/NtlmMinServerSec in depth here. Those are used for NTLM SSP-based authentication, such as RPC servers. The interested reader is referred to Microsoft Knowledge Base article 147706. LMCompatibilityLevel, however, deserves some mention because it is so misunderstood. There are six levels to this setting, as shown in Tables 11-3 and 11-4.

Table 11-3. Client-Side LMCompatibilityLevel Impact

Level	Group Policy Name	Sends	Accepts	Prohibits Sending
	Send LM and NTLM Responses	LM, NTLM	LM, NTLM, NTLMv2	NTLMv2, Session security
1	Send LM and NTLMuse NTLMv2 session security if negotiated	LM, NTLM, Session security	LM, NTLM, NTLMv2	NTLMv2
2	Send NTLM response only	NTLM, Session security	LM, NTLM, NTLMv2	LM and NTLMv2

Table 11-4. Server-Side LMCompatibilityLevel Impact

Level	Group Policy Name	Sends	Accepts	Prohibits Accepting
3	Send NTLMv2 response only	NTLMv2, Session security	LM, NTLM, NTLMv2	LM and NTLM
4	Send NTLMv2 response only/ refuse LM	NTLMv2, Session security	NTLM, NTLMv2	LM
5	Send NTLMv2 response only/refuse LM and NTLM	NTLMv2, Session security	NTLMv2	LM and NTLM

In all Windows versions except Windows Server 2003, the default setting is 0. In Windows Server 2003, the default setting is 2. That means that no version of Windows will send NTLMv2 authentication by default, and they all accept all three types. In an environment with Windows 95 or 98 clients without the Directory Services Client, the preferred level is 4, which prevents any of the Windows 95- and 98-based systems from connecting to any of the NT-based systems. Should you want to actually allow your Windows 95 and 98 systems to access resources on your NT-based systems, you must configure the NT-based systems no higher than 3. Windows 9x systems acting as servers (!) are unable to process any version of NTLM if they maintain their own accounts. They will, however, support all forms of inbound authentication if they can pass through the authentication to a domain controller. Hence, if the 9x systems are used as servers with share-level passwords, you must leave the setting at 0 on the NT-based systems to allow them to access resources on 9x systems. (On the other hand, if you use 9x systems as servers, you may not be all that interested in security anyway, and probably would not be reading this book.) In a pure Windows 2000 or higher environment, the setting should be set to 4. Setting it to 5 will cause a few things to break on systems olderthan Windows Server 2003 Service Pack 1. Among other things, RRAS may encounter problems if the RRAS server is set to 4. If LMCompatibilityLevel is set to 4 on all systems, nobody would be sending NTLM anyway. Therefore, the impact of allowing inbound NTLM is minimal.

How Users Pick Passwords

Before we go on with a discussion about password attacks, it is important to understand more about how users pick passwords. As mentioned earlier, 94 characters are available on a U.S. English keyboard for use in a password. However, it turns out that users do not actually use most of those characters. To learn more about how users pick passwords, we performed a totally unscientific study of whether users can remember long, say 10-character, passwords. Ninety-nine percent of administrators we asked said not only will users not remember a 10-character password, they will start a mutiny if they are forced to use one. This actually makes sense. A very famous paper that at least one of the authors loves to quote is Miller's 1956 classic "The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information" (http://www.well.com/user/smalin/miller.html). The premise of the paper, which is one of those great papers where it is enough to just read the title, is that humans have limited information-processing capability. We can remember 7 plus or minus 2 chunks of information at a time. The actual number 7 is less important than the fact that information-processing capability is limited. Some say it is 5 plus or minus 2, and we have met a few who say it is 3, although we think they just have a very frustrating set of co-workers . In any case, it is severely limited.

The definition of a chunk also varies with what we are trying to do. In essence, a chunk is the unit that the human needs to remember. In a 10-character random password, a chunk is a symbol, and as Miller would agree, most people cannot remember one of those. In a 10-character pass phrase, on the other hand, that consists of 2 or 3 short words, there are only 2 or 3 chunks, so it is much more likely that users can remember it.

In various works by Proctor et al., ^[1] it is shown that users do resist requirements for stronger passwords. Users are much better at remembering 5-character passwords than 8-character passwords, and, left to their own devices, will not use multiple character sets. The difference in recall time and the accuracy in entering a password also increase significantly when users are required to use complex passwords, although the research shows that they are able to actually do so.

^[1] See, for example, Proctor, R. W., Lien, M. C., Vu, K.-P. L., Schultz, E. E., and Salvendy, G. (2002). "Improving computer security for authentication of users: Influence of proactive password restrictions." Behavior Research Methods, Instruments, & Computers , 34, 163169.

Better passwords improve the resistance to cracking, which although it is not the most efficient form of attack is still interesting. To assess the strength of passwords, we cracked 28,000 passwords from a large domain using a precomputed hash approach (see the "Precomputed Hashes" section later in this chapter) based on a 50-character character set consisting of the uppercase letters (26 characters), the numbers (10 characters), and the 14 "upper row" symbolsthe symbols that appear on the top row of a U.S. English keyboard. ^[2]

^[2] To find the case-sensitive password, the uppercase password was cracked first and then all permutations of upper- and lowercase were tried. This is a very common approach.

The password policy on the domain required at least a 7-character password and at least 3 types of characters. Of the 28,000 passwords, 23,311, or 83 percent, were cracked completely, and an additional 13.16 percent were partially cracked (i.e., either the first or second half of the LM hash was cracked). Although these passwords are not entirely representative of the universe of passwords, it is probably the most complete study on password cracking ever undertaken. Therefore, the statistics throughout the rest of the chapter are based on the analysis done on the 23,311 passwords that were cracked.

Our analysis lends credence to the supposition that users will not pick passwords longer than 9 characters unless forced to. At least 64 percent of the cracked passwords on the domain consisted of 9 characters or fewer. At least 90.37 percent of all the passwords on the domain had fewer than 15 characters. (It is impossible to tell exactly how many had fewer than 15 characters, unless the passwords are captured in clear text, because the only way to tell for sure is to crack all of them.)

It is also interesting to note that the distribution of password lengths does not appear to be normal, as Figure 11-6 shows. Instead, it appears to be skewed to shorter passwords, as allowed by policy. (Note that the left tail of the distribution is cut off due to the minimum password length.)

Figure 11-6. Password length distribution.

Figure 11-6 also shows that 0.07 percent of the passwords were shorter than the minimum 7-character password length. These 16 passwords had either been programmatically set in a way as to circumvent the password policy or were left over from before the policy changed to a 7-character minimum.

Even more interesting, perhaps, is the character set users actually used in their passwords. As you recall, the character set used in the crack consisted of letters, numbers, and the symbols !@#$%^&*()-_+=. That character set has 26+26+10+14=76 characters in English (although if LM hashes are stored, the attacker need consider only 50 characters, since lower case characters are converted to upper case in the storage process), a few more in other languages. However, 80 percent of the characters used in the cracked passwords are chosen from only 32 of those 76 characters. (The 32 common characters are, in order of occurrence, ea1oirn0st2lud!m3hcyg94kSbpM758B.) Even more interesting, 10 percent of passwords were composed solely from those 32 characters! If we know that, and we know that 67 percent of the passwords are between 7 and 9 characters long, there are only 3.63 x 10 ¹³ possible passwords in use, instead of the 8.57 x 10 ¹⁶ allowed by the character set. If the LM hash is stored an optimal password cracker would only need to crack 34,359,739,424 different passwords. This represents roughly 35 bits of entropy, which, although quite a large number, is not nearly as much as you would get if the entire character set had the same probability. This is also very close to the entropy of 1- to 7-character English words (36.40 bits to be exact), indicating that the passwords users pick have many of the same characteristics of the language those users speak.

This same result was also found in a much larger study we performed where we analyzed an extremely large sample of passwords from a very large Web service. In that case, we found that passwords only had 18.25 bits of entropy in them. ^[3] In addition we found that almost 5 percent of the passwords on the Web service were either 1234, password, or 1111.

^[3] Thank you to our colleague Carl Ellison for his help in analyzing these passwords.

Clearly, users are not picking very good passwords and are not using the entire character set to their advantage. This is largely an artifact of language. Users pick passwords primarily from the characters that are most common in the language, and, as pointed out earlier, they use poor passwords unless forced otherwise . In the case of the Web service, the only password restriction was that they had to be 4 characters long. The restrictions in the case of the corporate domain gave us much higher entropy, although the passwords would not stand up to a sustained cracking attack even then.

Ideally, we would get rid of passwords and use other means of authentication; because it is very unlikely that we can do that in the foreseeable future, however, our best option is to help users generate better passwords. To that end, we now turn to how passwords are attacked so that we can understand how to make them more resilient against attacks.

How Passwords Are Attacked

Passwords are essentially attacked two ways: in online and in offline attacks. An online attack is essentially password guessing. Password guessing is where someone is sitting at the console or at a remote machine trying passwords. In an offline attack, the attacker has access to the stored hashes and can attack them at his leisure. This is the type of attack we usually refer to as cracking . Because guessing is a much more valid attack, we cover that first.

Password Guessing

The simple truth about guessing is that if an account has even a relatively complex password, guessing will not succeed . Even when we have only 18.25 bits of entropy, as in the case above, the attacker would need to try at least 155,872 passwords before guessing succeeds. If guessing succeeds, the core problem is a weak password. Let us look at some examples. A simple password-guessing tool would only be able to try a couple of passwords per second. With a perfect dictionary, assuming passwords have only 18.25 bits of entropy, it would take only a day to guess one password. However, increasing entropy by only 7 bits, to 25 bits, it now takes 97 days to guess a password. This could be accomplished by making three substitutions in the password, or by lengthening it by a mere two characters, or a combination thereof.

We have heard rumors of optimized password-guessing tools that can guess about 300 passwords per second. Using such a tool it would take only about 10 minutes to guess a password with 18.25 bits of entropy in the dictionary. To get at least 90 days of resiliency against such a tool, a password must have at least 33 bits of entropy. As we showed earlier, the passwords used on the corporate domain easily fulfilled that requirement, even though they were fairly easily crackable.

To protect against guessing, which is a valid attack, we just need to increase the strength of our passwords. This does not require extremely long or complicated passwords. We do not need perfect security here, we just need good enough security. If we can simply increase the passwords to be at least 7 or 8 characters long and have 3 of the 4 character types, we have accomplished that objective as long as they expire every 90 days. This would be sufficient protection against password guessing. Besides, there is at least some hope that the administrator would review the security log for excess password tries at least once every three months!

NOTE: If a password-guessing attack ever succeeds, the problem is extremely poorly chosen passwords, such as a short common dictionary word, possibly with some symbol appended. In practice, guessing attacks are remarkably successful.

Cracking

If you ask just about any IT administrator or information security professional how to attack passwords, just about all of them will start discussing cracking . Cracking is a form of offline attack used when the attacker has obtained the raw hashes. We mentioned this earlier, but it is worth repeating here: If bad guys have access to your hashes you have already been hacked! Cracking passwords is not needed to use those hashes to authenticate. Nevertheless, password cracking is commonly used by attackers because of the lack of pass-the-hash tools, and therefore it is worthwhile to discuss it here.

Cracking works by generating test passwords, hashing them, and then comparing the result to the stored hash. It is much, much faster than guessing. On a 1.7 GHz Pentium 4 M laptop, we were able to test 1,850,000 passwords per second in a brute-force attack against the LM hashes using LC5. Interestingly, the test rates were about the same against NT hashes, even though computing an MD4 hash should be considerably faster than computing an LM hash. More than likely, this is due to the LM algorithm in LC5 being much more optimized than the MD4 algorithm.

Using moderate-class hardware, an attacker can typically generate and test 3,000,000 passwords a second. In that case, it will take only 70 days to crack all the 7- to 9-character passwords based on the 32 commonly used characters discussed earlier. If LM hashes are stored, enabling the attacker to crack only the 7-, 1-, and 2-character passwords (remember that an 8-character password is actually stored as one 7- and one 7-character password when stored using an LM hash), it would take only 2 hours! If LM hashes are stored, and the passwords are based on the full 92-character set used on a U.S. English keyboard, it would take 108 days to crack all passwords. Removing the LM hashes extends that time to 2,521 years.

NOTE: Removing LM hashes extends crack times by almost four orders of magnitude!

Defending Against Password Cracking

Many people want to know how to defend against password cracking. Consider that on Windows, to crack domain passwords, the attacker has to have system-level access to the domain controller. If an attacker has already compromised a domain controller, cracking passwords is only a secondary problem. The proper way to defend against password cracking is to not allow attackers to have system access on your domain controllers; in other words, defense in depth!

Most attackers will crack passwords. In light of the fact that cracking passwords does not yield any additional privileges beyond the domain controller, this seems illogical. Why do they crack passwords? Mostly, it is out of the hope that someone has an account on a different system in a different domain with the same username and password. That is called an administrative dependency, and we discussed that in Chapter 8, "Security Dependencies." In some cases, we also see password cracking performed by malicious, but relatively incompetent, administrators to attack other administrators. The proper way to deal with such problems is to turn those administrators into ex- employees and then rebuild the domain.

Cracking Process

In practice, cracking usually proceeds in steps. First the attacker tries passwords from a dictionary. If that does not work, the next step is to modify the passwords in the dictionary using a hybrid attack. In this type of attack, a password cracking tool takes a dictionary word and appends characters, tries common substitutions, and so on. For instance, you have probably at some point used a password with an at sign (@) rather than an a, a dollar sign ($) rather than an s, an exclamation point (!) rather than an I or a 1, and so on. Well, you were almost certainly not the first one to think of that. In fact, every decent password cracker knows how to do those substitutions, too, which means they add only very little to the strength of your password.

If a hybrid attack fails, the attacker typically moves on to a brute-force attack, where he tries every single possible combination of passwords. At this point the only thing that stands between the attacker and your password is the strength of the algorithm. In practical use, the LM hash is almost always attacked first because it is so much weaker. Although cracking NT hashes technically is fasterbecause generating MD4 hashes is much more efficient than performing two DES encryptionsthe fact that there are so many more possible passwords makes NT hashes much more resilient to cracking. After the case-insensitive password is found based on the LM hash, the attacker just tries all upper- and lowercase combinations to obtain the case-sensitive password. In practice, this entire process is automated by tools such as LC5.

Precomputed Hashes

Recently, a new way to crack passwords has become common. Tools using so-called precomputed hashes can crack many passwords in mere minutes. This is accomplished by precomputing the hashes at the attacker's leisure and storing them. At runtime, the password cracker just looks up the hashes in the list of precomputed hashes. Precomputing the hashes obviously takes considerable time, but these precomputed hashes can be reused many times, making multiple cracks much more efficient. There are even Web services available now based on precomputed hash tables generated through a distributed process.

Precomputed hashes in and of themselves are nothing new. Quakenbush Password Appraiser did this in 1998. However, what is new is the theory and practice behind the space-time tradeoff, applied to password cracking by Dr. Phillippe Oechslin (http://lasecwww.epfl.ch/philippe.shtml). The time-space tradeoff avoids having to store all possible hashes, which still would take more storage than exists in the universe. If you store all the NT hashes up to 14 characters for the 76-character character set, it would require 5,652,897,009 exabytes of storage, which, as it turns out, is far more than any file system today can support. Storing all the LM hashes, although it only takes 310 terabytes, is still basically infeasible. What Dr. Oechslin came up with was a time-space tradeoff mechanism whereby you only store a portion of the hash and its associated passwords. This cuts storage requirements drastically, and with only 17 gigabytes of storage you can store the LM hashes for the same character set.

Many people have called upon Microsoft to break precomputed hash attacks by modifying its password storage algorithms to use salted hashes. However, doing so would also necessitate a change in the authentication protocols. Since salted password hashes are not immune to a pass-the-hash attack, which is much faster than a precomputed hash attack, creating a new authentication protocol to support salted hashes would buy us no security at all. If we make password hashes uncrackable, the attackers would simply not crack them, because it is not necessary. The proper solution instead is to use an authentication mechanism, such as token-based or smart card authentication, which is immune to both attacks. Such mechanisms are supported in Windows 2000 and higher, and are highly recommended in all organizational environments.

One method of password cracking that does not rely on access to password hashes involves capturing the challenge-response sequence off the wire and then cracking against that. This requires a significant amount of additional computation. For example, if we have a seven-character password, and we allow sending LM hashes, four DES-encryption operations are necessary to crack the password (one to generate a test password hash, and three more to generate the test response based on the challenge and the test hash). In other words, it takes four times longer to crack passwords this way than what it would take if the attacker has access to raw hashes. Obviously, weak passwords will fall very quickly, but even reasonably strong passwords would not take long to crack using this mechanism. If we can crack 750,000 passwords per second, we would crack the corporate passwords above in 6 hours using a perfect dictionary. Of course, having a perfect dictionary is pretty unlikely. If we have perfectly random 7- to 9-character passwords composed of the 76-character set used earlier, it would instead take 3,261 years to crack one of them. Clearly one defense against cracking captured challenge-response credentials is to use passwords that appear totally random. Another defense is to turn off LM and NTLM authentication, as discussed earlier. Finally, a really effective method is to physically control the network to prevent anyone from actually capturing the credentials. This includes using properly protected wireless networks, as we discussed in Chapter 10, "Preventing Rogue Access Inside the Network."

There are two final things to remember about cracking passwords. First, without either challenge-response captures or hashes, nobody will crack your passwords.

NOTE: If the bad guy has access to your hashes, you have already been hacked! The problem is not the cracking itself at that point.

Second, no protocols can protect bad passwords. If the attacker can reduce the search space by using heuristics or a dictionary, the time to crack a password will be considerably shorter than we have seen.

NOTE: You cannot protect bad passwords with good password storage techniques, proper protocols, or password-guessing controls. Bad passwords will get broken no matter what.

Attacking Cached Credentials

In early 2005, a tool to extract cached credentials was made available on the Internet. A companion tool patches the password cracking tool John The Ripper to crack against cached credentials. This is the first time a tool to extract and crack those credentials has been made available widely, and people are understandably worried about it. Should you be?

The answer to whether you should be worried about cached credentials cracking lies primarily in your operational practices, and in the "Password Best Practices" section later in this chapter we outline how to improve them to protect cached credentials. The process by which they are cracked is largely the same, although significantly slower, as the process that is used to crack any other password. For instance, although you can use a precomputed hash attack to crack the inner hash, you cannot use one to crack the outer hash of a cached credential. This means that cracking cached credentials takes substantially longer than cracking ordinary hashes. Based on benchmarks given by cracking tools, it should take roughly three times longer to crack cached credentials, and they cannot be cracked using precomputed hashes because they are salted.

We get asked repeatedly whether you should prefer to use local passwords instead of relying on cached domain credentials. Apart from the inconvenience associated with doing so, consider that cached credentials are immune to pass-the-hash attacks and take roughly 3-5 times longer to crack than regular hashes. In all likelihood users will use the same password on both their local account and their domain account, should they be forced to have both. Thus, whereas a stolen laptop would yield a password hash that can be used to authenticate to other resources in the case of a local account, in the case of a cached credential, the password verifier is only usable locally. That means you should still prefer cached credentials over local credentials, even in the face of the new tool.

Keystroke Loggers

One final method of attacking passwords is to use a keystroke logger. A keystroke logger is a device or a piece of software that captures keystrokes and either stores them or transmits them to the attacker. Such attacks take place on the host where the password is being used, and have been quite common for many, many years. The earliest forms were simply fake logon screens that enticed a victim to type a password and then stored what was typed. At one point, 90 percent of the systems at one of the authors high school had such fake logon screens on them. This was the primary reason for adding the Secure Attention Sequence (SAS) to Windows. The SAS, better known as Ctrl+Alt+Del, or the three-finger salute, is trapped by the kernel. Thus, even if a user is logged on and has created a fake logon screen, typing the SAS will cause a system dialog to come up, making it obvious that the logon screen is fake. This has not always been successful as a countermeasureone of the authors once had a very successful attack on a lab he was running using a fake Windows NT 4.0 logon screenbut it is an effective one if properly used.

Modern keystroke loggers are much more sophisticated. Some come as software, even kernel-mode software, that has a built-in Web server for remote control. There are also hardware devices available for purchase that fit between the keyboard and the computer. Less than $20 will get you one of these with sufficient memory to hold a day's worth of typing.

One of our favorite stories is of a friend of ours who was in Latin America. As with many of us when traveling, he was experiencing e-mail withdrawal, so when he found an Internet caf , he immediately entered, handed over his corporate credit card, and sat down. He opened a Web browser, typed in the corporate Outlook Web Access address, and logged on. Right after typing his password, he received a dialog like the one in Figure 11-7.

Figure 11-7. Do you type your password on public-access computers?

In general, you should assume that all public-access computers and kiosks have keystroke loggers installed. Most of them probably do. We have found them on kiosks, at Internet caf s, on the commnet machines at Microsoft TechEd, and even on one of the kiosks we put in the lobby of all buildings at Microsoft. If you are one of the unfortunates who have to run kiosks, you need to develop a good mechanism for re-imaging the computers frequently (at least after a day) and adequate physical access controls to prevent anyone from installing hardware keystroke loggers. We highly recommend never using a public-access machine for any kind of sensitive work. Strong passwords provide no defense against keystroke loggers. In fact, some smart card solutions provide no defense against keystroke loggers either. It depends on how the cryptographic service provider is implemented. Play it safe. Do not use public-access computers, and mention in your user security policy that nobody else should either.