The Sins Of NTLMv1

In the past year, one particular configuration in our clients' Active Directory (AD) domains has repeatedly caught our attention - the usage of NTLMv1. NTLMv1 is an outdated version of the NTLM authentication protocol. The NTLM protocol itself is considered insecure, and even Microsoft recommends switching to Kerberos, the recommended standard for AD domains, as mentioned here.

NTLM and NTLMv2 authentication is vulnerable to various malicious attacks, including SMB replay, man-in-the-middle attacks, and brute force attacks. Reducing and eliminating NTLM authentication from your environment forces the Windows operating system to use more secure protocols, such as the Kerberos version 5 protocol, or different authentication mechanisms, such as smart cards.

In this blog entry, we will take a look at why the NTLMv1 protocol in particular is insecure and explore two of the most popular attack vectors against the protocol: brute-force attacks and relaying attacks. Moreover, we will take a closer look at one particular type of brute-force attacks - rainbow table attacks.

NTLMv1 Under The Hood

The NTLMv1 authentication protocol is a fairly straight-forward challenge-response protocol. The client first sends a NEGOTIATE_MESSAGE to the server, indicating that it wants to authenticate itself. The server sends a challenge value to the client, which is known as the CHALLENGE_MESSAGE. The client uses the NTLM hash of its (or a user-supplied) password as an encryption key to encrypt the challenge value and sends the encrypted value back to the server. This is the RESPONSE. The server then forwards the RESPONSE and the CHALLENGE_MESSAGE to a domain controller, which checks the validity of the response. If the check passes, the authentication process is considered to be successful.

NTLMv1 uses the Digital Encryption Standard (DES) algorithm. The RESPONSE message actually consists of three concatenated DES ciphertexts. The reason for this is the length difference between NTLM hashes and DES keys. DES uses 7-byte keys, while NTLM hashes are 16-byte. The NTLM hash is therefore appended with five 0-bytes, resulting in a 21 byte total, which is then split into three 7-byte keys. These keys are then used to encrypt the server challenge, resulting in three DES ciphertexts which are concatenated together to form the response message.

K1 | K2 | K3 = NTLM-Hash | 5-bytes-0

RESPONSE = DES(K1,C) | DES(K2,C) | DES(K3,C)

Brute-Force Attacks

DES is a very old algorithm, which is considered insecure by modern standards. The reason for this is the small 7-byte key. This results in a very small keyspace of 2⁵⁶,  making the algorithm susceptible to brute-force attacks. The situation is further exascerbated by the fact that the three ciphertexts in the RESPONSE message are completely independent of each other, meaning that they can all be cracked independently of each other. The third ciphertext is particularly egregious, since it consists of two random bytes followed by five 0-bytes, effectively resulting in a keyspace of 65 536, or 2¹⁶ . Therefore, cracking the third ciphertext is trivial, even with limited computational resources. 

 Cracking the first two ciphertexts is, however, more challenging. With modern hardware, it is possible to directly brute-force the entire 2⁵⁶ keyspace. In our experience, this can be achieved by renting high-end GPUs, e.g. via websites such as trooper.ai. With appropriate hardware, an NTLMv1 hash can be cracked within a day, with financial costs around 50€, making it affordable even for opportunistic attackers.

There is, however, an even faster way to crack NTLMv1 hashes - rainbow tables. The problem of cracking a hash is a case of the problem of calculating the pre-image of a given output of a one-way function (essentially a function without an easily computible inverse function). There are two naive approaches to solving this problem: computing all possible input-output pairs on-the-fly until the pre-image is found and storing all possible input-output pairs in a lookup table. The first method requires no additional storage, but can take a long time, while the second method offers instant lookup times, but requires large amounts of storage.

Rainbow tables are data structures that attempt to optimize the time-memory trade-off (TMTO) between these two methods. Even in the case of DES with a small keyspace, brute-forcing all possible inputs can take a prohibitively long time without access to state-of-the-art hardware. Furthermore, storing a lookup table for all possible DES input-output pairs is even more prohibitive, requiring around 150 petabytes of storage.

