LMCrack - Cracked in 60 seconds

Hitchhiker's World Issue #9

Charles Gillman <chillman at pentester.com.au>

Introduction

As a security consultant, my job function includes Penetration Testing and Vulnerability Assessments. The aim of these types of engagements is to demonstrate risk to the customer. One of the steps involved in demonstrating risk is password auditing ("cracking") in order to assess the strength and quality of passwords in use in the environment.

On a Windows network this invariably means dumping and cracking the Windows SAM file. The SAM file holds username, user ID (SID) and hashed passwords for all users. There are already many tools in existence to crack the SAM file such as L0phtCrack and Cain & Abel amongst others.

These tools, as brilliant as they are, require a set amount of time to effectively audit a SAM file, often 8 hours or more for programs such as L0pht. While this is extremely fast given the amount of processing involved, for someone in my position limited by the commerciality of time constraints, this can often be too slow. It is for this reason that I decided to write LMCrack.

The design goal of LMCrack was to walk a large key space based on a dictionary style attack rather than on a comprehensive brute force attack and to complete the task in under 5 minutes. The result is a program that utilises a database of pre-computed hashes, which can search an effective key space of 3 trillion passwords in less than 60 seconds with an average success rate of 50+%. How is this possible? Read on...

 

Good Algorithms Implemented Badly

When Microsoft introduced Windows NT, they created their owning hashing format known as the LAN Manager Hash (LanMan or LM) based on the DES algorithm.  It is a 32 byte hash generated from the password as follows :

Due to this implementation, the problem of cracking a LanMan hashed password is reduced to cracking one or possibly two 7 character passwords without regard to upper or lower case. A rather small keyspace by modern standards.

 

LMCrack

As stated previously the design goal of LMCrack was to identify weak passwords in the shortest time possible. Where weak passwords are defined as any dictionary word or lame permutation of a dictionary word (e.g. password5).

LMCrack works by searching for a password hash against a database of pre-computed hashes. The pre-computed hashes are derived from multiple dictionaries of real words rather than random character sequences. The pre-computed hashes are indexed to speed up the hash searching against the database.

The current version of LMCrack parses a SAM file extracted using PWDump (although future versions may crack LanMan hashes sniffed off the wire). Each 32-byte hash is split into two 16-byte halves and each half is searched for against the database of pre-computed hashes independently of the other half . As the hash is composed of two halves, cracking the password will often result in a partial password being found where one 16-byte hash exists in the database and the other 16-byte hash does not.

LMCrack is not intended to replace any existing password cracking tools and the output files are compatible as input for other cracking tools. LMCrack outputs 5 files at the completion of a cracking run:

The cracked.txt and cracked.dic files can be used as input for other password crackers, for example the cracked.txt file works nicely as input for Brutus for testing web based or telnet passwords. Partial.dic is useful as a dictionary file for L0pht to speed up the cracking of partially cracked passwords. Newpwdump.txt can be fed into other cracking programs such as rainbowcrack if a comprehensive password audit is required.

 

The Database of Hashes

LMCrack is freeware but not open source as the "smarts" in LMCrack are found in the data not the code. LMCrack is written with Microsoft tools (I like irony) but it could have been written in any language that supports indexed data access. (If someone out there would like to take the database and port the functionality to another platform or languange please send me a copy.)

In order to have a database of hashes for LMCrack to search, a database of dictionary words needed to be generated. The database was created as follows:

  1. As a first step I took standard English dictionaries and wordlists of leet speak, countries, place names, first names, surnames, cuss words, numbers etc etc and combined them into a single homogenous database.

  2. Next hashes were created for all of these words, using the Crypt::SmbHash Perl library by Benjamin Kuit.

  3. Any word longer that 7 characters was considered as two separate words and split accordingly. The first word would be the first 7 characters and the second word being the remainder of the original word. For example password5 would become passwor and d5.

  4. The split word and their corresponding hashes were added to the database as two separate words.

  5. Obviously many words contain the first same 7 characters, these duplicates were accordingly removed.

This produced the final database of words of 7 characters or less in size and the corresponding 16-byte hash for each word. The final size of the database totalled 3 million words and corresponding hashes, with the final database size being 75MB.

Due to the way Microsoft implemented the LanMan hash as described, the effective size of the key space encompassed by the database is calculated as (the number of words in the database) + (the number of words which are 7 bytes long) * (the number of words in the database). Although there are "only" 3 million words and hashes stored in the database the result is a database that covers an effective key space of 3 trillion passwords.

 

A different approach

The size of the database could have prevented LMCrack from reaching its design goal of rapid operation. The secret to the speed of LMCrack comes from the way the database of pre-compted hashes is searched. The hashes are indexed into a binary tree, this ensures that any lookups of the hashes against the database occur in binary time. That is 2n database entries can be searched in n comparisons against keys within the index.

On modern hardware (P4 3Ghz, 1GB RAM) the time to crack a SAM file containing 2000 hashes is approximately 15 seconds. The actual cracking time is under 1 second, the rest of the time is loading the index into memory. Once the operating system has cached the index, subsequent runs are consistently executed in less than 1 second.

 

Preventing the use of LanMan hashes

The success of a password audit by LMCrack is due to the following two circumstances occuring:

  1. Firstly, LanMan hashes - for the reasons described are not cryptographically secure. The use of LanMan hashes is a large enough security vulnerability that the utilisation of these hashes is now included in the SANS Top 20 Security Vulnerabilities List.

    The use of LanMan hashes on the network can be disabled on Windows NT, 2000, 2003 & XP through registry edits or through the Local Security Policy. The instructions to do so can be found at in Microsoft Knowledgebase Article 147706

    The storage of LanMan hashes also needs to be disabled, this can be done for Windows 2000, XP and 2003 again via registry edits or the Local Security Policy. The instructions to do so can be found at in Microsoft Knowledgebase Article 299656.

  2. Secondly, the use of weak passwords. The use of strong passwords within an environment needs to be mandated for users. Using the stronger NTLMv2 hashing scheme won't prevent a successful dictionary attack - it would be a trivial exercise for LMCrack to be converted to handle NTLM hashes, although the database size would quickly grow.

    The use of strong passwords can be enforced on Windows NT through the use of the passfilt.dll. This is described in Microsoft Knowledgebase Article 161990. The use of strong passwords in Windows 2000, XP and 2003 can be enforced by settings in the Group Policy, which is described in Microsoft Knowledgebase Article 225230.

LMCrack can be downloaded from http://www.pentester.com.au/