Tuesday, January 8, 2013

NTLM Challenge Response is 100% Broken (Yes, this is still relevant)

Updated as it seems a lot of folks don't read. The reason this attack is interesting is that I steal or phish the hash in the attack WITHOUT physical or administrative access. Yes, I am aware of the 30 amazing tools that "already did that" using local admin access. Also here for why this is still matters.
First off, I can’t say I broke the NTLM handshake; the march of time did it.  Apparently I am just the one who bothered to put it together.
There have been numerous whitepapers, hacker conference sessions, and blog posts dedicated to the weaknesses of NTLM (and LM) authentication.  However, the weaknesses described in previously published works were theoretical, or required stealing hashes using admin rights. This means the host was already compromised, thus the exploits themselves are a bit boring and redundant.  One couldn’t just phish for the hashes or MITM the hashes; due to the challenge response mechanism.   The best case for getting to the hash or password from outside the host was to do a MITM attack (or a phish) and substitute a chosen challenge.  This only worked if the victim was willing to negotiate NTLM without the Session Security Flag. This would then allow an attacker to build rainbow tables to get the hash or password. Rather, the attacker probably already had tables built for the chosen challenge.  This scenario is a pretty high bar to reach.
To frame the conversation, there are actually 4 handshakes in the NTLM suite that move up in security and complexity. They are LM, NTLM, NTLM with session security, and NTLMv2.  As of now, only NTLMv2 stands as secure.  There is no way, other than encrypting your link with say IPSec, to secure the 3 weak handshakes.  The good news is, all Microsoft OSs already have a registry key that can control the handshakes options.  MS will release a KB and Advisory on 1/8 on this and the information can be found below.
Now, thanks to Moxie Marlinspike’s Cloudcracker, an attacker can skip the pre-chosen challenge and brute force the challenge response to get the NTLM hash.  If the victim is running XP, the situation is even worse, as Cloudcracker will return the LM hash which can always be broken overnight to derive the user’s password .

Why Does this Matter Now?

Before I get to the exploit details, let me clarify how relevant these technologies still are in today’s world. You might think that with all the papers and presentations, no one would be using NTLM...or, God forbid, LM. NTLMv2 has been around for quite some time. Surely, everyone is using it. Right?
Wrong!
According to the last data from the W3 Schools, 21% of computers are running XP, while NetMarketShare claims it is 39%.  Unless someone has hardened these machines (no MS patches do this), these machines are sending LM and NTLM responses!  While these lists leave out server OSs, 2003 Server still sends NTLM responses by default.  Yes, every MS OS since NT 4.0 SP4 has supported NTLMv2, but NTLM and LM were not excluded by default until Vista.  
But wait, there’s more! It is also very common for companies that have heterogeneous environments to use Active Directory Group Policy to keep the settings weak, usually out of fear of breaking Samba connectivity.  Sure, Samba has supported NTLMv2 for a long time, but most IT folks tend to think “Why beef up security if you might break something? No one is claiming to have broken NTLM.”
Well, here it is: I’VE BROKEN NTLM.
Now, get to fixin’.

More on fixin’ later.  (I can’t take credit for breaking NTLM. I’m no math whiz. I just happen to specialize in applied crypto, and I looked in the right place at the right time.)

The Attack

When I read a summary of Moxie’s MS-CHAPv2 crack, I saw that the big deal was not that the implementation had some crazy flaw, it was that Moxie had affordably built a system that can brute force the DES keys that make up the heart of the challenge response mechanism.  In less than 24 hours, given a known 64 bit plaintext (challenge) and a ciphertext (response), Cloudcracker can return the key to you.  
This made me wonder what else was broken, given affordable DES brute forcing now exists.  
I didn’t dig a lot deeper into the attack at the time, as I was researching NTLM so I could write a blog post on Pass the Hash Attacks.  I know this is well covered territory, but I never found a paper that covered all my questions, so I figured I’d do it myself.  Much of my research was done by reading the protocol details on Eric Glass’s exhaustive page on the topic. I’ve found no better source for understanding the protocols. 
That’s then I stumbled across this: (Bold added for emphasis.)
The NTLM response is calculated as follows :
The MD4 message-digest algorithm (described in RFC 1320) is applied to the Unicode mixed-case password. This results in a 16-byte value - the NTLM hash.
The 16-byte NTLM hash is null-padded to 21 bytes.
This value is split into three 7-byte thirds.
These values are used to create three DES keys (one from each 7-byte third).
Each of these keys is used to DES-encrypt the challenge from the Type 2 message (resulting in three 8-byte ciphertext values).
These three ciphertext values are concatenated to form a 24-byte value. This is the NTLM response.
Note that only the calculation of the hash value differs from the LM scheme; the response calculation is the same.

