Boomerang Attacks on Reduced-Round Midori64

Gönen, Mehmet Emin; Gündoğan, Muhammed Said; Otal, Kamil

doi:10.22042/isecure.2024.421023.1033

Boomerang Attacks on Reduced-Round Midori64

Document Type : Research Article

Authors

Mehmet Emin Gönen

Muhammed Said Gündoğan

Kamil Otal

T ¨UB ˙ITAK B ˙ILGEM National Research Institute of Electronics and Cryptology, Gebze, Turkey

https://doi.org/10.22042/isecure.2024.421023.1033

Abstract

Midori64 is a lightweight SPN block cipher introduced by Banik et al. at ASIACRYPT 2015 which operates on 64-bit states through 16 rounds using a 128-bit key. In the last decade, Midori64 has been exposed to several attacks intensely. In this paper, we provide the first boomerang attack on Midori64 in the literature, to the best of our knowledge. For this purpose, firstly we present a practical single key 7-round boomerang attack on Midori64 improving the mixture idea of Biryukov by a new technique which we call ``mixture pool", and then extend our attack up to 9 rounds with time complexity $2^{122.3}$, and memory and data complexity $2^{36}$. (The authors of Midori stated that they expect much smaller rounds than 8 rounds of Midori64 are secure against boomerang-type attacks.) We also emphasize that the mixture pool idea provides a kind of data-memory tradeoff and hence presents more usefulness for boomerang-type attacks.

Keywords

Boomerang attack

Substitution-Permutation Network(SPN)

Block Cipher

Midori

Lightweight Cryptography

[1] Subhadeep Banik, Andrey Bogdanov, Takanori Isobe, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, and Francesco Regazzoni. Midori: A block cipher for low energy. In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology
- ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 411–436. Springer, 2015.
[2] Jian Guo, J´er´emy Jean, Ivica Nikolic, Kexin Qiao, Yu Sasaki, and Siang Meng Sim. Invariant subspace attack against Midori64 and the resistance criteria for S-box designs. IACR Trans. Symmetric Cryptol., 2016(1):33–56, 2016.
[3] Yosuke Todo, Gregor Leander, and Yu Sasaki. Nonlinear invariant attack - practical attack on full scream, iscream, and Midori64. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II, volume 10032 of Lecture Notes in Computer Science, pages 3–33, 2016.
[4] Li Lin and Wenling Wu. Meet-in-the-middle attacks on reduced-round Midori64. IACR Trans. Symmetric Cryptol., 2017(1):215–239, 2017.
[5] Yong Liu, Zejun Xiang, Siwei Chen, Shasha Zhang, and Xiangyong Zeng. A novel automatic technique based on MILP to search for impossible differentials. In Mehdi Tibouchi and Xiaofeng Wang, editors, Applied Cryptography and Network Security - 21st International Conference, ACNS 2023, Kyoto, Japan, June 19-22, 2023, Proceedings, Part I, volume 13905 of Lecture Notes in Computer Science, pages 119–148. Springer, 2023.
[6] Aein Rezaei Shahmirzadi, Seyyed Arash Azimi, Mahmoud Salmasizadeh, Javad Mohajeri, and Mohammad Reza Aref. Impossible differential cryptanalysis of reduced-round Midori64 block cipher. In 14th International ISC (Iranian Society of Cryptology) Conference on Information Security and Cryptology, ISCISC 2017, Shiraz, Iran, September 6-7, 2017, pages 99–104. IEEE, 2017.
[7] Hongluan Zhao, Guoyong Han, Letian Wang, and Wen Wang. MILP-based differential cryptanalysis on round-reduced Midori64. IEEE Access, 8:95888–95896, 2020.
[8] Tim Beyne. Block cipher invariants as eigenvectors of correlation matrices. In Thomas Peyrin and Steven D. Galbraith, editors, Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part I, volume 11272 of Lecture Notes in Computer Science, pages 3–31. Springer, 2018.
[9] Ewan Fleischmann, Christian Forler, Michael Gorski, and Stefan Lucks. New boomerang attacks on ARIA. In Guang Gong and Kishan Chand Gupta, editors, Progress in Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryptology in India, Hyderabad, India, December 12-15, 2010. Proceedings, volume 6498 of Lecture Notes in Computer Science,
pages 163–175. Springer, 2010.
[10] Orr Dunkelman, Nathan Keller, Eyal Ronen, and Adi Shamir. The retracing boomerang attack. In Anne Canteaut and Yuval Ishai, editors, 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 I, volume 12105 of Lecture Notes in Computer Science, pages 280–309. Springer, 2020.
[11] Alex Biryukov. The boomerang attack on 5 and 6-round reduced AES. In Hans Dobbertin, Vincent Rijmen, and Aleksandra Sowa, editors, Advanced Encryption Standard - AES, 4th International Conference, AES 2004, Bonn, Germany,
May 10-12, 2004, Revised Selected and Invited Papers, volume 3373 of Lecture Notes in Computer Science, pages 11–15. Springer, 2004.
[12] Eli Biham and Adi Shamir. Differential cryptanalysis of des-like cryptosystems. J. Cryptology, 4(1):3–72, 1991.
[13] David A. Wagner. The boomerang attack. In Lars R. Knudsen, editor, Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, Italy, March 24-26, 1999, Proceedings, volume 1636 of Lecture Notes in Computer Science,
pages 156–170. Springer, 1999.
[14] J´er´emy Jean. TikZ for Cryptographers. https://www.iacr.org/authors/tikz/, 2016.
[15] Lorenzo Grassi. Mixture differential cryptanalysis: a new approach to distinguishers and attacks on round-reduced AES. IACR Trans. Symmetric Cryptol., 2018(2):133–160, 2018.
[16] Alex Biryukov, Christophe De Canni`ere, and Gustaf Dellkrantz. Cryptanalysis of SAFER++. In Dan Boneh, editor, Advances in Cryptology- CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 195–211. Springer, 2003.