This project required an understanding of DES, the LM hash algorithm, an estimate on the time required to search the keyspace and some idea of how to put it all together.
LM Hash[1]
Several aspects of the LM hash algorithm makes it relatively easy to crack due to weaknesses in its implementation. Passwords have a maximum length of 14 characters, those that are shorter than 7 are padded with ASCII NULs (0x00). The 14 bytes are converted to UPPER CASE, divided into two pieces, hashed separately and then concatenated to form the resulting LM hash. Changing all letters to upper case reduces the character set from 95 to 69 which reduces the number of possible keys from 95^7 to 69^7. A brute force attack can be mounted on both halves of the hash to obtain the key in plain text. LM hash does not include a salt which makes it possible to use rainbow tables, a time-memory trade-off technique that utilizes precomputed plain text and hash pairs to search for the key. Salting a password would complicate any attack because a given plain text password could produce different hashes if the salt, which consists of random bits is appended to the password before hashing, greatly increasing the search space if the salt size is significant.
The LM hash is computed as follows.
-
The user’s password as an OEM string is converted to uppercase.
-
This password is either null-padded or truncated to 14 bytes.
-
The “fixed-length” password is split into two 7-byte halves.
-
These values are used to create two DES keys, one from each 7-byte half, by converting the seven bytes into a bit stream, and inserting a zero bit after every seven bits. This generates the 64 bits needed for the DES key.
-
Each of these keys is used to DES-encrypt the constant ASCII string “
KGS!@#$%”, resulting in two 8-byte ciphertext values. -
These two ciphertext values are concatenated to form a 16-byte value, which is the LM hash.
Windows XP computes and stores a LM hash by default. From my experimentation with pwdump, XP does not create a LM hash if the password is longer than 14 characters. The method XP uses to authenticate a password during the login process is case sensitive. This means that [Red] can only recover the password to a user account in its uppercase form if the LM hash is attacked. Note that we can tell immediately from the LM hash whether the password is length 7 or less since LM pads a password with NULs to 14 bytes and the hash of 7 NUL characters on “KGS!@#$%” is always AAD3B435B51404EE.
DES
The DES algorithm is very well explained in[5], which was the reference I used to implement DES in MATLAB and Verilog. DES was selected by NIST and approved as a federal standard in 1976. The Federal Information Processing Standards (FIPS) publication on it can be found in[6]. Since then, DES has been considered insecure and has been replaced by Advanced Encryption Standard (AES).
DES is a block cipher algorithm. It uses a 56 bit key to transform 64 bit chunks of data into 64 bits of chipertext. The algorithm first takes the key and generates 16 subkeys through circular left shifts and bit shuffling. These keys are applied to the data block with the Feistel function for 16 rounds. The Feistel function consist of an expansion function, bit shuffling permutations, an XOR operation with the subkey and a nonlinear transformation using substitution boxes.
LM Keyspace
The LM keyspace is a subset of the entire DES space. Under LM, the key can only take on values equal to the concatenation of 7 ASCII characters. There are 69 characters to choose from in the character set which yields 69^7 such strings.
ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789
!@#$%^&*()-_+=~`[]{}|\:;"'<>,.?/ SPACE
Putting Things Together
Modules needed in this design will be a key generator, a unit to compute DES hashes, a controller and a user interface. The idea is to generate a key, check to see if the resulting hash matches the one we are searching for and repeat until we find a match. After the user has configured the unit through the interface, the main controller activates the DES and key generator. Asynchronous communication will now occur between the two entities. Key generator will generate 40 keys at a time and hand them over to 40 DES units to hash. While the DES units are busy applying the key to the data KGS!@#$%, the next 40 keys are generated. Once hashing is complete, the key generator is notified, it then checks the 40 DES units for any matches. If a DES unit matched the target hash, the key generator reports the plain text key that was used to generate that hash to the main controller for display. Otherwise, 40 new keys are handed to the DES units and the process repeats. Above is a schematic diagram detailing the design. Signals crossing the dotted line are external to the FPGA. These include the control lines connecting to the actual liquid crystal display, switches, pushbuttons and the 27 MHz oscillator.
DES and key generator were designed to work in parallel. Whichever one is slower will limit the rate at which [Red] can perform the brute force attack. A slow key generator will leave the DES unit idle. A slow DES unit will keep the key generator waiting.