That’s right, to reverse the challenge response, I just need to brute force two DES iterations that have 56 bit keys and one that only uses 2 bytes of the 56 bit key space for the last crack.  Moxie shows it like this, for those who are more visual.
I immediately went to Moxie’s posts on the topic to figure out how to use Cloudcracker to brute force out my hashes.  That’s when I discovered that MS-CHAPv2 uses the EXACT same math as the LM and NTLM challenge response.  Moxie was kind enough to point me to the line in his code that demonstrates how one can submit the challenge and response to Cloudcracker to get back the LM or NTLM hash.
print "CloudCracker Submission = $99$%s" % base64.b64encode("%s%s%s%s" % (plaintext, c1, c2, k3[0:2]))
Just concatenate your challenge, and the first two thirds of your response, and k3 as base64 and Bob’s your uncle.  The only thing that threw me was, why is k3 only 2 bytes?  To save on processing power, I assume, you must brute force the final key before sending it to Cloudcraker, which just appends it to the first two recovered keys and sends it back.  As the last key is the one that has 5 bytes that are always all 00, this is easy.
Using Eric Glasses example, I sent in $99$ASNFZ4mrze8lqYwcMegYR0ZrKbLfRoDz2Ag=  to Cloudcracker.  This is the challenge 0123456789ABCDEF, low response 25A98C1C31E81847, mid response 466B29B2DF4680F3, and D808, the first two bytes of the final third of the hash, which I brute forced locally.  If you decide to follow along with me, make sure to look at Glass’s parity adjusting of the keys.  DES keys are really 64 bit, not 56, but as the right bit of each byte is a parity bit, it can’t count toward the total entropy or key space.  Or, you can just use his provided Java code.
Then I just had to wait until I got an email with this:
CloudCracker has successfully completed its attack against your CHAPv2 handshake. The NT hash for the handshake is included below, and can be plugged back into the 'chapcrack' tool to decrypt a packet capture, or to authenticate to the server:
cd06ca7c7e10c99b1d33b7485a2ed808                           
This run took 68799 seconds. Thank you for using cloudcracker.com, this concludes your job.
For those who missed it, I just got the NT hash from the challenge and response, which are easily observed on the wire. I just got the hash WITHOUT compromising the host first.  To use this in an attack I just need the right MITM foothold or a phishing email.
To: All Employees
From: HR Communications
Subject: Updates to the Employee Handbook
Body: Human Resources has completed a significant rewrite and update to the Employee Handbook.  While some of the changes are minor, it is worth a look for all employees.  Employees with aging parents will likely be excited to see the increase in paid time off for emergency care of elder dependents.  The guidelines for company events where alcoholic beverages are provided have also been updated. 
Finally, with the passing of Washington Initiative 502, we are publishing the new guidelines for Marijuana in the work place.     
The handbook can be found here:                                                                          
\\hrFiles.ru\HRFiles\EmployeeManualv3.docx 
Best Regards,
Human Resources
I call this attack “Request the Hash”.  Sorry for the pun, but who wouldn’t immediately click the link to find out their companies new pot policy???

The Good News

