Rainbow Table Password Cracking
Attack Pattern ID: 55 (Standard Attack Pattern Completeness: Complete)Typical Severity: MediumStatus: Draft
+ Description

Summary

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

Explore
  1. Determine application's/system's password policy:

    Determine the password policies of the target application/system.

    Attack Step Techniques

    IDAttack Step Technique DescriptionEnvironments
    1

    Determine minimum and maximum allowed password lengths.

    env-All
    2

    Determine format of allowed passwords (whether they are required or allowed to contain numbers, special characters, etc.).

    env-All
    3

    Determine account lockout policy (a strict account lockout policy will prevent brute force attacks).

    env-All

    Indicators

    IDtypeIndicator DescriptionEnvironments
    1Positive

    Passwords are used in the application/system

    env-All
    2Negative

    Passwords are not used in the application/system

    env-All
  2. Obtain 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

    IDAttack Step Technique DescriptionEnvironments
    1

    Obtain copy of database table or flat file containing password hashes (by breaking access controls, using SQL Injection, etc.)

    env-All
    2

    Obtain password hashes from platform-specific storage locations (e.g. Windows registry)

    env-All
    3

    Sniff network packets containing password hashes.

    env-Web env-Peer2Peer env-ClientServer env-CommProtocol

    Indicators

    IDtypeIndicator DescriptionEnvironments
    1Negative

    Password authentication not used in application/system.

    env-All

    Outcomes

    IDtypeOutcome Description
    1Success
    At least one (unsalted) password hash obtained.
    2Failure
    No password hashes obtained by attacker.
Exploit
  1. 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

    IDAttack Step Technique DescriptionEnvironments
    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-All

    Indicators

    IDtypeIndicator DescriptionEnvironments
    1Positive

    Success outcome in step 2.

    env-All
    2Negative

    Failure outcome in step 2.

    env-All

    Outcomes

    IDtypeOutcome Description
    1Success
    A password corresponding to the hash recovered.
    2Failure
    Password corresponding to the hash could not be recovered with the given rainbow table.

    Security Controls

    IDtypeSecurity Control Description
    1Preventative
    Include salts in hashes.
+ Attack 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 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 Exploit

Likelihood: Medium

+ Methods of Attack
  • Brute Force
+ Examples-Instances

Description

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 Required

Skill 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 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.

+ Indicators-Warnings of Attack

This is a completely offline attack that an attacker can perform at their lesure after the password hashes are obtained.

+ Solutions and Mitigations

Use 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-IDWeakness NameWeakness Relationship Type
261Weak Cryptography for PasswordsTargeted
521Weak Password RequirementsTargeted
262Not Using Password AgingSecondary
263Password Aging with Long ExpirationSecondary
693Protection Mechanism FailureTargeted
719OWASP Top Ten 2007 Category A8 - Insecure Cryptographic StorageSecondary
+ Related Attack Patterns
NatureTypeIDNameDescriptionView(s) this relationship pertains toView\(s\)
ChildOfAttack PatternAttack Pattern49Password Brute Forcing 
Mechanism of Attack1000
+ Purposes
  • Penetration
+ CIA Impact
Confidentiality Impact: HighIntegrity Impact: HighAvailability Impact: Low
+ Technical Context
Architectural Paradigms
All
Frameworks
All
Platforms
All
Languages
All
+ Content History
Submissions
SubmitterOrganizationDate
Eugene LebanidzeCigital, Inc2007-02-26
Modifications
ModifierOrganizationDateComments
Sean BarnumCigital, Inc2007-03-01Review and revision of content
Amit SethiCigital, Inc.2007-10-29Added extended Attack Execution Flow