Differential-Linear Cryptanalysis of GIFT family and GIFT-based Ciphers

Shichang Wang; Meicheng Liu; Shiqi Hou; Dongdai Lin

doi:10.62056/a6n5txol7

Differential-Linear Cryptanalysis of GIFT family and GIFT-based Ciphers

Authors

Shichang Wang, Meicheng Liu, Shiqi Hou, Dongdai Lin

Shichang Wang

Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
wangshichang at iie dot ac dot cn

Meicheng Liu

Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
liumeicheng at iie dot ac dot cn

Shiqi Hou

Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
houshiqi at iie dot ac dot cn

Dongdai Lin

Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, Beijing, China
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
ddlin at iie dot ac dot cn

Keywords: Differential-linear attack GIFT GIFT-COFB HyENA

Abstract

At CHES 2017, Banik et al. proposed a lightweight block cipher GIFT consisting of two versions GIFT-64 and GIFT-128. Recently, there are lots of authenticated encryption schemes that adopt GIFT-128 as their underlying primitive, such as GIFT-COFB and HyENA. To promote a comprehensive perception of the soundness of the designs, we evaluate their security against differential-linear cryptanalysis.

For this, automatic tools have been developed to search differential-linear approximation for the ciphers based on S-boxes. With the assistance of the automatic tools, we find 13-round differential-linear approximations for GIFT-COFB and HyENA. Based on the distinguishers, 18-round key-recovery attacks are given for the message processing phase and initialization phase of both ciphers. Moreover, the resistance of GIFT-64/128 against differential-linear cryptanalysis is also evaluated. The 12-round and 17-round differential-linear approximations are found for GIFT-64 and GIFT-128 respectively, which lead to 18-round and 19-round key-recovery attacks respectively. Here, we stress that our attacks do not threaten the security of these ciphers.

References

[BCI⁺21]

Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB. NIST Lightweight Cryptography Project, 2021.

Google Scholar ePrint

[BDKW19]

Achiya Bar-On, Orr Dunkelman, Nathan Keller, and Ariel Weizman. DLCT: A new tool for differential-linear cryptanalysis. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I, volume 11476 of Lecture Notes in Computer Science, 313–342. Springer, 2019. https://doi.org/10.1007/978-3-030-17653-2_11.

Google Scholar ePrint

[BGG⁺23]

Emanuele Bellini, David Gérault, Juan Grados, Rusydi H. Makarim, and Thomas Peyrin. Fully automated differential-linear attacks against ARX ciphers. In Mike Rosulek, editor, Topics in Cryptology - CT-RSA 2023 - Cryptographers' Track at the RSA Conference 2023, San Francisco, CA, USA, April 24-27, 2023, Proceedings, volume 13871 of Lecture Notes in Computer Science, 252–276. Springer, 2023. https://doi.org/10.1007/978-3-031-30872-7_10.

Google Scholar ePrint

[BLN17]

Céline Blondeau, Gregor Leander, and Kaisa Nyberg. Differential-linear cryptanalysis revisited. J. Cryptol., 30(3):859–888, 2017. https://doi.org/10.1007/s00145-016-9237-5.

Google Scholar ePrint

[BLT20]

Christof Beierle, Gregor Leander, and Yosuke Todo. Improved differential-linear attacks with applications to ARX ciphers. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part III, volume 12172 of Lecture Notes in Computer Science, 329–358. Springer, 2020. https://doi.org/10.1007/978-3-030-56877-1_12.

Google Scholar ePrint

[BPP⁺17]

Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present - towards reaching the limit of lightweight encryption. In Wieland Fischer and Naofumi Homma, editors, Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, volume 10529 of Lecture Notes in Computer Science, 321–345. Springer, 2017. https://doi.org/10.1007/978-3-319-66787-4_16.

Google Scholar ePrint

[BS90]

Eli Biham and Adi Shamir. Differential cryptanalysis of des-like cryptosystems. In Alfred Menezes and Scott A. Vanstone, editors, Advances in Cryptology - CRYPTO '90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings, volume 537 of Lecture Notes in Computer Science, 2–21. Springer, 1990. https://doi.org/10.1007/3-540-38424-3_1.

Google Scholar ePrint

[CDJN19]

Avik Chakraborti, Nilanjan Datta, Ashwin Jha, and Mridul Nandi. HyENA. NIST Lightweight Cryptography Project, 2019.

Google Scholar ePrint

[CN21]

Murilo Coutinho and Tertuliano C. Souza Neto. Improved linear approximations to ARX ciphers and attacks against chacha. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, volume 12696 of Lecture Notes in Computer Science, 711–740. Springer, 2021. https://doi.org/10.1007/978-3-030-77870-5_25.

Google Scholar ePrint

[CZD19]

