Gildas Avoine
email: gildas.avoine@irisa.fr

Xavier Carpent
email: xavier.carpent@kuleuven.be

Diane Leblanc-Albarel
email: diane.leblanc-albarel@irisa.fr

Precomputation for Rainbow Tables Has Never Been so Fast

Keywords: Cryptography, Time-Memory Trade-Offs (TMTO), Rainbow Table, Distributed Precomputation

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 filtrationcomputation, 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 hours instead of 50 hours 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.

Introduction

Inverting a hash function (or equivalent cryptographic problem) can be addressed using an exhaustive search when the problem is reasonably sized. An illustrative case is password cracking, which consists in recovering a password from its hash stored by the targeted system. The computation cost may be prohibitive, though, when the attack is repeated. A time-memory trade-off (TMTO) is then an efficient alternative to an exhaustive search. It consists of a precomputation phase -or offline phase -performed once then stored, and an online phase performed each time the hash function should be inverted. The precomputation phase is therefore exploited to accelerate the online phase.

A TMTO, introduced by Martin Hellman [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF], offers a significant speedup in practice. Given a problem of size N (i.e., N = |A| where A is the considered set of possible solutions) and a memory M , the time complexity of the online phase is O(N 2 /M 2 ) instead of N for the exhaustive search. It is worth noting that the time complexity of the precomputation phase remains O(N ). This means that using a TMTO makes sense in specific scenarios: the attack has to be performed several times, the attack itself has to last for a short period of time ("lunch time" attack), or the attacker is not powerful enough to perform an exhaustive search but he can download the result of a precomputed phase, stored in what is called tables.

Hellman's work has been improved over time, particularly with the rainbow tables [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF] and the distinguished points [START_REF] Elizabeth | Cryptography and data security[END_REF]. These variants are faster [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF][START_REF] Ga | Comparison of perfect table cryptanalytic tradeoff algorithms[END_REF][START_REF] Hong | A comparison of cryptanalytic tradeoff algorithms[END_REF] than the original time-memory trade-off. A few improvements [START_REF] Hong | Variants of the distinguished point method for cryptanalytic time memory trade-offs[END_REF][START_REF] Standaert | A time-memory tradeo. using distinguished points: New analysis & fpga results[END_REF] have been suggested on the distinguished points, and the rainbow tables also benefited from various optimizations concerning the online phase, notably the way of storing and using tables [START_REF] Avoine | Analysis of rainbow tables with fingerprints[END_REF][START_REF] Avoine | Optimal storage for rainbow tables[END_REF][START_REF] Avoine | Heterogeneous rainbow table widths provide faster cryptanalyses[END_REF][START_REF] Avoine | Interleaving cryptanalytic time-memory trade-offs on non-uniform distributions[END_REF], checkpoints [START_REF] Avoine | Characterization and improvement of time-memory trade-off based on perfect tables[END_REF] and the use of data [START_REF] Biryukov | Improved time-memory trade-offs with multiple data[END_REF]. In 2016, Lee and Hong [START_REF] Ga | Comparison of perfect table cryptanalytic tradeoff algorithms[END_REF] demonstrated that, in the absence of excessive constraints such as a very limited memory, rainbow tables are the most efficient TMTOs for both online and precomputation phases. We consequently focus on rainbow tables in this paper.

The precomputation phase is very costly, though, typically of the order of 160 N when considering practical scenarios, even for rainbow tables. The precomputation phase must consequently be distributed on many computers.

This paper introduces distributed filtration-computation, a technique that drastically decreases the cost of the precomputation phase and that is compliant with a distribution of that phase. The filtration process identifies computations that will eventually be useless, avoiding so to carry out computations that would be thrown out at the end precomputation phase. The distribution trivially consists in sharing the computing load among several computing units. In common scenarios, the technique we introduce divides by 6 the precomputation time, but the speedup can be much higher in extreme cases, namely when considering what are called maximum tables. As far as we know, this is the first time a technique is introduced to improve the precomputation phase of TMTOs.

After providing background on rainbow tables in Section 2, we introduce the filters and a lower bound on the precomputation in Section 3. We provide a distributed version of the filters in Section 4, with an optimization algorithm for their positions, and we finally illustrate the theory with practical results in Section 5. Note that Appendix D contains a table that recaps the notations used through this paper.

Background

Rainbow Tables

