Download pdf
A review of time-memory trade-off techniques
- 1 University of Jinan
* Author to whom correspondence should be addressed.
Abstract
This paper delves into the discussion of time-memory trade-off techniques in the field of cryptanalysis. The method was initially introduced by Hellman in 1980, subsequently, DP trade-off, rainbow trade-off, and checkpoint trade-off have been proposed to enhance the efficiency of cryptographic attacks. This paper elaborates on the concept of rainbow trade-off and their variants and presents optimizations in terms of storage and runtime speed for time-memory trade--off methods. Ingenious storage optimization significantly reduces the storage overhead of pre-computed tables, and the rapid advancement of implementation platforms achieves speed optimization for the online phase. Through these optimization measures, time-memory trade-off methods exhibit even more remarkable performance in practical applications. For researchers and practitioners in the field of cryptography, the content of this paper provides valuable references and insights for their work.
Keywords
time-memory trade-off, cryptanalysis, rainbow trade-off, storage optimization
[1]. Goldreich O, Levin LA. A hard-core predicate for all one-way functions. In: Proceedings of the twenty-first annual ACM symposium on Theory of computing. New York, NY, USA: Association for Computing Machinery, pp. 25–32.
[2]. Avoine G, Carpent X. Optimal Storage for Rainbow Tables. In: Lee H-S, Han D-G (eds) Information Security and Cryptology -- ICISC 2013. Cham: Springer International Publishing, 2014, pp. 144–157.
[3]. Hong J, Moon S. A Comparison of Cryptanalytic Tradeoff Algorithms. J Cryptol 2013; 26: 559–637.
[4]. Avoine G, Junod P, Oechslin P. Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints. In: Maitra S, Veni Madhavan CE, Venkatesan R (eds) Progress in Cryptology - INDOCRYPT 2005. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 183–196.
[5]. Hellman M. A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory 1980; 26: 401–406.
[6]. Denning, D. E. Cryptography and Data Security (p.100, Ron Rivest’s distinguished points observation). Addison-Wesley, 1982.
[7]. Oechslin P. Making a Faster Cryptanalytic Time-Memory Trade-Off. In: Boneh D (ed) Advances in Cryptology - CRYPTO 2003. Berlin, Heidelberg: Springer, 2003, pp. 617–630.
[8]. Biryukov A, Mukhopadhyay S, Sarkar P. Improved Time-Memory Trade-Offs with Multiple Data. In: Preneel B, Tavares S (eds) Selected Areas in Cryptography. Berlin, Heidelberg: Springer, 2006, pp. 110–127.
[9]. Barkan E, Biham E, Shamir A. Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs. In: Dwork C (ed) Advances in Cryptology - CRYPTO 2006. Berlin, Heidelberg: Springer, 2006, pp. 1–21.
[10]. Borst J. Block Ciphers: Design, Analysis and Side-Channel Analysis, https://lirias.kuleuven.be/3006194 (2001, accessed 28 October 2022).
[11]. Biryukov A, Shamir A, Wagner D. Real Time Cryptanalysis of A5/1 on a PC. In: Goos G, Hartmanis J, van Leeuwen J, et al. (eds) Fast Software Encryption. Berlin, Heidelberg: Springer, 2001, pp. 1–18.
[12]. Avoine G, Carpent X, Leblanc-Albarel D. Rainbow Tables: How Far Can CPU Go? The Computer Journal 2022; bxac147.
[13]. Güneysu T, Kasper T, Novotný M, et al. Cryptanalysis with COPACOBANA. IEEE Trans Comput 2008; 57: 1498–1513.
[14]. Liu P, Li S, Ding Q. An Energy-Efficient Accelerator Based on Hybrid CPU-FPGA Devices for Password Recovery. IEEE Transactions on Computers 2019; 68: 170–181.
[15]. Li P, Zhu W, Chen J, et al. High-speed implementation of rainbow table method on heterogeneous multi-device architecture. Future Generation Computer Systems 2023; 143: 293–304.
[16]. Zhang Z, Liu P, Wang W, et al. High-Performance Password Recovery Hardware Going From GPU to Hybrid CPU-FPGA Platform. IEEE Consumer Electronics Magazine 2022; 11: 80–87.
[17]. Zhang Z, Liu P. A Hybrid-CPU-FPGA-based Solution to the Recovery of Sha256crypt-hashed Passwords. IACR Transactions on Cryptographic Hardware and Embedded Systems 2020; 1–23.
Cite this article
Teng,L. (2024). A review of time-memory trade-off techniques. Applied and Computational Engineering,43,313-321.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 2023 International Conference on Machine Learning and Automation
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).