In this article, we will look at some possible attacks on hash functions - dictionary attack and rainbow table attacks. These attacks aim to find the input given the hash. For example, an attacker can be trying to reconstruct the password given its hash. Another common attack on hash functions is the birthday attack, which is discussed in this article.

Dictionary Attacks

Dictionary attack is the simplest form of attack possible on a hash function. We simply store for each possible input the corresponding hash. Then, given a hash, we can look it up in our database, and find the matching input. Since storing the hash for all possible inputs is quite infeasible, a key component of dictionary attacks is to guess the likely inputs. For example, if we are trying to infer someones password given its hash, we could try common english words and phrases, as well as various combinations of data someone might use as an easy-to-remember password such as dates or names of people.

Rainbow Table Attacks

Introduction

Rainbow table attacks form a point on the spectrum of the space-time trade-off that occurs in exhaustive attacks. Traditional brute force attacks store no precomputed data and compute each hash at run time using minimal space and taking a long time. At the other end of the spectrum is a dictionary attack were all possible hashes are precomputed and then tried in turn. This requires a lot of space but is very fast at run time.

Rainbow tables form hash chains of length k and only store the endpoints of each chain. This reduces storage from the brute force case of n to 2n ÷ k (where n is the number of passwords we can quickly break). However, not having each case on hand at run time leads to run time computation longer than dictionary attacks but much lesser than brute force thanks to the precomputed end points (roughly k operations). The run time of a rainbow table attack will run in approximately logarithmic rather than the linear time of a brute-force attack.

How Rainbow Table Attack works

A rainbow table is a linked list of precomputed hash chains used for reversing cryptographic hash functions in order to crack password hashes. Having generated such a table attacks are then carried out by finding the hash and looking it up in the table to find the corresponding plaintext.

Generating the rainbow table:

The idea is to define a reduction function R that maps hash values back into values in the finite set of plaintexts P. Applying the hash function and the reduction function in an alternating fashion enables a plaintext to map to a hash which maps to a plaintext which maps to a hash and so on in a chain.

To generate the table, a random set of initial plaintexts is chosen and chains of some fixed length k are computed for each chosen plaintext. Only the first and last plaintext in each chain is stored. The first password is called the starting point and the last one is called the endpoint. None of the other plaintexts (or the hash values) are stored.

Finding the password given a hash:

Given a hash h₁ for which we desire the plaintext the following algorithm is applied. Compute a chain with h₁ as the starting point by applying the reduction function R and the hash function h in an alternating fashion. For each plaintext in this chain, we look for a matching plaintext among the end points stored in the rainbow table. If such an end point is found, a new chain is then started using the corresponding start point. This chain will contain the hash value observed h₁ and therefore we may deduce that the preceding plaintext in the chain is the plaintext corresponding to h­₁ that we desire.

Password Salting, aka Defense against above Attacks

Introduction

A salt is additional random data added to the input of a hash function in order to ensure that the output of repeated hashes of some input are not the same.

This is important for passwords where the same password may be used for a prolonged period or in different places, salting makes this more secure essentially by rendering each password random and therefore different. Salting makes passwords more complex and longer making attacks upon them far harder.

Salts protect against rainbow table and dictionary attacks wherein the hashes of many likely inputs are precomputed so that the observed hash can simply be looked up to reveal the input.

How Password Salting works

Historically passwords were stored as plaintext in the databases of user systems. Clearly this was vulnerable to attack and equally if the same password was used in different places giving it to one system enabled that system to use it elsewhere.

Example of Password Salting

Now only the hashes of salted passwords and the salts added are stored in databases so that the password is not known to the owner of the database or any attacker who may attain the database of hashes and salts. The salts and hashes are stored alongside the related user identifier in a database. Upon logging in the username will be used to retrieve the salt and the hash related to the user in question. The salt will be appended to the password input and the entire string then hashed. If the hash matches that retrieved for the user in the database then permission is granted, else permission is denied.

Caveats:

The use of salts makes precomputing hashes of any password difficult due to the need to predict a randomly generated salt. The salt for each password must be randomly generated for each new password to maintain a disconnect between the salt and the system or password. Repeated salts make any successful attack devastating since once the salt is attained any subsequent attacks are far simpler. Salts must also be long enough for it to be infeasible to calculate them all and all of their hashes.

Should the database be compromised this will aid the attacker in making new forms of attack easier as now the password is all that is missing to gain access to a users account.

Summary

Standard attacks on hash functions come in the form of brute force attacks, dictionary tables and more sophisticated rainbow table attacks. It is not possible to generate a truly collision free hash function but to be considered cryptographically secure a hash function must be designed such that it is infeasible to find a collision or determine the input when given its hash.