# Rainbow tables and blowfish

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

-