Clarification on how rainbow tables work

Question

If you goto : http://www.hanewin.net/encrypt/aes/aes-test.htm

for "Key in Hex" enter 00000000000000000000000000000056

for "Plaintext in Hex" enter 00000000000000000000000000000000

and click on "Encrypt" you get: 1bb171d2afef6e7f1ccb895ee9b35fe0

The password "56" is a two hex characters that was encrypted with a key of all zeros.

I am trying to implement the pre-computed hashes described here:

http://en.wikipedia.org/wiki/Rainbow_table

so that I can "discover" the password "56" given the encrypted hash (1bb171d2afef6e7f1ccb895ee9b35fe0)and key (00000000000000000000000000000000).

According to the algorithm on the wikipedia page, once all the end points are computed, you reduced the hash given to you and check if it exists in one of your end points. If so, get the corresponding starting point for the matching end point and compute the chain until you reach the hash (1bb171d2afef6e7f1ccb895ee9b35fe0). The password should be the one preceding this hash in the chain.

When I run my program I keep getting "00000000000000000000000000000084" as the password but when I hash it I get "1bf162058f3d909cddab3debd64ff2c4", which is not equal to the hash we are looking for. But I think it is interesting the first two characters "1b" are the same as the first two characters of the hash I am interested in finding.

I feel like I am really close but I'm missing an important piece of this algorithm. I was wondering if someone could point me in the right direction.

My code is below:

import java.util.Iterator;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import javax.crypto.Cipher;
import javax.crypto.SecretKey;
import javax.crypto.spec.SecretKeySpec;
import javax.xml.bind.DatatypeConverter;

