Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Rainbow Tables

Imagine a server that authenticates user passwords. Such a server would need to store a mapping from usernames to passwords so that it can determine whether a given username/password combination is valid. However, storing these passwords as-is on the server is a disaster waiting to happen! If someone hacks such a server, then they would have access to everyone’s passwords, and because people frequently use the same username/password combination, such an unscrupulous actor would be able to log into many other critical sites, e.g., an email account, for such a user.

To mitigate such a scenario, servers will typically not store passwords in plaintext. Instead, they store a hash of the password using a cryptographic hash function, a hash function with the additional property that it is hard to invert, i.e., given a hash, it is computationally difficult to discover the original password (even if a malicious attack knows what the hash function is). The server can then store mappings from usernames to hashes so that a data breach doesn’t disclose users’ passwords.

Password Chains

Now, let’s put on our black hats for a bit! Suppose that we breached a server and obtained a collection of username-hash pairs. The hashes are useless as-is; we need to recover the passwords from these hashes! How might we defeat such a scheme?

In an ultra ideal world, we could compute for each possible password its corresponding hash. We can then store this information in a reverse lookup table: a database of hash-password pairs. However, this is too much information to store! For example, if passwords were restricted to be exactly 12 characters in length and only consisted of lowercase alphabetical characters, there would be —96 quadrillion—entries to store in such a database. If we allow for more variety in password length or characters, that number balloons further!

How can we get away with storing less information? Let’s assume we know the hash function H and let’s consider starting with a password, say balloon. Suppose the hash function sends balloon to the hash value (written in hexadecimal notation) so we have:

balloon --H--> 0x03f0ad

Now let’s suppose we had an additional function R, called a reducer function. This function takes a hash value and produces a password. Note that this function does not (necessarily) invert the original hash function as that is supposed to be difficult! R is any function that produces a potential password from a hash, likely completely unrelated to the original password.

Let’s say that R takes our current hash 0x03f0ad and produces the new password, hotdog:

balloon --H--> 0x03f0ad --R--> hotdog

We can now repeat the process, using H to create a hash from the new password and R to create another password from that hash. Iterating this process a fixed number of times produces a chain of passwords and hashes, eventually end-pointed by a password.

balloon --H--> 0x03f0ad --R--> hotdog --H--> 0x11afde --R--> cattail --H--> ... --R--> guitar

Note that this process is deterministic: given the initial password, H, and R, we can produce the end password in the chain. Therefore, to save space, we only need to store the initial and ending password to “capture” this chain! In this case, we would store the mapping (balloon, guitar) in our database.

Using Password Chains to Discover Passwords

Given a collection of these chains, a hash function H, reduction function R, and a hash h, how can we use the chains to discover the password associated with h? Suppose that the hash we are given is 0x11afde. We can use H and R to recreate a password-chain starting at this hash:

0x11afde --R--> cattail --H--> ... --R--> guitar

For each generated password, we can see if it is the endpoint of a chain. For example, the chain starting with hash 0x11afde eventually produces guitar which is a known endpoint of a chain.

Once we discover such an endpoint, we can go back to the start of the chain (balloon) and recreate the chain until we encounter the hash again.

balloon --H--> 0x03f0ad --R--> hotdog -->H--> 0x11afde

The password for 0x11afde is hotdog, the password that preceded it in the chain!

The Rainbow Table data structure

A rainbow table consists of a hash function, reduction function, and the collection of chains. Given a hash, we can use the rainbow table to lookup up its corresponding password via the process described above.

Setup

As per usual, create a new lab repository for this week using our template for Maven-based Java projects. You should use this template repository to create a new repository on your account, giving the repo an appropriate name for this week’s work, e.g., security.

Once you have created and locally cloned your repository, add the following files, taking care to ensure that you add them to folders consistent with their declared packages, edu.ttap.rainbowtable.

Hash, Password, and Pair are all simple records declarations so that we get the benefits of free hashCode implementations! While Hash and Password are both Strings underneath the hood, we use different class types so that we don’t mix them up in our code.

The RainbowTable class

You should implement the two stubs in RainbowTable.java according to the description of RainbowTable above:

  • The constructor for RainbowTable takes a list of chains (pairs of passwords that are endpoints of the chain) along with a hashing and reducing function as input.
  • Optional<Password> invert(Hash h, int maxSteps) attempts to find the password that generates h by performing up to maxSteps hash-reduce cycles.

Think through the hash-inversion process and think about what data you need in invert in order to perform the operation. Working backwards, this data ought to be defined as fields of the RainbowTable class and those fields should be loaded in the constructor.

In our implementation, we’ll use two types from the standard library that require a bit of explanation:

  • The Function<T, U> interface describes functions that take a T as input and produce a U as input. We can produce such a function from a lambda, e.g., (Integer x) -> x.toString() has type Function<Integer, String>. Alternatively, if a static function has the correct type, we can also use method reference syntax ::, e.g., Integer::toString() also has type Function<Integer, String>. The Function interface provides a method apply(T value) that allows us to call the function.
  • The Optional<T> generic class is a box that can holds a single value of type T. We construct such a box with a value using the Optional.of static method, and we construct an empty box with the Optional.empty() static method.

To test your implementation, we’ve provided a codified version of the reading’s example in the following test file. This file should be placed in the edu.ttap.rainbowtable package of the test directory (src/test/java/...).