CAPEC-55: Rainbow Table Password Cracking
An attacker gets access to the database table where hashes of passwords are stored. They then use a rainbow table of pre-computed hash chains to attempt to look up the original password. Once the original password corresponding to the hash is obtained, the attacker uses the original password to gain access to the system.
Last updated
Overview
A password rainbow table stores hash chains for various passwords. A password chain is computed, starting from the original password, P, via a reduce(compression) function R and a hash function H. A recurrence relation exists where Xi+1 = R(H(Xi)), X0 = P. Then the hash chain of length n for the original password P can be formed: X1, X2, X3, ... , Xn-2, Xn-1, Xn, H(Xn). P and H(Xn) are then stored together in the rainbow table. Constructing the rainbow tables takes a very long time and is computationally expensive. A separate table needs to be constructed for the various hash algorithms (e.g. SHA1, MD5, etc.). However, once a rainbow table is computed, it can be very effective in cracking the passwords that have been hashed without the use of salt.
How the attack works
The phases an attacker typically follows to carry out this attack.
- Step 1Explore
[Determine application's/system's password policy] Determine the password policies of the target application/system.
- Determine minimum and maximum allowed password lengths.
- Determine format of allowed passwords (whether they are required or allowed to contain numbers, special characters, etc.).
- Determine account lockout policy (a strict account lockout policy will prevent brute force attacks).
- Step 2Explore
[Obtain password hashes] An attacker gets access to the database table storing hashes of passwords or potentially just discovers a hash of an individual password.