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

21–30 of 30 posts

Re: How Rainbow Tables Work

#21

Post by Cogito »

Reminds me of a famous prisoner-puzzle. Perhaps the solution will be clearer if you have the concepts of the article fresh when looking at it.

----

The prison warden brings a hundred prisoners to an empty room and hands each of them one of a hundred cards labeled from 1 to 100, and says:

"In the next room there are 100 drawers. Into each drawer has been placed one of a hundred cards labeled from 1 to 100."

"One by one we will let you into the next room. Each of you will be given fifty chances to look inside one of those drawers, and then you will continue into the final waiting room."

"If every single one of you is able to find the card in the drawers that matches the one you have been given, you will all be released from prison today."

"One more rule - if any of you, after entering the room with the drawers, communicates any information to the remaining participants, you all fail."

The prisoners talk among themselves, discussing strategies for opening the drawers that might let them all find their number, and be released today.

They know that the chance for one prisoner to find their card, choosing randomly, is 50/100, or 1/2. The problem is that they all need to find their card, and if they all choose randomly then the chance they all succeed is (1/2)^100 - or (7.9 * 10^-29)%

One of the prisoners, having just read about how rainbow tables work, realised there was a strategy that would give them a greater than 30% chance to all succeed.

What was their strategy?

----

It's trivial to find the solution to this problem if you've never seen it before, search for the 100 prisoners problem. I don't actually know if reading about ranbow tables makes it easier to reason the solution, but there seemed a strong similarity so hopefully someone can figure it out!

Re: How Rainbow Tables Work

#23

Post by jayflux »

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…

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

Re: How Rainbow Tables Work

#24

Post by tleb_ »

In the last section talking about improvements to reduce storage, couldn't the indexes be completely left out? Just storing the chain-end number in an array and using the array's index as the starting number.

Edit: this article is from 11/12/2006 and the last section from 04/09/2009 according the the website's home page.

Re: How Rainbow Tables Work

#26

Post by lomkju »

amenghra wrote: post #10
lomkju wrote: post #2

How 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. https://www.tarsnap.com/scrypt/scrypt.pdf

Will do thanks!

Re: How Rainbow Tables Work

#27

Post by sangel »

jayflux wrote: post #23
sangel wrote: post #7

Earlier quoted context omitted.

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…

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

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.

Re: How Rainbow Tables Work

#28

Post by marcosdumay »

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?

The GP is correct, and I made some mistake on my estimation.

The idea that password hashes should be slow is indeed relatively new. Also it's contemporary to the idea that algorithms should have salts builtin, so those features usually go together.

Re: How Rainbow Tables Work

#29

Post by tialaramex »

Wingman4l7 wrote: post #18
tialaramex wrote: post #9

Earlier quoted context omitted.

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.

The salt is defined to be random. To the extent you shove something that isn't random in as "salt" you don't get the desired consequences.

And I think ISP hand out WiFi routers stopped having daft names like this a decade or more ago. The only AP SSIDs that aren't partly random nonsense I see around here are my own (named "Reformed Distributed Republic") and somebody's FON router, the main ones I've seen elsewhere in my city are "eduroam" and "govroam" which are federated systems and so do not have a PSK - in all four cases you aren't going to help yourself by calculating rainbow tables with those SSIDs.

Re: How Rainbow Tables Work

#30

Post by Wingman4l7 »

tialaramex wrote: post #29
Wingman4l7 wrote: post #18

Earlier quoted context omitted.

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.

The salt is defined to be random. To the extent you shove something that isn't random in as "salt" you don't get the desired consequences. And I think ISP hand out WiFi routers stopped having daft names like this a decade or more ago. The only AP SSIDs that aren't partly random nonsense I see around here are my own (named "Reformed Distributed Republic") and somebody's FON router, the main ones I've seen elsewhere in…

I've definitely still seen several in-use private WiFi networks using "NETGEAR" (although they usually have 2 numbers appended to the end, so that expands the keyspace by 10^2 = 100 different rainbow tables to crack those hashes).

It looks like this generic, repeated-SSID-naming "vulnerability" might continue into the present day via the use of a default name on hotspot devices, or smartphones serving as hotspots -- notice that on the "top 25 pwned wifi network names in the @pwnagotchi project database"[1], the top 1st and 2nd place respectively go to "AndroidAP" and "iPhone". Looking at my Pixel 3, I notice that the default hotspot name doesn't appear to be randomized (it's "PixNet").

[1]: https://twitter.com/evilsocket/status/1305892201222807552

Post reply on HN