Complexity analysis of the method of rainbow tables with fingerprints

D. V. Pilshchikov

Matematičeskie voprosy kriptografii, Tome 8 (2017), pp. 99-116.

Résumé

The probabilistic model of the operative stage of the rainbow tables with fingerprints method is introduced. It is used to compute the mean time complexity of the complete processing of one table. Two-sided estimates of this complexity are obtained and computational approach to the construction of the optimal fingerprint is suggested. Our probabilistic model as opposed to other models permits to account for the impact of the variance of the preimages number of random uniformly chosen element of a finite set with respect to the one-way function.

Bibliographie

[1] Hellman M., “A cryptanalytic time-memory trade-off”, IEEE Trans. Inf. Theory, IT-26:4 (1980), 401–406 | DOI | MR | Zbl

[2] Denning D., Cryptography and Data Security, Addison-Wesley, Boston, MA, 1982, xiv+400 pp. | Zbl

[3] Oechslin P., “Making a faster cryptanalytic time-memory trade-off”, Lect. Notes Comput. Sci., 2729, 2003, 617–630 | DOI | MR | Zbl

[4] Biryukov A., Shamir A., Wagner D., “Real time cryptanalysis of A5/1 on a PC”, Lect. Notes Comput. Sci., 1978, 2000, 1–18 | MR

[5] Saarinen M.-J. O., “A time-memory tradeoff attack against LILI-128”, Lect. Notes Comput. Sci., 2365, 2001, 231–236 | DOI

[6] Mentens N., Batina L., Preneel B., Verbauwhede I., “Time-memory trade-off attack on FPGA platforms: UNIX password cracking”, Lect. Notes Comput. Sci., 3985 (2006), 323–334 | DOI

[7] Bono S., Green M., Stubblefield A., Juels A., Rubin A., Szydlo M., “Security analysis of a cryptographically-enabled RFID device”, 14th USENIX Security Symposium. USENIX'05, USENIX Assoc., Berkeley, CA, 2005, 1–15

[8] Avoine G., Junod P., Oechslin P., “Characterization and improvement of time-memory tradeoff based on perfect tables”, ACM Trans. Inf. Syst. Security (TISSEC), 11:4 (2008), 17, 22 pp.

[9] Avoine G., Junod P., Oechslin P., “Time-memory trade-offs: False alarm detection using checkpoints”, Lect. Notes Comput. Sci., 3797, 2005, 183–196 | DOI | MR | Zbl

[10] Barkan E., Biham E., Shamir A., “Rigorous bounds on cryptanalytic time/memory tradeoffs”, Lect. Notes Comput. Sci., 4117, 2006, 1–21 | DOI | MR | Zbl

[11] Avoine G., Bourgeois A., Carpent X., “Analysis of rainbow tables with fingerprints”, Lect. Notes Comput. Sci., 9144, 2015, 356–374 | DOI | Zbl

[12] Hong J., “The cost of false alarms in Hellman and rainbow tradeoffs”, Designs, Codes and Cryptography, 57:3 (2010), 293–327 | DOI | MR | Zbl

[13] Wang W., Lin D., “Analysis of multiple checkpoints in non-perfect and perfect rainbow tradeoff revisited”, Lect. Notes Comput. Sci., 8233, 2013, 288–301 | DOI | MR

[14] Kim J. W., Seo J., Hong J., Park K., Kim S.-R., “High-speed parallel implementations of the rainbow method in a heterogeneous system”, Lect. Notes Comput. Sci., 7668, 2012, 303–316 | DOI | Zbl

[15] Kim J. W., Seo J., Hong J., Park K., Kim S. R., “High-speed parallel implementations of the rainbow method based on perfect tables in a heterogeneous system”, Software: Practice and Experience, 45:6 (2015), 837–855 | DOI

[16] Lee G. W., Hong J., A comparison of perfect table cryptanalytic tradeoff algorithms, , 2012 http://eprint.iacr.org

[17] Hong J., Moon S., “A comparison of cryptanalytic tradeoff algorithms”, J. Cryptology, 26:4 (2013), 559–637 | DOI | MR | Zbl

[18] Hong J., “Perfect rainbow tradeoff with checkpoints revisited”, PLoS ONE, 11:11 (2016), e0166404, 18 pp. | DOI

[19] Zorich V. A., Matematicheskii analiz, v. 1, Izd. 2-e, FAZIS, M., 1997, 518 pp.

[20] Korn G., Korn T., Spravochnik po matematike dlya nauchnykh rabotnikov i inzhenerov, Nauka, M., 1970, 832 pp.

[21] Sevastyanov B. A., Vetvyaschiesya protsessy, Nauka, M., 1971, 436 pp.