Impossible Differential Cryptanalysis of Reduced-Round Midori64 Block Cipher (Extended Version)

Document Type: ORIGINAL RESEARCH PAPER

Authors

1 Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

2 Electronics Research Institute, Sharif University of Technology, Tehran, Iran

3 3Information Systems and Security Lab (ISSL), Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

Abstract

Impossible differential attack is a well-known mean to examine robustness of block ciphers. Using impossible differential cryptanalysis, we analyze security of a family of lightweight block ciphers, named Midori, that are designed considering low
energy consumption. Midori state size can be either 64 bits for Midori64 or 128 bits for Midori128; however, both versions have key size equal to 128 bits.
In this paper, we mainly study security of Midori64. To this end, we use various techniques such as early-abort, memory reallocation, miss-in-the-middle and turning to account the inadequate key schedule algorithm of Midori64. We first show two new 7round impossible differential characteristics which are, to the best of our knowledge, the longest impossible differential characteristics found for Midori64. Based on the new characteristics, we mount three impossible differential attacks for 10, 11, and 12 rounds on Midori64 with 2 87.7 , 2 90.63 , and 2 90.51 time complexity, respectively, to retrieve the master-key.

Keywords


[1] Aein Rezaei Shahmirzadi, Seyyed Arash Azimi, Mahmoud Salmasizadeh, Javad Mohajeri, and Mohammad Reza Aref. Impossible differential cryptanalysis of reduced-round midori64 block cipher. In Information Security and Cryptology
(ISCISC), 2017 14th International ISC Conference on. IEEE, 2017.
[2] Andrey Bogdanov, Lars R Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew JB Robshaw, Yannick Seurin, and Charlotte Vikkelsoe. Present: An ultralightweight  block cipher. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 450–466. Springer, 2007.
[3] Lars Knudsen, Gregor Leander, Axel Poschmann, and Matthew JB Robshaw. Printcipher: a block  cipher for ic-printing. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 16–32. Springer, 2010.

[4] Tomoyasu Suzaki, Kazuhiko Minematsu, Sumio Morioka, and Eita Kobayashi. Twine: A lightweight, versatile block cipher. In ECRYPT Workshop on Lightweight Cryptography, volume 2011, 2011.
[5] Julia Borghoff, Anne Canteaut, Tim Güneysu, Elif Bilge Kavun, Miroslav Knezevic, Lars R Knudsen, Gregor Leander, Ventzislav Nikov, Christof Paar, Christian Rechberger, et al. Prince–a low-latency block cipher for pervasive computing applications. In International Conference on the Theory and Application of Cryptology and Information Security, pages 208–225. Springer, 2012.
[6] WenlingWu and Lei Zhang. Lblock: a lightweight block cipher. In International Conference on Applied Cryptography and Network Security, pages 327–344. Springer, 2011.
[7] Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, and Tetsu Iwata. The 128-bit blockcipher clefia. In FSE, volume 4593, pages 181–195. Springer, 2007.
[8] Christophe De Canniere, Orr Dunkelman, and Miroslav Kneževic. Katan and ktantanâATa family of small and efficient hardware-oriented block ciphers. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 272–288. Springer, 2009.
[9] Subhadeep Banik, Andrey Bogdanov, Takanori Isobe, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, and Francesco Regazzoni. Midori: a block cipher for low energy. In International Conference on the Theory and Application of Cryptology and Information Security, pages 411–436. Springer, 2015.
[10] Jian Guo, Jérémy Jean, Ivica Nikolic, Kexin Qiao, Yu Sasaki, and Siang Meng Sim. Invariant subspace attack against full midori64. IACR Cryptology ePrint Archive, 2015:1189, 2015.
[11] Yosuke Todo, Gregor Leander, and Yu Sasaki. Nonlinear invariant attack: Practical attack on full scream, i scream, and midori 64. In 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, PartII 22, pages 3–33. Springer, 2016.
[12] Xiaoyang Dong and Yanzhao Shen. Cryptanalysis of reduced-round midori64 block cipher. Technical report, Cryptology ePrint Archive, Report 2016/676, 2016.
[13] David Gérault and Pascal Lafourcade. Relatedkey cryptanalysis of midori. In Progress in Cryptology–INDOCRYPT 2016: 17th International Conference on Cryptology in India, Kolkata, India, December 11-14, 2016, Proceedings 17, pages 287–304. Springer, 2016.
[14] Zhan Chen and Xiaoyun Wang. Impossible differential cryptanalysis of midori. IACR Cryptology ePrint Archive, 2016:535, 2016.
[15] Li Lin and Wenling Wu. Meet-in-the-middle attacks on reduced-round midori64. IACR Transactions on Symmetric Cryptology, 2017(1):215–239, 2017.
[16] Seyyed Arash Azimi, Zahra Ahmadian, Javad Mohajeri, and Mohammad Reza Aref. Impossible differential cryptanalysis of piccolo lightweight block cipher. In Information Security and Cryptology(ISCISC), 2014 11th International ISC Conference on, pages 89–94. IEEE, 2014.
[17] Christina Boura, María Naya-Plasencia, and Valentin Suder. Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon. ASIACRYPT(1), 8873:179–199, 2014.
[18] Masroor Hajari, Seyyed Arash Azimi, Poorya Aghdaie, Mahmoud Salmasizadeh, and Mohammad Reza Aref. Impossible differential cryptanalysis of reduced-round tea and xtea. In Information Security and Cryptology (ISCISC), 2015 12th International Iranian Society of Cryptology Conference on, pages 58–63. IEEE, 2015.
[19] Hamid Mala, Mohammad Dakhilalian, and Mohsen Shakiba. Impossible differential attacks on 13-round clefia-128. Journal of Computer Science and Technology, 26(4):744–750, 2011.
[20] Seyyed Arash Azimi, Siavash Ahmadi, Zahra Ahmadian, Javad Mohajeri, and Mohammad Reza Aref. Improved impossible differential and biclique cryptanalysis of hight. International Journal of Communication Systems, 31(1), 2018.
[21] Eli Biham and Adi Shamir. Differential cryptanalysis of des-like cryptosystems. In Advances
in Cryptology-CRYPTO, volume 90, pages 2–21. Springer, 1991.
[22] Lars R Knudsen. Deal a 128-bit cipher. Technical report, Technical Report, Department of Informatics, University of Bergen, Norway, 1998.
[23] Eli Biham, Alex Biryukov, and Adi Shamir. Miss in the middle attacks on idea and khufu. In FSE, volume 1636, pages 124–138. Springer, 1999.
[24] Eli Biham, Alex Biryukov, and Adi Shamir. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 12–23. Springer,1999.
[25] Joan Daemen and Vincent Rijmen. The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media, 2013.

