# 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

• Could you give the security parameters of your specific blowfish? – kelalaka Sep 21 '18 at 9:40
• Hi, here I want to test a plain text of 8 bytes, for keys of length 5 bytes (so N=2^40, n=64). – Wam Nov 4 '18 at 10:28

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

$$(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.