Rainbow Tables Simplified (Password Cracking for Windows)

July 17, 2006 Bhushan Shah Disk Forensics, Fundamentals, Network Forensics, Tools 3

By Bhushan Shah, NII Consulting

Windows passwords are stored in the registry (encrypted) in the form of a hash. LMHash was the first hash function used by Microsoft to secure their passwords. Eventually when the security issues popped up (as LMHash is quite insecure) they had to come up with NLTM and the most recent one being NTLM Version 2.

A hash function – is a way of creating a small digital “fingerprint” from any kind of data. The function chops and mixes the data to create the fingerprint, often called a hash value.

The LMHash – LM hash or LAN Manager hash is one of the formats that Microsoft LAN Manager and Microsoft Windows use to store Windows user passwords that are less than 15 characters long.

NTLM – Microsoft introduced the NTLM protocol which simply adds case sensitivity and removes the password-division. Dictionary attacks on this protocol are still very good for weak passwords, but Microsoft claims that 100 2GHz machines would still take 5.5 years to obtain the password by brute force. This protocol doesn’t offer any signing or encryption of the exchange of messages between the client and the server. Thus, the protocol is susceptible to message injection by an attacker, allowing “chosen plaintext” attacks.

NTLM Version 2 – This protocol expands the key space to 128-bits, increasing the difficulty of exhaustive brute force attacks (according to Microsoft). The protocol also enables the establishment of a secure channel (signing and/or encryption) between the client and the server prior to the challenge/response. The secure channel is established using a key set created specifically for that purpose (ie, not the password-derived key) and effectively eliminates chosen-plaintext attacks. Encryption can also effectively obscure the messages, preventing the offline cracking attempts that work so well against LM and NTLM authentication.

Windows Password cracking is not as easy as it sounds. Generally the traditional password crackers will try a dictionary attack or try to brute force the password.

Dictionary Attacks-

The dictionary attack is actually self explanatory. What it means that it tries every word in the dictionary. This makes the actual attack almost instantaneous but for a big dictionary you need a lot of storage. The success rate of a dictionary attack is minimal if the password contains special characters and it is also dependent on the number of words in the dictionary.

Brute Force Attacks-

A brute force attack is one where you try and defeat the password by trying a large number of possibilities. I.e. working thorough all possible keys in order to get the password. Such an attack has a better success rate but would take excruciatingly long time to get a password and at times is not feasible.

Theoretical Limits: –

“There is a physical argument that a 128 bit key is secure against brute force attack. It is argued that, by the laws of physics, in order to simply flip through the possible values for a 128-bit key (ignoring doing the actual computing to check it), one would need a device consuming at a minimum 10 gigawatts (about the equivalent of eight large, dedicated nuclear reactors) running continuously for 100 years. The full actual computation—checking each key to see if you have found a solution—would consume many times this amount.

However, this argument assumes that the register values are changed using conventional set and clear operations which inevitably generate entropy. It has been shown that computational hardware can be designed not to encounter this theoretical obstruction”

Now, as these methods are not always feasible and extremely time consuming Philippe Oechslin came up with a method based on time-memory trade-off using Rainbow Tables.

“In 1980 Martin Hellman described a cryptanalytic time-memory trade-off which reduces the time of cryptanalysis by using pre-calculated data stored in memory. This technique was improved by Rivest before 1982 with the introduction of distinguished points which drastically reduces the number of memory lookups during cryptanalysis. This improved technique has been studied extensively but no new optimizations have been published ever since.” (3)
This is a cryptanalytic attack which is based on exhaustive search need and a lot of computing power or a lot of time to complete. When the same attack has to be carried out multiple times, it may be possible to execute the exhaustive search in advance and store all results in memory. Once this pre-computation is done, the attack can be carried out almost instantly. We can also call it a pre-calculated attack

Rainbow Tables-

When you brute force a password you try different possibilities on one machine, you start to wonder if it is really necessary to try all possible passwords again and again on each new machine. This is the basis on which the rainbow tables were created. What seems more feasible is to save the brute force results and use the saves results to accelerate the cracking process to crack other passwords.

It is possible to crack windows passwords with the help of rainbow tables in a matter of seconds. Now, you would be wondering how the rainbow tables would crack a password in a matter of seconds where brute forcing the same password took a few days or a month even. And now you wonder how these tables can crack the password so quickly and with a better success rate.

This article might help you understand how the rainbow tables are built.

In order for the trade-off to work, the passwords and the hashes have to be organized in chains. To get this you need to define a reduction function that converts password hashes into passwords. Starting at the password you can generate a hash from the password with the hash function and then generate a new password from this hash with the reduction function. You can do this over and over again until you get about 10000 hashes and passwords. This chain can only be created in the forward direction.

(http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/)

Now, you can drop the whole chain except for the first and the last password that you store in the table. When you need to crack a hash, you calculate a chain starting from this hash. For every password that appears in the chain, you check if it is not the end of a chain that you stored in the table. When you find a matching end of a chain in the table, you know that the hash is probably part of this chain. Actually, the element just before the hash in that chain is the password you are looking for. You cannot go backwards, but you can look up the beginning of the chain in the table (this is why you stored it together with the end) and you just generate the whole chain from scratch until you get to the password.

“An interesting fact of rainbow tables is that the cracking time can be reduced by the square of the available memory, e.g., if you double the size of the tables, you can crack four times as fast. As an illustration, the online password cracker at (lasecwww.epfl.ch/~oechslin/projects/ophcrack) cracks alphanumerical windows passwords in about 2 seconds with a table set of 1.1G bytes. It takes about 16 seconds with a table set of 388M bytes available from the same web page. “3

Limitations-

This method for password cracking can only be used where the hashes are calculated in advance. In operating systems apart from the Windows operating system password hash is calculated by adding a random amount of salt (that is, the hash function takes an additional parameter as input). This salt is stored together with the hash {where Hash = password + salt}, such that a password can later be verified to match the hash.

Since we don’t know the value of salt being used with the hash in advance, we cannot create a table in advance.

MS-Windows and a few firewalls and routers and databases use salt-less hashing making the attack possible.

Tools-

  • Ophcrack – This tool uses rainbow tables to crack passwords.(Based on Rainbow tables and not Rainbowcrack)
    (This is a bootable Linux CD + Windows(setup) with 3 options – Local SAM, Remote SAM or Encrypted SAM)

Another implementation of the rainbow tables called rainbowcrack is used in tools like-

These tools use a less efficient way of storing chains in tables and ends up with tables that are more than twice as big, making it more that four times slower for the same amount of memory. (Not considering the memory and RAM)

If you would like a demo for this method it can be found here.

There are a few free tables can be found at:-

References:-

  1. Making a Faster Cryptanalytic Time-Memory Trade-Off, Philippe Oechslin
  2. http://www.microsoft.com
  3. http://en.wikipedia.org/wiki/Brute-force_attack
  4. http://www.objectif-securite.ch/
  5. http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/index.php
  6. http://www.rainbowcrack.com/
  •  
  •  
  •  
  •  
  •  
  •  
  •  

3 Comments

Comments are closed.