Construct rainbow table to break DES for a fixed plaintext

Question

I'm facing a project where I need to build a rainbow table to break DES for a fixed plaintext. I've already collected information about Hellman, DP, rainbow table method. Finally, I chose the rainbow table approach. I've read about the topic “Rainbow table for DES with all-zero plaintext”. Now, my consideration how to choose good parameter to obtain highest success rate.

The notations:

• N: search space
• m: number of chains
• t: chain length
• l: number of tables

Stopping matrix is $C = mt/N$. Success rate is $R = 1 - e^{-C\cdot l}$. By Theorem 6, $C = (-\ln(1- R))/l < 2$.

So… I can calculate $l$ to obtain expected $R$, from $l$ I can derive $C$. Now I´m wondering: can I simply choose $m$ and $t$ such that $mt/N = C$, or must it be dependent on something else?

Answer 1

Your formulas look somewhat strange to me, are you assuming perfect rainbow tables where you removed all collisions? If you don't need a very high success rate, building perfect tables is feasible, but as you move up your success rate collisions become a real issue (even with multiple tables and or rainbow tables) If you are not using perfect tables the math is more complicated. You can choose m and t any way you like. Also rainbow tables usually come instead of building multiple (distinguishing point) tables (though you still can build several). In many cases it is simple and preferable to build one rainbow table.

You can choose m and t anyway you like but normally you choose m to be as big as your memory (or disk) and then choose t to be as high as you need for your success rate, or according to your table building budget. for non-perfect tables table building is simply m*t, for perfect tables it can be much more (for high success rate).

So for high success rate you either pay a lot in table building throwing out colliding chains. Or you keep all the partially colliding and get an effective coverage of significantly less then m*t.