Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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