FIRE!!

And the problem with Rainbow Tables...

Thursday night's viewing of the film La Promesse was interrupted by a crackling, popping sound. Out of curiosity I opened the front door and looked outside, and was alarmed to see 6 foot high flames across the road. Some people from a few houses down were trying to put it out with 500ml measuring jugs (I kid not).

I rushed back inside, filled the washing bowl full of water and ran outside to help put it out. Liz followed me out with a wok full of water (the next largest item she could find). We soon had put it out, but it was a bit of a shock. The cause of all this drama? Some tit had thought it would be a good idea to discard their cigarette end over the fence into the long dry grass on the other side. Genius.

Anyway, today I've been considering the theory of Rainbow Tables some more.

One of the interesting problems that can arise is that chains within the table can collide and marge. Referring back to the example chain I created yesterday:

ABCD --HASH--> 1234

1234 --REDUCE--> M8UK

M8UK --HASH--> 6682

6682 --REDUCE--> YGA9

YGA9 --HASH--> 9102

9102 --REDUCE--> A00C

A00C --HASH--> 0176

0176 --REDUCE--> HHUA

...

KPUH --HASH--> 9091

9091 --REDUCE--> FRIN

FRIN --HASH--> 7682

7682 --REDUCE--> BVCR

Let's say for example we begin creating a new chain with the starting password of "T6YH" and this gives a hash of 3271. When we apply our reduction function it could, perhaps, lead to a password of "KPUH". This collides with the chain above. While the collision itself isn't too much of a problem, the fact that the two chains will now merge IS a problem as we are wasting a lot of space in the table that could be put to better use.

To get around this multiple tables can be used, and a different reduction function can be specified for each table. That way when collisions do occur the chains will not merge.

A related problem is that of false alarms. We have already seen that collisions can occur. What if a collision occurs and causes a match on and end-point of a chain? For example we are trying to crack the hash "3331" and the reduction algorithm produces a password "BVCR". This collides with the end-point of the hypothetical chain we generated yesterday. The crack algorithm is now going to start searching the 10,000 length chain that starts at ABCD and ends with BVCR, because it has matched the end-point but, in reality, the password we are attempting to crack cannot be found in this chain at all. This called a false alarm and can dramatically increase the time needed to search a table.

No mention of a cracking technique is complete with a mention of how to circumvent that form of attack, so here's how to stay safe: Firstly ensure that your password is of at least length 8 nad contains alpha upper, alpha lower, numerical, punctuation and special characters. If you have trouble choosing long passwords then choose two short passwords and break them up with a special character or punctuation. E.g. Choose a sentence such as "when the sun doth shine" and take the first letter of each word: wtsds. Replace suitable characters with numbers: wt5d5. Upper-case a character: wT5d5. Now do the same with another sentence: "and the beast said 'be you angels?'" atb5Bua? and then append the two passwords with, say, a > between them.

wT5d5>atb5Bua?

14 characters with upper, lower, numerical, punctuation and special characters. You can't get much stronger than that. It would cost a LOT of time and money to crack a password of that length. I often use this technique to generate very strong passwords, appending passwords I use regularly with extra punctuation between them.

In terms of designing systems that are not at risk from Rainbow Tables, simply ensure you use a good random salt. Say a user provides a password of "tImg.8p!". A hacker would need to search approximately 96^8 passwords but will, on average, only need to search half of those passwords to crack it. That's 3,606,947,894,919,168 (3 thousand billion) passwords to try.

If you add a 4 character salt to it: "tImg.8p!*S@!t" then that's (96^12)/2 average number of passwords to test. That's 306,354,878,664,883,681,886,208 (306 thousand trillion) passwords to test. That's far beyond what's feasible to hack.

Anyway I'm bored of Rainbow Tables now. Time to start finding something else of interest.