Cracking hashes with rainbow tables is done in two phases: the offline phase and the online phase. During the offline phase, the rainbow table is constructed, while the online phase is the actual pre-image search. Rainbow tables offer an alternative to the naive methods by storing not input-output pairs, but rather starting and endpoints of chains. Chains are computed by repeatedely applying the hash function we want to crack and a reduction function. The reduction function maps hashes back to the set of possible inputs in a uniformly distributed manner. The idea of a reduction function is to essentially rebuild the input space, in order to cover as much of the actual input space as possible, effectively simulating an inverse function. In practice, a family of reduction functions is used to reduce chain collisions, i.e. if two chains share an intermediate point, then both chains will produce the same set of points from then on. A typical reduction function is   r_i (x) = (x + i) mod N, for i ∈ { 1, ... , t -1 } where N  is the size of the input space. The structure of a rainbow table is depicted below, where t  is the chain length and m  is the number of starting and endpoint pairs. Note that only the starting points S_i  and endpoints E_i  are stored.

When building rainbow tables, the most important consideration to make is the choice of values for t und m.  These two values represent the trade-off between time and memory. The longer the chains stored in the rainbow table are (i.e. the higher the value of t is), the less starting and endpoint pairs have to be stored, since more hashes are covered by the chains' intermediate points. However, this would result in a slower online phase, i.e. slower lookup times. The opposite also holds, i.e. the more chains are stored (the higher the value of m), the shorter the chains can be. The trade-off is, of course, larger storage space requirements. Common values for
t are 10 000 and 100 000.  For clean maximal size rainbow tables, the expected number of chains for length t is given by
m_t^max  ≈ 2N/(t+2) , where N  is the size of the input space. A clean rainbow table is one that only contains unique endpoints. A rainbow table is of maximum size when the probability of adding a new unique endpoint to the table is negligible. Thus, we can compute the number of chains for t = 10 000 and t = 100 000 for our DES cracking problem. For t = 100 000, we have:

 This corresponds to around 2,8 terrabytes of storage, which is a reasonable amount, even for home PCs. Similarly, for t = 10 000, we get approximately 28 terrabytes of storage, which requires more investment, but is still feasible.

 The computation costs for constructing such a rainbow table, however, would require a higher investment. Experiments with the latest techniques for constructing rainbow tables for an input space of 2⁴² required around eight hours with a 128-core processor. For an input space of 2⁵⁶, the runtime would be prohibitively large (the runtime increases linearly with the size of the input space). To construct rainbow tables of maximum size would require utilizing multiple modern GPUs. As another possibility, one could use an alternative smaller input space, e.g. by utilizing a large wordlist. This would reduce the success probability of finding the correct pre-image, but would make the precomputation phase more affordable.

