A comparison of cryptanalytic tradeoff algorithms. (English) Zbl 1283.94069
J. Cryptology 26, No. 4, 559-637 (2013); erratum ibid. 27, No. 1, 181 (2014).
Summary: Three time-memory tradeoff algorithms are compared in this paper. Specifically, the classical tradeoff algorithm by Hellman, the distinguished point tradeoff method, and the rainbow table method, in their non-perfect table versions, are treated.
We show that, under parameters and assumptions that are typically considered in theoretic discussions of the tradeoff algorithms, the Hellman and distinguished point tradeoffs perform very close to each other and the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different.
The analysis of tradeoff efficiency presented in this paper does not ignore the effects of false alarms and also covers techniques for reducing storage, such as ending point truncations and index tables. Our comparison of algorithms fully takes into account success probabilities and precomputation efforts.
We show that, under parameters and assumptions that are typically considered in theoretic discussions of the tradeoff algorithms, the Hellman and distinguished point tradeoffs perform very close to each other and the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different.
The analysis of tradeoff efficiency presented in this paper does not ignore the effects of false alarms and also covers techniques for reducing storage, such as ending point truncations and index tables. Our comparison of algorithms fully takes into account success probabilities and precomputation efforts.
MSC:
| 94A60 | Cryptography |
References:
| [1] | G. Avoine, P. Junod, P. Oechslin, Characterization and improvement of time-memory trade-off based on perfect tables. ACM Trans. Inf. Syst. Secur.11(4), 17:1-17:22 (2008). Preliminary version in INDOCRYPT 2005 · doi:10.1145/1380564.1380565 |
| [2] | Babbage, S. H., Improved exhaustive search attacks on stream ciphers, No. 408, 161-166 (1995), London · doi:10.1049/cp:19950490 |
| [3] | E.P. Barkan, Cryptanalysis of ciphers and protocols. Ph.D. Thesis, Israel Institute of Technology, March 2006 |
| [4] | Barkan, E.; Biham, E.; Shamir, A., Rigorous bounds on cryptanalytic time/memory tradeoffs, No. 4117, 1-21 (2006), Berlin · Zbl 1161.94384 · doi:10.1007/11818175_1 |
| [5] | Biryukov, A.; Shamir, A., Cryptanalytic time/memory/data tradeoffs for stream ciphers, No. 1976, 1-13 (2000), Berlin · Zbl 0980.94013 · doi:10.1007/3-540-44448-3_1 |
| [6] | Biryukov, A.; Shamir, A.; Wagner, D., Real time cryptanalysis of A5/1 on a PC, No. 1978, 1-18 (2001), Berlin · Zbl 0994.68640 |
| [7] | J. Borst, Block ciphers: Design, analysis, and side-channel analysis. Ph.D. Thesis, Katholieke Universiteit Leuven, September 2001 |
| [8] | J. Borst, B. Preneel, J. Vandewalle, On the time-memory tradeoff between exhaustive key search and table precomputation, in Proceedings of the 19th Symposium on Information Theory in the Benelux (WIC, 1998) · Zbl 0994.68640 |
| [9] | C. Calik, How to invert one-way functions: time-memory trade-off method. M.S. Thesis, Middle East Technical University, January 2007 · Zbl 1020.94526 |
| [10] | D.E. Denning, Cryptography and Data Security (Addison-Wesley, Reading, 1982) · Zbl 0573.68001 |
| [11] | Flajolet, P.; Odlyzko, A. M., Random mapping statistics, No. 434, 329-354 (1990), Berlin · Zbl 0747.05006 |
| [12] | S. Goldwasser, M. Bellare, Lecture notes on cryptography. Unpublished manuscript, July 2008. Available at: http://cseweb.ucsd.edu/ mihir/papers/gb.html |
| [13] | Golić, J. Dj., Cryptanalysis of alleged A5 stream cipher, No. 1233, 239-255 (1997), Berlin |
| [14] | M.E. Hellman, A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory26, 401-406 (1980) · Zbl 0436.94016 · doi:10.1109/TIT.1980.1056220 |
| [15] | J. Hong, The cost of false alarms in Hellman and rainbow tradeoffs. Des. Codes Cryptogr.57, 293-327 (2010) · Zbl 1197.94192 · doi:10.1007/s10623-010-9368-x |
| [16] | J. Katz, Y. Lindell, Introduction to Modern Cryptography (Chapman & Hall/CRC, London, 2008) · Zbl 1143.94001 |
| [17] | I.-J. Kim, T. Matsumoto, Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.E82-A, 123-129 (1999) |
| [18] | K. Kusuda, T. Matsumoto, Optimization of time-memory trade-off cryptanalysis and its application to DES, FEAL-32, and Skipjack. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.79(1), 35-48 (1996) |
| [19] | D. Ma, J. Hong, Success probability of the Hellman trade-off. Inf. Process. Lett.109(7), 347-351 (2009) · Zbl 1191.68282 · doi:10.1016/j.ipl.2008.12.002 |
| [20] | A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 1997) · Zbl 0868.94001 |
| [21] | S. Moon, Parameter selection in cryptanalytic time memory tradeoffs. M.S. Thesis, Seoul National University, June 2009 · Zbl 1122.94393 |
| [22] | Narayanan, A.; Shmatikov, V., Fast dictionary attacks on passwords using time-space tradeoff, 364-372 (2005), New York |
| [23] | Oechslin, P., Making a faster cryptanalytic time-memory trade-off, No. 2729, 617-630 (2003), Berlin · Zbl 1122.94393 · doi:10.1007/978-3-540-45146-4_36 |
| [24] | R. Oppliger, Contemporary Cryptography (Artech House, Boston, 2005) · Zbl 1104.68044 |
| [25] | J.-J. Quisquater, J. Stern, Time-memory tradeoff revisited. Unpublished manuscript, December 1998 |
| [26] | N. Saran, Time memory trade off attack on symmetric ciphers. Ph.D. Thesis, Middle East Technical University, February 2009 |
| [27] | Saran, N.; Doganaksoy, A., Choosing parameters to achieve a higher success rate for Hellman time memory trade off attack, 504-509 (2009), New York · doi:10.1109/ARES.2009.140 |
| [28] | Standaert, F.-X.; Rouvroy, G.; Quisquater, J.-J.; Legat, J.-D., A time-memory tradeoff using distinguished points: New analysis & FPGA results, No. 2523, 593-609 (2003), Berlin · Zbl 1020.94526 · doi:10.1007/3-540-36400-5_43 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
