6
$\begingroup$

I have been trying to understand rainbow tables lately and one part is giving me trouble to understand here. Let's say I want to generate a table where the chains are 100 000 hash/plaintext long. I have 50 000 hash to reduce then.

  1. Is it necessary to have 50 000 different reducing functions to avoid the collisions?

  2. How do I create those reduction functions (not just take the n-first letters of the hash for instance) ?

$\endgroup$
  • $\begingroup$ I don't think so, I already know how reduction function work I just don't know how to generate a lot of them, different from each other. $\endgroup$ – Shashimee Jul 19 '16 at 13:46
  • $\begingroup$ Yeah, I guess that does not really answer this. $\endgroup$ – otus Jul 20 '16 at 3:44
5
$\begingroup$
  1. Is it necessary to have 50 000 different reducing functions to avoid the collisions?

Yes. If you do not have different functions it is not a rainbow table. It is just a table of hash chains which is less efficient, especially for high coverage tables. However, the functions do not have to be unrelated, just different.

  1. How do I create those reduction functions (not just take the n-first letters of the hash for instance) ?

Any way you want, as long as it leads to an even distribution and different functions. The simplest is to:

  1. Use the size of the search set (of passwords, keys or what have you) and take the hash value modulo that, so the last bits/bytes if the set size is a power of two.

  2. Then, to create different reduction functions you can add the index of the function to the value. I.e. you add nothing for the first, 1 for the second function and so on. This is sufficient, since the next hashing step will cause these small changes to again give a completely different output.

  3. Finally you turn the value into an element of the search set. E.g. encode it into lowercase letters if that is what you are looking for.


The simplest example is if you are looking for a binary key. For example, you are building a rainbow table for DES, which has 56-bit keys (ignoring parity) and 64-bit output.

You can use the last 56 bits of the output (i.e. the whole output modulo $2^{56}$) and add $i$ (again modulo $2^{56}$) for the $i$th reduction function. Pseudocode:

def R(i, x): # i'th reduction function
    return (x + i) % (2**56)

In the case of passwords, suppose you build a table for eight-letter lowercase passwords hashed with MD5. There are $26^8$ such passwords, so you can take the hash value, interpreted as a 128-bit integer and compute (x + i) % (26**8) instead.

(Or you could take the latter half of the hash as a 64-bit integer, then do the same.)

$\endgroup$
  • $\begingroup$ Thanks for answer ! Could you give me an example of your three steps ? I didn't understand the "take the hash value modulo that" part. $\endgroup$ – Shashimee Jul 20 '16 at 7:18
  • $\begingroup$ @Shashimee, added. $\endgroup$ – otus Jul 20 '16 at 7:45
  • $\begingroup$ I don't see the point of the modulo 2**56 :/ Could you do a concrete example please ? Let's say I have 8 characters-long passwords and 15 characters-long hashes. Example : hash=a5re8ze1sj2o5n1. What would be the first and second reduction function for instance (with a random hash function) ? Sorry but I always learn by concrete examples. $\endgroup$ – Shashimee Jul 20 '16 at 9:35
  • $\begingroup$ @Shashimee, that was a concrete example, but I added another based on passwords. I didn't use your hash value since I did not know the encoding. $\endgroup$ – otus Jul 20 '16 at 10:53
  • $\begingroup$ Okay, I get it now ! Thanks for taking the time to answer $\endgroup$ – Shashimee Jul 20 '16 at 12:14

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.