Gildas Avoine

Xavier Carpent

Diane Leblanc-Albarel

Stairway To Rainbow

Keywords: Security and privacy → Cryptanalysis and other attacks; Authentication Applied Cryptography, Time-Memory Trade-Offs, Password Cracking, Rainbow Tables

A cryptanalytic time-memory trade-off is a technique introduced by M. Hellman in 1980 to perform brute-force attacks. It consists of a time-consuming precomputation phase performed and stored once and for all, which is then used to reduce the computation time of brute-force attacks. A variant, known as rainbow tables, introduced by Oechslin in 2003 is used by most of today's off-the-shelf password-guessing tools. Precomputation of such tables is highly inefficient however, because much of the values computed during this task are eventually discarded. This paper revisits rainbow tables precomputation, challenging what has so far been regarded as an immutable foundation. The key idea consists in recycling values discarded during the precomputation phase, and adapting the brute force phase to make use of these recycled values. For a given memory and probability of success, the stepped rainbow tables thus created significantly reduce the workload induced by both the precomputation phase and the attack phase. The speedup obtained by using such tables is provided, and backed up by practical experiments.

TMTO [START_REF] Vanhoef | A Time-Memory Trade-Off Attack on WPA3's SAE-PK[END_REF]. TMTOs have notoriously been used to demonstrate the weakness of Windows passwords [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF] and played a significant role in the popularization of salting in password hashing.

The preimage problem is defined as "finding 𝑥 * ∈ 𝐴 such that ℎ(𝑥 * ) = 𝑦, given a one way (e.g., hash) function ℎ : 𝐴 → 𝐵, and an image 𝑦 ∈ ℎ(𝐴) ⊆ 𝐵". It has two extreme solutions: (1) the brute force attack, where all preimages in 𝐴 are tested sequentially; and (2) the dictionary or precomputed attack, where a database of preimage-image pairs is computed and saved, and answering an instance of the preimage problem consists in a simple lookup. Denoting 𝑁 = |𝐴|, the former costs 𝑂 (𝑁 ) hash operations during the attack phase but requires no setup or storage. The latter costs 𝑂 (𝑁 ) hash operations during the precomputation phase as well as 𝑂 (𝑁 ) in storage, but costs nothing in the attack phase (barring the cost of the lookup). A TMTO presents a compromise between the two: with 𝑂 (𝑀) memory, the attack phase costs 𝑂 (𝑁 2 /𝑀 2 ) and the precomputation phase is 𝑂 (𝑁 ) [START_REF] Barkan | Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs[END_REF].

Variants on Hellman's original construction have been developed over time. Some were designed to be applied to stream ciphers [START_REF] Babbage | Improved "exhaustive search" attacks on stream ciphers[END_REF][START_REF] Biryukov | Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers[END_REF][START_REF] Dj | Cryptanalysis of alleged A5 stream cipher[END_REF], or generalized to work with multiple data (socalled Time-Memory-Data Trade-Off [START_REF] Biryukov | Improved Time-Memory Trade-Offs with Multiple Data[END_REF]). Others apply TMTOs in specific circumstances or environments, such as when the input space is not uniformly distributed [START_REF] Avoine | Interleaving Cryptanalytic Time-Memory Trade-Offs on Non-uniform Distributions[END_REF][START_REF] Yaacov | Security analysis of generic iterated hash functions[END_REF], using external memory [START_REF] Avoine | How to Handle Rainbow Tables with External Memory[END_REF][START_REF] Kim | Analysis of the Rainbow Tradeoff Algorithm Used in Practice[END_REF], or FPGA [START_REF] Mentens | Time-Memory Trade-Off Attack on FPGA Platforms: UNIX Password Cracking[END_REF][START_REF] Standaert | A Time-Memory Tradeoff Using Distinguished Points: New Analysis & FPGA Results[END_REF] and GPU [START_REF] Kim | High-speed parallel implementations of the rainbow method based on perfect tables in a heterogeneous system[END_REF][START_REF] Lu | Time-Memory Trade-Off Attack on the GSM A5/1 Stream Cipher Using Commodity GPGPU[END_REF]. Finally, a number of techniques were designed to improve the trade-off characteristics, most notably distinguished points [START_REF] Hong | Variants of the Distinguished Point Method for Cryptanalytic Time Memory Trade-Offs[END_REF], rainbow tables [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF], and fuzzy rainbow tables [START_REF] Kim | Analysis of the Non-perfect Table Fuzzy Rainbow Tradeoff[END_REF]. All of these have been analyzed [START_REF] Avoine | Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables[END_REF][START_REF] Standaert | A Time-Memory Tradeoff Using Distinguished Points: New Analysis & FPGA Results[END_REF], improved upon [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 | Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints[END_REF], and compared extensively [START_REF] Hong | A Comparison of Cryptanalytic Tradeoff Algorithms[END_REF][START_REF] Lee | Comparison of perfect table cryptanalytic tradeoff algorithms[END_REF]. The rainbow tables technique in particular stands out in terms of efficiency as evidenced in [START_REF] Lee | Comparison of perfect table cryptanalytic tradeoff algorithms[END_REF], and is also popular in practice partly due to the visibility of the Windows password attack [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF], and a number of hacking tools that implement rainbow tables [START_REF]Cryptohaze, GPU Rainbow Cracker[END_REF][START_REF]L0phtCrack, L0phtCrack 6[END_REF][START_REF]Objectif Sécurité, Ophcrack[END_REF][START_REF]RainbowCrack Project, RainbowCrack and Rain-bowCrack for GPU[END_REF]. We consequently focus on rainbow tables in this work.

A TMTO is usually thought of as a trade-off between attack time and attack memory (as its name suggests). However, other characteristics are important, namely: probability of success and precomputation time. The precomputation time in particular should not be underestimated, as for large 𝑁 , it is the most likely practical bottleneck [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF].

In this paper, we identify that these four characteristics are dictated by only three parameters: length of chains 𝑡, number of tables ℓ, and coefficient of maximality 𝛼 (see Sect. 2). We then propose a new construction of rainbow tables that takes this framework into consideration. Using the same memory and the same probability of success, this construction, named stepped rainbow tables, can reach new points in the trade-off space that were not reachable with classic rainbow tables, and performs better everywhere else. Using stepped rainbow tables for instance allows (all other characteristics being equal) for 1.2 times smaller attack time, or 2.56 times smaller precomputation time (See Sect. 6.4). The paper is organized as follows. Some background on the construction and properties of rainbow tables is given in Sect. 2. The concept and construction of stepped rainbow tables is given in Sect. [START_REF]Objectif Sécurité, Ophcrack[END_REF]. A theoretical analysis of their properties is given in Sect. [START_REF]RainbowCrack Project, RainbowCrack and Rain-bowCrack for GPU[END_REF]. A comparison between theoretical analysis and experiments is given in Sect. 5. A comparison between rainbow tables and stepped rainbow tables is given in Sect. 6. Finally, Sect. 7 concludes on the benefits of using stepped rainbow tables.

𝑓 0 𝑓 1 𝒙 0,1 -→ 𝑥

BACKGROUND ON RAINBOW TABLES 2.1 Matrix Generation

The first and main step of the precomputation is the construction of a so-called rainbow matrix (see Fig. 1), which consists of 𝑡 + 1 columns and 𝑚 rows, where each element is denoted 𝑥 𝑖,𝑗 , such that 𝑥 𝑖,𝑗 ∈ 𝐴 with 0 ⩽ 𝑖 ⩽ 𝑡 and 0 < 𝑗 ⩽ 𝑚. Given 𝑥 𝑖,𝑗 , 𝑥 𝑖+1,𝑗 is defined as:

𝑥 𝑖+1,𝑗 = 𝑓 𝑖 (𝑥 𝑖,𝑗 ). The functions 𝑓 𝑖 are called the hash-reduction functions and they are different in each column of the matrix with: 𝑓 𝑖 : 𝐴 → 𝐴 𝑥 𝑖,𝑗 ↦ → 𝑅 𝑖 (ℎ(𝑥 𝑖,𝑗 )) = 𝑥 𝑖+1,𝑗 , where 𝑅 𝑖 : 𝐵 → 𝐴 are called reduction functions and ℎ is the oneway function intrinsic to the preimage problem at hand. The choice of reduction functions is discussed in [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF]. In a nutshell, they are chosen to (1) (nearly) uniformly map elements from 𝐵 to elements in 𝐴,;

(2) all be different; and (3) take negligible time compared to hash functions. A common construction is 𝑅 𝑖 : 𝑦 ↦ → 𝑦 + 𝑖 mod 𝑁 .

A sequence (𝑥 𝑖,𝑗 ) 𝑡 𝑖=0 is called a chain. The length of a chain is the number of hash-reduction functions applied to build a chain. A matrix of 𝑡 + 1 columns has chains of length 𝑡.

Fig. 1 depicts a rainbow matrix. 𝑥 0,𝑗 is called the start point (SP) of row 𝑗 and it can be arbitrarily chosen. 𝑥 𝑡,𝑗 is called the end point (EP) of row 𝑗.

After the matrix is computed, only the start points and end points, i.e., the first and the last columns (in bold in Fig. 1) are stored, while intermediary values are discarded. This is the key point of the timememory trade-off technique. The set of pairs resulting from the first and last columns is called a rainbow table.

Clean Rainbow Tables