[26] Chae Hoon Lim. Crypton: A new 128-bit block cipher. NIsT AEs Proposal, 1998.
[27] Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima, and Toshio Tokita. Camellia: A 128-bit block cipher suitable for multiple platformsdesign and analysis. In Selected Areas in Cryptography,
volume 2012, pages 39–56. Springer,2000.
[28] Daniel Dinu, Léo Perrin, Aleksei Udovenko, Vesselin Velichkov, Johann Großschädl, and Alex Biryukov. Design strategies for arx with provable bounds: Sparx and lax. In 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, PartI 22, pages 484–513. Springer, 2016.
[29] Jiqiang Lu, Orr Dunkelman, Nathan Keller, and Jongsung Kim. New impossible differential attacks on aes. In Indocrypt, volume 8, pages 279–293. Springer, 2008.
[30] Jung Hee Cheon, MunJu Kim, Kwangjo Kim,Lee Jung-Yeun, and SungWoo Kang. Improved impossible differential cryptanalysis of rijndael and crypton. In International Conference on Information Security and Cryptology, pages 39–49. Springer, 2001.
[31] Céline Blondeau. Impossible differential attack on 13-round camellia-192. Information Processing Letters, 115(9):660–666, 2015.
[32] Ahmed Abdelkhalek, Mohamed Tolba, and Amr M Youssef. Impossible differential attack on reduced round sparx-64/128. In AFRICACRYPT, pages 135–146, 2017.
[33] Yu Sasaki and Yosuke Todo. New impossible differential search tool from design and cryptanalysis aspects. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 185–215. Springer, 2017.
[34] Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque, and Gaëtan Leurent. New insights on impossible differential cryptanalysis. In Selected Areas in Cryptography, volume 7118, pages 243–259. Springer, 2011.
[35] Jongsung Kim, Seokhie Hong, and Jongin Lim. Impossible differential cryptanalysis using matrix method. Discrete Mathematics, 310(5):988–1002, 2010.
[36] Jongsung Kim, Seokhie Hong, Jaechul Sung, Sangjin Lee, Jongin Lim, and Soohak Sung. Impossible differential cryptanalysis for block cipher structures. In International Conference on Cryptology in India, pages 82–96. Springer, 2003.
[37] Jiqiang Lu, Jongsung Kim, Nathan Keller, and  Orr Dunkelman. Improving the efficiency of impossible differential cryptanalysis of reduced camellia and misty1. In CT-RSA, volume 4964, pages 370–386. Springer, 2008.