Given a hash function h : A → B, and given h(x) ∈ B, the purpose of a TMTO is to retrieve x ∈ A. To do so, the precomputation phase of the TMTO precomputes rainbow matrices, which consist of chains of elements x i ∈ A (0 i t) such that x i+1 = f i (x i ), where x 0 is an arbitrary value, introduced below, and f i s are hash-reduction functions defined as follows:

f i : A → A x → R i (h(x))
where each R i : B → A is a reduction function, that is a function that aims to map each value in B to a value in A. The choice of the reduction functions is out of the scope of this article, and interested readers can refer to [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF]. Note however that using a different reduction function in every iteration is a key feature of rainbow-based TMTOs that reduces the number of merging chains. It is also important to note that the execution time of a reduction function is negligible compared to that of a hash function.

Once the precomputation phase is completed, the matrix (see Figure 1) consists of m × (t + 1) values denoted X j,i with 0 < j m and 0 i t, and X j,i the element in row j and column i.

The length t, of a chain is the number of application of the Hash-Reduction functions f i performed to construct the chain.

f1 f2 X1,0 -→ X1,1 -→ X1,2 . . . . X1,t f1 f2 X2,0 -→ X2,1 -→ X2,2 . . . . X2,t . . . . . . . . . . . . f1 f2 Xm,0 -→ Xm,1 -→ Xm,2 . . . . Xm,t Fig. 1. Rainbow Matrix
Once the rainbow matrix is computed, only the first column that contains the so-called Start Points (SP) and the last column that contains the End Points (EP) are saved in what is called a table 3 . All intermediary columns are discarded to save memory.

Using a different reduction function in each column reduces the number of merging chains. Indeed, with rainbow tables, two chains merge if they collide in the same column.

From here on we consider a single matrix for the sake of clarity, but a rainbowbased TMTO usually consists of a few independently-computed matrices in order to reach a high success rate, typically 4 tables guarantee the success of the online phase with a probability greater than 99.96%.

Clean Rainbow Tables

Using a different reduction function per column reduces the number of merging chains, but two chains colliding in the same column can still happen. Detecting such a merge is however trivial, as it necessarily leads to equal EPs.

Given that colliding chains make the TMTO less memory-efficient due to the overlapping values, Philippe Oechslin introduced [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF] tables without merges, which are called clean tables 4 [START_REF] Avoine | How to handle rainbow tables with external memory[END_REF].

Merging chains are deleted to obtain clean tables, so if a matrix contains m 0 chains, the corresponding clean table only contains m t < m 0 chains, with m t the number of chains with distinct EPs in a matrix of length t.

Maximum Rainbow Tables

Given a set A with N = |A|, there is a limit to the number of EPs that can be obtained without duplicates. This number, denoted m max t , depends on N and the number of columns t in the table 5 . m max t is obtained from Eq. ( 1) [START_REF] Avoine | Characterization and improvement of time-memory trade-off based on perfect tables[END_REF] where m i is the theoretical number of different elements in column i:

m i ≈ 2N i + γ , with γ = 2N m 0 . (1)
Given a number of columns t + 1 and a sufficiently large number of elements N , the expected maximum number of chains m max t per clean rainbow table is hence given by Theorem 1 [START_REF] Avoine | Characterization and improvement of time-memory trade-off based on perfect tables[END_REF].

Theorem 1. Given t and a sufficiently large N, the expected maximum number of chains per clean rainbow table is:

m max t ≈ 2N t + 2 .
Proof. The proof is presented in [START_REF] Avoine | Characterization and improvement of time-memory trade-off based on perfect tables[END_REF].

In practice, computing m 0 = N chains is prohibitively expensive, so the chosen m 0 is generally markedly smaller than N . This produces tables of size α m max t with 0 < α < 1. Usually, chains are generated until a satisfactory α is reached and m 0 is then determined retrospectively. A satisfactory α allow to have an online success rate close to the rate of a maximal table 6 . When α is close to one (e.g., α = 0.95), the table is said to be quasi-maximum.

Filtering Chains

Preliminary Result on Quantifying Precomputation

