Turn off MathJax
Article Contents
ZHANG Yi, LIU Guoqiang, SHEN Xuan, LI Chao. Rectangle Attack Against Type-I Generalized Feistel Structures[J]. Chinese Journal of Electronics. doi: 10.1049/cje.2021.00.058
 Citation: ZHANG Yi, LIU Guoqiang, SHEN Xuan, LI Chao. Rectangle Attack Against Type-I Generalized Feistel Structures[J]. Chinese Journal of Electronics.

# Rectangle Attack Against Type-I Generalized Feistel Structures

##### doi: 10.1049/cje.2021.00.058
Funds:  This work is supported by the National Natural Science Foundation of China (No.62172427, No.61702537, No.61772545, No.62002370), State Key Laboratory of Information Security 2020-MS-02, Scientific Research Plan of National University of Defense Technology (No.ZK21-36)
• Author Bio:

was born in 1994. He is a Ph.D. candidate of National University of Defense Technology. His research interests include design and analysis of block ciphers. (Email: zhangyi12@nudt.edu.cn)

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

was born in 1990. He received the Ph.D. degree in National University of Defense Technology. His research interests include design and cryptanalysis of block ciphers. (Email: shenxuan_08@163.com)

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)

• Accepted Date: 2021-12-09
• Available Online: 2021-12-18
• Type-I Generalized Feistel Networks (GFN) are widely used frameworks in symmetric-key primitive designs such as CAST-256 and Lesamnta. Different from the extensive studies focusing on specific block cipher instances, the analysis against Type-I GFN structures gives generic security evaluation of the basic frameworks and concentrates more on the effect of linear transformation. Currently, works in this field mainly evaluate the security against impossible differential attack, zero-correlation linear attack, meet-in-the-middle attack and yoyo game attack, while its security evaluation against rectangle attack is still missing. In this paper, we filled this gap and gave the first structural analytical results of Type-I GFN against rectangle attack. We proved there exists a $(b^2-b)$ round boomerang switch for the first time, which is independent of the round functions when the GFN has $b$ branches of $m$ bits. Then we proposed a new rectangle attack model and turned the boomerang switch into chosen plaintext setting. By appending 1 more round in the beginning of the boomerang switch, we constructed a $(b^2-b+1)$ round rectangle distinguisher with probability $2^{-2(b-1)m}$, whose advantage over random permutation is $2^{m}$. Using this distinguisher, a $b^2$ round key recovery attack is performed with $2^{\frac{bm}{2}+1}$ chosen plaintexts and $(2b^{-2})2^{bm}$ encryptions.
•  [1] Y. Zheng, T. Matsumoto and H. Imai, “On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses,” Proc. of CRYPTO 1989, Santa Barbara, California, USA, pp.461–480, 1989. [2] N. Wang, “Security Evaluation Against Linear Cryptanalysis for a Class of Block Cipher Transform Cluster,” Acta Electronica Sinica, vol.48, no.1, pp.137–142, 2020. (in Chinese) [3] Y. Zheng and W. Wu, “Security of Khudra Against Meet-in-the-Middle-Type Cryptanalysis,” Chinese Journal of Electronics, vol.28, no.3, pp.482–488, 2019. [4] L. Cheng, B. Sun and C. Li, “Revised cryptanalysis for SMS4,” Science China Information Science, vol.60, no.12, pp.122101:1–122101:9, 2017. [5] L. Cheng and C. Li, “Revisiting impossible differentials of MARS-like structures,” IET Information Security, vol.11, no.5, pp.273–276, 2017. [6] C. Adams and J. Gilchrist, “The CAST-256 Encryption Algorithm,” Network Working Group, RFC 2612, 1999. [7] S. Hirose, H. Kuwakado and H. Yoshida, “SHA-3 Proposal: Lesamnta,” http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LESAMNTA_Comments.pdf, 2008. [8] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol.4, no.1, pp.3–72, 1991. [9] C. Blondeau and B. Gérard, “Multiple Differential Cryptanalysis: Theory and Practice,” Proc. of FSE 2011, Lyngby, Denmark, pp.35–54, 2011. [10] T. Cui, C. Jin and J. Ma, “A New Method for Finding Impossible Differentials of Generalized Feistel Structures,” Chinese Journal of Electronics, vol.27, no.4, pp.728–733, 2018. [11] D.A. Wagner, “The Boomerang Attack,” Proc. of FSE 1999, Rome, Italy, pp.156–170, 1999. [12] E. Biham, O. Dunkelman and N. Keller, “The Rectangle Attack – Rectangling the Serpent,” Proc. of EUROCRYPT 2001, Innsbruck, Austria, pp.340-357, 2001. [13] B. Sun, Z. Liu, V. Rijmen, et al., “Links Among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis,” Proc. of CRYPTO 2015, Santa Barbara, CA, USA, pp.95–115, 2015. [14] B. Sun, M. Liu, J. Guo, et al., “New Insights on AES-Like SPN Ciphers,” Proc. of CRYPTO 2016, Santa Barbara, CA, USA, pp.605–624, 2016. [15] T. Shirai and K. Araki, “On Generalized Feistel Structures Using the Diffusion Switching Mechanism,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E91-A, no.8, pp.2120–2029, 2008. [16] L. Cheng, “Cryptanalysis on Block Ciphers Structures,” Ph.D.Thesis, National University of Defense Technology, China, 2017. (in Chinese) [17] Y. Deng, C. Jin and R. Li, “Meet in the Middle Attack on Type-1 Feistel Construction,” Proc. of Inscrypt 2017, Xi'an, China, pp.427–444, 2017. [18] T. Cui, S. Chen and H. Zheng, “A Structural Attack on Type-I Generalized Feistel Networks,” IEEE Access, vol.7, pp.69304–69310, 2019. [19] B. Ni and X. Dong, “Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256,” Journal of Electronics & Information Technology, vol.42, no.2, pp.295–306, 2020. (in Chinese) [20] E. Biham, O. Dunkelman and N. Keller, “A Related-Key Rectangle Attack on the Full KASUMI,” Proc. of ASIACRYPT 2005, Chennai, India, pp.443–461, 2005. [21] H. Hadipour, N. Bagheri and L. Song, “Improved Rectangle Attacks on SKINNY and CRAFT,” IACR Transactions on Symmetric Cryptology, vol.2021, no.2, pp.140–198, 2021. [22] S. Murphy, “The return of the cryptographic boomerang,” IEEE Transactions on Information Theory, vol.57, no.4, pp.2517–2521, 2011. [23] A. Biryukov and D. Khovratovich, “Related-key cryptanalysis of the full AES-192 and AES-256,” Proc. of ASIACRYPT 2009, Tokyo, Japan, pp.1-18, 2009. [24] C. Cid, T. Huang, T. Peyrin, et al., “Boomerang connectivity table: A new cryptanalysis tool,” Proc. of EUROCRYPT 2018, Tel Aviv, Israel, pp.683-714, 2018. [25] K. Li, L. Qu, B. Sun, et al., “New Results About the Boomerang Uniformity of Permutation Polynomials,” IEEE Transactions on Information Theory, vol.65, no.11, pp.7542–7553, 2019. [26] H. Wang and T. Peyrin, “Boomerang switch in multiple rounds,” IACR Transactions on Symmetric Cryptology, vol.2019, no.1, pp.142–169, 2019. [27] L. Song, X. Qin and L. Hu, “Boomerang connectivity table revisited,” IACR Transactions on Symmetric Cryptology, vol.2019, no.1, pp.118–141, 2019. [28] H. Boukerrou, P. Huynh, V. Lallemand, et al., “On the Feistel Counterpart of the Boomerang Connectivity Table Introduction and Analysis of the FBCT,” IACR Transactions on Symmetric Cryptology, vol.2020, no.1, pp.331–362, 2020. [29] Z. Niu, “The Study of Modulo $2^n$,” https://eprint.iacr.org/2021/056, 2021. [30] J. Kelsey, T. Kohno and B. Schneier, “Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent,” Proc. of FSE 2000, New York, NY, USA, pp.75-93, 2000. [31] J. Kim, S. Hong, B. Preneel, et al., “Related-Key Boomerang and Rectangle Attacks: Theory and Experimental Analysis,” IEEE Transactions on Information Theory, vol.58, no.7, pp.4948–4966, 2012. [32] S. Tian, C. Boura and L. Perrin, “Boomerang uniformity of popular S-box constructions,” Designs, Codes and Cryptography, vol.88, no.9, pp.1959–1989, 2020.

### Catalog

###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

Figures(6)  / Tables(1)