CAPEC-55 - Rainbow Table Password Cracking

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.

Severity

Likelihood

Confidentiality

Integrity

Availability

  • Attack Methods 1
  • Brute Force
  • Purposes 1
  • Penetration
  • Scopes 1
  • Gain privileges / assume identity
  • Authorization
  • Access_Control
  • Confidentiality

Low level: 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.

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.

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.

Step 1 - Determine application's/system's password policy

Determine the password policies of the target application/system..

Tecnique ID: 1 - Environment(s) env-All

Determine minimum and maximum allowed password lengths.

Tecnique ID: 2 - Environment(s) env-All

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

Tecnique ID: 3 - Environment(s) env-All

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

Indicator ID: 1 - Environment(s) env-All

Type: Positive

Passwords are used in the application/system

Indicator ID: 2 - Environment(s) env-All

Type: Negative

Passwords are not used in the application/system


Step 2 - 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..

Tecnique ID: 1 - Environment(s) env-All

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

Tecnique ID: 2 - Environment(s) env-All

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

Tecnique ID: 3 - Environment(s) env-Web env-Peer2Peer env-ClientServer env-CommProtocol

Sniff network packets containing password hashes.

Indicator ID: 1 - Environment(s) env-All

Type: Negative

Password authentication not used in application/system.


Outcome ID: 1

Type: Success

At least one (unsalted) password hash obtained.

Outcome ID: 2

Type: Failure

No password hashes obtained by attacker.



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

Tecnique ID: 1 - Environment(s) env-All

Run rainbow table-based password cracking tool such as Ophcrack or RainbowCrack. Reduction function must depend on application's/system's password policy.

Indicator ID: 1 - Environment(s) env-All

Type: Positive

Success outcome in step 2.

Indicator ID: 2 - Environment(s) env-All

Type: Negative

Failure outcome in step 2.


Security Control ID: 1

Type: Preventative

Include salts in hashes.


Outcome ID: 1

Type: Success

A password corresponding to the hash recovered.

Outcome ID: 2

Type: Failure

Password corresponding to the hash could not be recovered with the given rainbow table.



Use salt when computing password hashes. That is, concatenate the salt (random bits) with the original password prior to hashing it.