| The table looks like this: Column 1 Column 2 start-text1 start-text2 <intermediate> <intermediate> last-hash1 last-hash2 You only store the start text and the last hash for each column. <intermediate> consists of a mix of passwords ("text ") and hashes. To see how they are computed, let us narrow our attention to a single column. text1 <hash-1> computed using H(text1) <text-2> computed using R_1(hash-1) <hash-2> computed using H(text-2) <text-3> computed using R_2(hash-2) last-hash computed using H(text-3) Each column will look like that. I'm using <stuff> to denote things that are not stored. H is the hash function you are creating the rainbow table for. R_1, R_2, etc. are the reduction functions. Each column uses the same hash function and reduction functions but uses a different starting text. Note that in a rainbow table that consists of k columns, there is no need to recompute hash/reduction functions for each chain. Instead, the attacker computes R_last(target-digest), and checks that against all the endpoints (last hash) of all column. If it matches any endpoint, then that chain likely has the corresponding password. Otherwise, compute R_last(H(R_second_to_last(target-digest))), and compare the result with all endpoints. Rinse and repeat. In the worst case, you have to compute as many hash/reduction functions as there are rows (regardless of the number of columns since all columns use the same hash and reduction functions). |
Wouldn’t R_last generate text? Why would you compare the text to last hash? Wouldn’t you just compare the target-digest to the last hash directly? (Nice explanation but I got lost here)