During the online phase, the search for the pre-image x of a hash y = h(x) proceeds in a column-by-column manner, starting at the last column. The search starts by looking up an endpoint E_i , so that E_i = r_t-1(y) ,  i.e. we want to verify if applying h  to the intermediate point X_i,t-1  would result in the hash y. If such a point is found, then the chain is recomputed to see if h(X_i,t-1) = y.  If yes, the search is ended with x = X_i,t-1 . If not, this match was a false alarm. In the case where a false alarm or no suitable endpoint is found, the search proceeds to the next column of the rainbow table, i.e. r_t-1(h(r_t-2(y)) is computed and the process described above is repeated for this value. In this case, we are effectively verifying if h(X_i,t-2) = y. The search then proceeds column-by-column until either a match is found or the table is exhausted.

 The reason this process works is because the reduction functions construct the input space in a uniformly random manner. Therefore, a very high number of hashes are "covered" by the chains in the rainbow table. When cracking password hashes, we technically do not need to find the exact password, but rather an input that results in the same hash. Due to this, we can be reasonably sure that the hash we want to crack will be found in one of the chains of the rainbow table. In practice, to further reduce chain collision probability, several rainbow tables with different reduction function families are used. The success probability for l clean maximum size rainbow tables is  1 - e^-2l . For l = 4, this results in a probability of approximately 99,97%.

When launching rainbow table attacks against NTLMv1, the tables have to be precomputed for a particular challenge value. This means that when imitating a server, the attacker must always send the same challenge in order for the rainbow tables to be of any use. A popular challenge value is 1122334455667788, since there are services that have computed rainbow tables for this challenge value. However, using this challenge value is noisy, since modern EDRs are configured to generate alerts when detecting it. Therefore, in order to perform a rainbow table attack in an OPSEC-safe manner, a custom challenge value should be used when precomputing rainbow tables.

 Rainbow table attacks can be effectively mitigated by salting the inputs to the hash function. Since rainbow tables have to be precomputed, an attacker would have to account for every possible salt value, and would therefore have to compute separate rainbow tables for every possible salt value. For example, introudcing a 16-byte salt would require the attacker to store 2¹²⁸ rainbow tables. From the analysis above, we can see that even for our relatively modest case, there is not enough storage capacity in the entire world to accomodate such needs. However, we can see that the only random value in the entire NTLMv1 protocol, i.e. the challenge, is effectively controlled by the attacker. This is one reason why a client challenge value was introduced in the newer NTLMv2 protocol, to introduce another random value that is outside of the attacker's control, which in the context of brute-force attacks can be seen as a salt value.

Relay Attacks

Another short-coming of the NTLMv1 protocol is that the data exchanged during the authentication process is in no way bound to a particular session. In other words, the client cannot verify that the challenge actually came from the server it is authenticating to, while the server cannot verify whether a response was actually addressed to it. This means that if this data is intercepted, it can be forwarded by the attacker to an arbitrary target. Such attacks are known as relay attacks.

A relay attack starts with either the attacker intercepting an authentication message or coercing a target to authenticate itself to an attacker-controlled machine. In both cases, the authentication is forwarded to an arbitrary service, in order to trick the service into performing a certain malicious action. Common relay targets for such attacks are Active Directory Certificate Services (AD CS), SMB and LDAP. An example of a relay attack can be seen below.

One way to mitigate relay attacks is to enable session signing, i.e. SMB signing, LDAP signing, etc. This effectively binds messages to their senders, enabling both the target of a relay attack and the service that is being relayed to to verify the authenticity of messages that they receive. A good chart with techniques, mitigations and impact of relay attacks has been published on The Hacker Recipes.

When session signing is enabled, the attacker cannot hijack the session, since they cannot retrieve the session key required for signing. However, relaying is still possible if the attacker relays to a protocol, where session integrity is not controlled via NTLM messages, e.g. HTTPS or LDAPS. Alternatively, the attacker can modify the NEGOTIATE_MESSAGE and unset the NTLMSSP_NEGOTIATE_SIGN flag. To prevent such attacks, a Message Integrity Code (MIC) was implemented, which is an HMAC_MD5 applied to the concatenation of all three NTLM messages using the session key. This is meant to ensure that the NTLM messages with the MIC have not been tampered with. However, this security measure can also be circumvented with an attack known as "Drop the MIC". As the name suggests, the attack consists of simply removing the MIC from the RESPONSE message, along with the version field. Additionally, several flags in the NEGOTIATE_MESSAGE (NTLMSSP_NEGOTIATE_ALWAYS_SIGN and NTLMSSP_NEGOTIATE_SIGN) and RESPONSE (NTLMSSP_NEGOTIATE_ALWAYS_SIGN, NTLMSSP_NEGOTIATE_SIGN, NEGOTIATE_KEY_EXCHANGE and NEGOTIATE_VERSION) have to be unset. "Drop the MIC" has been patched by Microsoft in 2019.

The analysis above highlights not just the shortcomings of the NTLM protocol, but also a common problem when trying to patch an insecure communication protocol, namely that mitigations for one attack introduce new attack vectors. In this case, we have demonstrated how the various security measures implemented by Microsoft can be bypassed with downgrade attacks. These bypasses are only possible in domains with lenient signing enforcement rules. Such configurations are common due to backwards compatibility considerations, which often come at the cost of . It is therefore always recommended to enforce signing. With this measure in place, a strict signing enforcement policy is implemented, whereby messages without an MIC and session signing would be rejected by the service that is being targeted by the relay attack.

Conclusion

In this blog post, we have taken a closer look at two of the most popular attack vectors against the NTLMv1 protocol. Our research has shown that both attack vectors can be exploited even by opportunistic attackers without massive computational and organizational resources. This shows that NTLMv1 is a very outdated protocol that has multiple vulnerabilities and should be abandoned in favor of the improved Kerberos or NTLMv2 protocols as soon as possible.

References

• https://static.aminer.org/pdf/20170130/pdfs/ccs/ggk0jpat2jerhuq8b1ssczpimw3v5eko.pdf
• https://hal.science/hal-03601665/file/precomputeForRainbowTables.pdf
• https://medium.com/@offsecdeer/ntlmv1-domain-compromise-9bd8dd7e9891
• https://en.wikipedia.org/wiki/NTLM#NTLMv1
• https://support.microsoft.com/en-us/topic/security-guidance-for-ntlmv1-and-lm-network-authentication-da2168b6-4a31-0088-fb03-f081acde6e73
• https://www.crowdstrike.com/en-us/blog/from-the-archives-drop-the-mic-cve-2019-1040/