How Rainbow Tables Work
kestas.kuliukas.com
How Rainbow Tables Work
1–10 of 30 posts
Re: How Rainbow Tables Work
#2How to beat rainbow tables, add some salt.
Re: How Rainbow Tables Work
#3How to beat rainbow tables, add some salt.
how to discomfort or discourage
Re: How Rainbow Tables Work
#4Is anyone still using rainbow tables? I have not heard much of it since GPU cracking
Re: How Rainbow Tables Work
#5Is anyone still using rainbow tables? I have not heard much of it since GPU cracking
Whatever you can do online with a GPU, you can do much in an offline session stored in a file.
Sharing rainbow tables over the internet is probably dead, but your disks can keep more hashes than you can calculate quickly.
Re: How Rainbow Tables Work
#6I 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).
Re: How Rainbow Tables Work
#7I 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. Wha…
The table looks like this:
Column 1 Column 2
start-text1 start-text2
last-hash1 last-hash2
You only store the start text and the last hash for each column. 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
computed using H(text1)
computed using R_1(hash-1)
computed using H(text-2)
computed using R_2(hash-2)
last-hash computed using H(text-3)
Each column will look like that. I'm using 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).
Re: How Rainbow Tables Work
#8[deleted]
Re: How Rainbow Tables Work
#9Is anyone still using rainbow tables? I have not heard much of it since GPU cracking
Rainbow tables don't make sense for a salted hash. So you're immediately narrowing down to only cases where an unsalted hash is used, like Microsoft's NTLM system or some older web systems that do MD5(password) or similar.
Building a rainbow tables is much more expensive (compute time, storage) than just breaking any individual hash. So unless you break hashes all day every day, you probably need to share that expense somehow, but then you can't customize. Maybe a large group of you want all of the old "NT hash" values, that's easy enough, but agreeing to do 5-7 alphanumerics for MD5() means the person attacking a site with an eight character minimum gets nothing out of it.
So aside from things like NT hash it has fallen out of favour.
Re: How Rainbow Tables Work
#10How to beat rainbow tables, add some salt.
There are actually hash functions designed for password storage (e.g. scrypt, argon2). These functions provide many features in addition to salting. The scrypt whitepaper is pretty easy to read if you want to learn more about this.