15.3 LM Challenge/ResponseIn plaintext mode, the client proves that it knows the password by sending the password itself to the server. In challenge/response mode, the goal is to prove that the password is known without risking any exposure. It's a bit of a magic trick. Here's how it's done:
Figure 15.1. Challenge/responseThe server generates a random challenge, which it sends to the client. Both systems encrypt the challenge using the secret encryption key. The client sends its result ( rc ) to the server. If the client's result matches the server's result ( rs ), then the two nodes have matching keys.
That's a rough, general overview of challenge/response. The details of its use in LAN Manager authentication are a bit more involved, but are fairly easy to explain. As we dig deeper, keep in mind that the goal is to protect the password while still allowing authentication to occur. Also remember that LM challenge/response was the first attempt to add encrypted password support to SMB. 15.3.1 DESThe formula used to generate the LM response makes use of the U.S. Department of Commerce D ata E ncryption S tandard (DES) function, in block mode. DES has been around a long time. There are a lot of references which describe it and a good number of implementations available, so we will not spend a whole lot of time studying DES itself. [6] For our purposes, the important thing to know is that the DES function as used with SMB takes two input parameters and returns a result, like so:
result = DES( key, source ); The source and result are both eight-byte blocks of data, the result being the DES encryption of the source . In the SNIA doc, as in the Leach/Naik draft, the key is described as being seven bytes (56 bits) long. Documentation on DES itself gives the length of the key as eight bytes (64 bits), but each byte contains a parity bit so there really are only 56 bits worth of " key " in the 64-bit key . As shown in Figure 15.2, there is a simple formula for mapping 56 bits into the required 64-bit format. The seven byte string is simply copied , seven bits at a time, into an eight byte array. A parity bit (odd parity) is inserted following each set of seven bits (but some existing DES implementations use zero and ignore the parity bit). Figure 15.2. DES key manglementConverting a seven byte key (56 bits) into an eight byte key with odd parity for use with DES. Some DES implementations perform this step internally.
The key is used by the DES algorithm to encrypt the source . Given the same key and source , DES will always return the same result . 15.3.2 Creating the ChallengeThe challenge needs to be very random, otherwise the logon process could be made vulnerable to "replay" attacks. A replay attack is fairly straightforward. The attacker captures the exchange between the server and the client and keeps track of the challenge, the response, and the username. The attacker then tries to log on, hoping that the challenge will be repeated (this step is easier if the challenge is at all predictable). If the server sends a challenge that is in the stored list, the attacker can use the recorded username and response to fake a logon. No password cracking required. Given that the challenge is eight bytes (64 bits) long, and that random number generators are pretty good these days, it is probably best to create the challenge using a random number function. The better the random number generator, the lower the likelihood (approaching 1 in 2 64 ) that a particular challenge will be repeated. The X/Open doc (which was written a long time ago) briefly describes a different approach to creating the challenge. According to that document, a seven-byte pseudo-random number is generated using an internal counter and the system time. That value is then used as the key in a call to DES() , like so: Ckey = fn( time( NULL ), counter++ ); challenge = DES( Ckey, "????????" ); (The source string is honest-to-goodnessly given as eight question marks.) That formula actually makes a bit of sense, though it's probably overkill. The pseudo-random Ckey is non-repeating (because it's based on the time), so the resulting challenge is likely to be non-repeating as well. Also note that the pseudo-random value is passed as the key , not the source , in the call to DES() . That makes it much more difficult to reverse and, since it changes all the time, reversing it is probably not useful anyway. As Andrew Bartlett [7] points out, however, the time and counter inputs are easily guessed so the challenge is predictable, which is a potential weakness. Adding a byte or two of truly random "salt" to the Ckey in the recipe above would prevent such predictability.
Using a plain random number generator is probably faster, easier, and safer. 15.3.3 Creating the LM HashLM challenge/response authentication prevents password theft by ensuring that the plaintext password is never transmitted across a network or stored on disk. Instead, a separate value known as the "LM Hash" is generated. It is the LM Hash that is stored on the server side for use in authentication, and used on the client side to create the response from the challenge. The LM Hash is a sixteen byte string, created as follows :
That outline would make a lot more sense as code, wouldn't it? Well, you're in luck. Listing 15.1 shows how the steps given above might be implemented. Listing 15.1 LM Hash functionstatic const uchar SMB_LMHash_Magic[8] = { 'K', 'G', 'S', '!', '@', '#', '$', '%' }; uchar *smb_LMHash( const uchar *password, uchar *result ) /* ---------------------------------------------------- ** * Generate an LM Hash. * password - pointer to the raw password string. * result - pointer to at least 16 bytes of memory * into which the LM Hash will be written. * Returns a pointer to the LM Hash (== result). * ---------------------------------------------------- ** */ { uchar tmp_pass[14] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; uchar *hash; uchar K1[7]; uchar K2[7]; int i; /* Copy at most 14 bytes of password to tmp_pass. * If the string is shorter, the unused bytes will * be nul-filled. */ (void)strncpy( tmp_pass, password, 14 ); /* Convert to uppercase. */ for( i = 0; i < 14; i++ ) tmp_pass[i] = toupper( tmp_pass[i] ); /* Split tmp_pass into two 7-byte keys. */ (void)memcpy( K1, tmp_pass, 7 ); (void)memcpy( K2, (tmp_pass + 7), 7 ); /* Use the keys to encrypt the 'magic' string. * Place each encrypted half into the result * buffer. */ hash = DES( K1, SMB_LMHash_Magic ); (void)memcpy( result, hash, 8 ); hash = DES( K2, SMB_LMHash_Magic ); (void)memcpy( (result + 8), hash, 8 ); /* Return a pointer to the result. */ return( result ); } /* smb_LMHash */ 15.3.4 Creating the LM ResponseNow we get to the actual logon. When a NEGOTIATE PROTOCOL REQUEST arrives from the client, the server generates a new challenge on the fly and hands it back in the NEGOTIATE PROTOCOL RESPONSE . On the client side, the user is prompted for the password. The client generates the LM Hash from the password, and then uses the hash to DES-encrypt the challenge. Of course, it's not a straightforward DES operation. As you may have noticed, the LM Hash is 16 bytes but the DES() function requires 7-byte keys. Ah, well... Looks as though there's a bit more padding and chopping to do.
Once again, we provide demonstrative code. Listing 15.2 shows how the LM Response would be generated. Listing 15.2 LM Response functionuchar *smb_LMResponse( const uchar *LMHash, uchar *chal, uchar *resp ) /* ---------------------------------------------------- ** * Generate an LM Response * LMHash - pointer to the LM Hash of the password. * chal - Pointer to the challenge. * resp - pointer to at least 24 bytes of memory * into which the LM response will be written. * Returns a pointer to the LM response (== resp). * ---------------------------------------------------- ** */ { uchar P21[21]; uchar K[7]; uchar *result; int i; /* Copy the LM Hash to P21 and pad with nuls to 21 bytes. */ (void)memcpy( P21, LMHash, 16 ); (void)memset( (P21 + 16), 0, 5 ); /* A compact method of splitting P21 into three keys, * generating a DES encryption of the challenge for * each key, and combining the results. * (i * 7) will give 0, 7, 14 and * (i * 8) will give 0, 8, 16. */ for( i = 0; i < 3; i++ ) { (void)memcpy( K, (P21 + (i * 7)) , 7 ); result = DES( K, chal ); (void)memcpy( (resp + (i * 8)), result, 8 ); } /* Return the response. */ return( resp ); } /* smb_LMResponse */ The server, which has the username and associated LM Hash tucked away safely in its authentication database, also generates the 24-byte response string. When the client's response arrives, the server compares its own value against the client's. If they match, then the client has authenticated. Under User Level security, the client sends its LM Response in the SESSION_SETUP_ANDX.CaseInsensitivePassword field of the SESSION SETUP request (yes, the LM response is in the SESSION SETUP REQUEST ). With Share Level security, the LM Response is placed in the TREE_CONNECT_ANDX.Password field. 15.3.5 LM Challenge/Response: Once More with FeelingThe details sometimes obfuscate the concepts, and vice versa. We have presented a general overview of the challenge/response mechanism, as well as the particular formulae of the LAN Manager scheme. Let's go through it once again, quickly, just to put the pieces together and cover anything that we may have missed. The LM Hash
The Challenge
The Logon
The LM Response
The SESSION SETUP ANDX RESPONSE
Well, that's a lot of work and it certainly goes a long way towards looking complicated. Unfortunately, looking complicated isn't enough to truly protect a password. LM challenge/response is an improvement over plaintext, but there are some problems with the formula and it turns out that it is not, in fact, a very big improvement. Let's consider what an attacker might do to try and break into a system. We've already explained the replay attack. Other common garden varieties include the "dictionary" and the "brute force" attack, both of which simply try pushing possible passwords through the algorithm until one of them returns the same response as seen on the wire. The dictionary attack is typically faster because it uses a database of likely passwords, so tools tend to try this first. The brute force method tries all (remaining) possible combinations of bytes, which is usually a longer process. Unfortunately, all of the upper- casing , nul-padding, chopping, and concatenating used in the LM algorithm makes LM challenge/response very susceptible to these attacks. Here's why: The LM Hash formula pads the original password with nul bytes. If the password is short enough (seven or fewer characters ) then, when the 14-byte padded password is split into two seven-byte DES keys, the second key will always be a string of seven nuls. Given the same input, DES produces the same output: 0xAAD3B435B51404EE = DES( "0xAAD3B435B51404EE = DES( "\0\0\0\0\0\0\0", "KGS!@#$%" )0xAAD3B435B51404EE = DES( "\0\0\0\0\0\0\0", "KGS!@#$%" )0xAAD3B435B51404EE = DES( "\0\0\0\0\0\0\0", "KGS!@#$%" )0xAAD3B435B51404EE = DES( "\0\0\0\0\0\0\0", "KGS!@#$%" )0xAAD3B435B51404EE = DES( "\0\0\0\0\0\0\0", "KGS!@#$%" )0xAAD3B435B51404EE = DES( "\0\0\0\0\0\0\0", "KGS!@#$%" )0xAAD3B435B51404EE = DES( "\0\0\0\0\0\0\0", "KGS!@#$%" )", "KGS!@#$%" ) which results in an LM Hash in which the second set of eight bytes are known:
To create the LM Response, the LM Hash is padded with nuls to 21 bytes, and then split again into three DES keys:
Now the problem is obvious. If the original password was seven bytes or less, then almost two- thirds of the encryption key used to generate the LM Response will be a known, constant value. The password cracking tools leverage this information to reduce the size of the keyspace (the set of possible passwords) that needs to be tested to find the password. Less obvious, but clear enough if you study the LM Response algorithm closely, is that short passwords are only part of the problem. Because the hash is created in pieces, it is possible to attack the password in 7-byte chunks even if it is longer than 7 bytes. Converting to uppercase also diminishes the keyspace, because lowercase characters do not need to be tested at all. The smaller the keyspace, the faster a dictionary or brute-force attack can run through the possible options and discover the original password. [11]
|