- Cracked in 60
Hitchhiker's World Issue #9
Charles Gillman <chillman at pentester.com.au>
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
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.
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:
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
The success of a password audit by LMCrack is due to the following two circumstances occuring:
LMCrack can be downloaded from http://www.pentester.com.au/