During the matrix generation, collisions may (and do) occur. When a collision between two values occurs in a given column, the corresponding chains merge, meaning that all their elements are equal after that column. More formally, a merge between two chains 𝑗 and 𝑘 occurs when 𝑥 𝑖,𝑗 ≠ 𝑥 𝑖,𝑘 and 𝑥 𝑖+1,𝑗 = 𝑥 𝑖+1,𝑘 for a given column 𝑖. Merges are a source of inefficiency for rainbow tables. It is thus recommended (see e.g., [START_REF] Hong | A Comparison of Cryptanalytic Tradeoff Algorithms[END_REF][START_REF] Lee | Comparison of perfect table cryptanalytic tradeoff algorithms[END_REF][START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF]) to keep a single chain in each set of merged chains. A table without merged chains is called a clean rainbow table 1 . The rest of the paper discusses clean tables only.

Maximality of Rainbow Tables

Since cleaning a table reduces the number of chains it contains, there is an upper-bound on the number of chains a clean table of a given length can have. A clean table is said to be maximal when it has been generated from 𝑚 0 = 𝑁 start points. Given a maximal table containing 𝑡 + 1 columns, the number of unique end points in column 𝑡 is given by Thm. 1, introduced and proved in [START_REF] Avoine | Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables[END_REF]. This approximation is very precise numerically, and its simple closed form allows for expressing other results in a clear and insightful way.

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

𝑚 max 𝑡 ≈ 2𝑁 𝑡 + 2 .
Computing maximal tables is not practical however, because 𝑁 is typically very large. In practice, non-maximal rainbow tables are generated, with 𝑚 0 ≪ 𝑁 . The maximality factor 𝛼 (with 0 < 𝛼 < 1), introduced in [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF] is defined in Eq. ( 1)

𝑚 𝑡 = 𝛼 𝑚 max 𝑡 . (1)
Eq. ( 2), introduced and proved in [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF], generalizes Thm. 1 and provides 𝑚 𝑖 , the expected number of unique points in column 𝑖, given 𝑚 0 :

𝑚 𝑖 ≈ 2𝑁 𝑖 + 2𝑁 𝑚 0 . (2)
By setting 𝑚 0 = 𝑟𝑚 max 𝑡 , one can combine Eq. (1) and Eq. ( 2) to derive Eq. (3) (see proof and details in [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF]):

𝑟 ≈ 𝛼 1 -𝛼 . (3)
This helps determine the target number of chains 𝑚 0 to generate in order to create a clean table with 𝑚 𝑡 chains and a maximality factor 𝛼:

𝑚 0 = 𝑚 𝑡 1 -𝛼 (4)

Success probability

The coverage of a given matrix is the ratio between the number of its unique values and 𝑁 . The coverage of a matrix is trivially equivalent to the success probability of the attack phase: a value in the matrix will always be recovered, and conversely. The success probability of a table with 𝑚 chains of length 𝑡 is given in [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF] for maximal rainbow tables and is adapted for non-maximal rainbow tables with 𝑚 𝑡 chains and 𝑡 + 1 columns in Eq. [START_REF] Avoine | Analysis of Rainbow Tables with Fingerprints[END_REF].

𝑝 = 1 -1 - 𝑚 𝑡 𝑁 𝑡 . (5)
With 𝑚 𝑡 = 𝑚 max 𝑡 , 𝑝 ≈ 1 -𝑒 -2 ≈ 0.86, which is an upper bound [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF]. In order to obtain a higher success probability, a set of ℓ independent tables should be used instead of a single one. For ℓ tables, the success probability is thus given by Eq. ( 6) [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF]:

𝑝 ℓ = 1 -(1 -𝑝) ℓ . (6)

Filtration

As explained in Sect. 2.2, among the 𝑚 0 chains used at the beginning of the precomputation phase, only 𝑚 𝑡 ≪ 𝑚 0 chains remain after cleaning. Therefore (𝑚 0 -𝑚 𝑡 ) •𝑡 hash operations -which represents most of the effort -are wasted.

The paper [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF] addresses this issue by introducing a technique named filtration, which significantly reduces the number of unnecessary hash operations during the precomputation phase. The filtration method consists in progressively cleaning the rainbow matrix in well-chosen columns instead of once at the end. Pushed to its limit, filtration in every column leads to Thm. 2 [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF].

Theorem 2. Given the factor 𝑟 = 𝑚 0 𝑚 max 𝑡 ≪ 𝑡, the number of columns 𝑡 + 1, the minimum precomputation cost is:

𝑃 min = 𝑡 -1 ∑ 𝑖=0 𝑚 𝑖 ≈ 2𝑁 ln(1 + 𝑟 ).
Filtering in every column is not advisable however, due to the overhead of the filtration process [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF]. Cleaning the tables in a limited number of well-chosen columns is already sufficient to be very close to the theoretical lower bound without incurring a significant overhead. For instance, filtering in 25 optimally-placed columns leads to a precomputation cost of 𝑃 ≈ 1.13 × 𝑃 min [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF].

Attack Phase

The attack phase is divided into 𝑡 steps (per table). One first assumes that 𝑥 * belongs to column 𝑡 -1 (of a given table) and tests the hypothesis as described below. If not, one proceeds similarly to column 𝑡 -2, and so on, until either a valid preimage is found, or until reaching the beginning of the table.

Checking whether 𝑥 * is in column 𝑡 -1 consists in checking whether 𝑅 𝑡 (𝑦) matches an end point 𝑥 𝑡,𝑗 (since the table is clean, there can be at most one such end point). If so, the chain 𝑗 is rebuilt from the corresponding start point 𝑥 0,𝑗 up to 𝑥 𝑡 -1,𝑗 . If ℎ(𝑥 𝑡 -1,𝑗 ) = 𝑦 (a case called a true alarm), the attack succeeds and the preimage of 𝑦 is 𝑥 𝑡 -1,𝑗 . If not (a case called a false alarm), the attack proceeds to the next step. In the next step, 𝑓 𝑡 (𝑅 𝑡 -1 (𝑦)) is computed and, again, the attacker checks for a matching end point. In the 𝑖-th step (corresponding to column 𝑡 -𝑖), 𝑓 𝑡 (𝑓 𝑡 -1 (. . . 𝑓 𝑡 -𝑖+1 (𝑅 𝑡 -𝑖 (𝑦)))) is computed.

The average number of hash operations needed to perform a search in column 𝑐 is given by Prop. 1. Proposition 1. For a given column 𝑐, the average number of hash operations 𝐶 𝑐 needed to perform a search is:

𝐶 𝑐 = 𝑡 -𝑐 𝑡 𝑖=𝑐 1 - 𝑚 𝑖 𝑁 .
Proof. A proof for maximal tables can be found in [START_REF] Avoine | Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables[END_REF]. The result is here generalized to non-maximal rainbow tables, as in the proof of Thm. 5. □

Once the search cost in a given column 𝑐 is known, the average number of hash operations for an entire attack using ℓ tables can be deduced. Thm. 3 gives a general expression of the average attack phase cost. Theorem 3. The average number of hash operations 𝑇 required to perform an attack using ℓ rainbow tables of length 𝑡, given a search space of size 𝑁 is:

𝑇 = ℓ 𝑡 ∑ 𝑐=1 𝑚 𝑡 𝑁 1 - 𝑚 𝑡 𝑁 ℓ (𝑐 -1) 𝑐 ∑ 𝑗=1 𝐶 𝑡 -𝑗+1 + ℓ 1 - 𝑚 𝑡 𝑁 𝑡 𝑡 ∑ 𝑐=1 𝐶 𝑐 .
Proof. See [START_REF] Avoine | Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables[END_REF]. □

Memory Used

Due to the characteristic complexity of the attack phase, 𝑂 (𝑁 2 /𝑀 2 ), optimizing the use of the memory is paramount. Different storage optimizations can be used to store rainbow tables [START_REF] Avoine | Optimal Storage for Rainbow Tables[END_REF][START_REF] Avoine | Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints[END_REF][START_REF] Avoine | Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables[END_REF]. In [START_REF] Avoine | Optimal Storage for Rainbow Tables[END_REF], the authors show that a very effective method to store rainbow tables, the compressed delta encoding method, allows to store tables with a memory very close to the theoretical lower bound (approx. 0.66% [START_REF] Avoine | Optimal Storage for Rainbow Tables[END_REF]). We use this lower bound in the rest of this paper, as it simplifies discussions, and is extremely close to the practical storage cost using compressed delta encoding. Near-optimal storage of rainbow tables consists in sorting and compressing the end points (using ad-hoc compression), and storing the start points as-is on ⌈log 2 (𝑚 0 )⌉ bits [START_REF] Avoine | Optimal Storage for Rainbow Tables[END_REF]. The total cost is given by Eq. ( 7):

𝑀 𝑅𝑇 = 𝑀 𝑅𝑇 𝑠𝑝 + 𝑀 𝑅𝑇 𝑒𝑝 = ℓ 𝑚 𝑡 ⌈log 2 (𝑚 0 )⌉ + log 2 𝑁 𝑚 𝑡 . ( 7
)

STEPPED RAINBOW TABLES

During the cleaning process of rainbow tables, most computed chains are discarded due to merges. Our key idea consists in recycling some of these merged chains instead of discarding them. The recycled chains are shorter than regular chains because the merged parts are removed. Such tables may contain several such "steps", leading to so-called stepped rainbow tables. For the sake of clarity, they are first introduced with a single step in Sect. 3.1, then generalized to the multiple steps in Sect. 3.2.

Stepped Rainbow Tables with a Single