In order to generate clean tables containing m t = α m max t chains, the common approach consists in computing chains until obtaining the desired number of 4 Initially called perfect tables by Philippe Oechslin. 5 The number of elements in a clean table is constant which implies that t is inversely proportional to m. The larger m is, the faster the online phase will be, but the more memory is needed for storage and inversely. 6 The probability of success for a single maximal table is 86% when t is large. For the same t and a table of size 0.95m max t , the probabilitity of success for a single table is 85% unique end points. We provide in Lemma 1 and Proposition 1 formulas to predict the value m 0 required to reach on average α m max t unique end points. α is called the maximality factor. Lemma 1. Let r = m 0 /m max t . The expected number of unique EPs is given by:

m t ≈ 1 (1 + 1 r ) m max t .
Proof. From Eq. ( 1), we have m 0 = 2N γ . Given that m 0 = r m max t , we can write γ = 2N r m max t . Using Theorem 1, we then obtain γ ≈ t+2 r ≈ t r . Replacing γ in Eq. ( 1) for i = t, we finally have:

m t ≈ 2N t(1 + 1 r ) = 1 (1 + 1 r ) m max t .
Proposition 1. With a target of m t = α m max t unique endpoints, m 0 = rm max t chains need to be generated, with:

r ≈ α 1 -α .
Proof.

From Lemma 1:

m t ≈ 1 (1+ 1 r ) m max t . Since m t = α m max t : α ≈ 1 (1+ 1 r )
Which conduct to : To illustrate Proposition 1, let us consider the case r = 20, which results in m t ≈ 0.95 m max t . This is a reasonable number that provides a high quality table (m t relatively close to m max t ), while significantly reducing the precomputation cost (compared to the m 0 = N case). With N = 2 42 and t = 10 000 for instance, generating 20 m max t chains instead of N brings the number of chains to be generated from 440 × 10 10 to 1.7 × 10 10 -a 258-fold reduction -while keeping the number of endpoints very close to the maximum, and thus preserving the density of the trade-off.

1 r ≈ 1 α -1 ⇔ r ≈ α 1-α 0
Figure 2 illustrates the difference between the scenarios m 0 = rm max t and m 0 = N in terms of maximum number of elements in each column.

Intermediary Filtration

Classically, computing a rainbow table requires m 0 ×(t+1) elements to compute, although only m t × (t + 1) elements are represented in the final (clean) matrix. Discarding merged chains at the end of the precomputation is a wasted effort, because a single chain is kept among multiple chains with the same EP (i.e., hash operations performed after a merge occurs are useless). An option to mitigate this waste is to remove duplicated values progressively.

So, instead of computing the full chains in a row, from the SPs to the EPs, chains are divided into sub-chains, and merging chains are detected and discarded at the end of each sub-chain. A sub-chain is delimited by Intermediary Points (IPs). Computation of chains is thus performed "column by column" (or group of columns after group of columns), as opposed to the typical "chain-bychain" method. A filter is placed in selected columns (IPs): when all sub-chains have been computed up to the filter, a filtration is performed: only one of the merged chains is saved. Figure 7 in appendix C, presents the mechanism of filtration with an example zooming on 2 filters.

Filtration in Each Column

The minimum number of elements to be computed to generate a table is obtained when duplicates are removed in each column, i.e., if each chain of length t is divided in t sub-chains of length 1. Proposition 2. Let m i denote the number of unique elements in column i of a rainbow matrix. The number P of hash operations to precompute a m t × (t + 1) clean rainbow matrix is lower bounded by:

P ≥ t-1 i=0 m i .
Proof. Given that the minimum hash operations to compute in order to obtained a table is when duplicates are removed in each column and that m i denote the number of unique elements in column i, then the expression of the lower bound is trivial.

Theorem 2 quantifies this with results from Section 3.1.

Theorem 2. Given m 0 = rm max t the number of SPs, t + 1 the number of columns, and r t, we have that the naïve precomputation cost is:

P naive = m 0 t ≈ 2rN, (2)
and the minimum precomputation cost is:

P min = t-1 i=0 m i ≈ 2N ln(1 + r). (3)
Proof. The proof of Eq. ( 2) follows directly from m 0 = 2N γ ≈ 2rN t . For Eq. ( 3), we have:

t-1 i=0 m i = 2N t-1 i=0 1 i + γ = 2N t+γ-1 i=γ 1 i = 2N t+γ-1 i=1 1 i - γ-1 i=1 1 i = 2N [H t+γ-1 -H γ-1 ] ≈ 2N [ln(t + γ -1) -ln(γ -1)] = 2N ln t + γ -1 γ -1 with H n = n k=1
1 k the n-th harmonic number. Using γ ≈ t r and given that r t, the exected result is obtained.

