Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints

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 significantly reduces the cryptanalysis time while using a minute amount of memory. Our method, based on "checkpoints", reduces 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. 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.


Published in:
The 6th International Conference on Cryptology in India - Indocrypt 2005, 3797, 183-196
Presented at:
The 6th International Conference on Cryptology in India - Indocrypt 2005, Bangalore, India, December 10-12, 2005
Year:
2005
Keywords:
Other identifiers:
Laboratories:




 Record created 2007-01-19, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)