Rectangle Attack Against Type-I Generalized Feistel Structures

ZHANG Yi; LIU Guoqiang; SHEN Xuan; LI Chao

doi:10.1049/cje.2021.00.058

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > Accepted Manuscript

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. doi: 10.1049/cje.2021.00.058

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. doi: 10.1049/cje.2021.00.058

PDF( 3437 KB)

Rectangle Attack Against Type-I Generalized Feistel Structures

doi: 10.1049/cje.2021.00.058

ZHANG Yi^{1, 4
,},
LIU Guoqiang^{1, 3, 4
,},
SHEN Xuan^2
,,
LI Chao^{1, 4
,}

1.
College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China
2.
College of Information and Communication, National University of Defense Technology, Wuhan 430010, China
3.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
4.
Hunan Engineering Research Center of Commercial Cryptography Theory and Technology Innovation, Changsha 410073, China

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)

More Information

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)
Received Date: 2021-02-03
Accepted Date: 2021-12-09

Available Online: 2021-12-18

Abstract

Abstract

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.
- Block cipher structures,
- Rectangle attack,
- Boomerang switch,
- Structural attack

FullText(HTML)

References(32)

References

[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. doi: 10.1049/cje.2019.03.008
[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. doi: 10.1049/iet-ifs.2016.0448
[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. doi: 10.1007/BF00630563
[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. doi: 10.1049/cje.2018.04.002
[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. doi: 10.1093/ietfec/e91-a.8.2120
[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. doi: 10.1109/ACCESS.2019.2918350
[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. doi: 10.1109/TIT.2011.2111091
[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. doi: 10.1109/TIT.2019.2918531
[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. doi: 10.1109/TIT.2012.2191655
[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. doi: 10.1007/s10623-020-00785-0