Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Rainbow Tables Work

kestas.kuliukas.com

Post reply on HN
Print view View original

11–20 of 30 posts

Re: How Rainbow Tables Work

#11

Post by tialaramex »

867-5309 wrote: post #3
lomkju wrote: post #2

How to beat rainbow tables, add some salt.

how to discomfort or discourage

For something ancient like original Unix crypt() with 12-bit salt sure, it's just discouragement. A time-space tradeoff like rainbow tables is only going to be ~4096 times worse to calculate and you can amortize that over just 4096 successful attacks.

But this isn't the 1970s suppose you have 32-bit salt, now you need to use the rainbow table in 4 billion attacks to amortize the extra cost. Hey maybe you can attack every adult in the world?

In reality modern hashes often use 128-bit salt. Now you need to do billions of attacks, for each of the billions of people on the planet, just to keep it only billions of billions of times more expensive than brute force per attack. Or to put it more simply: This prevents the use of rainbow tables.

Re: How Rainbow Tables Work

#13

Post by jorge_leria »

marcosdumay wrote: post #5
hoppla wrote: post #4

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

A new GPU is able to calculate ~50,000 million MD5 hashes per second, an MD5 hash is stored typically on a 32 bytes hex string. If you want to store that you'll need more than 1TB per second: https://gist.github.com/Chick3nman/bb22b28ec4ddec0cb5f59df97...

I used MD5 because that's the typical hash you find unsalted on leaks, but if you do the math with others it is almost impossible to find an example where storing beats using a GPU to crack (even an older one) for a couple of hours.

Re: How Rainbow Tables Work

#14

Post by fwip »

sangel wrote: post #7
fwip wrote: post #6

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

Thank you for the explanation, I appreciate it.

Re: How Rainbow Tables Work

#15

Post by sam1r »

sangel wrote: post #7
fwip wrote: post #6

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

Likewise ^^. Great explanation.

Re: How Rainbow Tables Work

#16

Post by codefined »

jorge_leria wrote: post #13
marcosdumay wrote: post #5

Earlier quoted context omitted.

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.

A new GPU is able to calculate ~50,000 million MD5 hashes per second, an MD5 hash is stored typically on a 32 bytes hex string. If you want to store that you'll need more than 1TB per second: https://gist.github.com/Chick3nman/bb22b28ec4ddec0cb5f59df97... I used MD5 because that's the typical hash you find unsalted on leaks, but if you do the math with others it is almost impossible to find an example where storing b…

Are there any archaic hashes that are built to be "slow" where this might not apply? It feels like a lot of modern slow hashes have salts built in (e.g. Bcrypt, Scrypt, Argon2) but if one didn't use a salt it would definitely still make sense to use a rainbow table against these hashes.

Is the idea that password hashes should be slow relatively new?

Re: How Rainbow Tables Work

#17

Post by bane »

A really great presentation that includes rainbow tables. I didn't ever really get them until I saw this talk. https://youtu.be/LLCyERn8iiw

Basically they're kinda sorta block-chains. And you throw away most of the middle computations since you can arrive at them again fairly trivially.

Re: How Rainbow Tables Work

#18

Post by Wingman4l7 »

tialaramex wrote: post #9
hoppla wrote: post #4

Is 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 expens…

Rainbow tables can still make sense for a salted hash if the salt can be predicted. A current real-world example I just recently learned about: SSIDs (network names) are used to salt WPA-based WiFi network password hashes. If the SSID is a default name (examples: NETGEAR, LINKSYS, XFINITY, etc.), then you could use a rainbow table.

Re: How Rainbow Tables Work

#19

Post by lostcolony »

codefined wrote: post #16
jorge_leria wrote: post #13

Earlier quoted context omitted.

A new GPU is able to calculate ~50,000 million MD5 hashes per second, an MD5 hash is stored typically on a 32 bytes hex string. If you want to store that you'll need more than 1TB per second: https://gist.github.com/Chick3nman/bb22b28ec4ddec0cb5f59df97... I used MD5 because that's the typical hash you find unsalted on leaks, but if you do the math with others it is almost impossible to find an example where storing b…

Are there any archaic hashes that are built to be "slow" where this might not apply? It feels like a lot of modern slow hashes have salts built in (e.g. Bcrypt, Scrypt, Argon2) but if one didn't use a salt it would definitely still make sense to use a rainbow table against these hashes. Is the idea that password hashes should be slow relatively new?

No, the idea that password hashing should be slow is built into the basic understanding of what password hashing is for and should do.

It's just that security wasn't as important (limited web attack surface) or generally understood back in the day (so people were even less likely to ask "is this hash suitable for passwords rather than checksums/indexing/etc?" than they are today), or the slow ones from then were fine -then-, but advances in hardware, the availability of the cloud/GPUs (so massive parallelization without a cost of infrastructure only a nation state could afford), etc, means they're easily compromised today.

Post reply on HN