For values of r such that m 0 N (i.e., "reasonable" values), we can make the approximation that γ is large (leading itself to the asymptotic approximation of H n ). This allows an expression of P min that only depends on N and r and is in particular virtually independent of t. For m 0 = N however these approximations do not hold, and the resulting expression of P min does depend on t (Corollary 1). We remark that the precomputation cost in all cases is linear in N .

Corollary 1. For the case m 0 = N , precomputation costs are respectively P naive = N t and P min ≈ 2N (H t+1 -1), with H n the n-th harmonic number.

Proof. The expression for P min results from instantiating 2N [H t+γ-1 -H γ-1 ] (similarly to the proof of 2) to γ = 2 (from Eq. ( 1)).

From Theorem 2, we observe, for instance, that using a filter in each column with a typical r = 20 reduces the number of performed hash operations by about 85% (regardless of N or t). Tables 1 and2 display the maximum speedup P naive /P min that can be obtained when filtering in each column with respect to no intermediary filtering. Results in Table 1 are valid for any (sensible) N and t.

Filtration in Chosen Columns

In practice, it may not always be beneficial to filter in every column, because this may involve an excessive overhead due to the filtering cost (results provided in Section 3.3 consider the number of hash operations, but they do not consider the additional time due to filtration and communication). Before considering this cost, an intermediary step consists in evaluating the number P of hash operations to be performed if the filtering technique is applied to a < t + 1 columns only:

P = a i=0 m ci (c i+1 -c i ), (4)
where c i the column of the i-th filter, and c 0 = 0 and c a = t + 1. Given a number of filters a and t very large compared to this number 7 , the optimal average number of hash operations is given in Theorem 3.

Theorem 3. The optimal average number of hash operations for precomputation with a filters and a t is:

P = 2N a t + γ -1 γ 1 a -1 .
The optimal placement of the filters is given by:

c i = γ t + γ -1 γ i a -γ + 1.
Proof. See Appendix A. 7 If a is too close to t, several filters could be affected to the same column. Choosing a t is not a problem, as presented in Figure 3. Figure 3 illustrates Theorem 3 for N = 2 42 , t = 10 000, and r = 20. It shows the number of hash operations needed for precomputation with varying number of filters a, placed according to Theorem 3. It also displays the lower bound (P min ) in terms of hash operations, which is reached when a filter is applied in each column. The case a = 1 corresponds to P naive (filtration only in the last column).

It indicates diminishing returns in increasing a. For instance in that scenario, P with a single filter is 2.88 times faster than using no filter. On the other hand, using a filter in each column is only about 1% faster than using 50 filters. Note that the optimal distribution of filters is actually not uniform. Indeed, detecting merges as soon as they occur avoids to waste time computing the useless remaining parts of the chains. As a consequence filters are mostly located on the left-hand parts of the chains.

This, together with the fact that the cost of non-hashing operations is not necessarily negligible in a practical implementation, implies that a limited number of filters is preferable. The next sections discuss an implementation and quantify this effect.

Distributing Precomputation

Distribution and Filtration

Even with filters, generating rainbow tables on a single computing node takes too much time when considering practical cases. To compute m 0 chains of length t, m 0 t = 2rN hash operations are needed. For example, for N = 2 42 and r = 20, building a clean table of about 0.95 m max t chains with optimal filters requires 2.7×10 13 hash operations, which would take about 40.5 days on a single processor core.

To generate tables of such size, precomputation should be distributed. Without filters, the precomputation phase is easily parallelizable. If n h hashing nodes are available, the total time is simply divided by n h , with each hashing node performing 2rN n h hash operations (assuming only the hashing time is taken into account and all hashing nodes have the same performances).

However, as seen in Section 3.2, precomputing a (quasi-maximum) clean rainbow table without intermediary filtering wastes significant effort due to merging chains. Therefore considering both distributing and filtering is essential8 .

Distributed Architecture

Distribution of the precomputation phase with intermediate filtering requires the nodes to communicate. We consider in what follows that n h nodes are dedicated to perform hash operations and n f nodes to filter chains, with n h + n f = n. Filtration and computation of chains are carried out in parallel 9 , in an effort to minimize the number of non-hashing operations. Sub-chains computed by the n h hashing nodes are sent eagerly to the n f filtration nodes.

