Rainbow Table Password Cracking |
| Attack Pattern ID: 55 (Standard Attack Pattern Completeness: Complete) | Typical Severity: Medium | Status: Draft |
DescriptionSummary
An attacker gets access to the database table where hashes of passwords are stored. He then uses a rainbow table of precomputed 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 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.
Attack Execution Flow
Determine application's/system's password policy:
Determine the password policies of the target application/system.
Attack Step Techniques
ID Attack Step Technique Description Environments 1 Determine minimum and maximum allowed password lengths.
env-All2 Determine format of allowed passwords (whether they are required or allowed to contain numbers, special characters, etc.).
env-All3 Determine account lockout policy (a strict account lockout policy will prevent brute force attacks).
env-AllIndicators
ID type Indicator Description Environments 1 Positive Passwords are used in the application/system
env-All2 Negative Passwords are not used in the application/system
env-AllObtain password hashes:
An attacker gets access to the database table storing hashes of passwords or potentially just discovers a hash of an indivual password.
Attack Step Techniques
ID Attack Step Technique Description Environments 1 Obtain copy of database table or flat file containing password hashes (by breaking access controls, using SQL Injection, etc.)
env-All2 Obtain password hashes from platform-specific storage locations (e.g. Windows registry)
env-All3 Sniff network packets containing password hashes.
env-Web env-Peer2Peer env-ClientServer env-CommProtocolIndicators
ID type Indicator Description Environments 1 Negative Password authentication not used in application/system.
env-AllOutcomes
ID type Outcome Description 1 Success At least one (unsalted) password hash obtained.2 Failure No password hashes obtained by attacker.
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.
Attack Step Techniques
ID Attack Step Technique Description Environments 1 Run rainbow table-based password cracking tool such as Ophcrack or RainbowCrack. Reduction function must depend on application's/system's password policy.
env-AllIndicators
ID type Indicator Description Environments 1 Positive Success outcome in step 2.
env-All2 Negative Failure outcome in step 2.
env-AllOutcomes
ID type Outcome Description 1 Success A password corresponding to the hash recovered.2 Failure Password corresponding to the hash could not be recovered with the given rainbow table.Security Controls
ID type Security Control Description 1 Preventative Include salts in hashes.
Attack PrerequisitesHash 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 reocmputed, 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.
Typical Likelihood of ExploitLikelihood: Medium
Methods of Attack- Brute Force
Examples-InstancesDescription
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.
Related Vulnerabilities
CVE-2006-1058
Attacker Skills or Knowledge RequiredSkill or Knowledge Level: Low
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 RequiredRainbow 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.
Indicators-Warnings of AttackThis is a completely offline attack that an attacker can perform at their lesure after the password hashes are obtained.
Solutions and MitigationsUse salt when computing password hashes. That is, concatenate the salt (random bits) with the original password prior to hashing it.
Attack Motivation-Consequences- Privilege Escalation
Related Weaknesses| CWE-ID | Weakness Name | Weakness Relationship Type |
|---|---|---|
| 261 | Weak Cryptography for Passwords | Targeted |
| 521 | Weak Password Requirements | Targeted |
| 262 | Not Using Password Aging | Secondary |
| 263 | Password Aging with Long Expiration | Secondary |
| 693 | Protection Mechanism Failure | Targeted |
| 719 | OWASP Top Ten 2007 Category A8 - Insecure Cryptographic Storage | Secondary |
Related Attack Patterns| Nature | Type | ID | Name | Description | View(s) this relationship pertains to |
|---|---|---|---|---|---|
| ChildOf |  Attack Pattern | 49 | Password Brute Forcing | Mechanism of Attack1000 |
Purposes- Penetration
CIA Impact Technical Context| Architectural Paradigms | All |
|---|---|
| Frameworks | All |
| Platforms | All |
| Languages | All |
Content History| Submissions | ||||
|---|---|---|---|---|
| Submitter | Organization | Date | ||
| Eugene Lebanidze | Cigital, Inc | 2007-02-26 | ||
| Modifications | |||||
|---|---|---|---|---|---|
| Modifier | Organization | Date | Comments | ||
| Sean Barnum | Cigital, Inc | 2007-03-01 | Review and revision of content | ||
| Amit Sethi | Cigital, Inc. | 2007-10-29 | Added extended Attack Execution Flow | ||
