Precomputation for Rainbow Tables has Never Been so Fast

Abstract

Cryptanalytic time-memory trade-offs (TMTOs) are techniques commonly used in computer security e.g., to crack passwords. However, TMTOs usually encounter in practice a bottleneck that is the time needed to perform the precomputation phase (preceding to the attack). We introduce in this paper a technique, called distributed filtration-computation, that significantly reduces the precomputation time without any negative impact the online phase. Experiments performed on large problems with a 128-core computer perfectly match the theoretical expectations. We construct a rainbow table for a space $N=2^{42}$ in approximately 8 h instead of 50 h for the usual way to generate a table. We also show that the efficiency of our technique is very close from the theoretical time lower bound.

Appendices

Appendix

A Proof of Theorem 3

We have $P = \sum _{i=0}^{a} m_{c_{i}} (c_{i+1} - c_{i})$. Deriving for each filter column position, we obtain:

$$\begin{aligned} \frac{\partial P}{\partial c_i} = \frac{\partial }{\partial c_i} \left[ m_{c_i}(c_{i+1} - c_i) + m_{c_{i-1}}c_i)\right] . \end{aligned}$$

Inserting $m_i = \frac{2N}{i+\gamma -1}$ we have:

$$\begin{aligned} \frac{\partial P}{\partial c_i}&= 2N \frac{\partial }{\partial c_i} \left[ \frac{c_{i+1} - c_i}{c_i+\gamma -1} + \frac{c_i}{c_{i-1}+\gamma -1}\right] \\&= 2N \left[ \frac{1}{c_{i-1}+\gamma -1} - \frac{c_{i+1}+\gamma -1}{(c_i+\gamma -1)^2}\right] . \end{aligned}$$

To minimize P, we must have $\frac{\partial P}{\partial c_i} = 0$, and thus:

$$\begin{aligned} c_i = \sqrt{(c_{i-1}+\gamma -1)(c_{i+1}+\gamma -1)}-\gamma +1. \end{aligned}$$

It is easy to verify that a solution to this recurrence relation with terminal conditions $c_0=1$ and $c_{a}=t$ is:

$$\begin{aligned} c_i = \gamma \left( \frac{t+\gamma -1}{\gamma }\right) ^{\frac{i}{a}} - \gamma + 1. \end{aligned}$$

Replacing in the expression for P gives the expected result.

B Online Phase Improvements and Their Impact on Precomputation

There exists many significant algorithmic improvements on the online phase and optimizations of the storage of tables. Their impact on the distribution and intermediate filtering of precomputation is briefly discussed below.

• Chain storage optimizations (prefix/suffix decomposition or compressed delta encoding [9]): lossless compression can be applied at the end of the table generation, with no impact on the precomputation process.

• Truncated endpoints [8]: Endpoints can be truncated at the end of the table generation, again with no impact.

• Checkpoints [8, 12]: Saving checkpoints can be done during the filtered and distributed precomputation with ease, although specific care must be taken. Hashing nodes must be made aware of which columns are checkpoint columns, and the filtration node needs to keep track of this. This adds no significant burden on either.

• Heterogeneous tables [10]: Precomputation of tables of different shapes is done independently, regardless of whether they operate on the same input set. Consequently The use of heterogeneous tables has no impact on precomputation improvements.

• Interleaving [11]: Just like with heterogeneous tables, the different tables are independently computed, again having no impact on precomputation improvements

C Intermediary Filtration

Fig. 7.

Intermediary filtration with 2 filters.

D Notation Through this Paper

Table 4. Notation