First of all, I commend MS for changing the default to NLTMv2, as of Vista, and for leaving us the option if we just can’t live without LM or NTLM.  At this point though, I think it is incumbent on MS to push the issue at the local security policy level, letting domain administrators override common sense as needed.
There might be some testing and some interoperability failures for enterprises, but the good news is the settings for LM, NTLM, and NTLMv2 have been around a long time. The reg key HKLM\SYSTEM\CurrentControlSet\Control\Lsa\LmCompatibilityLevel allows you to choose the level of fallback your system will allow.  Set this to 3 or greater for workstations and you are probably set. This situation is a bit more complex as almost all windows computers are not just clients, but also servers, offering you the admin$ share and c$, etc.  The same setting has slightly different bearing on which versions the machine will accept when acting as a server, say when doing remote administration of your desktops. This great article, by Jesper Johansson, covers both the client and server aspect. Personally, I am setting all my systems to 5.  If you allow systems to be set below 5, you may be masking the fact that clients are still performing NTLM or LM handshakes. 
Level
Group Policy Name
Sends                        
Accepts
Prohibits Sending
0
Send LM and NTLM Responses
LM, NTLM,
NTLMv2 Session Security is negotiated
LM, NTLM, NTLMv2
NTLMv2
Session Security (on Windows 2000 below SRP1, Windows NT 4.0, and Windows 9x)
1
Send LM and NTLM—use NTLMv2 session security if negotiated
LM, NTLM
NTLMv2 Session Security is negotiated
LM, NTLM, NTLMv2
NTLMv2
2
Send NTLM response only
NTLM,
NTLMv2 Session Security is negotiated
LM, NTLM, NTLMv2
LM and NTLMv2
3
Send NTLMv2 response only
NTLMv2
Session Security is always used
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

You may ask, “Who cares if my server accepts LM or NTLM?”  If not all your clients are managed, your server could be unwittingly used to compromise an account used by a client with weak settings.
I did a fresh Ubuntu install and verified that its SMB/CIFS client only sent NTLMv2 response, even when I attempted to downgrade using Cain.  I have not yet had a chance to test web browsers that support NTLM auth via SPNEGO.   That’s right; most web browsers perform NTLM auth in HTTP Headers when a trusted site requests it. 

A Reminder About the Downside of Doing Nothing

While web browsers only perform the NTLM auth for trusted sites by default, generally, Windows OSs seem to make no distinction between trusted and un-trusted zones for other protocols, such as CIFS/SMB, SQL/TDS, and RPC.  This means that a phishing attack with a file://server//share link could yield great results for an attacker.  Based on the rapid succession of tries and retries, it is safe to assume that the first 2 – 5 attempts by a machine are the OS, via SSPI, trying to auth with the victim’s cached creds.  This means the attacker does not need to see a successful auth to trust that the credentials are valid. Maybe you took my advice on Pass the Hash, and blocked all the protocols that use NTLM, at your perimeter.  This doesn’t stop one of your clients, say a laptop at home outside your perimeter from trying to do something that won’t try an NTLM handshake. There are just too many ways to fail, if you allow LM or NTLM in any context. OK, so the attacker has the hash, but they are outside the firewall… You’re safe, right?  No!  At this point, the attacker has a valid hash and is ready to use the account to get your data.  Now the attacker has two options:
·         If your system is sending LM responses, getting that hash makes for super light work in cracking the password.  If you are sending the better NTLM hash, you are still in hot water.  Cloudcracker also has a huge set of rainbow tables.  For another $20 I can submit the hash and likely get the password of an average user. There are surely plenty of ways inside your perimeter with just username and password. Moxie, if you are reading this, how about a one step operation (from the customer perspective) that pipes the recovered hash into the rainbow tables after it’s been cracked. Maybe a price a tad under $40 for the two cracks? 
·         BUT WAIT!!  Attackers don’t need your stinking password! If I have the hash, it is password equivalent! The first step of every auth involving NTLM and NTLMv2 is to convert the password to the NT hash.  Your weak settings just saved the attacker a step.  Once the hash has been stolen, the only ways to render it useless are to change the password or remove all of the channels by which it can be passed. (The latter feels infeasible). 

Protecting Yourself and Your Company