In the environments and problem sizes we considered, the filtration effort was not significant enough compared to the hashing effort to warrant using more than a single filtration node. It is possible that for other environments (e.g., low bandwidth) or larger spaces, dedicating more nodes to filtering could be beneficial.

Estimation of the Precomputation Time

Precomputation Process In an environment with a single filtration node, this node is also in charge of the different tasks sequencing. A job is defined as a number of sub-chains to be computed between two filters. A job of size s contains s SP-IP pairs. Precomputations are hence divided in two main parts: jobs to be performed between filters and the filtration of these jobs. Precomputations consists of managing, for each filter, the sending of jobs to the hashing nodes and the filtration of the completed jobs.

The rationale behind choosing to bundle sub-chains into jobs is to mitigate the communication overhead. Using s = 1 is, for instance, a bad idea, because the overhead due to the communication, would significantly hinder performance. On the other hand, using a very large s may result in additional idle time by the computing nodes, for instance if there is no available chains left to compute for an idling computing node but some other computing nodes are still busy 10 . In what follows, we consider that the value of s is reasonable.

Once receiving a job, a hashing node starts from each IP to compute the new IPs corresponding to the column of the next filter. Once these computations are done, it returns the SPs and the new IPs to the filtration node, sends a new job back to it. The filtration node purpose is to receive jobs from hashing nodes and send new ones as soon as it receive it. At the meantime the filtration node filters already received jobs. This procedure is repeated between each filter until the end of the computation phase. As described in Section 3.4, it is not possible in a distributed architecture to filter in every column since the filtration adds an overhead. The problem of choosing the positions of the filters is discussed in Section 4.4.

Impacting Functionalities Several functionalities are required to perform the precomputation phase: hashing (i.e., computing sub-chains), filtration, and communication. In this section the way to evaluate the time needed for each of these functionalities is described.

Hashing time (H). Jobs computations are carried out by hashing nodes. Given a filters with a < t + 1, the total number of hash operations to be performed is a i=1 m ci-1 (c i -c i-1 ) (Eq. ( 4)) with c i the column of the i-th filter, c 0 = 0 and c a = t + 1. A hashing node can perform v h applications of f i = R i • h per second. v h is determined before the beginning of precomputations and depends of the hashing nodes performance. Computations of chains are considered to be done in parallel, by n h hashing nodes with equal performances. The total hashing time can therefore be estimated as:

H = 1 n h v h a+1 i=1 m ci-1 (c i -c i-1 ). ( 5
)
Filtration time (F ). For a filter in column i, the number of points that have to be filtered is m ci-1 . The total number of points that have to be filtered in the entire precomputation is hence a+1 i=1 m ci-1 . We consider that a filtration node can perform v f filtrations per second. The total time due to filtration is thus:

F = 1 v f n f a+1 i=1 m ci-1 . (6)
We also model for a potential overhead due to the filtration. This can for instance result from processing the output of the filtration into jobs to be sent to hashing nodes. This overhead depends on the number of elements generated and depends on the implementation (filtration algorithm, memory allocation, etc.). Given d o the average overhead time per point, the total overhead O can be expressed as:

O = d o a+1 i=1 m ci-1 . ( 7
)
particular choice of s therefore has negligible impact on the performance, provided it lies in that range

Communication time (C).

Communication time is the time needed for the communication of jobs between filtration nodes and computing nodes. Let d c be the average time for a job to be sent from a filtration node to a hashing node and We assume that when a communication is in progress with one hashing node all the other hashing nodes are computing. The impacting communication time can then be estimated by:

C = d c n h a+1 i=1 m ci-1 (8)
Total time. Given that computation of sub-chains and filtration are performed in parallel, the most impacting component in the total time spend to generate a rainbow table is the maximum time between the hashing time H and the filtration time F i.e., Max(H, F )11 . To obtain the total time, the communication time has to be added as well as the overhead time due to filtration. The total time T needed to generate a clean rainbow table is hence:

T = Max(H, F ) + C + O. ( 9
)

Optimal Configuration

The number of filters and their positions have a considerable impact on the precomputation time. Let a configuration be a set C = {c 1 , . . . , c a }, where a is the number of filters, and c i the position (column number) of the i-th filter. Let C * a be the configuration of a filters that minimizes Eq. ( 9), and C * = min a C * a . Due to the various operations outside of hashing, in particular the filtering process (which, to some extent, can be done in parallel to hashing) and other communication/data processing overheads, the configuration given by Theorem 3 typically gives sub-optimal results. For this reason we rely instead of numerical minimization of Eq. ( 9), which models the precomputation time given by our implementation.

