In fact I think this would be more informative as a description of rainbow tables, so here goes: Okay, so Bob in principle can write down a lookup table, but t

In fact I think this would be more informative as a description of rainbow tables, so here goes: Okay, so Bob in principle can write down a lookup table, but there's a problem -- that lookup table is going to be as long as the dictionary! What if he has to take it somewhere, or if he wants to make a copy for someone? That's serious work each time. We'd like to take the 100,000 words in the dictionary and convert them to only, say, 1,000 words. Fortunately for Bob, and unfortunately for Alice, one-way functions come with a really simple compression method, where you can reduce the look up table as much as you want. This will make extracting the actual word slower, but you don't have to store a huge book anywhere. Here is how it works. We work with 'chains' of one-way computations. See, our one-way function maps ORNATE → CEASE. Now we 'chain' the function by looking up CEASE and we find that it maps CEASE → SNIDE. We can "chain" it again to find SNIDE → JOYRIDE. After a hundred of these chained together, we find that ORNATE ⇒ HOMOPHONE. In our lookup table we store the entry 'homophone: chain starts with ornate.' And I claim that now the lookup table can be about a hundred times smaller. Why? Because CEASE and SNIDE now do not need to start chains of their own! They are covered by the chain which starts with ORNATE. These chain tables are called "rainbow tables." It might help to see how we use the rainbow table to look up some word near the end of this chain. Let's say that Alice has the word VEGAN and calculates that VEGAN → ORATION, so she sends us ORATION. Bob can't easily reverse this, but he can do the one-way function to ORATION and find some other word, ORATION → PERSECUTOR. But Bob can't find that in our rainbow table! So he does the one-way function again, PERSECUTOR → PAY. He can't find that either! So he does the one-way function again, PAY → CREATIVE. Nope, still no help! But then, CREATIVE → HOMOPHONE, and we find in our rainbow table that yes, we know how to make HOMOPHONE, because the rainbow table, remember, stored the fact that HOMOPHONE ⇐ ORNATE. Now we use the one-way function again, starting with ORNATE → CEASE → SNIDE → ... → VEGAN → ORATION. Hey look, we found ourself back at ORATION, but now we know a word (VEGAN) which maps to ORATION! It's a long process of about 100 queries of the one-way function, but it's not so long -- because remember, the one-way function was fast. There is a one-way function called SHA1 sometimes used to protect passwords. Today you can download a big file -- 86 GB -- which is just a rainbow table for passwords hashed with it. This rainbow table covers all passwords from 1 to 7 characters -- any combination of upper- or lower-case letters, numbers, spaces, special symbols, anything. That's about 95^7 = 70 trillion passwords! But it doesn't take ~70 trillion bytes, it only takes ~70 billion bytes, because it's been compressed by a factor of 1000 this way. There's also a lookup table for 1-10 character passwords which are made of lowercase letters and numbers only, so about 36^10 = 3.6 quadrillion passwords. The file size is 588 GB, it's been compressed by a factor of 5,000 to make it possible to store on a modern hard drive. So if your password is all lower-case letters and numbers, it had better be a very long password, at least 12 characters long.