public class RainbowCrack {

public static TreeMap<String, String> map = new TreeMap<String, String>();
public static final String myPassword =   "00000000000000000000000000000056";
public static final String plaintextHex = "00000000000000000000000000000000";
public static final String hash1 = "1bb171d2afef6e7f1ccb895ee9b35fe0".toUpperCase();

public static int m = 500;
public static int t = 500;

public static void main(String args[]) throws Exception {

    String[] SPi = new String[m];
    String[] EPi = new String[m];

    Random randomGenerator = new Random();
    for (int x = 0; x < m; x++) {
        int randomHex = randomGenerator.nextInt(255);

        String currRandomStrHexVal = String.format("%032x", randomHex);
        SPi[x] = getHashStr(currRandomStrHexVal);

        String currHash = SPi[x];
        for (int chain = 0; chain < t; chain++) {

            // reduce hash to a 2 characters (in order to simulate another potential password)
            currHash = R_low30(currHash);

            // perform AES
            currHash = getHashStr(currHash);

        }

        EPi[x] = currHash;

        // store map (endpoint -> starting point)
        map.put(EPi[x], SPi[x]);

    }


    // pre compuated table completed


    String origHash = hash1;
    int distanceFromEndpoint=0;
    while (distanceFromEndpoint != t){

        // check if the original hash is one of the endpoints
        if (map.containsKey(origHash)){
            // compute # of times to iterate through chian
            int numIterations = t - distanceFromEndpoint - 1;

            String startingPoint = map.get(origHash);
            for (int currChain=0;currChain < numIterations; currChain++){
                startingPoint = R_low30(startingPoint);
                startingPoint = getHashStr(startingPoint);
            }

            System.out.print("potential password = " + R_low30(startingPoint));
            System.out.println(" hashes to " + getHashStr(R_low30(startingPoint)));
            if (getHashStr(R_low30(startingPoint)).equalsIgnoreCase(hash1)){
                System.out.println("Done");
                break;
            }
            else{
                System.out.println("Keep looking...");
                origHash = R_low30(origHash);
                origHash = getHashStr(origHash);
                distanceFromEndpoint++;
            }
        }

        // original hash is not one of the endpoints
        else {
            // perform H(R(origHash)) to prepare for next round of searching
            origHash = R_low30(origHash);
            origHash = getHashStr(origHash);
            distanceFromEndpoint++;
        }
    }
}

public static String bytesToString(byte[] byteArr) {
    if (byteArr == null) {
        return null;
    }

    return DatatypeConverter.printHexBinary(byteArr);
}

public static byte[] stringToBytes(String str) {
    if (str == null) {
        return null;
    }

    return DatatypeConverter.parseHexBinary(str);
}

public static String getHashStr(String str) throws Exception {
    SecretKey key1 = new SecretKeySpec(DatatypeConverter.parseHexBinary(str), "AES");

    Cipher cipher = Cipher.getInstance("AES/ECB/NoPadding");
    cipher.init(Cipher.ENCRYPT_MODE, key1);

    byte[] currEndPoint = cipher.doFinal(DatatypeConverter.parseHexBinary(plaintextHex));

    return bytesToString(currEndPoint);
}
private static String R_low30(String str) {
    if (str == null) {
        return null;
    } else {
        return "000000000000000000000000000000" + str.substring(0, str.length() - 30); // chop off 104 bits from 128 = 24 bits = 6 hex chars
    }
}

Answer 1

There are a few wrong things in your code. Let's first see the minor points:

• That's not a hash function; in particular, it can trivially be reversed. You encrypt the password with a fixed key; this yields an output block. To recover the password, simply decrypt the block, with the same fixed key ! As such, a rainbow table would be totally useless in such a situation. If you want to test rainbow tables with a hash function, you might as well use... a hash function. Java (I am guessing your code is in Java) supports a few of them by default (MD5, SHA-1, SHA-256...).

• That's not a rainbow table. Your are apparently trying to use the ancestor of rainbow tables, Hellman's time-memory trade-off. That's like a monocolour rainbow. That's not bad as a first step (actually that's simpler, hence better for learning) but remember you are not using the real thing.

• The code you show is partial, and lacks some of the functions you call. I am reduced to guessing what the functions do (and what they should do, not necessarily the same thing).

This being said, let's see the major problem, which is that you are not "walking" your chains. I now enter exposition mode:

---

In Hellman's TMTO (and rainbow tables), the point is to use a big table of precomputed hashes, but not storing it. You only store a skeleton of it, namely the "chain ends". Let's call h the hash function you try to invert. It takes as input passwords in a given space P (e.g. 8-character strings) and provides an output in the space V of hash values (such as 128-bit blocks if h is MD5). If you were building a regular precomputed table, you would just generate a lot of possible passwords, hash them all, and store all the pairs (p,h(p)). To "invert" a hash value, look it up in the stored h(p), and voilà! you have the password.

Since a regular precomputed table is huuuuge, Hellman said: let's store only a small subset of the hash values, but we will organize the hashes so that the missing parts of the table can be dynamically reconstructed. These are the chains. We need to add a new function, called the reduction function (let's note it R), which takes a hash value v and maps it to a potential password p. How R works is not very important, as long as it is deterministic and fast. A chain is then a sequence of hash values v_i such that:

• v₀ is an arbitrary hash value; this is the chain start point.
• v_i+1 = h(R(v_i)) for all i, up to a value v_t which is the chain end point. The chain has length t, which is chosen arbitrarily (but smartly).

In plain words, instead of hashing potential passwords "at random", we get each potential password by applying R on a previous hash value. Our chains have length t: each chain involves computing h exactly t times. The important point of a chain is that it can be rebuilt. Given a value v_j somewhere in the chain, we can recompute v_j+1, v_j+2, and so on.

In the table, we store only the start and end points of our chains. Then, at attack time, we have a value w and we tell ourselves: hey, maybe this value w is one of the hash values we went through during the table construction. Now pay attention, this is the point where your code is wrong: this value w is not necessarily an end point. Actually, the probability of being an end point is low. That's the WHOLE POINT. We store only very few hash values (the end points) so there is little chance of having a match on the end points themselves. However, if w is really one of the hash values covered by our table, then we can rebuild the partial chain, from the value w itself to the chain end. The algorithm goes like this:

• First, we try our luck, and just see if w is nevertheless one of our stored chain ends. If w is equal to one of the v_t values, then we have a putative chain (the chain which ends on that v_t).
• Then, we hypothesize that w might be, possibly, the value of a chain just before a chain end. That is, we compute h(R(w)) and look up that value in the chain ends. If there is a match, then that's one more putative chain.
• Possibly, w could be the next to next to last value of the chain, i.e. h(R(h(R(w)))) is the chain end. Then again, we look it up, and possibly get yet another putative chain.
• We continue this process for the t possible locations of w among a chain. This entails t computations of h and t lookups. Each lookup may yield a putative chain.

Each putative chain is a chain which MAY contain our value w. For each putative chain, we have the chain start point and the chain end point (that's what we store) so we can rebuild the whole chain and see if it really contains w. If it does, yipee, the password is revealed (by construction, if w is the v_j in a chain, then R(v_j-1) is a password which hashes to w, just what we were looking for). Rebuilding the chain up to the putative position of w in that chain has average cost t/2 hash function invocations.

What your code does wrong is that it is lazy. It tries to see if w is directly a chain end. Your code does not try to find putative chains where w is in the middle of the chain and not exactly at the end. You only find one putative chain, if any.

A table has false positives. That's why I use the term "putative". Both the hash function h and the reduction function R may trigger collisions (in practice, R will have many more collisions than h, with usual hash functions). Thus, two chains may "merge" at some point, and it happens a lot. In particular, the chain chunk generated from w may end up on a given chain end v_t while coming from "elsewhere" than the nominal chain start v₀. Here, have a hastily drawn schema:

Each arrow is the computation of R then h. Each circle is a hash value. The chain, as computed during table construction, starts with the golden circle and ends with the green circle. The chain chunk rebuilt from w starts with w and, at some point, reaches one of the values in the putative chain, thus ending with v_t. And that's because the chain chunk from w lead us to v_t that we declared the v₀..v_t chain to be putative. But when we rebuild the chain, we disappointingly notice that w is not part of it. So that's a false positive. You will get a lot of these.

Indeed, even with your code which is lazy and considers only one putative chain at most, you got a false positive. As you notice, you get the wrong password, but, after hashing and then reduction with R, you get the "1b" value you expected. That's a collision on R, all right.

---

Note the important point: the table can successfully invert only hash values which have been encountered during table construction. You still pay the full cost of exhaustive search when you build the table. But you pay it once, and then you can apply the table to hundreds of passwords.

After that, things become subtle. It is a whole area of academic research (e.g. see this article which says it all, albeit perhaps not with optimal clarity for students).