Time memory tradeoff (TMTO) attack has proven to be an effective cryptanalysis method against block ciphers and stream ciphers. Since it was first proposed in 1980s, many new ideas have come out to reduce the false alarms during the online phase, among which rainbow table introduced by Oechslin and perfect table introduced by Borst et al. are notable landmarks. Avoine et al. introduced the checkpoints technique to detect false alarms using little additional memory without regenerating the pre-computed chain. In this paper, we revisit the analysis of multiple checkpoints in rainbow tradeoff. For non-perfect table we give a new sight to the computation of the expected decreasing number of chain regenerations at the k-th iteration. This helps to better understand the real nature of false alarms and leads us to the same results as the work of Jung Woo Kim et al. at Indocrypt 2012. For perfect rainbow tradeoff we give the first way to find optimal positions of multiple checkpoints. The results are better than previous work of Avoine et al., which only applies when the perfect table has the maximum number of chains. All the results are verified through meticulous experiments.
展开▼
