A Comparison of Cryptanalytic Tradeoff Algorithms.
Jin Hong, Sunghwan Moon · 2010
the date of receipt and acceptance should be inserted later Abstract Three time memory tradeoff algorithms are compared in this paper. Specifically, the classical tradeoff algorithm by Hellman, the distinguished point tradeoff method, and the rainbow table method, in their non-perfect table versions, are treated. We show that, under parameters and assumptions that are typically considered in theo-retic discussions of the tradeoff algorithms, Hellman and distinguished point tradeoffs per-form very close to each other and that the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different. The analysis of tradeoff efficiency presented in this paper does not ignore the effects of false alarms and also covers techniques for reducing storage, such as ending point trun-cations and index tables. Our comparison of algorithms takes the success probabilities and pre-computation efforts fully into account. Keywords time memory tradeoff · Hellman · distinguished point · rainbow table 1