(This paragraph presupposes you get the general idea -- go read wikipedia if you don't, as its exposition is way better than whatever sources I had read.) The rainbow twist was using a different reduction function for each iteration of a chain, as that reduces collisions between two chains. That makes lookup more complicated, but it's more like O(n^2) in the chain length and chains are relatively short. With that in mind, I think the graphic provided on wikipedia has the coloring along the wrong axis; really, the differing reduction functions ought to be the stripes of the rainbow, as they're fixed and a known set for a given table containing any number of chains.
Though I know how and why it works, it's still a bit creepy to see it in action:
$ echo -n hello | sha1sum aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d - $ time ./rainbow data aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d Configuration: chains: 65536 of length 512 = 33554k hashes (with repeats) keys: keys of length 5 from 26 letters = 11881k outputs pairtable loaded; 65539 entries of 11 bytes at offset 39 reversed: hello real 0m0.151s user 0m0.152s sys 0m0.000s
Anyway, you can browse source and check it out with
git clone http://neugierig.org/software/git/rainbow.gitif you're really curious. Since I started writing this post I glanced at the source of the project that wikipedia links to and found it pretty opaque (of course, it's much more industrial-strength than my hobbyist project), so maybe you'll find it interesting to learn from. I could easily still have my implementation wrong, though...