Wednesday 31 March 2010

Seasoned Authentication

Lots of systems that employ user authentication obscure users' passwords using a hashing routine such as MD5 or SHA1, which produce hash strings of 32 or 40 characters respectively.

These hashing algorithms are one-way only, so although the MD5 of 'My Password' is '14ddb8585ddfc6c4670b9c18aed1fe8b', there is no way to return 'My Password' by running code against '14ddb8585ddfc6c4670b9c18aed1fe8b'.

However, most users do not use particularly secure passwords, so if a cookie containing a hashed password is stolen, the thief may be able to bombard the hash with the MD5 hashes of dictionary words in order to find one that matches. MD5 runs extremely quickly, and a modern computer can perform millions of these comparisons every second.

Rainbow Tables

Even if users use secure passwords, it is possible to work out what the original password may have been by using a rainbow table. This is look-up table that store the hashed values of vast numbers of plain-text strings. If the user's password is among the plain-text strings in the table, its hash will match the hash stored, and the security is broken.

Salting Passwords

One way to combat the threat posed by rainbow tables is to 'salt' the password hashes
with a random string of text that is stored un-hashed in a secure location. The password hash is then generated using md5(salt . md5(password)), or a similar method that hashes the salt with the password.

The use of salting can make rainbow tables redundant, as a separate table needs to be generated for every possible salt value. However, modern computers are very fast and hashes can be generated very quickly, so a short salt length may make the task of breaking the hash with a rainbow table feasible. In order to combat this, a longer salt length may be employed.

Caveat

It is important to note that salting is only effective if the person attempting to break the password hash does not know the salt value. If the salt value is known by the attacker, the attacker can simply start running the (known) hashing routine against the potential password plus the (known) salt until a match is made.

Therefore, if a hacker exploits a vector to gain access to a password database and the salt values are stored together with the password hashes, it will not matter if the salt value is three characters or three-thousand - exactly the same amount of work is required to and break the hash.