Rectangle Attack Against Type-I Generalized Feistel Structures

ZHANG Yi; LIU Guoqiang; SHEN Xuan; LI Chao

doi:10.1049/cje.2021.00.058

Volume 31 Issue 4

Jul. 2022

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2022 > 31(4): 713-720

ZHANG Yi, LIU Guoqiang, SHEN Xuan, et al., “Rectangle Attack Against Type-I Generalized Feistel Structures,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 713-720, 2022, doi: 10.1049/cje.2021.00.058

Citation:

ZHANG Yi, LIU Guoqiang, SHEN Xuan, et al., “Rectangle Attack Against Type-I Generalized Feistel Structures,” Chinese Journal of Electronics, vol. 31, no. 4, pp. 713-720, 2022, doi: 10.1049/cje.2021.00.058

Citation:

PDF( 3493 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 was supported by the National Natural Science Foundation of China (62172427, 61702537, 61772545, 62002370), State Key Laboratory of Information Security (2020-MS-02), and Scientific Research Plan of National University of Defense Technology (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 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)

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 Doctoral 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

Publish Date: 2022-07-05

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. By exploiting its structural properties, we proved there exists a boomerang switch for Type-I GFN for the first time, which is independent of the round functions. Then we turned the boomerang switch into chosen plaintext setting and proposed a new rectangle attack model. By appending 1 more round in the beginning of the boomerang switch, we constructed a rectangle distinguisher and a key recovery attack could be performed.
- Block cipher structures,
- Rectangle attack,
- Boomerang switch,
- Structural attack,
- Generalized Feistel networks

FullText(HTML)

References(28)

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) doi: 10.3969/j.issn.0372-2112.2020.01.017
[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]	C. Adams and J. Gilchrist, “The CAST-256 encryption algorithm,” Network Working Group, RFC 2612, available at: https://www.ipa.go.jp/security/rfc/RFC2612EN.html, 1999.
[5]	S. Hirose, H. Kuwakado, and H. Yoshida, “SHA-3 proposal: Lesamnta,” available at: http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LESAMNTA_Comments.pdf, 2008.
[6]	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
[7]	C. Blondeau and B. Gérard, “Multiple differential cryptanalysis: Theory and practice,” Proc. of FSE 2011, Lyngby, Denmark, pp.35–54, 2011.
[8]	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
[9]	D. A. Wagner, “The boomerang attack,” Proc. of FSE 1999, Rome, Italy, pp.156–170, 1999.
[10]	E. Biham, O. Dunkelman, and N. Keller, “The rectangle attack – Rectangling the serpent,” Proc. of EUROCRYPT 2001, Innsbruck, Austria, pp.340–357, 2001.
[11]	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.
[12]	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
[13]	L. Cheng, “Cryptanalysis on block ciphers structures,” Ph.D.Thesis, National University of Defense Technology, China, 2017. (in Chinese)
[14]	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.
[15]	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
[16]	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) doi: 10.11999/JEIT190633
[17]	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.
[18]	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.
[19]	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
[20]	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.
[21]	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.
[22]	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
[23]	H. Wang and T. Peyrin, “Boomerang switch in multiple rounds,” IACR Transactions on Symmetric Cryptology, vol.2019, no.1, pp.142–169, 2019. doi: 10.13154/tosc.v2019.i1.142-169
[24]	L. Song, X. Qin, and L. Hu, “Boomerang connectivity table revisited,” IACR Transactions on Symmetric Cryptology, vol.2019, no.1, pp.118–141, 2019. doi: 10.13154/tosc.v2019.i1.118-141
[25]	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. doi: 10.13154/tosc.v2020.i1.331-362
[26]	Z. Niu, “The study of modulo $2^n $,” available at: https://eprint.iacr.org/2021/056, 2021.
[27]	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.
[28]	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