Step corresponds to the application of a filter). The stepped rainbow matrix obtained at the end of precomputation phase is colored in green.

3.1.2 Attack Phase. In a classic rainbow table, all columns have the same probability of raising a true alarm, but the further to the right the column is, the lower is the cost of searching in that column (in other words, 𝐶 𝑐 is decreasing). Therefore, the most effective search order is from the last column 𝑡 and in subsequent decreasing order. For a 1-step stepped rainbow table, the probability of finding the preimage depends on the column index, because not all columns contain the same number of points: columns 0 to 𝑠 contain 𝑚 𝑠 points and columns 𝑠 + 1 to 𝑡 contain 𝑚 𝑡 points.

Moreover, when an alarm (true or false) occurs in a column 𝑐 with 𝑐 < 𝑠, it can either be detected in column 𝑠 or in column 𝑡. It is detected in column 𝑠 if a match occurs with one of the chains of length 𝑠, otherwise the alarm is detected in column 𝑡. The number of cryptographic operations needed to obtain an alarm is consequently not the same in all columns. Additionally, the number of cryptographic operations to check whether an alarm is true or false similarly depends whether the alarm was raised in column 𝑠 or in column 𝑡.

Consequently, with 1-step stepped rainbow tables, instead of exploring the table from column 𝑡 -1 to column 0, the search is performed in an order that minimizes the total expected time. This corresponds to searching in the non-explored column with the highest success probability over average cost ratio 2 .

The procedure to perform the attack phase with 1-step stepped rainbow table is provided in Algo. 1. The definition of the function 𝜇 that appears in Algo. 1 is provided in Def. 3. In a nutshell, this function returns the index of the most promising column for the forthcoming search.

Stepped Rainbow Tables with 𝜏 Steps

The concept of stepped rainbow tables can be naturally generalized to 𝜏 > 1 steps. Fig. 3 illustrates the resulting structure. In what Algorithm 1: Attack Phase (1-step) follows, the columns that specify the steps are denoted 𝑠 𝑖 with 0 < 𝑖 ⩽ 𝜏, with 𝑠 𝑖 < 𝑠 𝑗 for 𝑖 < 𝑗.

Input : 𝑦 ∈ 𝐵 : 𝑦 = ℎ (𝑥 * ) ∈ 𝐴 Output :𝑥 * (success) or ⊥ (failure) 1 𝑠𝑡𝑒𝑝𝑠𝐿𝑖𝑠𝑡 ← [𝑠, 𝑡 ] 2 𝐸𝑃 ← [ [𝐸𝑃 1 ...𝐸𝑃 𝑚𝑠 -𝑚𝑡 ], [𝐸𝑃 𝑚𝑠 -𝑚𝑡 +1 ...𝐸𝑃 𝑚𝑠 ] ] 3 𝑆𝑃 ← [ [𝑆𝑃 1 ...𝑆𝑃 𝑚𝑠 -𝑚𝑡 ], [𝑆𝑃 𝑚𝑠 -𝑚𝑡 +1 ...𝑆𝑃 𝑚𝑠 ] ] 4 𝑐 ← [𝑠, 𝑡 ] 5 v ← [0 : len(𝑐 ) -1] 6 𝑠𝑢𝑐𝑐𝑒𝑠𝑠 ← False 7 while 𝑐 ≠ [0, 0] and 𝑠𝑢𝑐𝑐𝑒𝑠𝑠 = False do 8 𝑎𝑙𝑎𝑟𝑚 ← False 9 for 𝑑 = 0 to len(𝑐 ) -1 do 10 v[𝑑 ] ← 𝜇 (𝑐 [𝑑 ] ) 11 end 12 𝑗 ← 𝑐 [v.index(max(v) ) ] 13 𝑖 ← 𝑗 14 𝑥 𝑖 ← 𝑅 𝑖 (𝑦) 15 while 𝑖 ⩽ 𝑡 and 𝑎𝑙𝑎𝑟𝑚 = False do 16 if 𝑖 ∈ 𝑠𝑡𝑒𝑝𝑠𝐿𝑖𝑠𝑡 then 17 𝑖𝑛𝑑𝑒𝑥 𝑖 ← 𝑠𝑡𝑒𝑝𝑠𝐿𝑖𝑠𝑡 .index(𝑖 ) 18 if 𝑥 𝑖 ∈ 𝐸𝑃 [𝑖𝑛𝑑𝑒𝑥 𝑖 ] then 19 𝑎𝑙𝑎𝑟𝑚 ← True 20 𝑥 ← 𝑆𝑃 [𝐸𝑃 [𝑖𝑛𝑑𝑒𝑥 𝑖 ].index(𝑥 𝑖 ) ] 21 for 𝑔 = 1 to 𝑗 -1 do 22 𝑥 ← 𝑓 𝑔 (𝑥 )
In the stepped rainbow table, 𝑚 𝑠 1 end points and their corresponding start points are stored: for each step 𝑠 𝑖 with 0 < 𝑖 < 𝜏, 𝑚 𝑠 𝑖 -𝑚 𝑠 𝑖+1 chains are stored with a length 𝑠 𝑖 , and 𝑚 𝑡 chains of length 𝑡 are also stored.

The attack phase using 𝜏 steps is similar to Algo.

ANALYSIS OF STEPPED RAINBOW TABLES

This section presents an analysis of the characteristics of stepped rainbow tables.

Notations

Definition 1. We note 𝑘 (𝑐) the index of the leftmost step that is to the right of column 𝑐, i.e., 𝑠 𝑘 (𝑐 ) -1 ⩽ 𝑐 < 𝑠 𝑘 (𝑐 ) .

Def. 1 is useful to express some quantities concisely, in particular: there are 𝑚 𝑠 𝑘 (𝑐 ) points in the step immediately to the right of column 𝑐; similarly, there are 𝑚 𝑠 𝑘 (𝑐 ) -𝑚 𝑠 𝑘 (𝑐 )+1 chains of length 𝑠 𝑘 (𝑐 ) there.

Where appropriate, 𝑠 𝜏+1 refers to column 𝑡 and 𝑠 0 refers to column 0. This convention allows for some results to be presented more clearly and concisely.

The ratio 𝜌 is also introduced in Def. 2 for the purpose of making subsequent results more concise. Definition 2. Given a column 𝑐 and a step 𝑠 𝑖 of a stepped rainbow table, the proportion of chains with length 𝑠 𝑖 in column 𝑐 is given by 𝜌 𝑖,𝑘 (𝑐 ) with 𝜌 𝑖,𝑗 such that:

𝜌 𝑖,𝑗 =        𝑚 𝑠 𝑖 -𝑚 𝑠 𝑖+1 𝑚 𝑠 𝑗 𝑖 ⩽ 𝜏 𝑚 𝑡 𝑚 𝑠 𝑗 𝑖 = 𝜏 + 1
In what follows, the attack chain refers to the chain built from 𝑦. The attack chain starting in column 𝑐 and ending in column 𝑡 is thus the chain finishing by the value 𝑓 𝑡 (𝑓 𝑡 -1 (. . . 𝑓 𝑐+1 (𝑅 𝑐 (𝑦)))))).

Success Probability

Theorem 4. Given 𝜏 steps noted 𝑠 𝑖 with 0 < 𝑖 ⩽ 𝜏, 𝑠 0 = 0 and 𝑠 𝜏+1 = 𝑡, and considering 𝑚 𝑠 𝑖 the number of unique elements in column 𝑠 𝑖 , the success probability 𝑝 of a single clean stepped rainbow table is:

𝑝 = 1 - 𝜏+1 𝑖=1 1 - 𝑚 𝑠 𝑖 𝑁 𝑠 𝑖 -𝑠 𝑖 -1 .
Proof. Each column 𝑐 covers 𝑚 𝑠 𝑘 (𝑐 ) different elements. Following a similar argument as for Eq. ( 5), we write:

𝑝 = 1 - 𝑡 𝑐=1 1 - 𝑚 𝑠 𝑘 (𝑐 ) 𝑁 .
Using the fact that 𝑠 𝑘 (𝑐 ) (and therefore 𝑚 𝑠 𝑘 (𝑐 ) ) is equal for all 𝑐 between two steps, we can group these factors together, resulting in the expression in Thm. [START_REF]RainbowCrack Project, RainbowCrack and Rain-bowCrack for GPU[END_REF]. □

The success probability for ℓ stepped rainbow tables 𝑝 ℓ is then directly obtained from Thm. 4, and is given by Eq. ( 8)

𝑝 ℓ = 1 -(1 -𝑝) ℓ . ( 8
)

Precomputation Time

Constructing stepped rainbow tables costs the same number of hash operations as classic rainbow tables (see Sect. 2.5). Whether intermediary steps are saved during the precomputation phase or not has no bearing on the number of hash computations (only the number 𝑚 0 of start points considered at the beginning of generation and the number and positions of filters matter). As shown in Sect. 6.4, the overhead due to filtration or the storage of intermediary points is insignificant.

A distinguishing feature of stepped rainbow tables however is that, for a given target memory and probability of success, 𝑚 0 is typically much smaller than with classic tables. All other things being equal, this significantly reduces the precomputation time.

The figure 𝑃 = 1.13 × 𝑃 min is used to quantify the number of hash operations performed in this phase (for both stepped rainbow and classic tables, in accordance with [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF]). As discussed in Sect. 5, our experimental results closely match this estimation.

Attack Time

