Wikipedia rainbow tables entry

Wikipedia page for rainbow tables says:

"this use of multiple reduction functions approximately doubles the speed of lookups."

Assuming the "Average" position in the chain, we take a hash and run it through a 9 iteration chain...

The original table runs it through 4 reductions and 4 hashes and finds the end of the chain, then looks it up for another 5 hashes 5 reductions... total 9 hashes 9 reductions

The rainbow table runs it through Rk-1, Rk-2, Rk-3, and Rk-4 calculations to find the end of the chain, then another 5 hashes 5 reductions to get the plaintext: total 15 hashes 15 reductions...

开发者_StackOverflow

What am I missing here? By my math the only time a rainbow lookup is even the same speed as a normal table is when the hash just happens to be at the very end of the chain... In fact the RT should be incrementally slower the further towards the beginning the hash lies...

A 5k chain with the hash at the beginning should be approx 2500 times slower with rainbow tables than with normal hash tables...

Am I missing something or did Wikipedia make a mistake? (The paper referenced on that page (Page 13) would also be wrong, so I'm leaning towards the former)

---

The purpose of rainbow tables isn't to necessarily be faster but to reduce space. Rainbow tables trade speed for size.

Storing hashes for all possible 10 digit passwords for example would be prohibitively expensive in terms of disk space. Also you need to consider that since the dictionary space is so large it will require significant paging (very slow operation).

Rainbow tables are more CPU intensive but they are much much much smaller requiring less disk space and also allowing more of the potential dictionary space in memory at one time. Keep in mind that means in the real world higher potential performance on large dictionary spaces due to less paging (disk reads are prohibitively slow).

Here is a better illustrated example: http://kestas.kuliukas.com/RainbowTables/

Of course this is all academic. Rainbow tables provide no value against well designed security systems. 1) Use a cryptographically secure algorithm (no "roll your own") 2) Use a key derivation function (with thousands of iterations) to slow attackers hash throughput. 3) Use large (32 to 64 bit) random salt. Rainbow tables can no longer be precomputed, nor can that computation be used for any other system (unless they happen to share same salt. 4) If possible use different salt per record thus making rainbow table completely invalid.

---

All the answers are in the original paper. First of all, you must see that you must compare a single rainbow table with t classical tables, t being the number of elements in a chain. Indeed, each column in the rainbow table acts like a single classical table (e.g. if you have to identical elements in a column of a rainbow table, you will have a merge, if you have two identical elements in a classical table you also have a merge). Then you see that for searching in t classical tables you would need t^2 operations if you have to go through all the tables (t tables with chains of length t). If you search in the single rainbow table you will need 1+2+3+...+t operations which is equal to t^2/2. So in the worst case, where you don't find the password you will be two times faster. Now if the password shows up in average after you have gone through half of the tables or columns then it will be 4 times faster. If you want a high probability of success (e.g. 99%) then in average a password would already show up after 10% of the table, making rainbow tables 20x faster.