Optimal Storage for Rainbow Tables
(2013) International Conference on Information Security and Cryptology (ICISC 2013) — Location: Seoul, South Korea (27.November.2013)
Files
article.pdf
Restricted Access - Adobe PDF
- 326.88 KB
Details
- Authors
- Abstract
- Cryptanalytic time-memory trade-offs were introduced by Martin Hellman in 1980, and they have since had a major impact on practical cryptanalysis. Hellman’s technique has been studied as well as improved significantly, most notably by Philippe Oechslin who introduced the rainbow tables. As it has been highlighted in various papers, the way the memory is handled is extremely important. In this paper, we analytically describe how rainbow tables are currently stored, and we introduce a new structure that considerably reduces the memory requirement. We mathematically analyze these techniques, provide optimal parameterization, and show that our structure is extremely close to the theoretical lower bound. Using our optimized storage for rainbow tables realizes the equivalent of a speedup of three with respect to the naive approach.
- Affiliations
Citations
Avoine, G., & Carpent, X. (2013). Optimal Storage for Rainbow Tables. International Conference on Information Security and Cryptology (ICISC 2013), Seoul, South Korea. https://hdl.handle.net/2078.5/221041