Contrarily to rainbow tables, the search order is not monotonic. The cost in each column has an associated average cost, and a given probability that the search succeeds. The average attack time corresponds to the sum of the cost of the search in all columns, visited in optimal order, and weighted by the probability that the search stops there.

As in the classic case, a search in a given column either leads to a true alarm (successful search), a false alarm or to no alarm. An analysis of these probabilities and the associated costs is the focus of sections 4.4.1 to 4.4.6.

A useful intermediary result is the probability that no merge occurs between two given columns. This is one of the fundamental results in [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF] and is generalized to any two columns 𝑐 and 𝑐 ′ in Lemma 1. Lemma 1. Given two columns 𝑐 and 𝑐 ′ with 𝑐 < 𝑐 ′ ⩽ 𝑡, the probability that the attack chain does not merge with any chain of the rainbow matrix by 𝑐 ′ , given it had not merged in or before 𝑐, is:

𝑝 nomrg (𝑐, 𝑐 ′ ) = 𝑐 ′ 𝑖=𝑐+1 1 - 𝑚 𝑖 𝑁 . (9)
4.4.1 Probability of True Alarm. A true alarm occurs when the start point of the attack chain appears in the corresponding column of the stepped rainbow matrix.

Proposition 2. The probability that a true alarm occurs when starting the attack chain in 𝑐 is:

𝑝 find (𝑐) = 𝑚 𝑠 𝑘 (𝑐 ) 𝑁 .
Proof. There are 𝑚 𝑠 𝑘 (𝑐 ) different elements in column 𝑐 of the stepped rainbow matrix. Given that elements are uniformly distributed and that the number of elements in the solutions space is 𝑁 , the probability that the target 𝑥 * is an element of a column 𝑐 is the stated quantity. □ 4.4.2 Probability of False Alarm. In stepped rainbow tables, a false alarm occurs when the attack chain at column 𝑐 merges with a chain of the matrix. This is similar to classic rainbow tables, with the exception that this merge can be observed at any of the steps 𝑠 𝑖 > 𝑐, including indeed 𝑠 𝜏+1 = 𝑡, but not exclusively.

There is a distinction to be made as to whether the merge occurs before 𝑠 𝑘 (𝑐 ) or after. The two cases are analyzed in Props. 3 and4.

Proposition 3. The probability to raise a false alarm due to a merge between columns 𝑐 and 𝑠 𝑘 (𝑐 ) is

𝑝 fa-pre (𝑐) = 1 -𝑝 find (𝑐) -𝑝 nomrg (𝑐, 𝑠 𝑘 (𝑐 ) ).
Proof. Straightforward, as these events (no alarm, true alarm, false alarm) are mutually exclusive. □ Proposition 4. The probability to raise a false alarm due to a merge between columns 𝑠 𝑖 an 𝑠 𝑗 , with 𝑐 ⩽ 𝑠 𝑘 (𝑐 ) < 𝑠 𝑖 < 𝑠 𝑗 , is:

𝑝 fa-post (𝑐, 𝑠 𝑖 , 𝑠 𝑗 ) = 𝑝 nomrg (𝑐, 𝑠 𝑖 ) -𝑝 nomrg (𝑐, 𝑠 𝑗 ).
Proof. A false alarm due to a merge between columns 𝑠 𝑖 and 𝑠 𝑗 means that no merge occurs between 𝑐 and 𝑠 𝑖 but one occurs between 𝑠 𝑖 and 𝑠 𝑗 . Writing 𝐸 1 and 𝐸 2 respectively the events "no merge occurs between 𝑐 and 𝑠 𝑖 " and "a merge occurs between 𝑠 𝑖 and 𝑠 𝑗 ", we have:

𝑝 fa-post (𝑐, 𝑠 𝑖 , 𝑠 𝑗 ) = Pr(𝐸 1 ∧ 𝐸 2 ) = Pr(𝐸 1 ) × Pr(𝐸 2 | 𝐸 1 ) = 𝑝 nomrg (𝑐, 𝑠 𝑖 ) 1 -𝑝 nomrg (𝑠 𝑖 , 𝑠 𝑗 ) = 𝑝 nomrg (𝑐, 𝑠 𝑖 ) -𝑝 nomrg (𝑐, 𝑠 𝑖 )𝑝 nomrg (𝑠 𝑖 , 𝑠 𝑗 ) = 𝑝 nomrg (𝑐, 𝑠 𝑖 ) -𝑝 nomrg (𝑐, 𝑠 𝑗 )
The last equality stems from the nature of Eq. ( 9). □

Probability of No Alarms.

When no match occurs between the attack chain and end points of a table, no alarm is raised.

Proposition 5. The probability that no alarm occurs between a column 𝑐 and column 𝑡 is

𝑝 noalarm (𝑐) = 𝑝 nomrg (𝑐, 𝑡).
Proof. For no alarm to happen, the attack chain must not merge with the stepped rainbow matrix at any point between its start in column 𝑐 and its end in column 𝑡. □ 4.4.4 Cost of Alarms. The cost of an alarm, i.e., the number of cryptographic operations performed when an alarm occurs, is the same for true and false alarms. In both cases, an entire chain has to be rebuilt: firstly from column 𝑐, where the search is performed, to a step 𝑠 𝑖 or to column 𝑡 (depending where the merge is detected) and then from column 0 to column 𝑐 -1. Therefore, the cost of an alarm does not depends on its nature (true or false alarm) but only on the column in which it is detected. The cost of an alarm is given in Prop. 6 using Def. 2.

Proposition 6. Given a search performed in a column 𝑐 and 𝑘 (𝑐) the index of the leftmost step that is to the right of column c, the number of hash operations needed to rule out a false alarm is:

𝜏+1 ∑ 𝑖=𝑘 (𝑐 )
𝜌 𝑖,𝑘 (𝑐 ) 𝑠 𝑖 .

Proof. 𝜌 𝑖,𝑘 (𝑐 ) is the proportion of chains with length 𝑠 𝑖 in column 𝑐. It corresponds to the number of chains with a length 𝑠 𝑖 in column 𝑠 𝑖 divided by the total number of chains in column 𝑠 𝑖 . Given 𝑐 and 𝑘 (𝑐) as 𝑠 𝑘 (𝑐 ) -1 ⩽ 𝑐 < 𝑠 𝑘 (𝑐 ) , alarms are not necessarily detected in step 𝑠 𝑘 (𝑐 ) but can be detected in each step 𝑠 𝑗 > 𝑠 𝑘 (𝑐 ) . If a merge occurs in column 𝑗 with 𝑐 < 𝑗 ⩽ 𝑠 𝑖 , the probability that this merge is detected in step 𝑠 𝑖 is 𝜌 𝑖,𝑘 (𝑐 ) .

If an alarm is detected in step 𝑠 𝑖 , a chain of length 𝑠 𝑖 has to be rebuilt, which costs 𝑠 𝑖 hash operations. Therefore, the average cost of an alarm in a column 𝑐 is the sum of the probability to detect the alarm in each step 𝑠 𝑖 with 𝑐 ⩽ 𝑠 𝑖 , multiplied by the number of hash operations needed to rule it out, depending on the step in which the alarm is detected. □ 4.4.5 Cost of No Alarm. The cost of no alarm in a given column 𝑐 is (𝑡 -𝑐). If no alarm occurs in any steps, no chain will be rebuilt, therefore only (𝑡 -𝑐) hash operations will be computed.

Total Time of a Search in a Given

Column. The number of operations needed to perform a search in a column 𝑐 is given by Thm. 5.

Theorem 5. For a given column 𝑐 and the index 𝑘 (𝑐), the average number of cryptographic operations 𝐶 𝑐 needed to perform a search is: For 𝑠 𝜏 < 𝑐 ⩽ 𝑡:

𝐶 𝑐 = 𝑡 -𝑐𝑝 noalarm (𝑐). For 𝑐 ⩽ 𝑠 𝜏 : The average attack time i.e., the average number of hash operations needed to perform an attack with a set of ℓ stepped rainbow tables, is given by Thm. 6. Theorem 6. Given 𝑁 , ℓ stepped rainbow tables with 𝜏 steps, and considering its vector 𝜈 = [𝜈 1 , 𝜈 2 , ...𝜈 𝑡 ] ordering the columns of tables, the average number of hash operations 𝑇 required to perform an attack is:

𝐶 𝑐 = 1 -𝑝 nomrg (𝑐, 𝑠 𝑘 (𝑐 ) ) 𝜏+1 ∑ 𝑖=𝑘 (𝑐 ) 𝜌 𝑖,𝑘 (𝑐 ) 𝑠 𝑖 + 𝜏 ∑ 𝑗=𝑘 (𝑐 ) 𝑝 fa-post (𝑐, 𝑠 𝑗 , 𝑠 𝑗+1 ) 𝜏+1 ∑ 𝑖=𝑗+1 𝜌 𝑖,𝑗+1 𝑠 𝑖 + (𝑡 -𝑐) 𝑝 noalarm (𝑐).

Proof. See Appendix

𝑇 = ℓ 𝑡 ∑ 𝑐=1 𝑚 𝜈 𝑐 𝑁 𝑐 -1 𝑖=1 1 - 𝑚 𝜈 𝑖 𝑁 𝑐 ∑ 𝑗=1 𝐶 𝜈 𝑡 -𝑗 +1 +ℓ 𝑡 𝑖=1 1 - 𝑚 𝜈 𝑖 𝑁 𝑡 ∑ 𝑐=1 𝐶 𝜈 𝑐 .
with 𝑚 𝜈 𝑐 the number of points in column 𝑐, and with

