For this project I used the Verilog hardware description language to design a brute force DES key cracker nicknamed [Red] to search the abbreviated keyspace of the LM algorithm. The search is done by hardware running on a Altera Cyclone II FPGA containing 33,216 logic elements (LEs). The final design runs on a DE2 development and education board as a self contained entity. Users control the device by interacting with four pushbuttons and a toggle switch. Information is displayed on the LCD.
The Lan Manager hash or LM hash is one of the formats Microsoft Windows used, prior to Windows Vista, to store user passwords fewer than 15 characters in length.[1] I came across LM and NTLM-method hashes without knowing what they were back when I was a student at Chelsea Vocational High School in New York City. I was part of an informal club that met in the morning. We worked on computers mostly to enjoy Mr. Ford and the company of peers. One day I was confronted with a computer we did not have the password to. A couple of seconds on Google and I knew that we could use a program that manipulated the SAM Database in Windows to reset the password.[2] Before doing that, I must have tried a version of pwdump[3], which printed something like this on the screen:
Administrator:500:NO PASSWORD*********************:NO PASSWORD*********************:::
Guest:501:NO PASSWORD*********************:NO PASSWORD*********************:::
HelpAssistant:1000:49B8CFC443F90E8B0F2FA540967D4738:A9E42EEFDF04B62AAF0E85386C06CDCA:::
SUPPORT_388945a0:1002:NO PASSWORD*********************:58A7C3CB9564DAC1D1D538EEE9F0BB5E:::
tony:1003:BED45CEAB653D37CAAD3B435B51404EE:90934199CDA1DEDAC480198503B77732:::
The program extracted the User Account, LM and NTLM hashes from the Windows target. That day we opted to reset the password rather than discover what it was. It is well known in present day that programs such as L0phtcrack, ophcrack, Cain & Abel, John the Ripper and others, can operate on these hashes and perform rainbow table and brute-force attacks to recover the original password in plain text and with ease. ophcrack is available in the form of a LiveCD.
The shortcomings of the LM hash method and my prior encounter with it made for the perfect project. Further reassurance came from the fact that such a project would not be groundbreaking work. Many have demonstrated the ability to perform an exhaustively search on Data Encryption Standard (DES), the underlying encryption algorithm used in LM hashing. The COPACOBANA machine built by the Universities of Bochum and Kiel, Germany, can search the entire keyspace in 6.4 days on average using low-cost FPGAs.[4] It is not possible for [Red] to search all 2^56 keys. Luckily, the LM keyspace is only a small fraction that represents 0.01% of the entire DES keyspace. [Red] can search this space in no more than 2500 minutes by checking 50 million hashes per second running on a 27 MHz clock. It is possible that [Red] can finish in less than 1000 minutes if the theoretical 120 million hashes per second can be achieved by increasing the internal clock of the DES units to 100 MHz.