Volume 31 Issue 4
Jul.  2022
Turn off MathJax
Article Contents
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

Rectangle Attack Against Type-I Generalized Feistel Structures

doi: 10.1049/cje.2021.00.058
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
  • 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.
  • loading
  • [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
  • 加载中

Catalog

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

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

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(6)  / Tables(1)

    Article Metrics

    Article views (417) PDF downloads(40) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return