𝑠 𝜈 𝑐 -1 ⩽ 𝑐 < 𝑠 𝜈 𝑐 .
Proof. This expression is a generalization of Thm. 3. The proof is constructed using an approach similar to the one used in [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF]. 𝑇 is obtained by adding on the one hand, the success probability of the attack using ℓ tables, multiplied by its average cost, and on the other hand, the failure probability of the attack using ℓ tables, multiplied by the cost of a failed search.

The first term is obtained by multiplying for each column 𝑐, the probability of true alarm in the column, with the probability of no true alarm in all earlier iterations:

𝑚 𝜈 𝑐 𝑁 𝑐 -1 𝑖=1 1 - 𝑚 𝜈 𝑖 𝑁
This is multiplied by the cost of all searches performed until reaching this column: 𝑐 𝑗=1 𝐶 𝜈 𝑡 -𝑗 +1 . The second term is obtained by multiplying the failure probability using ℓ tables, namely ℓ 𝑡 𝑖=1

Memory Used

Formulas to evaluate the memory needed to store rainbow tables are presented in [START_REF] Avoine | Optimal Storage for Rainbow Tables[END_REF]. In this section, these are adapted to stepped rainbow tables.

4.5.1 Rationale. When using stepped rainbow tables, instead of considering one set of points per table, end points and start points are grouped according to their step. For the same number of chains and the same number of tables, storage of stepped rainbow tables end points thus takes more memory than rainbow tables. Indeed, the points to be stored are divided into independent collections as opposed to a single collection, resulting in less efficient compression.

On the other hand, in order to generate the same number of chains and the same number of tables, much fewer start points need to be considered at the beginning of precomputation. Thus for a given number of chains (regardless of their size), 𝑚 0 is smaller for stepped rainbow tables than for classic tables. As the memory needed for storing start points depends on 𝑚 0 , the storage of start points ends up using less memory for stepped rainbow tables than for rainbow tables.

Overall, the memory for stepped rainbow tables compared to classic tables depends on specific parameters (See Sect. 6.5.3 for discussion). Nevertheless, in this paper we always choose parameters to compare with rainbow tables for the same coverage and memory.

4.5.2 Analysis. For each step 𝑠 𝑖 , there are 𝑚 𝑠 𝑖 -𝑚 𝑠 𝑖+1 points to be stored. These are in addition to the 𝑚 𝑡 chains of length 𝑡.

The memory needed to store the table end points is given by Eq. ( 10), adapted for stepped rainbow tables from [START_REF] Avoine | Optimal Storage for Rainbow Tables[END_REF].

𝑀 𝑆𝑅𝑇 𝑒𝑝 = ℓ log 2 𝑁 𝑚 𝑡 + 𝜏 ∑ 𝑖=1 log 2 𝑁 𝑚 𝑠 𝑖 -𝑚 𝑠 𝑖+1 . ( 10
)
As for start points, 𝑚 𝑠 1 points are stored for each table instead of 𝑚 𝑡 . The storage of individual start points is the same as in the classic case. The memory needed to store stepped rainbow tables start points, 𝑀 𝑆𝑅𝑇 𝑠𝑝 , is given in Eq. ( 11)):

𝑀 𝑆𝑅𝑇 𝑠𝑝 = ℓ𝑚 𝑠 1 ⌈log 2 (𝑚 0 )⌉. (11)
The total memory used to store ℓ stepped rainbow tables 𝑀 𝑆𝑅𝑇 is simply 𝑀 𝑆𝑅𝑇 = 𝑀 𝑆𝑅𝑇 𝑠𝑝 + 𝑀 𝑆𝑅𝑇 𝑒𝑝 .

EXPERIMENTS

This section illustrates the theoretical results obtained in Sect. 4 with practical experiments. Stepped rainbow tables with between 1 to 5 steps have been generated, and their precomputation time, success probability, and attack time have been compared to the respective theoretical results. In all cases, when a sufficient number of experiments have been done, the relative difference between theoretical and practical results is below 1%.

It is worth noting that the precomputation time (number of hash operations) is the same for both rainbow tables and stepped rainbow tables when considering equal parameters, namely number of start points, number and positions of filters, and value of 𝑡. The comparison that follows consequently focuses on attack time and success probability only.

In what follows, for the sake of clarity, we call configuration a list of parameters describing a set of rainbow tables: maximality factor of the tables, number of columns, and number of tables, respectively denoted 𝛼, 𝑡, and ℓ. When considering stepped rainbow tables, the configuration also contains the number of steps, denoted 𝜏, and their positions 𝑠 1 , . . . , 𝑠 𝜏 .

Availability

The code used to generate stepped rainbow tables and perform attacks with them is publicly available on GitHub 3 . It provides a python script that launches stepped rainbow tables generation for parameters (i.e., 𝑁 , ℓ, 𝛼, 𝑡 and step positions) given in the script header, and performs attacks using these generated tables. The number of attacks to perform has to be specified. Log files are created for tracing success probability, precomputation time and attack time.

Environment

Experiments were conducted on a computer hosting two AMD EPYC 7H12 processors composed of 64 physical cores and 64 virtual cores each, for a total of 128 physical cores and 128 virtual cores. We used up to 128 of the physical cores in our experiments.

The precomputation phase has been distributed as proposed in [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF] using the filtration method adapted on stepped rainbow tables. Both the precomputation and attack phases were written in C, using function SHA256 of OpenSSL for hashing. The Open MPI library was used to distribute the precomputation phase.

Success Probability

Theorem 4 is used to choose stepped rainbow tables configurations that reach a target success probability.

Experiments with different configurations were performed, containing up to 5 steps positioned between columns 0.3𝑡 and 𝑡. The positions of the steps are not critical in these experiments, given that there is no "optimal" configuration. Indeed, the position of the steps defines a trade-off between precomputation time and the attack time. Nevertheless, configurations with widely different step positions were tested to cover various cases: concentrated on the right, concentrated on the left, uniformly distributed, etc. Success probabilities were tested from 85% to 99.5%. All experiments lead to the same conclusions. For brevity, only the case using 2 tables and a 95% success probability is presented here. The probability of 95% have been chosen arbitrary but same results are obtained with other target success probabilities.

Fig. 4 depicts the success probabilities when considering experiments based on ℓ stepped rainbow tables with ℓ = 2. The blue horizontal line in the figure is the theoretical success probability, chosen to be 95%.

A test consists in randomly choosing one of the 𝑁 elements of the space 𝐴, hashing it, and trying to find its preimage using the generated stepped rainbow tables. In Fig. 4, 25 configurations are tested. A batch of 10 000 attacks was performed for each configuration. Each point of the figure represents a different tested configuration. The success probability obtained corresponds to the proportion of the attacks in the batch that succeeded.

For all configurations, the obtained success probabilities are all between 94.7% and 95.4%.

Attack Time

To test the compliance of the attack time with the model given in Sect. 4, various configurations have been tested. For each configuration tested, 25 batches of 20 000 attacks were performed, i.e., 500 000 attacks per configuration. For brevity and clarity of exposition, we display a random selection of 25 among the large sample of tested configurations. Tests were made for the same coverage and memory, though experiments performed for different memory and coverage lead to same conclusion. The 25 configurations presented here use 5 steps, 2 tables, and a 95% success probability. The differences between each configuration tested are various values of the parameters 𝛼 and 𝑡, and steps positions. The target probability and memory are the same. The memory 𝑀 and 𝑁 have been arbitrarily chosen to correspond to reasonable cases, namely 𝑀 = 63.9 GB and 𝑁 = 2 42 . The position of the steps varies between 0.3𝑡 and 𝑡 (See Sect. 6.3 for explanations about this bound).

Fig. 5 presents the results obtained. For each tested configuration, the average attack time of the configuration corresponds to the average number of hashes performed over the 500 000 attacks. Each point represents the ratio between the average attack time of each configuration and the theoretical counterpart given by Thm. 6.

The black line represents for each point the first and third quartile obtained on each of the 25 batches of 20 000 attacks. The black dashes represent quartiles 0 and 4.

The results are well distributed around 1.0. The large majority of experiments (between first and third quartile) are within ±1.5%. Fig. 5 leads to conclude that experimental results fit the theory very well. It is worth noting that significant variations in the attack time are intrinsic to rainbow tables and are noticeable for both stepped rainbow and classical rainbow tables.

EVALUATION

This section compares performances of rainbow tables and stepped rainbow tables. The comparison methodology is first introduced, then the configurations used for the comparison are established, the results are presented, and the compatibility of the stepped rainbow tables with existing improvements is finally discussed.

Comparison Methodology

The concept of configuration is introduced in Sect. 5. Defining such a configuration is needed prior to generating a set of tables. As concluded in [START_REF] Avoine | Rainbow Tables: How Far Can CPU Go?[END_REF], the precomputation time is usually the bottleneck that prevents the use of large-scale TMTOs. Nonetheless, the attack time is of primary importance as well. The comparison thus focuses on the trade-off between these two constraints.

Various trade-off curves are compared. For each comparison, a target success probability and an available memory for the attack phase are set. These parameters being fixed, the best configuration refers to the configuration for which there is no other configuration having both better precomputation time and better attack time, whether we consider rainbow tables or stepped rainbow tables. These configurations define the Pareto frontier for each comparison.

