Rainbow tables and blowfish

Question

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

Answer 1

• How many starting keys should I choose?

The answer lies in the storage size and lookup time in the table. For example; if we split the $2^{40}$ into $t$ and $l$, the size of the chains and the number of chains, respectively. Let say $t = 2^{20}$ and $l = 2^{20}$

• $t = 2^{20}$ chains;
  • Storage: $2* 64 * 2^{20} = 2^{27}$-bit that is $2^{21}$-Byts storage size.
  • Sorting: Only once you need to sort the $2^{20}$ chains ends by $\mathcal{O}(n\log n )$ time is $\approx 20*2^{20}$
  • The lookup time: at most for $2^{20}$ chains we have $2^{20} *\log_2(2^{20})$ by binary search.

You can use this site to calculate the parameters.

• 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?

No, we can not be sure about this.

• 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?

There is no problem in the password cracking case; you found a valid one.

• 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.

$(H(k_{i-1}+i))$, $H$ is a hash funtion, $k_{i-1}$ output of the previous node in the chain, $i$ the $i$-th node. Strip the $H$ to 64-bit.

• 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?

Other than storing them, no.