Constructing the Impossible Differential of Type-II GFN with Boolean Function and Its Application to WARP

SHI Jiali; LIU Guoqiang; LI Chao

doi:10.23919/cje.2022.00.132

Volume 33 Issue 1

Jan. 2024

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > 33(1): 80-89

Jiali SHI, Guoqiang LIU, Chao LI, “Constructing the Impossible Differential of Type-II GFN with Boolean Function and Its Application to WARP,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 80–89, 2024 doi: 10.23919/cje.2022.00.132

Citation:

Jiali SHI, Guoqiang LIU, Chao LI, “Constructing the Impossible Differential of Type-II GFN with Boolean Function and Its Application to WARP,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 80–89, 2024 doi: 10.23919/cje.2022.00.132

Citation:

PDF( 4209 KB)

Constructing the Impossible Differential of Type-II GFN with Boolean Function and Its Application to WARP

doi: 10.23919/cje.2022.00.132

SHI Jiali^1
,,
LIU Guoqiang^{1, 2, 3
,
,},
LI Chao^{1, 2, 3
,}

1.
College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410000, China
2.
Hunan Engineering Research Center of Commercial Cryptography Theory and Technology Innovation, Changsha 410000, China
3.
State Key Laboratory of Information Security, Institute of Information Engineering, Beijing 100000, China

More Information

Author Bio:
Jiali SHI was born in 1992. She is a Ph.D. candidate of National University of Defense Technology. Her research interests include design and analysis of the block ciphers. (Email: jiali00@126.com)

Guoqiang LIU was born in 1986. He received the Ph.D. degree in Information Engineering University. His research interests include design and cryptanalysis of block ciphers. (Email: liuguoqiang87@hotmail.com)

Chao LI was born in 1966. He is a Ph.D. Researcher and Ph.D. Supervisor in National University of Defense Technology. His research interests include coding theory and symmetric-key cryptography. (Email: lichao_nudt@sina.com)
Corresponding author: Email: liuguoqiang87@hotmail.com
Received Date: 2022-05-16
Accepted Date: 2022-08-22

Available Online: 2023-11-16

Publish Date: 2024-01-05

Abstract

Abstract

Type-II generalized Feistel network (GFN) has attracted a lot of attention for its simplicity and high parallelism. Impossible differential attack is one of the powerful cryptanalytic approaches for word-oriented block ciphers such as Feistel-like ciphers. We deduce the impossible differential of Type-II GFN by analyzing the Boolean function in the middle round. The main idea is to investigate the expression with the variable representing the plaintext (ciphertext) difference words for the internal state words. By adopting the miss-in-the-middle approach, we can construct the impossible differential of Type-II GFN. As an illustration, we apply this approach to WARP, a lightweight 128-bit block cipher with a 128-bit key which was presented by Banik et al. at SAC 2020. The structure of WARP is a 32-branch Type-II GFN. Therefore, we find two 21-round truncated impossible differentials and implement a 32-round key recovery attack on WARP. For the 32-round key recovery attack on WARP, some observations are used to mount an effective attack. Taking the advantage of the early abort technique, the data, time, and memory complexities are 2^125.69 chosen plaintexts, 2^126.68 32-round encryptions, and 2¹⁰⁰-bit, repectively. To the best of our knowledge, this is the best attack on WARP in the single-key scenario.
- WARP,
- Feistel cipher,
- Impossible differential attack

FullText(HTML)

References(24)

References