Huaifeng Chen, Rui Zong, and Xiaoyang Dong. Improved differential attacks on GIFT-64. In Jianying Zhou, Xiapu Luo, Qingni Shen, and Zhen Xu, editors, Information and Communications Security - 21st International Conference, ICICS 2019, Beijing, China, December 15-17, 2019, Revised Selected Papers, volume 11999 of Lecture Notes in Computer Science, 447–462. Springer, 2019. https://doi.org/10.1007/978-3-030-41579-2_26.

Google Scholar ePrint

[HPTY23]

Kai Hu, Thomas Peyrin, Quan Quan Tan, and Trevor Yap. Revisiting higher-order differential-linear attacks from an algebraic perspective. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part III, volume 14440 of Lecture Notes in Computer Science, 405–435. Springer, 2023. https://doi.org/10.1007/978-981-99-8727-6_14.

Google Scholar ePrint

[JZZD20a]

Fulei Ji, Wentao Zhang, Chunning Zhou, and Tianyou Ding. Improved (related-key) differential cryptanalysis on GIFT. IACR Cryptol. ePrint Arch., pages 1242, 2020.

Google Scholar ePrint

[JZZD20b]

Fulei Ji, Wentao Zhang, Chunning Zhou, and Tianyou Ding. Improved (related-key) differential cryptanalysis on GIFT. In Orr Dunkelman, Michael J. Jacobson Jr., and Colin O'Flynn, editors, Selected Areas in Cryptography - SAC 2020 - 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers, volume 12804 of Lecture Notes in Computer Science, 198–228. Springer, 2020. https://doi.org/10.1007/978-3-030-81652-0_8.

Google Scholar ePrint

[Leu16]

Gaëtan Leurent. Improved differential-linear cryptanalysis of 7-round chaskey with partitioning. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, 344–371. Springer, 2016. https://doi.org/10.1007/978-3-662-49890-3_14.

Google Scholar ePrint

[LH94]

Susan K. Langford and Martin E. Hellman. Differential-linear cryptanalysis. In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, 17–25. Springer, 1994. https://doi.org/10.1007/3-540-48658-5_3.

Google Scholar ePrint

[LJC23]

Guangqiu Lv, Chenhui Jin, and Ting Cui. A miqcp-based automatic search algorithm for differential-linear trails of ARX ciphers(long paper). IACR Cryptol. ePrint Arch., pages 259, 2023.

Google Scholar ePrint

[LLL21]

Meicheng Liu, Xiaojuan Lu, and Dongdai Lin. Differential-linear cryptanalysis from an algebraic perspective. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, 247–277. Springer, 2021. https://doi.org/10.1007/978-3-030-84252-9_9.

Google Scholar ePrint

[LSL21]

Yunwen Liu, Siwei Sun, and Chao Li. Rotational cryptanalysis from a differential-linear perspective - practical distinguishers for round-reduced friet, xoodoo, and alzette. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, volume 12696 of Lecture Notes in Computer Science, 741–770. Springer, 2021. https://doi.org/10.1007/978-3-030-77870-5_26.

Google Scholar ePrint

[Mat93]

Mitsuru Matsui. Linear cryptanalysis method for DES cipher. In Tor Helleseth, editor, Advances in Cryptology - EUROCRYPT '93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, volume 765 of Lecture Notes in Computer Science, 386–397. Springer, 1993. https://doi.org/10.1007/3-540-48285-7_33.

Google Scholar ePrint

[MWGP11]

Nicky Mouha, Qingju Wang, Dawu Gu, and Bart Preneel. Differential and linear cryptanalysis using mixed-integer linear programming. In Chuankun Wu, Moti Yung, and Dongdai Lin, editors, Information Security and Cryptology - 7th International Conference, Inscrypt 2011, Beijing, China, November 30 - December 3, 2011. Revised Selected Papers, volume 7537 of Lecture Notes in Computer Science, 57–76. Springer, 2011. https://doi.org/10.1007/978-3-642-34704-7_5.

Google Scholar ePrint

[NSLL22]

Zhongfeng Niu, Siwei Sun, Yunwen Liu, and Chao Li. Rotational differential-linear distinguishers of ARX ciphers with arbitrary output linear masks. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I, volume 13507 of Lecture Notes in Computer Science, 3–32. Springer, 2022. https://doi.org/10.1007/978-3-031-15802-5_1.

Google Scholar ePrint

[Sel08]

Ali Aydin Selçuk. On probability of success in linear and differential cryptanalysis. J. Cryptol., 21(1):131–147, 2008. https://doi.org/10.1007/s00145-007-9013-7.

Google Scholar ePrint

[SHW⁺14a]

Siwei Sun, Lei Hu, Meiqin Wang, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Danping Shi, Ling Song, and Kai Fu. Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties. 2014.

