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
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-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
ID
type
Indicator Description
Environments
1
Positive
Passwords are used in the
application/system
env-All
2
Negative
Passwords are not used in the
application/system
env-All
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
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-All
2
Obtain password hashes from
platform-specific storage locations (e.g. Windows
registry)
Password authentication not used in
application/system.
env-All
Outcomes
ID
type
Outcome Description
1
Success
At least one (unsalted)
password hash obtained.
2
Failure
No password hashes obtained by
attacker.
Exploit
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-All
Indicators
ID
type
Indicator Description
Environments
1
Positive
Success outcome in step 2.
env-All
2
Negative
Failure outcome in step 2.
env-All
Outcomes
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 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.
Vision and Technical Leadership provided by Cigital, Inc.
This Web site is hosted by The MITRE Corporation.
Copyright 2009, The MITRE Corporation. CAPEC and the CAPEC logo are trademarks of The MITRE Corporation.
Description
