Life isn't always colorful, Rainbow attack!
A rainbow table is a pre-computed table for reversing cryptographic hash
functions, usually for cracking password hashes.
Tables are usually used in recovering a plaintext password up
to a certain length consisting of a limited set of characters. It is a
practical example of a space/time trade-off, using less computer processing time and more storage
than a brute-force attack which
calculates a hash on every attempt, but more processing time and less storage
than a simple lookup table with
one entry per hash. Use of a key derivation function that employs a salt makes this attack infeasible.
Where did
it come from?
Any computer system that requires password authentication must
contain a database of passwords, either hashed or in plaintext, and
various methods of password storage exist. Because the tables are
vulnerable to theft, storing the plaintext password is dangerous. Most
databases therefore store a cryptographic hash of a user's password
in the database. In such a system, no one—including the authentication
system—can determine what a user's password is simply by looking at the value
stored in the database. Instead, when a user enters his or her password for
authentication, it is hashed and that output is compared to the stored entry
for that user (which was hashed before being stored). If the two hashes match,
access is granted.
After
gathering a password hash, using said hash as a password would fail since the
authentication system would hash it a second time. In order to learn a user's
password, a password that produces the same hashed value must be found, usually
through a brute-force or dictionary attack.
Rainbow
tables are one tool that has been developed in an effort to derive a password
by looking only at a hashed value.
Rainbow
tables are not always needed, for there are simpler methods of hash reversal
available. Brute-force attacks and dictionary attacks are
the simplest methods available, however these are not adequate for systems that
use large passwords, because of the difficulty of storing all the options
available and searching through such a large database to perform a
reverse-lookup of a hash.
To
address this issue of scale, reverse lookup tables were generated that stored
only a smaller selection of hashes that when reversed could generate long
chains of passwords. Although the reverse lookup of a hash in a chained table
takes more computational time, the lookup table itself can be much smaller, so
hashes of longer passwords can be stored. Rainbow tables are a refinement of
this chaining technique and provide a solution to a problem called chain
collisions.
An
example of pre computed hash chain
Suppose
we have a password hash function H and a finite set of passwords P. The goal is
to pre compute a data structure that, given any output h of
the hash function, can either locate an element p in P such
that H(p) = h, or determine that there is no such p in
P. The simplest way to do this is compute H(p) for all p in
P, but then storing the table requires Θ(|P|n)
bits of space, where n is the size of an output of H, which is
prohibitive for large |P|.
Hash
chains are a technique for decreasing this space requirement. The idea is to
define a reduction function R that maps hash values back into
values in P. Note, however, that the reduction function is not actually an
inverse of the hash function. By alternating the hash function with the
reduction function, chains of alternating passwords and hash
values are formed. For example, if P were the set of lowercase alphabetic
6-character passwords, and hash values were 32 bits long.
The
only requirement for the reduction function is to be able to return a
"plain text" value in a specific size.
- Starting from the hash ("re3xes") in the image below, one computes the last reduction used in the table and checks whether the password appears in the last column of the table (step 1).
- If the test fails (rambo doesn't appear in the table), one computes a chain with the two last reductions (these two reductions are represented at step 2)
- Note: If this new test fails again, one continues with 3 reductions, 4 reductions, etc. until the password is found. If no chain contains the password, then the attack has failed.
- If this test is positive (step 3, linux23 appears at the end of the chain and in the table), the password is retrieved at the beginning of the chain that produces linux23. Here we find passwd at the beginning of the corresponding chain stored in the table.
- At this point (step 4), one generates a chain and compares at each iteration the hash with the target hash. The test is valid and we find the hash re3xes in the chain. The current password (culture) is the one that produced the whole chain: the attack is successful.
Defense against rainbow tables
A rainbow table is ineffective against one-way hashes that
include large salts. For example, consider a password hash that is
generated using the following function (where "||"
is the concatenation operator):
saltedhash(password) = hash(password || salt)
Or
saltedhash(password) = hash(hash(password) ||
salt)
The
salt value is not secret and may be generated at random and stored with the
password hash. A large salt value prevents pre computation attacks, including
rainbow tables, by ensuring that each user's password is hashed uniquely. This
means that two users with the same password will have different password hashes
(assuming different salts are used). In order to succeed, an attacker needs to
pre compute tables for each possible salt value. The salt must be large enough,
otherwise an attacker can make a table for each salt value. For older Unix
passwords which used a 12-bit salt this would require 4096 tables, a
significant increase in cost for the attacker, but not impractical with
terabyte hard drives. The SHA2-cryptand bcrypt methods—used
in Linux, BSD Unixes, and Solaris—have salts of 128 bits. These
larger salt values make precomputation attacks against these systems infeasible
for almost any length of password. Even if the attacker could generate a
million tables per second, he would still need billions of years to generate
tables for all possible salts.
Another
technique that helps prevent precomputation attacks is key stretching.
When stretching is used, the salt, password, and a number of intermediate hash
values are run through the underlying hash function multiple times to increase
the computation time required to hash each password. For instance,
MD5-Crypt uses a 1000 iteration loop that repeatedly feeds the salt, password,
and current intermediate hash value back into the underlying MD5 hash function. The
user's password hash is the concatenation of the salt value (which is not
secret) and the final hash. The extra time is not noticeable to users because
they have to wait only a fraction of a second each time they log in. On the
other hand, stretching reduces the effectiveness of a brute-force attacks in
proportion to the number of iterations because it reduces the number of
attempts an attacker can perform in a given time frame. This principle is
applied in MD5-Crypt and in bcrypt. It also greatly increases the time
needed to build a pre computed table, but in the absence of salt, this needs
only be done once.
An
alternative approach, called key strengthening, extends the key
with a random salt, but then (unlike in key stretching) securely deletes the
salt. This forces both the attacker and legitimate users to perform a
brute-force search for the salt value. Although the paper that introduced
key stretching referred to this earlier technique and intentionally chose
a different name, the term "key strengthening" is now often (arguably
incorrectly) used to refer to key stretching.
Rainbow
tables and other pre computation attacks do not work against passwords that
contain symbols outside the range presupposed, or that are longer than those
pre computed by the attacker. However tables can be generated that take into
account common ways in which users attempt to choose more secure passwords,
such as adding a number or special character. Because of the sizable investment
in computing processing, rainbow tables beyond fourteen places in length are
not yet common. So, choosing a password that is longer than fourteen characters
may force an attacker to resort to brute-force methods.
Certain
intensive efforts focused on LM hash, an older hash algorithm used by
Microsoft, are publicly available. LM hash is particularly vulnerable because
passwords longer than 7 characters are broken into two sections, each of which
is hashed separately. Choosing a password that is fifteen characters or longer
guarantees that an LM hash will not be generated.
Comments
Post a Comment