We settled on a truncated-Newton method [START_REF] Stephen | A survey of truncated-newton methods[END_REF], an optimization algorithm suitable to solving bounded optimization problems with many variables (see e.g., [START_REF] Stephen | A survey of truncated-newton methods[END_REF] for a thorough description). The minimization is used to find C * a , coupled with an exhaustive search on a12 . The optimality of the configuration found by the numerical minimization is predicated on the two following conjectures: (1) C * a is a convex function of a and (2) Eq. ( 9) is smooth enough (w.r.t. C) to guarantee or approach the conditions of optimality of the truncated-Newton search13 [START_REF] Stephen | A survey of truncated-newton methods[END_REF]. We offer no proof of these conjectures, but note that they seem to hold true both intuitively and after extensive testing.

Regardless of the validity of these conjectures however, the configuration obtained through numerical minimization presents a significant over the analytical minimization that assumes no overhead or filtration cost (Theorem 3). In addition, the estimated precomputation time comes very close to the theoretical minimum, as detailed in Section 5.

Experiments

Computing Environments

We conducted our experiments on two different environments that are described below. We benchmarked these two environments before starting the precomputation phase in order to measure the hashing speed v h , the filtration speed v f , the overhead d o related to the implementation of the filtration, and the communication cost d c . The benchmark has been done by generating tables on a small-sized problem (N = 2 32 ) with filters placed according to Theorem 3.

Environment 1 consists of a computer hosting two AMD EPYC 7742 3.2 GHz processors composed of 64 cores each, for a total of 128 cores 14 . The benchmark measured v h = 7 747 002 hashs per seconds, v f = 15 949 709 filtrations per second, and v 0 = 1.37 × 10 -10 . The communication overhead is negligible compared to v h and v f , it can hence be considered that d c = 0 which implies that d o + dc n h = d o = 1.37 × 10 -10 seconds to treat one point. Environment 2 is a cluster of 8 computers with 2 CPUs per machine and 14 cores for each CPU, i.e., a total of 224 cores. Each CPU is an Intel Xeon E5-2680 v4 (Broadwell, 2.40GHz, 14 cores). The computers are directly connected through switches, meaning that they commnicate using the ethernet protocol. The benchmark provided v h = 6 403 611 hashs per seconds, v f = 7 918 745 filtrations per second, and d o + dc sn h = 7.5 × 10 -10 seconds to treat one point.

Filtration Implementation

For the filtration, we used an open addressing hash table with the following parameters:

-A load factor λ = 2/3, which is a good compromise between size overhead and low probability of collision. -The number of slots of the table is k = m ci /λ = 1.5m ci with m ci the theoretical number of different points after filtration (given by Eq. ( 1)).

-The hash function used is IP mod k.

We used linear probing for collision resolution (with interval of 1). This is appropriate because inputs to the hash table are uniformly distributed in A (by construction). At each filtration the following steps carried out:

-A hash table of size k = 1.5m ci is created.

-As soon as a job is received by the filtration node this job is filtered as follow:

1. For each couple (SP ;IP ) of the job, IP mod k is computed.

2. The index IP mod k of the table is checked.

3. If at the index computed no value is present then IP and its corresponding SP are inserted at this index.

4. If at the index computed the same value equals to IP is present then a merge has occurred between two chain and IP and its corresponding SP are deleted.

5. If at the index computed, a different value of IP is present then a new value of index is computed and is equals to IP + 1 mod k, the index IP + 1 mod k is checked and the steps 3. to 5. are repeated.

-When all jobs have been filtered, the hash table is scanned and all the IP s and their corresponding SP s are transferred by copying them to an array in a form facilitating the sending of the jobs.

-The hash table is deleted.

Positions of the Filters

We conducted experiments where filters were optimally placed using the Truncated Newton Constrained (TNC) algorithm (Section 4.4) applied to Eq. ( 9).

For environment 1, the optimal configuration was 31 filters, with positions as provided in Figure 4. The latter figure also displays the positions of the 31 filters in the theoretical case where filtering and communicating are free (Theorem 3).

