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.
- Obtain copy of database table or flat file containing password hashes (by breaking access controls, using SQL Injection, etc.)
- Obtain password hashes from platform-specific storage locations (e.g. Windows registry)
- Sniff network packets containing password hashes.
- Step 3Exploit
[Run rainbow table-based password cracking tool] An attacker finds or writes a password cracking tool that uses a previously computed rainbow table for the right hashing algorithm. It helps if the attacker knows what hashing algorithm was used by the password system.
- Run rainbow table-based password cracking tool such as Ophcrack or RainbowCrack. Reduction function must depend on application's/system's password policy.
What the attacker needs
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.
Skills required
- Low skill: A variety of password cracking tools are available that can leverage a rainbow table. The more difficult part is to obtain the password hash(es) in the first place.
Resources required
- Rainbow table of password hash chains with the right algorithm used. A password cracking tool that leverages this rainbow table will also be required. Hash(es) of the password is required.
Consequences
What a successful CAPEC-55 attack can achieve.
Gain Privileges
Affects: Confidentiality, Access Control, Authorization
How to mitigate it
Defenses that reduce the risk of CAPEC-55.
- Use salt when computing password hashes. That is, concatenate the salt (random bits) with the original password prior to hashing it.
How to detect it
Indicators that this attack may be underway.
- This is a completely offline attack that an attacker can perform at their leisure after the password hashes are obtained.
Examples
BusyBox 1.1.1 does not use a salt when generating passwords, which makes it easier for local users to guess passwords from a stolen password file using techniques such as rainbow tables. See also: CVE-2006-1058
Terminology & mappings
Mapped taxonomies
- ATTACK: Brute Force:Password Cracking (1110.002)
Frequently asked questions
Common questions about CAPEC-55.
- What is CAPEC-55?
- 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.
- How does a Rainbow Table Password Cracking attack work?
- It typically unfolds over 3 phases. It begins with: [Determine application's/system's password policy] Determine the password policies of the target application/system.
- How do you prevent CAPEC-55?
- Use salt when computing password hashes. That is, concatenate the salt (random bits) with the original password prior to hashing it.
- What weaknesses does CAPEC-55 target?
- CAPEC-55 exploits 8 CWE weaknesses, including CWE-261 (Weak Encoding for Password), CWE-262 (Not Using Password Aging), CWE-263 (Password Aging with Long Expiration), CWE-308 (Use of Single-factor Authentication).
- How severe is CAPEC-55?
- MITRE rates CAPEC-55 as Medium severity with medium likelihood of attack.
References
Attack-pattern data is sourced from the MITRE CAPEC catalog (v3.9). Weakness associations link to the corresponding CWE entries on RadicalNotion.AI.
Defend against CAPEC-55
Track the CVEs and weaknesses attackers exploit with this technique, with AI-written analysis and remediation guidance.