Google Scholar ePrint

[SHW⁺14b]

Siwei Sun, Lei Hu, Peng Wang, Kexin Qiao, Xiaoshuang Ma, and Ling Song. Automatic security evaluation and (related-key) differential characteristic search: application to simon, present, lblock, DES(L) and other bit-oriented block ciphers. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873 of Lecture Notes in Computer Science, 158–178. Springer, 2014. https://doi.org/10.1007/978-3-662-45611-8_9.

Google Scholar ePrint

[SWW21a]

Ling Sun, Wei Wang, and Meiqin Wang. Improved attacks on GIFT-64. In Riham AlTawy and Andreas Hülsing, editors, Selected Areas in Cryptography - 28th International Conference, SAC 2021, Virtual Event, September 29 - October 1, 2021, Revised Selected Papers, volume 13203 of Lecture Notes in Computer Science, 246–265. Springer, 2021. https://doi.org/10.1007/978-3-030-99277-4_12.

Google Scholar ePrint

[SWW21b]

Ling Sun, Wei Wang, and Meiqin Wang. Linear cryptanalyses of three aeads with GIFT-128 as underlying primitives. IACR Trans. Symmetric Cryptol., 2021(2):199–221, 2021. https://doi.org/10.46586/tosc.v2021.i2.199-221.

Google Scholar ePrint

[SWW22]

Ling Sun, Wei Wang, and Meiqin Wang. Addendum to linear cryptanalyses of three aeads with GIFT-128 as underlying primitives. IACR Trans. Symmetric Cryptol., 2022(1):212–219, 2022. https://doi.org/10.46586/TOSC.V2022.I1.212-219.

Google Scholar ePrint

[ZDC⁺21]

Rui Zong, Xiaoyang Dong, Huaifeng Chen, Yiyuan Luo, Si Wang, and Zheng Li. Towards key-recovery-attack friendly distinguishers: application to GIFT-128. IACR Trans. Symmetric Cryptol., 2021(1):156–184, 2021. https://doi.org/10.46586/tosc.v2021.i1.156-184.

Google Scholar ePrint

[ZDY19]

Baoyu Zhu, Xiaoyang Dong, and Hongbo Yu. Milp-based differential attack on round-reduced GIFT. In Mitsuru Matsui, editor, Topics in Cryptology - CT-RSA 2019 - The Cryptographers' Track at the RSA Conference 2019, San Francisco, CA, USA, March 4-8, 2019, Proceedings, volume 11405 of Lecture Notes in Computer Science, 372–390. Springer, 2019. https://doi.org/10.1007/978-3-030-12612-4_19.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a6n5txol7

History

Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Shichang Wang, Meicheng Liu, Shiqi Hou, and Dongdai Lin, "Differential-Linear Cryptanalysis of GIFT family and GIFT-based Ciphers," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a6n5txol7.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-1-13,
    author = "Wang, Shichang and Liu, Meicheng and Hou, Shiqi and Lin, Dongdai",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Differential-Linear Cryptanalysis of {GIFT} family and {GIFT}-based Ciphers",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a6n5txol7"
}

TY - JOUR
AU - Wang, Shichang
AU - Liu, Meicheng
AU - Hou, Shiqi
AU - Lin, Dongdai
PY  - 2024
TI  - Differential-Linear Cryptanalysis of GIFT family and GIFT-based Ciphers
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/a6n5txol7
UR  - https://doi.org/10.62056/a6n5txol7
AB  - <p>At CHES 2017, Banik et al. proposed a lightweight block cipher GIFT consisting of two versions GIFT-64 and GIFT-128. Recently, there are lots of authenticated encryption schemes that adopt GIFT-128 as their underlying primitive, such as GIFT-COFB and HyENA. To promote a comprehensive perception of the soundness of the designs, we evaluate their security against differential-linear cryptanalysis.</p><p>For this, automatic tools have been developed to search differential-linear approximation for the ciphers based on S-boxes. With the assistance of the automatic tools, we find 13-round differential-linear approximations for GIFT-COFB and HyENA. Based on the distinguishers, 18-round key-recovery attacks are given for the message processing phase and initialization phase of both ciphers. Moreover, the resistance of GIFT-64/128 against differential-linear cryptanalysis is also evaluated. The 12-round and 17-round differential-linear approximations are found for GIFT-64 and GIFT-128 respectively, which lead to 18-round and 19-round key-recovery attacks respectively. Here, we stress that our attacks do not threaten the security of these ciphers. </p>
ER  -

Shichang Wang, Meicheng Liu, Shiqi Hou, and Dongdai Lin, "Differential-Linear Cryptanalysis of GIFT family and GIFT-based Ciphers," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a6n5txol7.