10

Is there much of a difference between the two tables? Can you get one from the other? (i.e. hash -> rainbow) How do they work? Are there different variables (in reference to speed, strength, resources, size, etc) that other things depend on? An in depth explanation of the two as well as a compare and contrast would be great and maybe a few examples/scenarios in which the two can be used.

WMPR
  • 313
  • 1
  • 4
  • 9
  • 2
    Simple answer: rainbow tables chain similar hashes together to save space, by not storing the prefix for every hash. (e.g. `f2ca5152b0...`, `f2ca513a13...`, and `f2ca5177b8...` can be stored as `f2ca51 -> 52b0..., 3a13..., 77b8...` since they share the same prefix). – Polynomial Jul 01 '15 at 13:52

1 Answers1

6

Both hash tables and rainbow tables store precomputed hash values. Rainbow tables are a computing power vs storage tradeoff compared to hash tables. They are used because hash tables can grow very large especially as the throughput of cracking hardware has improved. You can brute force more combinations but now you need to store more.

How much space are we talking about? There are common password lists (taken from previous hacks) with tens of millions of known passwords and that is usually where crackers start. This can be supplemented by hundreds of millions of permutations of those weak passwords (if someone used password1111 someone else probably used password2222). Then lastly for good measure the gaps can be filled in with an exhaustive search of all possible combinations of passwords up to a certain length. Take 1 billion passwords, with an average length of 8 characters, and a 32 byte hash. That is 40GB of storage space to store the hash table.

A rainbow table is a way to store the same information using less space. There is no free lunch though in computing you can always trade storage for computing power and that is what you are doing. To build a rainbow table, a traditional hash table is first constructed. Starting with those hash values a hash chain is constructed using alternating hashing and reduction functions. The reduction function maps the hashes back to different passwords in the list. The length of the chain is determines how much of a tradeoff is used (longer = more space saved but more work to perform a search).

Only the chain beginning and end are saved and the rest is discarded so the final table is much smaller. Locating a match now required multiple lookups which means it takes longer than a hash table.

  • Both hash tables and rainbow tables are used to save the results of a precomputation attack.
  • Lookups in a rainbow table are slower*, but require less space to store the precomputed results of a given number of passwords.
  • Lookups in a hash table are faster*, but requires more space to store the precomputed results of a given number of passwords.
  • Both hash tables and rainbow tables are equally and totally defeated by using a pseudo-random salt per record.

*This assumes equal hardware response time which may not be the case (i.e. rainbow table can fit in main memory but hashtable requires a read from slower disk because it is too large to fit in main memory).

Gerald Davis
  • 2,250
  • 16
  • 17
  • What's a "pseudo-random salt per record"? – WMPR Jul 01 '15 at 19:36
  • 1
    There are plenty of answers on why a salt is needed to prevent precomputation attacks but the simple version is we can prevent precomputation attacks by adding a random value to each password record. Instead of hashing password say 'P@ssword!' you generate a salt (large random number) like say 1844674407370961099511627776 and hash the combined value HASH(P@ssword!1844674407370961099511627776) and store the salt and hashed password together. Precomputation becomes impossible because the attacker would need to hash 'P@ssword!' for all 2^64 (or more) possible salt values. – Gerald Davis Jul 01 '15 at 19:57
  • Ah. I understand. Thank you for the explanation :) – WMPR Jul 01 '15 at 20:02