If you are a lone user, make sure all of your systems are set to LmCompatibilityLevel 3 or higher via local security policy, group policy, or via the registry key.
If you are a corporate type, make sure the GPO is set to force 3 or higher.  You may notice that levels 4 and 5 talk about domain controllers refusing different levels.  This is not a great protection and may even mask a problem.  While the DC blocking the LM auth passed by a client won’t let the user access the system, the damage is already done: The LM response was sent, and the attacker may have it.  Sure, it is nice for the attacker to see the successful auth so they know the crack is worth the time, but the rapid fails and retries will tell the attacker that the client OS had the creds cached and the hash that was used is almost certainly good, at a minimum on that client machine, if not the domain.
If you are running a Samba client, enter this line ‘client ntlmv2 auth’ into your smb.conf file.

Final Paranoid Thought

If you have any of the weak settings, CHANGE YOUR PASSWORD after fixing them!
I made this discovery when I realized DES was brute-forcible on a budget.  I immediately started thinking of a list of all of the processes that broke along with DES.  I’m sure this is exactly the list that every nations’ spy services started making when they acquired the computing power to brute force DES.  I assume that it has been affordable for most of them for 5 – 10 years now. 
Sorry, spies, if this closes a door for you.  I read a book that says another one will open.  ;-)

Appendix A: Proof of Concept Code

In order to validate my work, I built a simple tool proof the crypto and create the CloudCracker token.  First off, I am not a great or professional coder, so don’t laugh when you look at the code.  Second, Eric Glass’s code was a great help.  His is in Java, while mine is c#.  Last, I used Bouncy Castle’s c# crypto library, for two reasons.  The .NET libraries do not support MD4, because for hashing it is VERY weak and the .NET libraries block the use of weak DES keys.  NTLM does not account for weak keys.
My code is a fair bit redundant, checking and rechecking itself.  This is because each CloudCracker summation costs $20 and I didn’t want to have to send/spend several failed submissions during debugging.
The code can be found here.
The challenge and response data should be in hex, while the password should be ASCII. 

16 comments:

hernan said...

Hi Mark,

I just wanted to add that stealing hashes/passwords from memory allows you to elevate your privileges and extend the compromise.

It may require local admin rights, but it can allow you to obtain domain admin rights.

You can also obtain hashes/passwords of multiple users that do not have an entry in the local SAM, for example, users that logged in remotely using RDP.

These are some of the reasons why stealing credentials with WCE from memory, locally, is still relevant and useful in my opinion.

See http://www.ampliasecurity.com/research/wce12_uba_ampliasecurity_eng.pdf for a description of the scenarios I'm describing.

Also, I guess you've already seen this, but check out http://www.ampliasecurity.com/research/NTLMWeakNonce-bh2010-usa-ampliasecurity.pdf and http://www.ampliasecurity.com/research/OCHOA-2010-0209.txt for the description a series of flaws that affected and broke NTLM for 17 years.

Thank you!

Anonymous said...

Have a look here:

https://github.com/SpiderLabs/Responder

This tool breaks a Windows network in seconds.

Mark Gamache said...

Hernan, it's an honor to have you read and comment on my work. Thanks! I'd only seen one of the two articles. I look forward to reading the other.

Cheers,

Mark Gamache

Zack Fasel said...

@Mark What do you mean by "As of now, only NTLMv2 stands as secure." Frankly, I have to strongly disagree with this statement for the following reasons:

1) No matter what level you force, the system will still auto-authenticate and you can still off-line brute force the hash. It just adds a bit of uniqueness by adding a client salt in v2, so it increases the brute force time to the factor of the number of users you're trying to crack. So it just increases cracking time /slightly/ in comparison to NTLM.

2) Without a secondary protection mechanism (i.e. smb/ldap signing or https extended authentication), NTLMv2 is just as problem-matic as NTLM in the realm of relaying the authentication requests. Take a look at my derbycon talk (was also at defcon and sector this year) about this over at http://www.irongeek.com/i.php?page=videos/derbycon2/1-2-4-zack-fasel-pwned-in-60-seconds-from-network-guest-to-windows-domain-admin. Granted, the tool still needs a lot of work, but it clearly proves that you can easily relay NTLMv2 auth across different protocols and even demonstrates external impact (through exchange web services).

