Rainbow Table File Format

File format of a rainbow table (.rt)

To explain the file format of .rt rainbow table used by RainbowCrack, we generate a simple rainbow table with following command:

rtgen md5 loweralpha-numeric 1 7 0 3800 3 0

The parameters of the command above are identical to the parameters used in tutorial, except that the chain_num parameter is replaced with 3. The command will finish instantly, and the binary data of the generated rainbow table will be:

00000000: 00 00 00 00 00 00 00 00 30 02 3C 61 01 00 00 00
00000010: 01 00 00 00 00 00 00 00 77 09 F0 98 06 00 00 00
00000020: 02 00 00 00 00 00 00 00 14 49 40 CB 0A 00 00 00

Rainbow table consists of lots of rainbow chains. The size of one rainbow chain is 16 bytes, so the size of the table above will be 48 bytes. Each rainbow chain consists of an 8 byte start point (marked as red) and an 8 byte end point (marked as green).

Both the start point and the end point are 64-bit integer in little endian, representing a plaintext.
In this example, the charset is "abcdefghijklmnopqrstuvwxyz0123456789" with the plaintext length range from 1 to 7. So 0 stands for plaintext "a", 1 stands for plaintext "b", 35 stands for plaintext "9", 36 stands for plaintext "aa", and 80603140211 stands for plaintext "9999999".

The start point is generated by the rtgen program, and the end point is computed based on the start point.

File format of a rainbow table (.rtc)

The .rt rainbow table uses 64 bits for the start point, and another 64 bits for the end point.

The .rtc rainbow table introduced in RainbowCrack 1.4 uses configurable number of bits for the start point and end point. As an example, if the start point uses 25 bits and the end point uses 31 bits, one rainbow chain requires 7 bytes.

To support this level of flexibility, a simple 32 bytes file header is used in .rtc rainbow table:

struct RTCFileHeader
{
    unsigned int   uVersion;    // 0x30435452
    unsigned short uIndexSBits; // number of bits that is used to store the encoded start point, range from 1 to 64
    unsigned short uIndexEBits; // number of bits that is used to store the encoded end point, range from 1 to 64
    uint64         uIndexSMin;
    uint64         uIndexEMin;
    uint64         uIndexEInterval;
};

Assume the encoded value of start point is s, and the encoded value of end point is e. Then the actual start/end point will be:

    actual start point = uIndexSMin + s
    actual end point = uIndexEMin + uIndexEInterval * i + e

In the expression above, i is the index of the rainbow chain in a .rtc rainbow table. Value of the first rainbow chain will be 0, value of the second rainbow chain will be 1, and so on.

All encoded & packed rainbow chains follow the file header. Size of each rainbow chain will be:

    byte number of each encoded & packed rainbow chain = (uIndexSBits + uIndexEBits + 7) / 8

The start point generation algorithm

In RainbowCrack 1.2, the start points are random numbers smaller than the key space of the rainbow table.

In RainbowCrack 1.3 and 1.4, the chain_num and part_index parameters of rtgen command are used to generate start points:
    rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index
The start points used in a rainbow table are:
    (chain_num * part_index + 0) % key_space
    (chain_num * part_index + 1) % key_space
    (chain_num * part_index + 2) % key_space
    ......
    (chain_num * part_index + chain_num-1) % key_space

The rtsort program and rcrack program does not care about how the start points are generated.
The rcrack program in any version of RainbowCrack can use rainbow tables generated by rtgen program in any version of RainbowCrack.

Limitation of rtgen

In current implementation of RainbowCrack (1.2, 1.3 and 1.4), the maximum file size of a rainbow table is 2GB - 16bytes.
As we can store the rainbow chains logically belong to same rainbow table to multiple files, this limitation does not cause any problem.

Plaintexts are represented by an 8 byte unsigned integer, so the maximum key space supported is:
2^64 - 1 = 18446744073709551615