We describe costs (both precomputation and attack phases) in terms of number of hash operations. This allows for better accuracy, and can be transposed to any computing environment. A good approximation of the time in seconds for the precomputation or attack phase is indeed simply the number of hash operations to be performed divided by the number of hash operations computable per second on the chosen environment. As shown in [START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF], this approximation may vary slightly for the precomputation phase depending on the distributed environment used. For the attack phase, this approximation is very accurate.

Configurations

This section presents how the configurations for the comparisons were determined.

Rainbow Tables.

As previously explained in Sect. 5, three parameters, namely 𝛼, 𝑡, and ℓ are sufficient to fully define the characteristics of a rainbow table. The success probability of a single table and the memory available for the attack phase, respectively given by Eq. ( 5) and Eq. ( 7), are fixed by 𝛼 and 𝑡. Only the number of tables, ℓ, remains free. As a consequence, for any given value 4for ℓ, there exist a unique configuration once 𝛼 and 𝑡 are chosen.

Typically, the number ℓ of tables chosen, is the smallest or second smallest value that allows reaching the expected success probability 5 given by Eq. ( 6). In practice, only a small range of values for ℓ is used, since, above a certain number of tables (e.g., 6 tables and up), adding a table does not reduce the precomputation time significantly but does increases the attack significantly. Therefore, in practice, for a given success probability and a given memory for the attack phase, only a few configurations of rainbow tables are meaningful.

6.2.2

Stepped Rainbow Tables. By using stepped rainbow tables instead of rainbow tables, new parameters are available for determining possible configurations: the number of steps 𝜏, and their positions. Considering various numbers of steps and their possible positions, a large number of stepped rainbow tables configurations can reach the expected success probability and memory. When considering 𝜏 steps, the number of possible configurations is technically bounded by (𝑡 -1) 𝜏 . Among these, many provide better performance than rainbow tables. However, some of them perform worse. This often arises for example when the steps are mostly located towards the left part of the chains. Indeed, in such a case, a lot of very short chains are stored, causing a significant increase in memory without significantly increasing the success probability.

Parameters

We considered configurations with 1 to 5 steps positioned between 0.3𝑡 and 𝑡. Placing steps further to the left of the table (in columns smaller than about 0.3𝑡) is possible and the formulas apply perfectly to these cases, but in practice these tables are very inefficient and are therefore never used. Using more than 5 steps is possible but we have observed that it does not improve the trade-off between precomputation time and attack time sufficiently to justify the effort in finding the optimal step positions. To determine the configurations that reach the success probability and the available memory, we performed a search according to Algo. 3 available in Appendix C.

We chose a set of size 𝑁 = 2 42 and a memory of size 63.9 GB distributed over ℓ tables. 𝑁 = 2 42 has been used to provide an easy comparison with articles [START_REF] Avoine | Analysis of Rainbow Tables with Fingerprints[END_REF][START_REF] Avoine | Precomputation for Rainbow Tables has Never Been so Fast[END_REF], also dealing with this space. The memory was arbitrarily chosen to enable use of our results in practical cases.

For each evaluation we performed, we identified the configurations that reach the expected success probability and available memory according to Algo. 3. For all configurations, the precomputation time and the attack time are plotted, both expressed in number of hash operations.

Results

Results are presented in Fig. 6a to 6c, which correspond to success probabilities of 96%, 98%, and 99.5%, respectively. The (green) crosses in the figures represent the results for rainbow tables and the (red) dots, the results for stepped rainbow tables. Black dots identify the best results, which indeed all correspond to stepped rainbow tables.

It is worth noting that the precomputation times differ between Fig. 6a to 6c depending on both the number of chains and the number of tables to generate to reach the target coverage given the target memory.

The main highlight is that, no matter the success probability, there is always a configuration where stepped rainbow tables behave better than rainbow tables. In other words, when comparing rainbow tables and stepped rainbow tables for a same memory and success probability, rainbow tables are not on the Pareto frontier of configurations.

The relative gain depends on the success probability, which is mostly due to the maximality factor 𝛼. Indeed, whatever the success probability, using stepped rainbow tables reduces 𝛼 and thus the number of chains to be computed during the precomputation phase. Therefore the gain in precomputation time is even more important when the success probability requires a larger maximality factor. For example, Fig. 6b for success probability of 98%, using two stepped rainbow tables instead of two rainbow tables divides the precomputation time by 2.56 without increasing the attack time (as all of these comparisons, for the same coverage and the same memory used). On the environment described in Sect. 5.2, this correspond to generating a set of tables in approximately 5.6 hours, instead of 14.4 hours. If three classic rainbow tables are used instead of two, stepped rainbow tables perform 11% faster. On a single core, these attack times correspond to approximately 0.08 second per attack.

Table 1 provides the expected gains of several configuration examples with various success probabilities.

We compared so far stepped rainbow tables and rainbow tables either for the same attack time or for the same precomputation time. However, Fig. 6a to 6c shows that many other configurations ("best configurations", represented by black dots) may also be interesting in practice.

For instance, for a success probability of 99.5%, in the configuration identified by an orange dot in Fig. 6c, the use of stepped rainbow tables results in a precomputation time of 3.98 × 10 13 hash operations and an attack time of 1.53 × 10 6 hash operations. Compared to the 3-tables rainbow table configuration, this stepped rainbow tables configuration allows a reduction of 38% in the precomputation time for an attack time phase only 5% slower.

In the same vein, in Fig. 6a, the stepped rainbow tables configuration identified by an orange dot has a much faster attack time than the 3-table rainbow table configuration (right green cross) and in the same time has a slightly faster precomputation time. Indeed, using this stepped rainbow tables configuration instead of 3 rainbow tables decreases by 2% the precomputation time, and decreases by 16% the attack time. Compared to the 2-tables rainbow table configuration (left green cross), this stepped rainbow tables configuration allows a reduction of more than 30% in the precomputation time for an attack time phase only 4% slower.

Conclusion on Efficiency Comparison

6.5.1 Coverage. As seen in Sect. 2.4, the maximum coverage of a rainbow table is approximately 86%. Stepped rainbow tables, however, have a maximum coverage of 100%, obtained when a step is placed in every column. Of course, placing a step in every column is not worth the cost in memory. Instead, a few, well-positioned steps are used. Nevertheless, the coverage obtained with a stepped rainbow table is better than those obtained with a rainbow table. This allows using one or two fewer tables to obtain the same coverage for the same memory. This decreases simultaneously the attack time, and the precomputation time (all other characteristics being equal). 6.5.2 Attack Time. Even for the same number of tables used, there are always better configurations of stepped rainbow tables with the same memory and coverage as rainbow tables, that are faster in both attack and precomputation. The gain in precomputation is obtained from the smaller number of chains that have to be computed to obtain the same coverage.

When using the same number of tables, the attack time is smaller for a less obvious reason. As mentioned in Sect. 4, when a false is detected in a step, the attack chain is not rebuilt until the last column of the table. This allows to decrease the average cost of false alarms and thus, the attack time.

6.5.3 Memory. Intuitively, stepped rainbow tables are more expensive in memory than rainbow tables. However, in this paper, rainbow tables and stepped rainbow tables are compared for the same memory and the same coverage.

The memory used to store end points is larger for stepped rainbow tables than for rainbow tables, but as fewer points are considered at the beginning of the generation, less memory is required to store start points. The storage of start points allows to keep the total storage cost of stepped rainbow tables close to those of classic tables and thus obtain more efficient tables in precomputation and attack for the same memory and coverage. 6.5.4 Memory Accesses. Depending on the memory used for the trade-off, the number of memory accesses may also be quite relevant to determine the real cost of an attack.

The number of memory accesses needed for an attack with stepped rainbow tables and rainbow tables are very close. In our experiments, stepped rainbow tables in their optimal configurations typically require fewer memory accesses. This is particularly the case when stepped rainbow tables have fewer tables than classic rainbow tables, which is often the case, as discussed in 6.5.1.

Future Work

Many improvements on the seminal rainbow tables introduced by Oechslin [START_REF] Oechslin | Making a Faster Cryptanalytic Time-Memory Trade-Off[END_REF] have been published. Although some improvements and variants concern the precomputation phase, the vast majority of them focus on the attack phase.

Concerning the precomputation phase, the fuzzy rainbow variant [START_REF] Kim | Analysis of the Non-perfect Table Fuzzy Rainbow Tradeoff[END_REF] of TMTOs can have, for a same attack time, a slightly faster precomputation time than clean rainbow tables, but only for low success probabilities, which makes this variant uninteresting in many practical cases. The filtration method introduced in [10], designed for clean rainbow tables significantly reduces the precomputation time of rainbow tables and can be applied on stepped rainbow tables as well. The stepped rainbow tables and the rainbow tables configurations used in Sect. 5, have been generated using this method.

Concerning the attack phase, the major improvements on rainbow tables are checkpoints [START_REF] Avoine | Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints[END_REF], truncation and fingerprints [START_REF] Avoine | Analysis of Rainbow Tables with Fingerprints[END_REF][START_REF] Lee | Comparison of perfect table cryptanalytic tradeoff algorithms[END_REF], and the heterogeneous tables [START_REF] Avoine | Heterogeneous Rainbow Table Widths Provide Faster Cryptanalyses[END_REF], which is arguably the most efficient variant suggested so far. For the sake of clarity, stepped rainbow tables are introduced in the general case, without any improvement on the attack phase. Combining the concept of heterogeneous tables with stepped rainbow tables seems very promising since this could drastically reduce both the precomputation and attack phases. We leave the evaluation of combining these two methods for future work.

CONCLUSION