Making the recommendation of "switch to NTLMv2 and you're fine" is the problem with the security recommendations we're making to clients. It's not. Currently, the ONLY way to resolve it is to begin migration to kerberos only. Granted, this opens a whole 'nother can of worms with devices that can't migrate to this (can somebody say integrated auth in organizations on web content gateways that rely on ntlm or legacy systems / systems not joined to the domain and thus not getting kerberos tickets).

And that's my rant :p I'll be writing up a blog post soon-ish to go over this in more detail and clear up the common mis-conceptions with ntlmv2 and it being the fix, but not enough time today :)

- [zf]

Stewart F said...

Great Article!

Can you provide some detail on how to use your C# code to generate the submision to CloudCrack? Can you use a previously captured NTLM Challenge/Response Hash (from tools like Metasploit, etc)

Mark Gamache said...

@Zack

NTLMv2 and NTLM2 are not the same thing. NTLMv2 uses much more data and 2 rounds of HMAC-MD5, not DES. My code covers only NTLM and NTLM2 which use DES.

http://davenport.sourceforge.net/ntlm.html#theNtlmv2Response


Like Kerberos, NTLMv2 can also be brute forced off-line. I'm slightly over simplifying here, but Kerberos users the REALM name as the salt when hashing the password. One can build rainbow tables for an entire realm


When I say "you're set" I am implying that this low cost attack is stopped. I haven't looked at the computational complexity, but I suspect that 2 rounds of HMAC-MD5 will not hold up a lot longer either.

I'm a big Kerberos fan, it's my bread and butter really, but as you say, it can be tricky. Admins who don't understand SPNs and the implication of NAT, etc. have no chance to get it right and then fall back to NTLM occurs.

I probably should have said, "allowing NTLMv2 is the best you can do". Actually, win7 and 2008R2 and greater have a way to ban NTLM on a per host basis.

http://blogs.technet.com/b/askds/archive/2009/10/08/ntlm-blocking-and-you-application-analysis-and-auditing-methodologies-in-windows-7.aspx

I look forward to your blog post.

Thanks for reading and your comments!

Mark Gamache said...

@Stewart F

Yes, you can use any captured CH/resp. You just need them as hex, which is the LC format, and MetaSploit format if I recall. My tool does not do the captures, just creates the token.

CC takes a token as text in a file. The token looks like this.

$99$AbXQgTRe9IzOu5B23rD4XJdtbIFjOwDiq3s=

$99$ is a CC delimiter or something.

The rest is base-64. This is the whole response, as well as the first 2/3rds of the challenge plus the final 3rd already brute forced. My tool brute forces the final 3rd as that is the CC format. The final third is easy. Only 2 bytes of key space as the tailing 6 bytes are always all 00.

Beware, most Ch/Resp use the session security so there is a client and a server challenge. My code accounts for this as long as you enter them both.

Anonymous said...

@Zack,

