I feel like there should be a more efficient way to store these things. You have a complete enumeration of possible inputs (passwords), but unfortunately we need to go in the opposite direction, so we couldn't just index into a n*9 bytes array. Depending on how well distributed the md5 hash space is, it's possible a prefix tree might save you a bit of storage (you'd only have to save a couple of bytes per entry to cancel out the overhead) but I couldn't tell you the numbers there. Otherwise I think you're right, and we'd just have to store a map of md5 -> password.

(Edit: Also being limited to alphanumeric for hashes and printable ascii for input gives you pretty good compression potential.)

They are actually much more complicated than just a big table of 'password | hash'. Check out https://www.freerainbowtables.com/en/articles/ for in-depth explanations.

That isn't how a rainbow table works, it doesn't need to store a hash, plaintext pair for every possibility.

Precomputed hash chains are a simplistic way of explaining how rainbow tables work. http://en.wikipedia.org/wiki/Rainbow_table#Precomputed_hash_...