Name Rainbow Table Password Cracking
Summary An attacker gets access to the database table where hashes of passwords are stored. He then uses 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. 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.
Prerequisites Hash of the original password is available to the attacker. For a better chance of success, an attacker should have more than one hash of the original password, and ideally the whole table. Salt was not used to create the hash of the original password. Otherwise the rainbow tables have to be re-computed, which is very expensive and will make the attack effectively infeasible (especially if salt was added in iterations). The system uses one factor password based authentication.
Solutions Use salt when computing password hashes. That is, concatenate the salt (random bits) with the original password prior to hashing it.
Related Weaknesses
CWE ID Description
CWE-261 Weak Encoding for Password
CWE-262 Not Using Password Aging
CWE-263 Password Aging with Long Expiration
CWE-521 Weak Password Requirements
CWE-693 Protection Mechanism Failure
CWE-719 OWASP Top Ten 2007 Category A8 - Insecure Cryptographic Storage
CWE-916 Use of Password Hash With Insufficient Computational Effort
Back to Top