Characterization and improvement of time-memory trade-off based on perfect tables

Cryptanalytic time-memory trade-offs have been studied for 25 years and have benefited from several improvements since the original work of Hellman. The ensuing variants definitely improve the original trade-off but their real impact has never been evaluated in practice. We fill this lack by analyzing the perfect form of classic tables, distinguished point-based tables, and rainbow tables. We especially provide a thorough analysis of the latter variant, whose performances have never been formally calculated yet. Our analysis leads to the concept of a characteristic that enables to measure the intrinsic quality of a trade-off. We finally introduce a new technique based on checkpoints that still reduces the cryptanalysis time by ruling out false alarms probabilistically. Our analysis yields the exact gain of this approach and establishes its efficiency when applied on rainbow tables.