Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints, Extended Version

Since the original publication of Martin Hellman's cryptanalytic time-memory trade-off, a few improvements on the method have been suggested. In all these variants, the cryptanalysis time decreases with the square of the available memory. However, a large amount of work is wasted during the cryptanalysis process due to so-called "false alarms". In this paper we present a method of detection of false alarms which can significantly reduce the cryptanalysis time while using a minute amount of memory. Our method, based on "checkpoints", can reduce the time by much more than the square of the additional memory used, e.g., an increase of 0.89% of memory yields a 10.99% increase in performance. Even if our optimization is bounded, the gain in time per memory used is radically more important than in any existing variant of the trade-off. Beyond this practical improvement, checkpoints constitute a novel approach which has not yet been exploited and may lead to other interesting results. In this paper, we also present theoretical analysis of time-memory trade-offs, and give a complete characterization of the variant based on rainbow tables. This is the first time an exact expression is given for a variant of the trade-off and that the time-memory relationship can actually be plotted.