Heckroth Industries

An Introduction To Password Hashes

What is a password hash?

In the early days of computing there was required a method of storing passwords so that users logging in could be autheticated. While it would be possible to store the passwords in plain text in a file anyone who could access that file would have the login details for everyone on the machine.

The solution to this problem was to hash the password. A hash function is a one way function. What is meant by one way is that it is easy to generate the hash from the password but very difficult / time consuming to generate the password from the hash.

Brute Force Attacks and Dictionary Attacks

One method of converting a hash back to the password that generated it is to imply try hashing every possible combination of characters are valid for the password and then comparing that hash to the one being cracked. This is called a brute force attack.

Another similar method is a dictionary attack where every word in a dictionary of probably passwords is hashed and compared to hash that is being cracked. This is quicker than a brute force attack but does not guarentee a result.

Rainbow Tables

Some hashing schemes (e.g. those used by windows) can be easily defeated if the attacker has spent the time to generate a set of rainbow tables for their target hash method. Rainbow tables are way of reducing the amount of time it takes to crack a hash by precomputing most of the possible hashes before hand.

It works by having another function that maps a hash back to a possible password. Then the system builds up chains of a set length by starting with a password and generating the relating hash and then using it’s function it maps that hash back to a possible password and then it generates the hash for that password and then uses it’s function to map that that hash to a new password.

The system then stores the original password in the chain and the final hash. The system generates enough chains to cover the majority of possible passwords. The collection of these chains are refered to as rainbow tables.

When breaking a hash it checks the list of hashes to see if it has a match. If not then it uses it’s function to generate a password from the hash which it hashes and compares it to the list of hashes in the rainbow table. The system keeps generating passwords based on the previous hash and then hashing that password and comparing till it finds a match. Then all it has to do is generate the chain that it finds a match on and then it should find in that chain the hash and a password that generates it.

Salts

A common method used to defeat rainbow tables is to use a salt in a password. This is a little bit of information that is stored with the hash that is used to alter the way that the hash function hashes the password. It could be a simple as a bit of text that is concatenated onto the password or it may actually change how the hash function operates in some way. With a large enough variation possible in the salt then the time taken to generate the rainbow tables and the space required to store them are drastically increased (i.e. into the realms only available to government bodies).

More Information

For more information check out the following links.

Jason — 2009-12-04