Tuesday, August 6, 2013

Challenger: A Tool for Breaking NETNTLM/MSCHAP Hashes

A few months ago I stumbled upon an excellent write-up explaining the details of NETNTLM (NTLMv1 Challenge Response) authentication. It's an interesting design, and two things jumped out at me right away: the use of a symmetric cipher (DES) rather than only hashing functions, and the odd way the hash is split into three, uneven, portions. This inspired me to work on increased attack speeds against NETNTLM. In the end, I created a small Python tool called Challenger that significantly accelerates dictionary-based attacks on NETNTLM challenge-response hashes.

If you're just looking to download the Challenger tool click here.

Note: I know I'm beating a dead horse, attacking NETNTLM challenge-response hashes. Yes, I know the protocol is ancient and not recommended, but it was fun to analyze something, make a tool and, besides, NETNTLM hashes are still found on networks today.

I think that this page does a great job of explaining NETNTLM, and it's worth a quick read in case you're not familiar with how it works. It should be noted that this is the same process used for authenticating via MSCHAP for PPTP and WPA2 Enterprise, and is just as applicable there as it is in SMB or HTTP authentication scenarios - this works wherever you find NETNTLM.

My first idea was to accelerate brute force attacks by avoiding unnecssary operations during an attack on the hash. Since each third of the NETNTLM hash is independent, we can reduce the iniital computational requirements significantly by only working a single third of the hash. That is, for any given password to be tested, rather than conducting the full NETNTLM challenge-response function each time, hash the password into raw NTLM, and then conduct the expensive DES operation on only the first block (e.g. the first 8 bytes of the raw NTLM) and test the output against the first 8 bytes of the target NETNTLM hash. This avoids two expensive additional DES key expansions and encryption rounds that are unnecessary.

While this is a fun idea, I didn't feel like making yet another cracking tool. I'm sure I'm not the first to think of this and that others have already been implementing this acceleration for years in password cracking tools.

Next, I considered what I could do with the last third of the hash. While the use of a symmetric cipher isn't obviously harmful at first, the fact that final third section of the hash has only two bytes of entropy in the key makes the use of a reversible algorithm much more interesting - especially since the two bytes making up the entropy are the last two bytes of raw NTLM hash of the user's password.

Since the last third of the NETNTLM hash is just the encryption of the challenge with last two bytes of the raw NTLM hash, and we know the challenge, we can trivially brute force the key and recover these raw NTLM hash bytes.

I set off to write a small Python script to do just this. In the process of researching different python DES and NTLM libraries, I stumbled upon this article (REF). Apparently Moxie Marlinspike had not only published work on this already, he has tool for doing it. Moxie's chapcrack not only will find those last two bytes, but will let you take the output of the tool and, for a fee, submit it to an online system that will brute force the rest of the hash with purpose-built hardware!

This is great, but what about doing it for free or offline?

Not to be left completely empty handed, I wrote a small tool called Challenger. Challenger will take a given NETNTLM challenge-response and brute force the last two bytes of the underlying raw NTLM hash. On a modern computer this takes less than one second. From those last two bytes, Challenger will first use a preprocessed dictionary that is sorted by the last two bytes of the hash of each word. So, for example, if the last two bytes of the raw NTLM recovered '1e2b', then Challenger will look for a file called ./rainbowtable/1e/2b, which has all words from a dictionary that have an NTLM hash ending in '1e2b'.

While recovering 16-bits of the hash might not seem like a lot, using it to accelerate a dictionary attack works extremely well. As an example, using the 14 million words in the popular RockYou word list it would take a many minutes on a modern computer to test all of the words in the list against a given NETNTLM hash. Since each NETNTLM hash contains a unique challenge, traditional rainbow tables have been impractical against the NETNTLM algorithm. However, once we brute force the last 16-bits of the raw hash, and use that as a reference to a smaller subset of passwords to be tested, we accelerate the test by approximately 65,000 times, making a search of the proper subset of the 14 million word wordlist take less than one second. We've basically got a rainbowtable-like acceleration, using part of the hash rather than the whole.

Finally, if Challenger does not recover the password via dictionary and precomputed table attacks, it will output a chapcrack-compatible hash that you can upload to CloudCracker.com, Moxie's online cracking service, where it can be used to recover the entire raw NTLM hash - guaranteed. It's not the plaintext password but, in the Windows world, it's close enough. The raw NTLM hash can be used with various tools to authenticate with the associated account (e.g. MSF, WCE, Pass-the-Hash toolkit), and it can be used with chapcrack's decrypt option for decrypting PPTP tunnels.

Download the Challenger tool here.

2014-08-04: Updated URLs for download.