[1]	E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials,” in Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, pp. 12–23, 1999.
[2]	S. Lucks, “On the security of the 128-bit block cipher DEAL,” in Proceedings of the 6th International Workshop on Fast Software Encryption, Rome, Italy, pp. 60–70, 1999.
[3]	E. Biham, A. Biryukov, and A. Shamir, “Miss in the middle attacks on IDEA and Khufu,” in Proceedings of the 6th International Workshop on Fast Software Encryption, Rome, Italy, pp. 124–138, 1999.
[4]	A. Biryukov, “Miss-in-the-middle attack,” in Encyclopedia of Cryptography and Security, 2nd ed., H. C. A. van Tilborg and S. Jajodia, Eds. Springer, New York, NY, USA, pp. 786, 2011.
[5]	J. Kim, S. Hong, J. Sung, et al., “Impossible differential cryptanalysis for block cipher structures,” in Proceedings of the 4th International Conference on Progress in Cryptology, New Delhi, India, pp. 82–96, 2003.
[6]	Y. Y. Luo, X. J. Lai, Z. M. Wu, et al., “A unified method for finding impossible differentials of block cipher structures,” Information Sciences, vol. 263, pp. 211–220, 2014. doi: 10.1016/j.ins.2013.08.051
[7]	S. B. Wu and M. S. Wang, “Automatic search of truncated impossible differentials for word-oriented block ciphers,” in Proceedings of the 12th International Conference on Progress in Cryptology, Kolkata, India, pp. 283–302, 2012.
[8]	T. T. Cui, S. Y. Chen, K. T. Jia, et al., “New automatic search tool for impossible differentials and zero-correlation linear approximations,” Available at: http://eprint.iacr.org/2016/689, 2016.
[9]	Y. Sasaki and Y. Todo, “New impossible differential search tool from design and cryptanalysis aspects,” in Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, pp. 185–215, 2017.
[10]	L. Sun, D. Gerault, W. Wang, et al., “On the usage of deterministic (related-key) truncated differentials and multidimensional linear approximations for SPN ciphers,” IACR Transactions on Symmetric Cryptology, vol. 2020, no. 3, pp. 262–287, 2020. doi: 10.13154/tosc.v2020.i3.262-287
[11]	X. C. Hu, Y. Q. Li, L. Jiao, et al., “Mind the propagation of states,” in Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, pp. 415–445, 2020.
[12]	B. Sun, M. C. Liu, J. Guo, et al., “Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis,” in Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, pp. 196–213, 2016.
[13]	W. Y. Zhang, M. C. Cao, J. Guo, et al., “Improved security evaluation of SPN block ciphers and its applications in the single-key attack on SKINNY,” IACR Transactions on Symmetric Cryptology, vol. 2019, no. 4, pp. 171–191, 2020. doi: 10.13154/tosc.v2019.i4.171-191
[14]	K. Nyberg, “Generalized Feistel networks,” in Proceedings of the International Conference on the Theory and Applications of Crypotology and Information Security, Kyongju, Korea, pp. 91–104, 1996.
[15]	T. Suzaki, K. Minematsu, S. Morioka, et al., “TWINE: A lightweight block cipher for multiple platforms,” in Proceedings of the 19th International Conference on Selected Areas in Cryptography, Windsor, Canada, pp. 339–354, 2013.
[16]	S. Banik, Z. Z. Bao, T. Isobe, et al., “WARP: revisiting GFN for lightweight 128-bit block cipher,” in Proceedings of the 27th International Conference on Selected Areas in Cryptography, Halifax, NS, Canada, pp. 535–564, 2021.
[17]	Z. J. Xiang, W. T. Zhang, Z. Z. Bao, et al., “Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers,” in Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, pp. 648–678, 2016.
[18]	N. Mouha, Q. J. Wang, D. W. Gu, et al., “Differential and linear cryptanalysis using mixed-integer linear programming,” in Proceedings of the 7th International Conference on Information Security and Cryptology, Beijing, China, pp. 57–76, 2012.
[19]	J. S. Teh and A. Biryukov, “Differential cryptanalysis of WARP,” Available at: https://eprint.iacr.org/2021/1641, 2021.
[20]	H. Boukerrou, P. Huynh, V. Lallemand, et al., “On the Feistel counterpart of the boomerang connectivity table,” IACR Transactions on Symmetric Cryptology, vol. 2020, no. 1, pp. 331–362, 2020. doi: 10.13154/tosc.v2020.i1.331-362
[21]	J. Q. Lu, J. Kim, N. Keller, et al., “Improving the efficiency of impossible differential cryptanalysis of reduced camellia and MISTY1,” in Proceedings of the Cryptographers’ Track at the RSA Conference on Topics in Cryptology, San Francisco, CA, USA, pp. 370–386, 2008.
[22]	Y. L. Zheng, T. Matsumoto, and H. Imai, “On the construction of block ciphers provably secure and not relying on any unproved hypotheses,” in Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp. 461–480, 1989.
[23]	S. Banik, A. Bogdanov, T. Isobe, et al ., “Midori: A block cipher for low energy,” in Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, pp. 411–436, 2015.
[24]	T. Suzaki and K. Minematsu, “Improving the generalized Feistel,” in Proceedings of the 17th International Workshop on Fast Software Encryption, Seoul, Korea, pp. 19–39, 2010.