×

Analysis of the perfect table fuzzy rainbow tradeoff. (English) Zbl 1442.94040

Summary: Cryptanalytic time memory tradeoff algorithms are tools for inverting one-way functions, and they are used in practice to recover passwords that restrict access to digital documents. This work provides an accurate complexity analysis of the perfect table fuzzy rainbow tradeoff algorithm. Based on the analysis results, we show that the lesser known fuzzy rainbow tradeoff performs better than the original rainbow tradeoff, which is widely believed to be the best tradeoff algorithm. The fuzzy rainbow tradeoff can attain higher online efficiency than the rainbow tradeoff and do so at a lower precomputation cost.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hellman, M. E., A cryptanalytic time-memory trade-off, IEEE Transactions on Information Theory, 26, 4, 401-406 (1980) · Zbl 0436.94016 · doi:10.1109/TIT.1980.1056220
[2] Denning, D. E., Cryptography and Data Security (1982), Reading, Mass, USA: Addison-Wesley, Reading, Mass, USA · Zbl 0573.68001
[3] Oechslin, P., Making a faster cryptanalytic time-memory trade-off, Advances in Cryptology—CRYPTO 2003. Advances in Cryptology—CRYPTO 2003, Lecture Notes in Computer Science, 2729, 617-630 (2003), Berlin, Germany: Springer, Berlin, Germany · Zbl 1122.94393 · doi:10.1007/978-3-540-45146-4_36
[4] Barkan, E. P., Cryptanalysis of Ciphers and Protocols [Ph.D. thesis] (2006), Technion—Israel Institute of Technology
[5] Barkan, E.; Biham, E.; Shamir, A., Rigorous bounds on cryptanalytic time/memory tradeoffs, Advances in Cryptology—CRYPTO 2006. Advances in Cryptology—CRYPTO 2006, Lecture Notes in Computer Science, 4117, 1-21 (2006), Berlin, Germany: Springer, Berlin, Germany · Zbl 1161.94384 · doi:10.1007/11818175_1
[6] Nohl, K., Attacking phone privacy, Proceedings of the Black Hat USA
[7] Nohl, K.; Paget, C., GSM-SRSLY?, Proceedings of the 26th Chaos Communication Congress
[8] van den Broek, F.; Poll, E., A comparison of time-memory trade-off attacks on stream ciphers, Progress in Cryptology—AFRICACRYPT 2013. Progress in Cryptology—AFRICACRYPT 2013, Lecture Notes in Computer Science, 7918, 406-423 (2013), Berlin, Germany: Springer, Berlin, Germany · Zbl 1312.94107 · doi:10.1007/978-3-642-38553-7_24
[9] Kim, B. I.; Hong, J., Analysis of the non-perfect table fuzzy rainbow tradeoff, Information Security and Privacy. Information Security and Privacy, Lecture Notes in Computer Science, 7959, 347-362 (2013), New York, NY, USA: Springer, New York, NY, USA · Zbl 1379.68171 · doi:10.1007/978-3-642-39059-3_24
[10] Biryukov, A.; Mukhopadhyay, S.; Sarkar, P., Improved time-memory trade-offs with multiple data, Selected Areas in Cryptography. Selected Areas in Cryptography, Lecture Notes in Computer Science, 3897, 110-127 (2006), Berlin, Germany: Springer, Berlin, Germany · Zbl 1151.94481 · doi:10.1007/11693383_8
[11] Biryukov, A.; Shamir, A., Cryptanalytic time/memory/data tradeoffs for stream ciphers, Advances in Cryptology—ASIACRYPT 2000. Advances in Cryptology—ASIACRYPT 2000, Lecture Notes in Computer Science, 1976, 1-13 (2000), Berlin, Germany: Springer, Berlin, Germany · Zbl 0980.94013 · doi:10.1007/3-540-44448-3_1
[12] Hong, J.; Moon, S., A comparison of cryptanalytic tradeoff algorithms, Journal of Cryptology, 26, 4, 559-637 (2013) · Zbl 1283.94069 · doi:10.1007/s00145-012-9128-3
[13] Lee, G. W.; Hong, J., A comparison of perfect table cryptanalytic tradeoff algorithms, Cryptology ePrint Archive, 2012/540 (2012)
[14] Avoine, G.; Junod, P.; Oechslin, P., Characterization and improvement of time-memory trade-off based on perfect tables, ACM Transactions on Information and System Security, 11, 4, article 17, 1-17 (2008) · doi:10.1145/1380564.1380565
[15] Biryukov, A.; Shamir, A.; Wagner, D., Real time cryptanalysis of A5/1 on a PC, Fast Software Encryption. Fast Software Encryption, Lecture Notes in Computer Science, 1978, 1-18 (2001), Berlin, Germany: Springer, Berlin, Germany · Zbl 0994.68640
[16] Borst, J., Block Ciphers: Design, Analysis, and Side-Channel Analysis [Ph.D. thesis] (2001), Katholieke Universiteit Leuven
[17] Standaert, F.-X.; Rouvroy, G.; Quisquater, J.-J.; Legat, J.-D., A time-memory tradeoff using distinguished points: new analysis & FPGA results, Cryptographic Hardware and Embedded Systems—CHES 2002. Cryptographic Hardware and Embedded Systems—CHES 2002, Lecture Notes in Computer Science, 2523, 593-609 (2002), Berlin, Germany: Springer, Berlin, Germany · Zbl 1020.94526
[18] Kim, B. I.; Hong, J., Analysis of the non-perfect table fuzzy rainbow tradeoff, Cryptology ePrint Archive, 2012/612 (2012)
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.