This paper introduces stepped rainbow tables, which outperform classic rainbow tables. The key idea of stepped rainbow tables consists in recycling chains that merged during the precomputation phase instead of discarding them. These recycled chains are shorter than classic ones. This leads to the concept of stepped rainbow tables, a name inspired by their staircase-like appearance in a graphical representation. The attack phase is modified accordingly to take advantage of the new construction. Stepped rainbow tables allow configurations that are not reachable by classic rainbow tables. The impact is twofold.

Firstly, stepped rainbow tables always perform better than classic rainbow tables. Either precomputation is reduced without increasing the attack time, or the attack time is reduced without increasing precomputation. Both of those characteristics are reduced in certain scenarios. The gain depends on the problem parameters and other characteristics. In the practical examples we explored, stepped rainbow tables divide by 2.56 the precomputation time for the same attack time, same coverage and same memory used, or reduce the attack time by up to 17% for the same precomputation time, same coverage and memory.

Secondly, stepped rainbow tables are able to slightly increase a parameter to significantly reduce another one. For instance for same coverage and same memory used, stepped rainbow tables can reduce the precomputation time by 38% while increasing by 5% the attack phase.

The consequence of the reduction in precomputation time in particular is not to be understated. The precomputation phase is the bottleneck of rainbow tables for large spaces today. And a reduction in the precomputation cost directly translates into a (admittedly modest, but significant) increase in the reachable attack space.

A PROOF OF THEOREM 5

Proof. To obtain the total cost of the search, the probability of the three events (true alarm, false alarm, no alarm) has to be multiplied by their cost and summed together. Case 1: 𝑠 𝜏 < 𝑐 ⩽ 𝑡.

(a) The probability of a true alarm is obtained from Prop. 2 and is 𝑚 𝑡 𝑁 , its cost is obtained from Prop. 6 and is 𝜌 𝜏+1,𝑘 (𝑐 ) 𝑠 𝜏+1 = 𝜌 𝜏+1,𝜏+1 𝑠 𝜏+1 = 𝑡.

(b) The probability of false alarm is given by Prop. 3 and is: 1 -𝑚 𝑡 𝑁 -𝑝 noalarm (𝑐). The cost is the same as for true alarms. (c) The probability of no alarm is given by Prop. 5 and its cost is 𝑡 -𝑐 (Sect. 4.4.5).

In total, we thus have: -𝑝 nomrg (𝑐, 𝑘 (𝑐)). Its cost is the same as for a true alarm.

𝐶 𝑐 =
(b') The probability of a false alarm due to a merge between 𝑠 𝑗 and 𝑠 𝑗+1 is 𝑝 fa-post (𝑐, 𝑠 𝑗 , 𝑠 𝑗+1 ) with 𝑐 ⩽ 𝑠 𝑗 < 𝑠 𝑗+1 and is given by Prop. 4. Therefore the probability of false alarm due to a merge between 𝑠 𝑘 (𝑐 ) and 𝑠 𝜏 is 𝜏 𝑗=𝑘 (𝑐 ) 𝑝 fa-post (𝑐, 𝑠 𝑗 , 𝑠 𝑗+1 ). Its cost, given by Prop. 6, depends of step 𝑠 𝑗 in which the false alarm is detected and is 𝜏+1 𝑖=𝑗+1 𝜌 𝑖,𝑗+1 𝑠 𝑖 . (c) The probability of no alarm is given by Prop. 5 and its cost is 𝑡 -𝑐 (Sect. 4.4.5).

In total, we thus have:

𝐶 𝑐 =

Figure 1 :

 1 Figure 1: Rainbow Matrix.

Figure 2 :

 2 Figure 2: Construction of stepped rainbow matrix with single step.

29 if 31 𝑖

 2931 𝑎𝑙𝑎𝑟𝑚 = False and 𝑠𝑢𝑐𝑐𝑒𝑠𝑠 = False then 30 𝑥 𝑖 ← 𝑓 𝑖 (𝑥 𝑖 ) False then 35 𝑐 [𝑐.index( 𝑗 ) ] ← 𝑐 [𝑐.index( 𝑗 ) ] -

Figure 3 :

 3 Figure 3: Stepped rainbow matrix with 𝜏 steps.

Figure 4 :

 4 Figure 4: Experimental success probability according to the configuration used, with theoretical success probability equal to 95%.

Figure 5 :

 5 Figure 5: Average number of hash for an attack over theoretical number of hash for different configurations.

  (a) Trade off between precomputation time and attack time 96% of success, 𝑁 = 2 42 and a 63.9 GB memory. 2 and 3 tables used. (b) Trade off between precomputation time and attack time 98% of success, 𝑁 = 2 42 and a 63.9 GB memory. 2, 3 and 4 tables used.(c) Trade off between precomputation time and attack time 99.5% of success, 𝑁 = 2 42 and a 63.9 GB memory. 3 to 5 tables used.

Figure 6 :

 6 Figure 6: Trade-off between precomputation and attack.

21 for 𝑔 = 1 29 if 31 𝑖 ← 𝑖 + 1 FunctionAlgorithm 3 : 15 𝑡 ← 𝑡 - 1 16𝑠𝑡𝑒𝑝𝑠 20 𝑡 ← 𝑡 + 1 21 𝑠𝑡𝑒𝑝𝑠

 2112931131512021 to 𝑔 = 𝑗 -1 do 22 𝑥 ← 𝑓 𝑔 (𝑥 ) 𝐴𝑙𝑎𝑟𝑚 = 𝐹𝑎𝑙𝑠𝑒 and 𝑠𝑢𝑐𝑐𝑒𝑠𝑠 = 𝐹𝑎𝑙𝑠𝑒 then 30 𝑥 𝑖 ← 𝑓 𝑖 (𝑥 𝑖 ) .𝑖𝑛𝑑𝑒𝑥 ( 𝑗 ) ] ← 𝑐 [𝑐.𝑖𝑛𝑑𝑒𝑥 ( 𝑗 ) ] -adjust used in Algo. 3, takes a number of column 𝑡, and a list of steps, with a relative step position between 30% and 100% of 𝑡 for each step. It return the positions of steps according to 𝑡. Algorithm used to find valid configurations input : The success probability TargetProba The targeted memory TargetMemory output : A list validConfig of configurations that reaches the targeted success probability and memory 1 Procedure: 2 𝑡 ← 1 3 𝛼 ← 0.001 4 for 𝑒𝑙𝑙 = 1 to ℓ = 6 do 5 for 𝑛𝑏𝑆𝑡𝑒𝑝𝑠 = 1 to 𝑛𝑏𝑆𝑡𝑒𝑝𝑠 = 5 do 6 for 𝑝𝑜𝑠 in all possible steps combinations do 7 𝑐𝑜𝑛𝑓 𝑖𝑔 ← [𝑡, 𝑎𝑙𝑝ℎ𝑎, ℓ, 𝑠𝑡𝑒𝑝𝑠] 8 𝑒𝑛𝑑 ← 𝑣𝑎𝑙𝑖𝑑_𝑐𝑟𝑖𝑡𝑒𝑟𝑖𝑎(𝑐𝑜𝑛𝑓 𝑖𝑔) 9 while 𝑒𝑛𝑑 ≠ 1 do 10 while 𝑝𝑟𝑜𝑏𝑎(𝑐𝑜𝑛𝑓 𝑖𝑔) < 𝑇 𝑎𝑟𝑔𝑒𝑡𝑃𝑟𝑜𝑏𝑎 do 11 𝛼 ← 𝛼 + 0.001 12 𝑐𝑜𝑛𝑓 𝑖𝑔 ← [𝑡, 𝑎𝑙𝑝ℎ𝑎, ℓ, 𝑠𝑡𝑒𝑝𝑠] 𝑖𝑔) < 0.999𝑇 𝑎𝑟𝑔𝑒𝑡𝑀𝑒𝑚𝑜𝑟𝑦 do ← 𝑎𝑑 𝑗𝑢𝑠𝑡 (𝑡, 𝑝𝑜𝑠) 17 𝑐𝑜𝑛𝑓 𝑖𝑔 ← [𝑡, 𝑎𝑙𝑝ℎ𝑎, ℓ, 𝑠𝑡𝑒𝑝𝑠] 𝑖𝑔) > 1.001𝑇 𝑎𝑟𝑔𝑒𝑡𝑀𝑒𝑚𝑜𝑟𝑦 do ← 𝑎𝑑 𝑗𝑢𝑠𝑡 (𝑡, 𝑝𝑜𝑠) 22 𝑐𝑜𝑛𝑓 𝑖𝑔 ← [𝑡, 𝑎𝑙𝑝ℎ𝑎, ℓ, 𝑠𝑡𝑒𝑝𝑠]

  1,1 -→ 𝑥 2,1 . . . . 𝒙 𝒕,1 𝑓 0 𝑓 1 𝒙 0,2 -→ 𝑥 1,2 -→ 𝑥 2,2 . . . . 𝒙 𝒕,2 𝒙 0,𝒎 -→ 𝑥 1,𝑚 -→ 𝑥 2,𝑚 . . . . 𝒙 𝒕,𝒎

	. . .	. . .	. . .	. . .
	𝑓 0	𝑓 1

  1. Algo. 2, provided in Appendix B, depicts the attack phase of the generalized stepped rainbow tables. 𝒎 𝒔 1 . . . 𝒙 𝒔 1 ,𝒎 𝒔 1

	𝒙 0,1	. . .	. . .	. . .	. . .	𝒙 𝒕,1
	. . .					. . .
	𝒙 0,𝒎 𝒕	. . .	. . .	. . .	. . .	𝒙 𝒕,𝒎 𝒕
	𝒙 0,𝒎 𝒕 +1	. . .	. . .	. . .	𝒙 𝒔 𝝉 ,𝒎 𝒕 +1
	. . .				. . .
	𝒙 0,𝒎 𝒔𝝉	. . .	. . .	. . .	𝒙 𝒔 𝝉 ,𝒎 𝒔𝝉
	𝒙 0,𝒎 𝒔𝝉 +1 . . .	. . .	𝒙 𝒔 𝝉 -1 ,𝒎 𝒔𝝉 +1
	. . .			. . .
	𝒙 0,𝒎 𝒔 𝝉 -1 . . .	. . .	𝒙 𝒔 𝝉 -1 ,𝒎 𝒔 𝝉 -1
	. . .		. . .
	. . .		. . .
	𝒙 0,

  A □ 4.4.7 Average Attack Time. As explained in Sect. 3.1.2, a metric 𝜇 (corresponding to probability of success over average cost ratio) is used to determine the most efficient column in which to perform each iteration of the search. Using 𝜇 as defined in Def. 3, vector 𝜈 is defined in Def. 4. Vector 𝜈 is composed of all columns of a stepped rainbow table from the most to least efficient. Definition 3. Given 𝑁 and a column 𝑐 with 0 ⩽ 𝑐 ⩽ 𝑡: Given a stepped rainbow table with 𝑡 columns, the vector 𝜈 with 𝜈 = [𝜈 1 , 𝜈 2 , . . . , 𝜈 𝑡 ] is obtained by sorting the columns [1, . . . , 𝑡] in decreasing order of 𝜇 (𝑐).

	𝜇 (𝑐) =	𝑚 𝑠 𝑘 (𝑐 )	.
		𝑁𝐶 𝑐
	Definition 4.

