Parameter optimization of time-memory trade-off cryptanalysis in RainbowCrack

by Zhu Shuanglei <shuanglei@hotmail.com>
http://www.antsight.com/zsl/rainbowcrack/

1. Introduction

RainbowCrack is a general propose implementation of Philippe Oechslin's faster time-memory trade-off technique. In the tutorial and some other document of the tool, four ready to work configurations are introduced. However, you may be puzzled by the parameters(m, t and l) if you want to build tables for your custom charset. If these parameters are casually selected, the performance will be really poor.
In this article, we present some useful information which is helpful if you want to determine your parameters of a rainbow table set, which can be used to attack the ciphertexts of a selected key space of a hash algorithm .

The RainbowCrack tool is mainly based on the paper Making a Faster Cryptanalytic Time-Memory Trade-Off. We will not talk about the basic concepts here, so please read the paper and make clear the following concepts before you continue:
1. What is a rainbow chain
2. Why the rainbow chains merge in a rainbow table

2. Parameters in time-memory trade-off cryptanalysis

To determine the parameter "speed of hash computation":
Run the program rtgen like this:
C:\rainbowcrack>rtgen lm alpha 1 7 0 -bench
lm hash speed: aaaaaa / s
lm step speed: bbbbbb / s
C:\rainbowcrack>rtgen md5 alpha 1 7 0 -bench
md5 hash speed: cccccc / s
md5 step speed: dddddd / s
Here "bbbbb" is the speed of lm hash, "dddddd" is the speed of md5 hash

To determine the parameter "speed of the harddisk":
If the program rcrack can read 610 MB of data in 19 seconds, the speed is considered as "19 / 610"

To determine the parameter "N":
If the charset is "alpha"(26 characters) and the plaintext length range is 1 to 7, N = 26^1 + 26^2 + 26^3 + 26^4 + 26^5 + 26^6 + 26^7 = 8353082582
If the charset is "byte"(256 characters) and the plaintext length range is 1 to 4, N = 256 + 256^2 + 256^3 + 256^4 = 4311810304

Parameter t, m and l are the only parameters you can adjust. If you change any of them, the output parameters will change. Of course we would like to select some good input parameters which will produce better output parameters.
Some parameters are considered more important than the others. These "important" parameters are in bold font in the above table.

3. Computation of the output parameters

In this section, we will talk about how the output parameters are determined by the input parameters. The discussion is not complete, the prototype of the matlab scripts used to compute the output parameters are given in appendix A. However, you can also take the source of these scripts as another reference.

3.1 Disk usage

The format of a rainbow table generated by rainbowcrack is given in appendix B. Each rainbow chain will take 16 bytes, so the formula is:
disk_usage = m * 16 * l

3.2 success probability

Random plaintext-ciphertext pairs are stored in rainbow chains. If the ciphertext you want to crack is inside any of the rainbow chains you generated, you will be able to crack it.
If you generate the rainbow chain with longer rainbow chain length(t), you can store more plaintext-ciphertext pairs in a single chain(16 bytes). But the rainbow chains have some bad properties: they will merge. Each merge reduces the number of distinct keys which are actually covered by a table:


Fig: More rainbow chains will merge when t increase
Matlab: demo_chain_merge(8353082582, 2100, 8000000)




Fig: More rainbow chains will merge when m increase(compared to the figure above)
Matlab: demo_chain_merge(8353082582, 2100, 16000000)

The matlab scripts which will produce the figures are given too. So you can generate the figures yourself, change the parameters and see how the rainbow chains will merge.

If we store all rainbow chains in a single rainbow table(with same reduce function set), the success probability will increase very slowly. So we use different rainbow tables to store the chains:


Fig: We can archive better success probability with same disk usage if we use different rainbow tables
Matlab: demo_advantage_of_multiple_table(8353082582, 2100, 256, 4096)



Fig: We can archive better success probability with same disk usage if we use different rainbow tables(zoomed in)
Matlab: demo_advantage_of_multiple_table(8353082582, 2100, 256, 4096)

