The table is a mixture of 2 concepts, namely distinguished points and rainbow tables.

It is a rainbow table with 32 colors/columns/round functions. Each of those colors is approx. 32000 A5/1 steps wide, that is to say the round function changes when a distinguished point of size 15 bit is reached. The chain also ends at a 15 bit wide distinguished point, or at the point where you would change to the 33rd round function.

So a chain has a length of 2¹⁵ * 32 = 2²⁰ on average. Each table is expected to have 2^28.5 chains and we want to generate 2^8.5 tables for a grand total of 2^20+28.5+8.5 = 2⁵⁷.

As for the lookup complexity:

You need to generate (1 + 2 + 3 + ... + 32) * 2¹⁵ A5/1 links on average for each of the 204 keystream samples. This is roughly 3.5 billion. With 162 million fast hardware it will take 21 seconds to do so. You also have to do 32 * 204 = 6528 disk accesses. One disk seek is 10ms, so all seeks complete after 65 seconds. take 3 disks or an SSD if you don't want the disk to be a bottleneck. This lookup has to be done on all of the 2^8.5 network nodes. If you wanted to do the lookup on a single computer with one graphics card you would need 21 * 2^8.5 seconds or roughly 2 hours. The single location storage would be about 2.5 TiB while the distributed node storage is about 6 GiB.

Chain merges

Chain merges occur when there is a collision in the same rainbow table column. Here are the actual numbers from our test table:

million chains	million merges	million unique chains	million unique chains table 2	merges percentage	merges percentage relative to 400m chains table	merges percentage table 2	relative to 400m chains table2
20	0.6	19.4	19.4	3	0.15	0.6	0.15
40	2.4	37.6	37.6	6	0.6	2.4	0.6
60	5.2	54.8	TBD	8.7	1.3	TBD	TBD
80	9	71	TBD	11.3	2.3	TBD	TBD
100	13.7	86.3	86.3	13.7	3.4	13.7	3.4
150	28.7	121.3	TBD	19.1	7.2	TBD	TBD
200	48.0	152.0	152.0	24	12	48.0	24
300	96.0	204.0	TBD	32	24	TBD	TBD
400	151.3	248.7	TBD	38.5	38.5	TBD	TBD
500	TBD	TBD	280.6	TBD	TBD	43.9	-
600	TBD	TBD	310	TBD	TBD	48.3	-

So what do these numbers tell us? They say our naive calculations above are wrong. Our tables do not cover 2^48.5 of the keyspace. So what can you do about it? You can throw away the merges and calculate new chains till you have 2^28.5 chains without merges. Since you can expect to have to throw away 50% of your chains, you need to calculate 150%. This number is not correct since you also get merges in the 50% you are calculating again. The other possibility is to keep the merges. Since they merge at half the chain length on average, you still have to compute extra chains, but not as many. And you are storing degenerate chains on disk which take up more diskspace per fraction of keyspace covered.

We all love diagrams don't we, this one shows the compression used. Green fields are constant and not stored. The index field is not stored also, but you have to create an index. The advantage of an index is that it speeds up the lookup process and reduces the amount of storage needed. If you cut off N bits of the end value, then you have to store 2^N file offsets into your table in the index. A sane size of the index would balance between the size of the index and the size of the table (minimize size_table + size_index) and would have to fit into RAM completely. If you have enough RAM and a large index (hundreds of megabytes), then after finding the table offset in the index, you can read a couple of sectors (all table entries between to index offsets) with one hard disk seek and search through those values.

And this one shows the overall table structure