Table 1 :

 1 Expected gain illustrated on several examples with SRT meaning Stepped Rainbow Tables, and RT meaning Rainbow Tables. Precomputation and attack phase numbers are quantity of cryptographic operations.

		Success probability: 96%
		Precomputation	Attack
	2 SRT	2.46 × 10 13
	2 RT	3.26 × 10 13	6.99 × 10 5
	Gain	25%
	2 SRT		7.17 × 10 5
	3 RT	2.32 × 10 13	8.6 × 10 5
	Gain		17%
		Success probability: 98%
		Precomputation	Attack
	2 SRT	2.96 × 10 13
	2 RT	7.59 × 10 13	9.79 × 10 5
	Gain	61%
	2 SRT		1.04 × 10 6
	3 RT	3.17 × 10 13	9.26 × 10 5
	Gain		11%
		Success probability: 99.5%
		Precomputation	Attack
	3 SRT	4.4 × 10 13
	3 RT	6.42 × 10 13	1.45 × 10 6
	Gain	31%
	3 SRT		1.59 × 10 6
	4 RT	4.35 × 10 13	1.46 × 10 5
	Gain		8%

  𝑝 noalarm (𝑐) + (𝑡 -𝑐)𝑝 noalarm (𝑐) = 𝑡 -𝑐𝑝 noalarm (𝑐).Case 2: 𝑐 ⩽ 𝑠 𝜏 .(a) The probability of a true alarm is𝑚 𝑠 𝑘 (𝑐 )𝑁 , and its cost is𝜏+1 𝑖=𝑘 (𝑐 ) 𝜌 𝑖,𝑘 (𝑐 ) 𝑠 𝑖 . (b)The probability of a false alarm due to a merge between 𝑐 and 𝑠 𝑘 (𝑐 ) is given by Prop. 3 and is 1 -

	𝑡	𝑚 𝑡	+ 𝑡 1 -	𝑚 𝑡	-
		𝑁		𝑁

𝑚 𝑠 𝑘 (𝑐 )

𝑁

  𝑚 𝑠 𝑘 (𝑐 ) 𝜌 𝑖,𝑘 (𝑐 ) 𝑠 𝑖 + 1 -𝑚 𝑠 𝑘 (𝑐 ) 𝑁 -𝑝 nomrg (𝑐, 𝑠 𝑘 (𝑐 ) ) 𝑝 fa-post (𝑐, 𝑠 𝑗 , 𝑠 𝑗+1 ) 𝜌 𝑖,𝑘 (𝑐 ) 𝑠 𝑖 terms canceling out. □ B ATTACK PHASE WITH 𝜏 STEPS Algorithm 2: Attack Phase with 𝜏-Steps stepped rainbow table input : 𝑦 ∈ 𝐵 s.t. 𝑦 = ℎ (𝑥 * ) ∈ 𝐴 output :𝑥 * , if it belongs to the stepped rainbow matrix1 𝑠𝑡𝑒𝑝𝑠𝐿𝑖𝑠𝑡 ← [𝑠 1 , 𝑠 2 , ...𝑠 𝜏 , 𝑡 ] 2 𝐸𝑃 ← [ [𝐸𝑃 1 ...𝐸𝑃 𝑚𝑠 1 -𝑚𝑠 2 ], [𝐸𝑃 𝑚𝑠 1 -𝑚𝑠 2 +1 ...𝐸𝑃 𝑚𝑠 1 -𝑚𝑠 3 ]... [𝐸𝑃 𝑚𝑠 1 -𝑚𝑡 +1 ...𝐸𝑃 𝑚𝑠 1 ] ] 3 𝑆𝑃 ← [𝑆𝑃 1 ...𝑆𝑃 𝑚𝑠 1 -𝑚𝑠 2 ], [𝑆𝑃 𝑚𝑠 1 -𝑚𝑠 2 +1 ...𝑆𝑃 𝑚𝑠 1 -𝑚𝑠 3 ]... [𝑆𝑃 𝑚𝑠 1 -𝑚𝑡 +1 ...𝑆𝑃 𝑚𝑠 1 ] ] 4 𝑐 ← [𝑠 1 , 𝑠 2 , ..𝑠 𝜏 , 𝑡 ] 5 v ← [0 : 𝑙𝑒𝑛 (𝑐 ) -1]6 𝑠𝑢𝑐𝑐𝑒𝑠𝑠 ← 𝐹𝑎𝑙𝑠𝑒 7 while 𝑐 ≠ [0, 0, .., 0] and 𝑠𝑢𝑐𝑐𝑒𝑠𝑠 = 𝐹𝑎𝑙𝑠𝑒 do

			𝜏+1
			∑
		𝑁	𝑖=𝑘 (𝑐 )
				𝜏+1
				∑	𝜌 𝑖,𝑘 (𝑐 ) 𝑠 𝑖
				𝑖=𝑘 (𝑐 )
		𝜏
	+	∑
		𝑗=𝑘 (𝑐 )
	The conclusion follows from the	𝑚 𝑠 𝑘 (𝑐 ) 𝑁	𝜏+1 𝑖=𝑘 (𝑐 )

𝜏+1 ∑ 𝑖=𝑗+1 𝜌 𝑖,𝑗+1 𝑠 𝑖 + (𝑡 -𝑐) 𝑝 noalarm (𝑐).

8 𝐴𝑙𝑎𝑟𝑚 ← 𝐹𝑎𝑙𝑠𝑒 9 for 𝑑 = 0 to 𝑙𝑒𝑛 (𝑐 ) -1 do 10 v[𝑑 ] ← 𝜇 (𝑐 [𝑑 ] ) #See Def. 3 11 end 12 𝑗 ← 𝑐 [v.𝑖𝑛𝑑𝑒𝑥 (𝑚𝑎𝑥 (v) ) ] 13 𝑖 ← 𝑗 14 𝑥 𝑖 ← 𝑅 𝑖 (𝑦) 15 while 𝑖 ⩽ 𝑡 and 𝐴𝑙𝑎𝑟𝑚 = 𝐹𝑎𝑙𝑠𝑒 do 16 if 𝑖 in 𝑠𝑡𝑒𝑝𝑠𝐿𝑖𝑠𝑡 then 17 𝑖𝑛𝑑𝑒𝑥 𝑖 ← 𝑠𝑡𝑒𝑝𝑠𝐿𝑖𝑠𝑡 .𝑖𝑛𝑑𝑒𝑥 (𝑖 ) 18 if 𝑥 𝑖 in 𝐸𝑃 [𝑖𝑛𝑑𝑒𝑥 𝑖 ] then 19 𝐴𝑙𝑎𝑟𝑚 ← 𝑇 𝑟𝑢𝑒 20 𝑥 ← 𝑆𝑃 [𝐸𝑃 [𝑖𝑛𝑑𝑒𝑥 𝑖 ].𝑖𝑛𝑑𝑒𝑥 (𝑥 𝑖 ) ]

Also known as perfect rainbow table.

Another example of non-monotonic search order is discussed in the analysis of rainbow tables with heterogeneous widths[START_REF] Avoine | Heterogeneous Rainbow Table Widths Provide Faster Cryptanalyses[END_REF]. Optimality of the "success probability over average cost ratio" as a decision metric is also discussed there.

https://github.com/DianeLeblancAlbarel/Stairway-To-Rainbow

Barring those for which the target success probability or memory are unattainable.

Certain success probabilities are only achievable by using a sufficient number of tables.

ACKNOWLEDGMENTS

A significant portion of this work was done while author Xavier Carpent worked at COSIC/KULeuven (Leuven, Belgium).