Large charset configurations for RainbowCrack

1. Introduction

In this article, we will introduce some large charset configurations for RainbowCrack. All these configurations need long precomputation time. 
If you haven't read the tutorial of RainbowCrack, read it first before you read this.

2. Explanation of success rate

In the tutorial, there is a configuration for charset "alpha-numeric"(configuration #2). We precompute five rainbow tables and reach the success rate 99.04%, which  means if there are 1000 alpha-numeric passwords to crack, you can crack about 990 of them with the help of these five tables. Perhaps you want to go further.
In fact, each rainbow table has its own success rate. In configuration #2, the success rate of each table is 60.55%.(see Appendix A for more infomation). However, success rate of each table is independent and if you have two such rainbow tables, the success rate will reach:
1 - (1 - 0.6055) ^ 2 = 0.8444
If you have five such tables, the success rate is now:
1 - (1 - 0.6055) ^ 5 = 0.9904

Now you know how to reach better success rate: 
1 - (1 - 0.6055) ^ 6 = 0.9962
1 - (1 - 0.6055) ^ 7 = 0.9985
1 - (1 - 0.6055) ^ 8 = 0.9994
1 - (1 - 0.6055) ^ 9 = 0.9998
....

Just generate additional rainbow tables to reach any success rate you want:
rtgen lm alpha-numeric 1 7 5 2400 40000000 all
rtgen lm alpha-numeric 1 7 6 2400 40000000 all
rtgen lm alpha-numeric 1 7 7 2400 40000000 all
rtgen lm alpha-numeric 1 7 8 2400 40000000 all
....

This is another trade-off: higher success rate at the cost of additional precomputation time and larger disk space.

3. Configuration #3 for charset "alpha-numeric-symbol14"

4. Configuration #4 for charset "all"

5. General notes for large charset configurations

• These configurations are ready for a typical 666MHz CPU. The performance will be better with faster CPU.
• Table precomputation of these configurations is time expensive. When precomputation is partially finished, it is strongly recommended to test the files before you continue to find out whether everything is well.
  In configuration #3, when the five files for the first rainbow table (lm_alpha-numeric-symbol14#1-7_0_*.rt) is finished, you will have the chance of 68.6% to crack an "alpha-numeric-symbol14" password. Just sort these files and test the files with "random_lm_alpha#1-7.hash". If everything goes well, you can crack about 7 of all 10 passwords.
  In configuration #4, the success rate of the first rainbow table(25 files, lm_all#1-7_0_*.rt) is 0.5802. This may be an acceptable success rate with only 12.5% of full precomputation time.
• Distributed table precomputation is recommended. In fact, all rainbow tables are independent and you can distribute the tasks to many computers to save time.
• Earlier version of rcrack.exe will run several times slower than it should be when key space is large. It is recommended that you use version 1.2 if you want this configuration.
• A fast harddisk will greatly improve the performance of rcrack.exe because it always takes a long time to load the files.

      Notes for advanced users:

• The openssl's des routine(des_set_key and des_ecb_encrypt) takes most of the table precomputation time. If you have a faster routine, replace it with yours. This may save the time of rtgen.exe and rcrack.exe.

Appendix A: calc_success_probability.m

The matlab script below is used to calculate the success rate of a rainbow table.
File: calc_success_probability.m

% 1 - (1 - 1 / N)^(m(1) + m(2) + m(3) + ... + m(t - 1))
% m(1) = m, m(i) = N * (1 - (1 - 1 / N) ^ m(i - 1))

function ret = calc_success_probability(N, t, m)
arr = zeros(1, t - 1);
arr(1) = m;
for i = 2 : t - 1
	arr(i) = N * (1 - (1 - 1 / N) ^ arr(i - 1));
end;

exp = 0;
for i = 1 : t - 1
	exp = exp + arr(i);
end;

ret = 1 - (1 - 1 / N) ^ exp;

Parameters:
N               key space
t                 rainbow chain length
m               rainbow chain count
return         success rate of the rainbow table

You need matlab to run the script, for example:

>> calc_success_probability(80603140212, 2400, 40000000)

ans =

    0.6055

Create date: 2003/10/12
Revised: 2003/11/21