4
$\begingroup$

I have a question regarding Reduction Functions in Rainbow Tables.

If the hashing function is MD5 or SHA-1 etc then should the reduction functions also be MD5 or SHA-1? That is, should the Reduction Function be the same as the Hashing Function but of course with a different set of rules/constraints for input and output parameters?

So, basically should the reduction function algorithms be same/similar as the Hashing Function algorithm but just differ in terms of rules/constraints for input and output parameters?

$\endgroup$
1
$\begingroup$

No, the way to define the reduction functions isn't related with the hash function used.

Let's consider that we want to recover a password $pwd$ knowing $hsh = H(pwd)$ where $H$ is a hash function. So we will compute a rainbow table for a certain set of passwords $\mathcal{P}$. Note that when the hash chains are computed, at each step $i$ we apply the hash function $H$ and a reduction function $R_i$ (note that several reduction functions are used to avoid collision problems).

A distinction must be made between the hash function $H$ and the reduction functions $R_i$. The reduction functions are used to map hash values produced by $H$ back into values in $\mathcal{P}$.

So the way to define the reduction functions $R_i$ depends on how you chose the set $\mathcal{P}$. For example $R$ can be the decomposition in base $n$ where $n$ is the size of $\mathcal{P}$ (the incrementation functions $R_i$ can be simply defined by incrementing the input of $i$ and then apply the decomposition).

The Wikipedia page also gives an example:

An example for a reduction function: Given a 32 bit hash, get the last 6 characters in the hash.

$\endgroup$

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.