5 ms·

I feel like I'm missing something fundamental in this paragraph: > Rainbow tables differ in that they don't use multiple tables with different reduction functi

by fwip 6y ago

I feel like I'm missing something fundamental in this paragraph: > Rainbow tables differ in that they don't use multiple tables with different reduction functions, they only use one table. However in Rainbow Tables a different reduction function is used for each column. This way different tables with different reduction functions aren't needed, because different reduction functions are used within the same table. What exactly is the structure of the final rainbow table - does it contain a column for each reduction function, or does it still only contain "start text" and "last hash" of each chain? I would loved to have seen a diagram of the table structure here. (From my own reading, I think these "extra columns" are not stored anywhere).

sangel 6y ago
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).
- fwip 6y ago
  Thank you for the explanation, I appreciate it.
- sam1r 6y ago
  Likewise ^^. Great explanation.
- jayflux 6y ago
  > Instead, the attacker computes R_last(target-digest), and checks that against all the endpoints (last hash) of all column. 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)
  - sangel 6y ago
    You are right. I'm missing an H at the end. You first compare target-digest with all endpoints. If it's a match with any of them, good. Then you know a pre-image is in that column. If not, then try H(R_last(target-digest)). Does it match any endpoint? If not, then try H(R_last(H(R_second-to-last(target-digest))). Rinse and repeat.

by fwip 6y ago

sangel 6y ago

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).

fwip 6y ago
Thank you for the explanation, I appreciate it.
sam1r 6y ago
Likewise ^^. Great explanation.
jayflux 6y ago
> Instead, the attacker computes R_last(target-digest), and checks that against all the endpoints (last hash) of all column. 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)
- sangel 6y ago
  You are right. I'm missing an H at the end. You first compare target-digest with all endpoints. If it's a match with any of them, good. Then you know a pre-image is in that column. If not, then try H(R_last(target-digest)). Does it match any endpoint? If not, then try H(R_last(H(R_second-to-last(target-digest))). Rinse and repeat.