nach oben

Designs, Codes and Cryptography

Erschienen in:

08.07.2023

Improved attacks against reduced-round Whirlwind

verfasst von: Congming Wei, Bingyou Dong, Jialiang Hua, Xiaoyang Dong, Guoyan Zhang

Erschienen in: Designs, Codes and Cryptography | Ausgabe 11/2023

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Whirlwind hash function was proposed by Barreto et al. (Des Codes Cryptogr 56(2–3):141–162, 2010, https://doi.org/10.1007/s10623-010-9391-y). In this paper, we focus on preimage and collision attacks on reduced-round Whirlwind. With the help of MILP models, a 7-round pseudo-preimage attack is presented. Then we revisit the framework of Ma et al. and successfully improve the preimage attack on 4-round Whirlwind with time complexity reduced from \(2^{497}\) to \(2^{417}\). Meanwhile, by using quantum algorithms, we find a quantum collision attack on 5-round Whirlwind, which improves running time from \(2^{190.5}\) to \(2^{127.15}\) comparing to standard BHT algorithm while using the same amount of quantum memory. Also, semi-free-start collision of Whirlwind compression function is improved from 6 round to 7 round, while keeping complexity unchanged.

Vorheriger Artikel Covering schemes of strength t

Nächster Artikel New method for combining Matsui’s bounding conditions with sequential encoding method

When applying the rebound attack to build limited-birthday attacks [22, 24], we often have \(\Delta _{in} \ne \Delta _{out}\).

For simplicity, we only consider the case that x is unique.

Read from \(L_i'\) and write to \(L_i\) are consider done within a single random memory access.

One Whirlwind encryption includes 12 rounds of CF, where each round includes 64 Sbox computations. Thus the complexity of Whirlwind encryption can be estimated as \(12\times 64=768\) Sbox computations.

AlTawy R., Youssef A.M.: Second preimage analysis of whirlwind. In: Lin D., Yung M., Zhou J. (eds.) Information Security and Cryptology—10th International Conference, Inscrypt 2014, Beijing, China, December 13–15, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8957, pp. 311–328 (2014). https://doi.org/10.1007/978-3-319-16745-9_17.

Aoki K., Sasaki Y.: Preimage attacks on one-block md4, 63-step MD5 and more. In: Avanzi R.M., Keliher L., Sica F. (eds.) Selected Areas in Cryptography, 15th International Workshop, SAC 2008, Sackville, New Brunswick, Canada, August 14–15, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5381, pp. 103–119 (2008). https://doi.org/10.1007/978-3-642-04159-4_7.

Bao Z., Dong X., Guo J., Li Z., Shi D., Sun S., Wang X.: Automatic search of meet-in-the-middle preimage attacks on AES-like hashing. In: Canteaut A., Standaert F. (eds.) Advances in Cryptology—EUROCRYPT 2021—40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I. Lecture Notes in Computer Science, vol. 12696, pp. 771–804 (2021). https://doi.org/10.1007/978-3-030-77870-5_27.

Bao Z., Guo J., Shi D., Tu Y.: Superposition meet-in-the-middle attacks: updates on fundamental security of AES-like hashing. In: Dodis Y., Shrimpton T. (eds.) Advances in Cryptology—CRYPTO 2022—42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I. Lecture Notes in Computer Science, vol. 13507, pp. 64–93 (2022). https://doi.org/10.1007/978-3-031-15802-5_3.

Barreto P.S.L.M., Nikov V., Nikova S., Rijmen V., Tischhauser E.: Whirlwind: a new cryptographic hash function. Des. Codes Cryptogr. 56(2–3), 141–162 (2010). https://doi.org/10.1007/s10623-010-9391-y.MathSciNetCrossRefMATH

Bernstein D.J.: Cost analysis of hash collisions: will quantum computers make SHARCS obsolete. SHARCS 9, 105 (2009).

Bouillaguet C., Derbez P., Fouque P.: Automatic search of attacks on round-reduced AES and applications. In: Rogaway P. (ed.) Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6841, pp. 169–187 (2011). https://doi.org/10.1007/978-3-642-22792-9_10.

Brassard G., Høyer P., Tapp A.: Quantum cryptanalysis of hash and claw-free functions. In: LATIN ’98, Campinas, Brazil, April, 20–24, 1998, Proceedings, pp. 163–169 (1998).

Brassard G., Hoyer P., Mosca M., Tapp A.: Quantum amplitude amplification and estimation. In: AMS Contemporary Mathematics Series, vol. 305 (2000). https://doi.org/10.1090/conm/305/05215.

10.

Chailloux A., Naya-Plasencia M., Schrottenloher A.: An efficient quantum collision search algorithm and implications on symmetric cryptography. In: ASIACRYPT 2017, Hong Kong, China, December 3–7, 2017, Proceedings, Part II, pp. 211–240 (2017).

11.

Derbez P., Fouque P.: Automatic search of meet-in-the-middle and impossible differential attacks. In: Robshaw M., Katz J. (eds.) Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9815, pp. 157–184 (2016). https://doi.org/10.1007/978-3-662-53008-5_6.

12.

Dong B., Liu T., Cui Y., Ni B., Qin L., Dong X.: Improved quantum collision attack on 5-round grøstl-512. J. Cryptol. Res. 8(6), 974 (2021). https://doi.org/10.13868/j.cnki.jcr.000491.

13.

Dong X.Y., Sun S.W., Shi D.P., Gao F., Wang X.Y., Hu L.: Quantum collision attacks on AES-like hashing with low quantum random access memories. In: Moriai S., Wang H. (eds.) Advances in Cryptology—ASIACRYPT 2020—26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II. Lecture Notes in Computer Science, vol. 12492, pp. 727–757 (2020).

14.

Dong X., Hua J., Sun S., Li Z., Wang X., Hu L.: Meet-in-the-middle attacks revisited: Key-recovery, collision, and preimage attacks. In: Malkin T., Peikert C. (eds.) Advances in Cryptology—CRYPTO 2021—41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part III. Lecture Notes in Computer Science, vol. 12827, pp. 278–308 (2021). https://doi.org/10.1007/978-3-030-84252-9_10.

15.

Fuhr T., Minaud B.: Match box meet-in-the-middle attack against KATAN. In: Cid C., Rechberger C. (eds.) Fast Software Encryption—21st International Workshop, FSE 2014, London, UK, March 3–5, 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8540, pp. 61–81 (2014). https://doi.org/10.1007/978-3-662-46706-0_4.

16.

Gilbert H., Peyrin T.: Super-sbox cryptanalysis: Improved attacks for AES-like permutations. In: FSE 2010, Seoul, Korea, February 7–10, 2010, pp. 365–383 (2010).

17.

Giovannetti V., Lloyd S., Maccone L.: Architectures for a quantum random access memory. Phys. Rev. A 78(5), 052310 (2008). https://doi.org/10.1103/physreva.78.052310.CrossRefMATH

18.

Giovannetti V., Lloyd S., Maccone L.: Quantum random access memory. Phys. Rev. Lett. 100(16), 160501 (2008). https://doi.org/10.1103/physrevlett.100.160501.MathSciNetCrossRefMATH

19.

Grover L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22–24, 1996, pp. 212–219 (1996).

20.

Hosoyamada A., Sasaki Y.: Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound. In: Canteaut A., Ishai Y. (eds.) Advances in Cryptology—EUROCRYPT 2020—39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II. Lecture Notes in Computer Science, vol. 12106, pp. 249–279 (2020). https://doi.org/10.1007/978-3-030-45724-2_9.

21.

Hosoyamada A., Sasaki Y.: Quantum collision attacks on reduced SHA-256 and SHA-512. In: Malkin T., Peikert C. (eds.) Advances in Cryptology—CRYPTO 2021—41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I. Lecture Notes in Computer Science, vol. 12825, pp. 616–646 (2021). https://doi.org/10.1007/978-3-030-84242-0_22.

22.

Hosoyamada A., Naya-Plasencia M., Sasaki Y.: Improved attacks on SLISCP permutation and tight bound of limited birthday distinguishers. IACR Trans. Symmetric Cryptol. 2020(4), 147–172 (2020). https://doi.org/10.46586/tosc.v2020.i4.147-172.

23.

Hua J., Dong X., Sun S., Zhang Z., Hu L., Wang X.: Improved MITM cryptanalysis on Streebog. IACR Trans. Symmetric Cryptol. 2022(2), 63–91 (2022). https://doi.org/10.46586/tosc.v2022.i2.63-91.

24.

Iwamoto M., Peyrin T., Sasaki Y.: Limited-birthday distinguishers for hash functions—collisions beyond the birthday bound can be meaningful. In: Sako K., Sarkar P. (eds.) Advances in Cryptology—ASIACRYPT 2013—19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1–5, 2013, Proceedings, Part II. Lecture Notes in Computer Science, vol. 8270, pp. 504–523 (2013). https://doi.org/10.1007/978-3-642-42045-0_26.

25.

Jean J., Naya-Plasencia M., Peyrin T.: Improved rebound attack on the finalist grøstl. In: FSE 2012, Washington, DC, USA, March 19–21, 2012, pp. 110–126 (2012).

26.

Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M.: Breaking symmetric cryptosystems using quantum period finding. In: CRYPTO 2016, Santa Barbara, CA, USA, August 14–18, 2016, Proceedings, Part II, pp. 207–237 (2016).

27.

Khovratovich D., Rechberger C., Savelieva A.: Bicliques for preimages: attacks on skein-512 and the SHA-2 family. In: Canteaut A. (ed.) Fast Software Encryption—19th International Workshop, FSE 2012, Washington, DC, USA, March 19–21, 2012. Revised Selected Papers. Lecture Notes in Computer Science, vol. 7549, pp. 244–263 (2012). https://doi.org/10.1007/978-3-642-34047-5_15.

28.

Kuwakado H., Morii M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: ISIT 2010, June 13–18, 2010, Austin, Texas, USA, Proceedings, pp. 2682–2685 (2010).

29.

Kuwakado H., Morii M.: Security on the quantum-type even-Mansour cipher. In: ISITA 2012, Honolulu, HI, USA, October 28–31, 2012, pp. 312–316 (2012).

30.

Lamberger M., Mendel F., Rechberger C., Rijmen V., Schläffer M.: Rebound distinguishers: results on the full whirlpool compression function. In: ASIACRYPT 2009, Tokyo, Japan, December 6–10, 2009. Proceedings, pp. 126–143 (2009).

31.

Ma B., Li B., Hao R., Li X.: Cryptanalysis of reduced-round whirlwind. In: Foo E., Stebila D. (eds.) Information Security and Privacy—20th Australasian Conference, ACISP 2015, Brisbane, QLD, Australia, June 29–July 1, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9144, pp. 20–38 (2015). https://doi.org/10.1007/978-3-319-19962-7_2.

32.

Mendel F., Rechberger C., Schläffer M., Thomsen S.S.: The rebound attack: cryptanalysis of reduced whirlpool and grøstl. In: FSE 2009, Leuven, Belgium, February 22–25, 2009, pp. 260–276 (2009).

33.

Sasaki Y.: Integer linear programming for three-subset meet-in-the-middle attacks: application to GIFT. In: Inomata A., Yasuda K. (eds.) Advances in Information and Computer Security—13th International Workshop on Security, IWSEC 2018, Sendai, Japan, September 3–5, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11049, pp. 227–243 (2018). https://doi.org/10.1007/978-3-319-97916-8_15.

34.

Sasaki Y., Aoki K.: Preimage attacks on 3, 4, and 5-pass HAVAL. In: Pieprzyk J. (ed.) Advances in Cryptology—ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7–11, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5350, pp. 253–271 (2008). https://doi.org/10.1007/978-3-540-89255-7_16.

35.

Sasaki Y., Aoki K.: Finding preimages in full MD5 faster than exhaustive search. In: Joux A. (ed.) Advances in Cryptology—EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26–30, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5479, pp. 134–152 (2009). https://doi.org/10.1007/978-3-642-01001-9_8.

36.

Sasaki Y., Li Y., Wang L., Sakiyama K., Ohta K.: Non-full-active super-sbox analysis: applications to ECHO and grøstl. In: Abe M. (ed.) Advances in Cryptology—ASIACRYPT 2010—16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5–9, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6477, pp. 38–55 (2010). https://doi.org/10.1007/978-3-642-17373-8_3.

37.

Sasaki Y., Wang L., Wu S., Wu W.: Investigating fundamental security requirements on whirlpool: improved preimage and collision attacks. In: Wang X., Sako K. (eds.) Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2–6, 2012, Proceedings, pp. 562–579 (2012).

38.

Schrottenloher A., Stevens M.: Simplified MITM modeling for permutations: new (quantum) attacks. In: Dodis Y., Shrimpton T. (eds.) Advances in Cryptology—CRYPTO 2022—42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part III. Lecture Notes in Computer Science, vol. 13509, pp. 717–747 (2022). https://doi.org/10.1007/978-3-031-15982-4_24.

39.

Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). https://doi.org/10.1137/S0097539795293172.MathSciNetCrossRefMATH

40.

van Oorschot P.C., Wiener M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999). https://doi.org/10.1007/PL00003816.MathSciNetCrossRefMATH

Titel: Improved attacks against reduced-round Whirlwind
verfasst von: Congming Wei
Bingyou Dong
Jialiang Hua
Xiaoyang Dong
Guoyan Zhang
Publikationsdatum: 08.07.2023
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 11/2023
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01254-0

Springer Professional

Improved attacks against reduced-round Whirlwind

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 11/2023

Proving knowledge of isogenies: a survey

Zero-knowledge proofs for set membership: efficient, succinct, modular

New method for combining Matsui’s bounding conditions with sequential encoding method

Generalized attack on ECDSA: known bits in arbitrary positions

Guest editorial: Special issue on Mathematics of Zero-Knowledge

Covering schemes of strength t

Premium Partner