Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables

ABSTRACT

Cryptanalytic time-memory trade-offs have been studied for 25 years and have benefited from several improvements since the original work of Hellman. The ensuing variants definitely improve the original trade-off but their real impact has never been evaluated in practice. We fill this lack by analyzing the perfect form of classic tables, distinguished point-based tables, and rainbow tables. We especially provide a thorough analysis of the latter variant, whose performances have never been formally calculated yet. Our analysis leads to the concept of a characteristic that enables to measure the intrinsic quality of a trade-off. We finally introduce a new technique based on checkpoints that still reduces the cryptanalysis time by ruling out false alarms probabilistically. Our analysis yields the exact gain of this approach and establishes its efficiency when applied on rainbow tables.

REFERENCES

• 1: Avoine, G., Junod, P., and Oechslin, P. 2005. Time-memory trade-offs: False alarm detection using checkpoints. In Proceedings of Progress in Cryptology -- 6th International Conference on Cryptology (INDOCRYPT'05). Lecture Notes in Computer Science, vol. 3797. Cryptology Research Society of India, Springer-Verlag, Bangalore, India, 183--196.
• 2: Barkan, E., Biham, E., and Shamir, A. 2006. Rigorous bounds on cryptanalytic time/memory tradeoffs. In Proceedings of Advances in Cryptology -- 26th Annual International Cryptology Conference (CRYPTO'06). C. Dwork, Ed. Lecture Notes in Computer Science. IACR, Springer-Verlag, Santa Barbara, CA.
• 3: Biryukov, A., Mukhopadhyay, S., and Sarkar, P. 2005. Improved time-memory trade-offs with multiple data. In Proceedings of the 12th Annual Workshop on Selected Areas in Cryptography (SAC'05), B. Preneel and S. Tavares, Eds. Lecture Notes in Computer Science, vol. 3897. Springer-Verlag, Kingston, Canada, 110--127.
• 4: Alex Biryukov , Adi Shamir, Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.1-13, December 03-07, 2000
• 5: Alex Biryukov , Adi Shamir , David Wagner, Real Time Cryptanalysis of A5/1 on a PC, Proceedings of the 7th International Workshop on Fast Software Encryption, p.1-18, April 10-12, 2000
• 6: Borst, J., Preneel, B., and Vandewalle, J. 1998. On the time-memory tradeoff between exhaustive key search and table precomputation. In Proceedings of the 19th Symposium on Information Theory in the Benelux, P. de With and M. van der Schaar-Mitrea, Eds. Veldhoven, The Netherlands, 111--118.
• 7: Dorothy Elizabeth Robling Denning, Cryptography and data security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 8: Amos Fiat , Moni Naor, Rigorous time/space tradeoffs for inverting functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.534-541, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103473]
• 9: Amos Fiat , Moni Naor, Rigorous Time/Space Trade-offs for Inverting Functions, SIAM Journal on Computing, v.29 n.3, p.790-803, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795280512]
• 10: Hellman, M. 1980. A cryptanalytic time-memory trade off. IEEE Trans. Inform. Theory IT-26, 4 (July), 401--406.
• 11: Hong, J. and Sarkar, P. 2005. New applications of time memory data tradeoffs. In Proceedings of Advances in Cryptology -- 11th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'05), B. Roy, Ed. Lecture Notes in Computer Science, vol. 3788. IACR, Springer-Verlag, Chennai, India, 353--372.
• 12: Kim, I. and Matsumoto, T. 1999. 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 (January), 123--129.
• 13: Kusuda, K. and Matsumoto, T. 1996. Optimization of time-memory trade-off cryptanalysis and its application to DES, FEAL-32, and Skipjack. IEICE Trans. Fundamentals E79-A, 1 (January), 35--48.
• 14: Mentens, N., Batina, L., Preneel, B., and Verbauwhede, I. 2005. Cracking Unix passwords using FPGA platforms. In Proceedings of the Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS'05).
• 15: Oechslin, P. 2003. Making a faster cryptanalytic time-memory trade-off. In Proceedings of Advances in Cryptology -- 23th Annual International Cryptology Conference (CRYPTO'03), D. Boneh, Ed. Lecture Notes in Computer Science, vol. 2729. IACR, Springer-Verlag, Santa Barbara, CA. 617--630.
• 16: Jean-Jacques Quisquater , Jean-Paul Delescaille, How easy is collision search? Application to DES, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.429-434, November 1990, Houthalen, Belgium
• 17: Francois-Xavier Standaert , Gael Rouvroy , Jean-Jacques Quisquater , Jean-Didier Legat, A Time-Memory Tradeoff Using Distinguished Points: New Analysis & FPGA Results, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.593-609, August 13-15, 2002
• 18: Wiener, M. and van Oorschot, P. 1999. Parallel collision search with cryptanalytic applications. J. Crypto. 12, 1 (March), 1--28.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Performance, Security

Keywords:
Cryptography, Hellman's time-memory trade-off, password cracking, rainbow tables