Could you possibly distinguish between NTLMv2 and V2 session there?
NTLMv2 is not only an extra client salt, it's HMAC-MD5 based for constructing the response. I.e. you can't reduce bruteforcing a NTLMv2 responses to DES 2^57 to get a NTLM hash. [that said, you can still certainly try to bruteforce it, but I'm not sure how fast 3 hmac-md5 is on modern hardware. [inherently all challenge response sent in the clear relies on the weak key or password]


'NTLMv2 session' response however, is similar to V1, but includes the extra client nonce as you mentioned and still suffers the weak DES problem, and lack of eavesdropping protection problem heavily potentially leading to someone expensing the three des encryptions [IDK if padding there means the 3rd des encryption is now more

Perhaps the distinction is moot given there doesn't seem to be a way to only enable NTLMv2 but not use the old session security compatibility extension.

Am I missing something in my reasoning or does that sound right?

Anonymous said...

>[that said, you can still certainly try to bruteforce it, but I'm not sure how fast 3 hmac-md5 is on modern hardware. [inherently all challenge response sent in the clear relies on the weak key or password]


or dictionary attack it, but either way, no Rainbow tables for NTLMv2 or NTLMv2 Session.

Anonymous said...

>NTLMv2 is not only an extra client salt, it's HMAC-MD5 based for constructing the response. I.e. you can't reduce bruteforcing a NTLMv2 responses to DES 2^57 to get a NTLM hash. [that said, you can still certainly try to bruteforce it, but I'm not sure how fast 3 hmac-md5 is on modern hardware. [inherently all challenge response sent in the clear relies on the weak key or password]


more specifically for bruteforcing or dictionary attacking NTLMv2 non session, you'd be straight trying to match a NTLM hash (md4) through an output of the 2 HMAC-MD5 (Mark is right - 2 HMAC, not 3) with various nonces, which seems like a rather annoying thing to do, as opposed to reducing NTLMv2 session to three counts of single DES [or two depending on padding]

Anonymous said...

at the end of the day bruteforcing an entire 128b keyspace [md4 input of ntlm base hash] for hmac-md5 or dictionary or bruteforce attacking it selectively is a whole lot more preferrable to 3 counts or two counts of single DES for NTLMv1 or NTLMv2 session. but again, if you can't only allow NTLMv2 and disallow everything else, including v2 session, the difference is moot.

Anonymous said...

Here’s the revised version:

NTLM1 is broken,
NTLMv2 is not broken, provided you enforce some settings on the client and server that prevent legacy NTLMv1 fallback as part of NTLMv2 session security responses (GP settings from http://technet.microsoft.com/en-gb/magazine/2006.08.securitywatch.aspx )

"In other words, you can think of NTLMv2 Session Security as having two components: a stronger response computation and a better session key generation algorithm. The response computation, however, can be either the mysterious NTLM2 Session Response or a real NTLMv2 response."

So
a) Set client LMCompatibilityLevel to 3 that forces that NTLMv2 session security related response to be stronger and not DES based. And [forbids sending NTLMv1 and LM requests]
b) Enforce LMCompatibilityLevel 5 on the server to only accept V2 requests/responses.

If client LMCompatibilityLevel is <3, you can still get insecure DES based bits in the protocol [aka NTLM2 Session response]

Anonymous said...

thanks for share.

Anonymous said...

nessus plugin 63478 detects this now.

Rich Rumble said...

As herman said, WCE or Mimikatz stealing the plain-text hash from LSASS is relevent. Kerberos everywhere is a pipe dream, I've been on hundreds of networks, and you can sniff all day and find each user sends maybe 1 or 2 kerb auth's. Once Windows has the token, it goes with NTLMv1/2 99.99999% of the time. SMB/CIFS connections, Outlook, Http auth, all NTLM. Pass-the-hash works well for networked sessions, which gets any talk of 2-factor out of the conversation, as does pass-the-pass via mimikatz/wce. pass the pass works even better for interactive/rdp/http sessions. 2-factor may be more in force there than it is at the network, non-interactive logon types. We recommend people make use of the built-in IPSEC functions windows supports natively since win2k. You can use GRE/null encryption so your IDS's don't miss anything, but you add a second factor with ease doing so. It's a pain to roll out, and to maintain, but that's security my friends. You could fall back to LM if you want at that point, windows ipsec and firewalls should be better utilized by everyone I've ever audited. Also JtR has quite a fast kerberos cracker that can extract from pcap's, and it shows you more often than not, the users password is the weakest factor, not the hash/encryption that's being used. Always has been, always will be.

Dmitry Evteev said...

Mark,
cloudcracker does not work now?

for "-cc ffffff0011223344 -sc 0123456789abcdef -r 10d550832d12b2ccb79d5ad1f4eed3df82aca4c3681dd455 -p SecREt01" i'm waiting for a reply more than 3 days((

Inputting falsified referrals to this site violates the terms of service of this site and is considered unauthorized access (hacking).