Wednesday, April 20, 2011

LM/NTLMv1 Challenge/Response Authentication Explained

The Microsoft Windows platform uses a myriad of protocols to authenticate users across a network. Two such protocols widely in use today are the LANMAN challenge/response and NTLMv1 protocols. Whilst newer, more secure protocols (such as NTLMv2) are ready to take their place, LANMAN challenge/response and NTLMv1 are still widely deployed today for reasons of interoperability. As with most things Microsoft-related, ubiquity often equates to exploitability.

In this two part series I will discuss how the LANMAN challenge/response and NTLMv1 protocols operate, how malicious users can take advantage of their shortcomings, and best practice recommendations for securely deploying these protocols.

Microsoft Windows supports two primary algorithms for locally authenticating users. These algorithms generate what’s known as an “LM Hash” or an “NT Hash”.

Enabled by default in Windows NT, 2000, XP, and Server 2003, the LM Hash has become synonymous with bad hashing practices over the years. Used for backward compatibility, this older hashing method has several inherit flaws, making it trivial for attackers to crack LM Hashes within minutes.

The second, more secure, hashing algorithm generates what’s known as an NT Hash. Exclusively on by default in Windows Vista, 7, and Server 2008, this hash is generated using the MD4 hashing algorithm.
Note: By default, Windows XP stores both the LM Hash and the NT Hash.

Whilst this reading does not require a technical understanding of how the NT Hash and the LM Hash are generated, some readers may like to broaden their understanding of how these hashes are generated. The following paper provides an in depth discussion on the topic.

Before we begin looking at the Microsoft network authentication protocols, it is important to note that LANMAN challenge/response and NTLMv1 are the same protocol except for one key difference: LANMAN challenge/response utilises the locally stored “LM Hash” whilst NTLMv1 uses the locally stored “NT Hash”. Aside from this, the protocols (for all intensive purposes) operate exactly the same way.

The LANMAN challenge/response and NTLMv1 protocols authenticate users in the following manner:
1. Client sends an authentication request to the Server.
2. A protocol negotiation occurs between the Client and Server.
3. The Server sends the Client a (pseudo-random) 8-byte challenge.
4. The Client sends a 24-byte response.
5. The Server authenticates the Client.
The Client’s response is made up of the following steps:
  1. Split the locally stored 16-byte hash (LM Hash for LANMAN challenge/response or NT Hash for NTLMv1) into three 7-byte portions.
  2. Using the DES encryption algorithm, encrypt the Server’s challenge three separate times using each of the keys derived in Step 1.
  3. Concatenate the response of all three outputs.
Now, at first glance this protocol seems fairly sensible. But you may have noticed something in Step 1 of the Client’s response. If the hash (LM or NT) is 16-bytes long, how do we break it up into three 7-byte portions? i.e. 7 does not divide into 16 evenly.
To combat this unevenness, the LANMAN and NTLMv1 algorithms pad the third key with 5 nulls. By doing this, we now have three evenly portioned keys.
So, the response process in its entirety looks something like this:
Now that we have an understanding of how the LANMAN challenge/response and NTLMv1 protocols work, let’s take a look at some of the deficiencies these protocols inherit.
  1. There is no “diffusion” within the protocol. That is, there are three separate parts to the response that could individually be attacked. Diffusion would ensure each part of the DES output relied on the previous – increasing the overall complexity.
  2. DES is old and considered cryptographically weak by many.
  3. The third DES key is weak. As the third DES key is padded with 5 nulls, there are only 2^16 possible unknown values. This would take a modern computer seconds to crack.
  4. There is a lack of randomness. The only randomness occurring within the algorithm is that provided by the pseudo-random challenge generated by the server.
In Part 2 of this series I will demonstrate how attackers can take advantage of the aforementioned deficiencies in the LANMAN challenge/response and NTLMv1 protocols.