0
$\begingroup$

I'm continuing doing some personal research on rainbow tables, but forsome reason I cannot understand how to choose the correct reduction function. Wikipedia states that

"Only when the attacker has a good idea of what the likely plaintexts will be they can choose a function R that makes sure time and space are only used for likely plaintexts, not the entire space of possible passwords."

In this case, how can a reduction function like taking the last 6 characters of a hash as a reduction function serve in a rainbow table trying to find a password such as Password123? It would be really helpful if someone would explain this for me. Thanks

$\endgroup$
0
$\begingroup$

In this case, how can a reduction function like taking the last 6 characters of a hash as a reduction function serve in a rainbow table trying to find a password such as Password123?

It can't. Assuming the reduction function takes the last six bytes of output it can only be used to generate passwords up to 6 (ASCII) characters long.

To crack any password up to 6 characters long you need to precompute a number of hashes on the order of $256^{6}$. That takes more space/time than is actually needed. If you don't target passwords that use non-ASCII or non-printble ASCII characters then you can reduce $256^6$ to about $95^6$. ($95$ being the number of "printable" characters.)

So then you substitute your reduction function that simply reinterprets binary data, substituting 6 bytes of hash output for a six character long string, with a more complex function. You can convert the bytes of output to a base 95 number, then create an ASCII string where each value 0 through 95 corresponds to one of the printable ASCII characters.

You don't want to use the first reduction function because it creates unlikely passwords. No ASCII string with any character in the range [0, 31] or [127, 255] is likely to be a real world password, so your rainbow table will be inefficient if you use this reduction function.

The base-95 example I gave is one reduction function that improves efficiency because it avoids characters from these two ranges. For six bytes of hash output you could actually generate 7 character long passwords. (Because $\log_{95} (256^6) \approx 7.30$)

More efficient reduction functions could be used but they would need to be more complex. Maybe you want to rule out candidate passwords that have 4 or more of the same letter in a row unless it's in the form "aaaa.....a" or "aaaa...123". Then you have to make assumptions about what is considered a "likely" password in the real world and then you need to find a way to implement it efficiently.

There are tradeoffs to such choices. If you omit a string from the set of possible outputs that a reduction function can produce then your rainbow table can not crack those passwords if they're used in the real world. If the reduction function can't produce a string then the rainbow table can't crack that password.

You can crack a larger set of potential passwords by increasing the amount of bits your reduction function uses. In the naive implementation you can crack passwords up to six characters long if you use six bytes. Or seven characters if you use seven bytes. And so on.

But when you grow that password set you also need to do more precomputation (and us more time and/or memory during querying). In practice you get diminishing returns by using more and more bytes.

If you don't do precomputation work proportional to the entire then your table will only cover a fraction of all possible passwords. If your password set is $X$ elements large and you do $X \over 2$ work then less than half of those candidate passwords will actually be covered by a rainbow table.

A larger candidate password set size means you need to do more hashing, even for rainbow tables. Rainbow tables are not effective for targeting long low-entropy passwords. Instead dictionary based cracking and rule-based-brute-force cracking is used.

Rainbow tables are not the go-to algorithm for password cracking anymore. It is a precomputation-based cracking method. Any precomputation method for sound password hashes using cryptographic hash algorithms can easily be made ineffective by using a unique (per-password) random salt.

Today, people attempt to crack correctly hashed passwords by using brute force methods that run in parallel. GPUs differ from CPU hardware in that they do identical operations in parallel. GPUs have many more (simpler) cores than CPUs have, so the are better at doing certain tasks in parallel.

Rainbow tables aren't so important anymore where proper password hashing (with salts) is used. And they never really worked very well for long passwords.

$\endgroup$
  • $\begingroup$ Sorry for asking so late, but thinking about it now, shouldn't there be more than 1 reduction function per column? It sounds there was only one you explained. $\endgroup$ – DecanalGossypine27 Aug 30 '18 at 22:16
  • $\begingroup$ @DecanalGossypine27 I forgot that part. Yes and no. What you can do is define a function of two parameters, the hash-output and iteration number, say $R(h, i)$. Then from that one function you can define $R_1(h) = R(h, 1)$, $R_2(h) = R(h, 2)$, and so on. Each reduction function can be related. It's not necessary to come up with $R_1$ first then make a totally novel $R_2$. (I assume it's not done that way.) It's about the same job coming up with one reduction function or coming up with one family of reduction functions. $\endgroup$ – Future Security Aug 31 '18 at 3:17
  • $\begingroup$ To use an analogy, imagine the infinite monkeys on typewriters scenario. It isn't necessary to put a monkey on a DVORAK typewriter, a chimp on a QWERTY typewriter, and a cat on a laptop keyboard. You can use three animals of the same species on three of the same model of typewriters. (Not a great analogy. Reduction functions are deterministic. Monkey typing functions are not.) If you find a reduction that works well for real world password distributions then use it for every $R_i$, just make the mapping of inputs to outputs different. $\endgroup$ – Future Security Aug 31 '18 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.