Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm thinking of implementing rainbow tables for a specific blowfish problem, but I have trouble thinking of the proper way to apply the original paper (and its application to hash functions) to blowfish.

Say we have a not too clever password hashing function, which just uses the password as a key to blowfish-encrypt a known plaintext of size $n$. I want to build a rainbow table enabling me to quickly find which key (where the key belongs to a space of size $N$) gave an encrypted text.

From what I understand of the rainbow tables original paper and wikipedia page, I should choose a number $k$ to be the length of my chains, and build them :

  • Given a starting key $x_0$, calculate $h_0 = \text{blowfish}_{x_0}(\text{plainText})$
  • Define $x_1 = R_0 (h_0)$ where $R_0$ is my first reduction function.
  • Keep doing that, calculating $x_{k+1} = R_k(\text{blowfish}_{x_k}(\text{plainText}))$

I understand the principle of building these chains, I understand how/why I'll be able to do a not-too-slow lookup on the sorted chains, but there are several things I still don't understand in this case :

  • How many starting keys should I choose ? If I just use $N/k$, my intuition would be that all the keys should end up being tested in one chain, but can we be sure of that ? To me blowfish is bijective (since reversible) on the plaintext, but how can I be sure that two keys won't give the same encrypted text ?
  • What reduction functions should I use ? It seems to me like this would play a crucial role in making sure that all of my search space has been done.
  • If the two assumptions above don't hold, is there an efficient way to know which keys still haven't been tested to make sure they are used to generate new chains ?

I hope my questions won't look too dumb, feel free to point me to other papers/proofs, I'd be happy to understand this fully. Thanks a lot

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.