Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avoine, G., Dysli, E., Oechslin, P.: Reducing time complexity in RFID systems. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 291–306. Springer, Heidelberg (2006)
Avoine, G., Junod, P., Oechslin, P.: Time-memory trade-offs: False alarms detection using checkpoints. Technical Report LASEC-REPORT-2005-002, Swiss Federal Institute of Technology (EPFL), Security and Cryptography Laboratory (LASEC), Lausanne, Switzerland (September 2005)
Biryukov, A., Shamir, A., Wagner, D.: Real time cryptanalysis of A5/1 on a PC. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 1–18. Springer, Heidelberg (2001)
Borst, J., Preneel, B., Vandewalle, J.: On the time-memory tradeoff between exhaustive key search and table precomputation. In: Symposium on Information Theory in the Benelux, Veldhoven, The Netherlands, May 1998, pp. 111–118 (1998)
Denning, D.: Cryptography and Data Security, p. 100. Addison-Wesley, Boston (1982)
Fiat, A., Naor, M.: Rigorous time/space tradeoffs for inverting functions. In: ACM Symposium on Theory of Computing STOC 1991, New Orleans, Louisiana, USA, May 1991, pp. 534–541. ACM Press, New York (1991)
Fiat, A., Naor, M.: Rigorous time/space tradeoffs for inverting functions. SIAM Journal on Computing 29(3), 790–803 (1999)
Hellman, M.: A cryptanalytic time-memory trade off. IEEE Transactions on Information Theory IT-26(4), 401–406 (1980)
Kim, I., Matsumoto, T.: Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size. IEICE Transactions on Communications/Electronics/Information and Systems E82-A(1), 123 (1999)
Kusuda, K., Matsumoto, T.: Optimization of time-memory trade-off cryptanalysis and its application to DES, FEAL-32, and Skipjack. IEICE Transactions on Fundamentals E79-A(1), 35–48 (1996)
Mentens, N., Batina, L., Preneel, B., Verbauwhede, I.: Cracking Unix passwords using FPGA platforms. In: SHARCS - Special Purpose Hardware for Attacking Cryptographic Systems (February 2005)
Oechslin, P.: Making a faster cryptanalytic time-memory trade-off. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 617–630. Springer, Heidelberg (2003)
Quisquater, J.-J., Delescaille, J.-P.: How easy is collision search? Application to DES (extended summary). In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 429–434. Springer, Heidelberg (1990)
Standaert, F.-X., Rouvroy, G., Quisquater, J.-J., Legat, J.-D.: A time-memory tradeoff using distinguished points: New analysis & FPGA results. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 593–609. Springer, Heidelberg (2003)
Wiener, M., van Oorschot, P.: Parallel collision search with cryptanalytic applications. Journal of Cryptology 12(1), 1–28 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Avoine, G., Junod, P., Oechslin, P. (2005). Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds) Progress in Cryptology - INDOCRYPT 2005. INDOCRYPT 2005. Lecture Notes in Computer Science, vol 3797. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11596219_15
Download citation
DOI: https://doi.org/10.1007/11596219_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30805-8
Online ISBN: 978-3-540-32278-8
eBook Packages: Computer ScienceComputer Science (R0)