We use different curves to represent how the success probability will increase if we use more disk space(larger m*l).
There are five curves in the figure(l=1 to 5). When l(rainbow table count) is equal to 5, The curve reach the success probability 0.999 first.

When l increase, we will reach same success probability with less disk space. But the cryptanalysis time will increase too. This is the dilemma.

The marked point is the configuration we selected in configuration #0 in rainbowcrack tutorial. However, any points in these curves represent a configuration.

3.3 mean cryptanalysis time

We need "t*t/2" times rainbow chain walk(hash computation and a reduce function) to finish the search of a rainbow table. Thus the time to search a rainbow table is "t*t/2 / step_speed".
Each rainbow table has its success probability. If we can't find the plaintext in a rainbow table, we will continue with the next. The formula is:
mean_cryptanalysis_time = rate_of_each_table * 1 * t*t/2 / step_speed
                                         + (1 - rate_of_each_table) ^ 1 * rate_of_each_table * 2 * t*t/2 / step_speed
                                         + (1 - rate_of_each_table) ^ 2 * rate_of_each_table * 3 * t*t/2 / step_speed
                                         ...
                                         + (1 - rate_of_each_table) ^ (table_count - 1) * rate_of_each_table * table_count * t*t/2 / step_speed
                                         + (1 - rate_of_each_table) ^ table_count * table_count * t*t/2 / step_speed

4. Parameter optimization of time-memory trade-off cryptanalysis

We use the matlab script performance_chart.m to select our configurations. We pass the script with our desired success probability, disk usage range and the rainbow chain count range.

Fig: Performance chart of key space 8353082582
Matlab: performance_chart(8353082582, 0.999, 250, 2000, 3, 8, 354000, 19 / 610)

We use different colors to represent the performance curves if we use different rainbow table count.

There are three charts in the figure:
chart 1: The minimal t we can use if we want to reach the desired success probability 
chart 2: mean cryptanalysis time if we use the t selected in char 1
chart 3: mean cryptanalysis time plus mean disk access time if we use the t selected in char 1

The cryptanslysis time will decrease when disk space increase(m*l increase). However, we will need longer disk access time if use larger tables. Look at the chart 3 to find out how "mean_cryptanalysis_time + mean_disk_access_time" change when disk space change.

You can select any point in these curves as your configuration of the rainbow table set. Of course some configurations are better than the others.

Fig: Performance chart of key space 8353082582(zoomed to where we select the configuration #0)
Matlab: performance_chart(8353082582, 0.999, 250, 2000, 3, 8, 354000, 19 / 610)

Now we zoomed the figure to where we select the configuration #0.

When a configuration is selected, you can determine the parameter t and l directly from the figure. m*l can be determined by: 
m *  l = disk_usage / 16

If you want to crack one ciphertext at a time, the total time is: mean_cryptanalysis_time + mean_disk_access_time
If you want to crack n ciphertexts at a time, the total time is:   mean_cryptanalysis_time * n + max_disk_access_time (when n >> 1)
                                                                  the mean time is:  (mean_cryptanalysis_time * n + max_disk_access_time) / n = mean_cryptanalysis_time  (when n >> 1)
You should also take the curves in chart 2 into consideration if you always have dozens of ciphertexts to crack. In this situation, the disk access time will take very little percent in cracking progress.

Appendix A - Matlab scripts

Appendix B - Format of a rainbow table in RainbowCrack

A rainbow table is a raw array of rainbow chains. Only the starting point and the end point are stored in a rainbow chain. The data struct is defined as:
struct RainbowChain
{
uint64 nIndexS;
uint64 nIndexE;
};
Each rainbow chain takes 16 bytes.
For example:

We generated a simple rainbow table with 4 rainbow chains and the size of the generated file is 64 bytes.

The rtsort program is very simple too. It sort the end points and write the rainbow chains back to the file.

Interestingly, you can dump the content of a rainbow chain like this:

The starting point and end point are same in the output of hexdump and rtdump.

Create date: 2004/1/1