Figure 5 displays the number of hash operations needed to generate a clean rainbow table in our scenario, when: (left case) there are no filters, which is the current state of the art; (middle case) there are filters optimally placed, which is our approach ; and (right case) filtration and communication are free, with so a filter in each column, which is the theoretical lower bound. It is worth noting that our approach is tightly close to the theoretical lower bound (about 10% of the theoretical lower bound). Experiments were performed with the following parameters that represents a realistic scenario: N = 2 42 , t = 10 000, and r = 20. Corollary 1 provides the number of starting points in the experiment: m 0 = 2rN/t ≈ 1.76 × 10 10 . According to Proposition 1, the expected number of chains in a single such table is: 0.9524 m max t ≈ 8.38 × 10 8 . The chain length (t = 10 000) has an impact on the online phase: when t decreases, the time required for the online phase decreases as well, but the required memory increases. The chain length also has an impact on the precomputation phase when filters are used, but this effect is much smaller. As shown in Figure 6, the smaller t is, the greater the precomputation time.

We chose t = 10 000 because this value leads to a very fast online phase in the order of a few seconds with a reasonably-sized memory (for N = 2 42 ). Choosing t = 20 000 for instance would provide a 20% faster precomputation but would increase the time of the online phase four-fold.

Figure 6, also shows that our experimental results (green curve) is close to the theoretical lower bound (red curve) and that our method is much more efficient that the usual way to generate table (blue curve) as detailed in Section 5.5.

Results

Environment 1. Precomputing a single rainbow table without any filter requires m 0 t hash operations in our scenario, which is 100×2 42 . Given that v h = 7 747 002 and the environment consists of 127 cores (each core corresponding to one node) with 1 filtration node and 126 hashing nodes, the precomputation time is estimated to be 180 225 seconds (50 hours and 3 minutes), which is very close from our experimental result of 179 850 seconds (49 hours and 57 minutes). Now, using 31 filters optimally placed significantly reduces the precomputation time. Using Eq. ( 9), we obtain that the predicted precomputation time is as low as 30 657 seconds (about 8 hours). Filters thus divide by 5.9 the precomputation time in this scenario. The experimental result is 31 029 seconds.

Environment 2. According to the TNC algorithm, without any filter, the precomputation time of a single rainbow table should be around 123 194 seconds (about 34 hours and 13 minutes).

If 11 filters optimally placed are used, our experimental results show that a table can be generated in 26 499 seconds (about 7 hours and 20 minutes). According to TNC algorithm with the parameters for this second environment, given in Section 5.1, this precomputation time is estimated to 26 139 seconds (about 7 hours and 12 minutes). Our experimental results are therefore very close from the predicted one.

Utilization of filters on this environment hence allows to generate a table in about 5 times less time than the naive method. Table 3 provides a summary of the results obtained for environments 1 and 2.

Conclusion

This paper introduces the concept of distributed filters to precompute rainbow tables. Such tables are widely used by the community of security experts, especially, but not only, to tests passwords. Given that the precomputation phase is highly resource-consuming, the technique we introduce in this paper has a strong practical impact. It also comes with formulas to compute the optimal positions of the filters, and to evaluate the precomputation time. We illustrate our technique on a typical scenario, namely a problem of size N = 2 42 (t = 10 000 and r = 20). In such a scenario, the precomputation phase requires 1.76 × 10 14 hash operations, which takes about 50 hours on a 128-core computer, while our technique requires 2.8 × 10 13 hash operations, which were performed (including filtering) in about 8 hours and 36 minutes on the same 128-core computer. Distributed filtration-computation thus divides by about 6 the expected precomputation time. It is also close to the theoretical lower bound of 27 452 seconds i.e., 7 hours and 33 minutes (for r = 20), with the difference due to the filtering and communication overheads.

We considered a typical scenario in the sense that we used quasi-maximum tables (r = 20) instead of maximum tables. Such maximum tables (corresponding to r = 5 001 in our case) are usually considered in the literature, but they are never used in practice because precomputing maximum tables is prohibitive. However, considering maximum tables would make distributed filtration-computation much more valuable still (e.g., increasing the speedup from 6 to 4 500 with the same parameters).

It is worth noting that our technique to speed up the precomputation phase has been applied to classical rainbow tables but we state in this article that it is fully compliant with the improvements published during the last years to make the online phase more efficient.

