Association for Computing Machinery
Cryptanalytic time-memory trade-offs have been studied for twenty five years and have benefited from several improvements. The ensuing variants definitely improve the original trade-off but their real impact has never been evaluated in practice. The authors fill this lack by analyzing the perfect form of classic tables, distinguished point-based tables, and rainbow tables. They especially provide a thorough analysis of the latter variant, whose performances have never been formally calculated yet. Their analysis leads to the concept of a characteristic that enables to measure the intrinsic quality of a trade-off. They finally introduce a new technique based on checkpoints that still reduces the cryptanalysis time, by ruling out false alarms probabilistically.