-Heterogeneous tables [START_REF] Avoine | Heterogeneous rainbow table widths provide faster cryptanalyses[END_REF]: 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 [START_REF] Avoine | Interleaving cryptanalytic time-memory trade-offs on non-uniform distributions[END_REF]: Just like with heterogeneous tables, the different tables are independently computed, again having no impact on precomputation improvements

C Intermediary Filtration

Fig. 2 .

 2 Fig. 2. Number of unique elements mi remaining in column i (log scale) according to the value of m0 for N = 2 42 and t = 10 000.

14 PFig. 3 .

 143 Fig.3. Number of hash operations P (log scale) according to the number of filters used a, with N = 2 42 , t = 10 000, and r = 20. P with a filters according to Theorem 3 and P with t filters according to Theorem 2.

Fig. 4 . 14 Fig. 5 .Fig. 6 .

 41456 Fig. 4. Positions of the 31 filters

Fig. 7 .

 7 Fig. 7. Intermediary filtration with 2 filters.

Table 1 .

 1 Speedup for quasi-maximum tables for different values of r.

	r	10 15 20 30 50
	r ln(1+r) 4.17 5.41 6.57 8.74 12.72

Table 2 .

 2 Speedup for maximum tables of various lengths.

	t	1 000 10 000 100 000
	t 2(H t+1 -1) 77.03 568.98 4508.50

Table 3 .

 3 Summary of the results (N = 2 42 , t = 10 000, r = 20)

	Scenario	#Filters #Hashes (×10 12 )	#Cores	Time Experimental	Predicted
	Environment 1 (state of the art)	0	176	127	179 850	180 225
	Environment 1 (our approach)	31	28	127	31 029	30 657
	Environment 1 (theoretical bound)	10 000	26.8	127	-	27 452
	Environment 2 (state of the art)	0	176	224	123 717	123 194
	Environment 2 (our approach)	11	31	224	26 499	26 139
	Environment 2 (theoretical bound)	10 000	26.8	224	-	18 765

Table 4 .

 4 Notation N Cardinality of A t Number of columns in a table m Number of rows in a table m i Number of different elements in column i a Number of filters n h Number of computing nodes n f Number of filtration nodes n Number of nodes n = n h + n f α maximality factor r Column of the ith filter s Job size v h hashing speed v f Filtration speed d c Communication cost d o Filtration overhead

	α
	1-α
	c i

This paper will not discuss how to use the rainbow tables during the online phase, as the approach is developed in other papers.

Distributed filtration-computation has negligible impact on the online phase, including its many improvements. See Appendix B for more details.

[START_REF] Avoine | Optimal storage for rainbow tables[END_REF] Technically, filtration starts and stops slightly after computation of

chains.[START_REF] Avoine | Heterogeneous rainbow table widths provide faster cryptanalyses[END_REF] Experiments show that, for the typical problem sizes and architecture considered, choosing s to be anywhere from 1 000 to 100 000 mitigates both of these issues. The

In general, for an architecture with a single filtration node, hashing time is much bigger than the filtering time. If the parameters of the problem and the architecture are such that it is not the case, then an other architecture with several filtration nodes should be considered.

To keep things efficient, the search is from 0 up to a reasonable upper bound amax. A more sophisticated approach could be used here (e.g., Newton descent on a), but we found it to be unnecessary.

Namely strong convexity and Lipschitz-continuous Hessian.

We used 127 of them to be sure that all cores are fully exploited for the precomputation, and the last core was left available for the basic operations performed by the system.

Appendix

A Proof of Theorem 3

We have P = a i=0 m ci (c i+1 -c i ). Deriving for each filter column position, we obtain:

Inserting m i = 2N i+γ-1 we have:

To minimize P , we must have ∂P ∂ci = 0, and thus:

It is easy to verify that a solution to this recurrence relation with terminal conditions c 0 = 1 and c a = t is:

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 [START_REF] Avoine | Optimal storage for rainbow tables[END_REF]): lossless compression can be applied at the end of the table generation, with no impact on the precomputation process. -Truncated endpoints [START_REF] Avoine | Analysis of rainbow tables with fingerprints[END_REF]: Endpoints can be truncated at the end of the table generation, again with no impact. -Checkpoints [START_REF] Avoine | Characterization and improvement of time-memory trade-off based on perfect tables[END_REF][START_REF] Avoine | Analysis of rainbow tables with fingerprints[END_REF]: 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.