Volume 31 Issue 1
Jan.  2022
Turn off MathJax
Article Contents
CUI Yaxin, XU Hong, QI Wenfeng. MILP-Based Linear Attacks on Round-Reduced GIFT[J]. Chinese Journal of Electronics, 2022, 31(1): 89-98. doi: 10.1049/cje.2020.00.113
 Citation: CUI Yaxin, XU Hong, QI Wenfeng. MILP-Based Linear Attacks on Round-Reduced GIFT[J]. Chinese Journal of Electronics, 2022, 31(1): 89-98.

# MILP-Based Linear Attacks on Round-Reduced GIFT

##### doi: 10.1049/cje.2020.00.113
Funds:  This work was supported by the National Natural Science Foundation of China (61521003) and the National Cryptography Development Fund of China (MMJJ20180204, MMJJ20170103)
• Author Bio:

is a master degree candidate of Information Engineering University. Her research interest is the design and analysis of block ciphers. (Email: cuiyaxinxin@163.com)

(corresponding author) is an Associate Professor of Information Engineering University. Her research interests include symmetric ciphers and sequences. (Email: xuhong0504@163.com)

is a Professor of Information Engineering University. His research interests include symmetric ciphers and sequences. (Email: wenfeng.qi@263.net)

• Accepted Date: 2020-12-17
• Available Online: 2021-10-09
• Publish Date: 2022-01-05
• GIFT is a lightweight block cipher with an substitution-permutation-network (SPN) structure proposed in CHES 2017. It has two different versions whose block sizes are 64 and 128 respectively. In RSA 2019, Zhu et al. found some differential characteristics of GIFT with mixed integer linear programming (MILP) method and presented corresponding differential attacks. In this paper, we further find some linear characteristics with MILP method. For GIFT-64, we find two 11-round linear characteristics with correlation ${\boldsymbol{2^{-29}}}$, and use one of them to present a 16-round linear attack on GIFT-64 by adding 4 rounds before and one round after the linear characteristic. For GIFT-128, we find a 16-round linear characteristic with correlation ${\boldsymbol{2^{-62}}}$. As far as we know, it is the longest linear characteristic found for GIFT-128. Using the 16-round linear characteristic, we present a 20-round linear attack on GIFT-128 by adding 2 rounds before and 2 rounds after the linear characteristic.
•  [1] A. Bogdanov, L. Knudsen, G. Leander, et al., “PRESENT: An ultra-lightweight block cipher,” in Proc. of the 9th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2007), Vienna, pp.450–466, 2007. [2] W. L. Wu and L. Zhang, “Lblock: A lightweight block cipher,” in Proc. of the 9th International Conference on Applied Cryptography and Network Security (ACNS 2011), Nerja, pp.327–344, 2011. [3] R. Beaulieu, D. Shors, J. Smith, et al., “The SIMON and SPECK families of lightweight block ciphers,” IACR Cryptology ePrint Archive, https://eprint.iacr.org/ 2013/404.pdf, 2013. [4] C. Beierle, J. Jean, S. Kölbl, et al., “The SKINNY family of block ciphers and its low-latency variant MANTIS,” in Proc. of the 36th Annual International Cryptology Conference on Advances in Cryptology ( CRYPTO 2016), Santa Barbara, CA, pp.123–153, 2016. [5] S. Banik, S. Pandey, T. Peyrin, et al., “GIFT: A small present towards reaching the limit of lightweight encryption,” in Proc. of the 19th International Conference on Cryptographic Hardware and Embedded Systems (CHES 2017), Taipei, pp.321–345, 2017. [6] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol.4, no.1, pp.3–72, 1991. [7] M. Matsui, “Linear cryptanalysis method for DES cipher,” in Proc. of Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT’93), Lofthus, pp.386–397, 1993. [8] M. Matsui, “On correlation between the order of sboxes and the strength of DES,” in Proc. of Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT ’94), Perugia, pp.366–375, 1994. [9] K. Ohta, S. Moriai, and K. Aoki, “Improving the search algorithm for the best linear expression,” in Proc. of the 15th Annual International Cryptology Conference (CRYPT0 1995), Santa Barbara, California, pp.157–170, 1995. [10] K. Aoki, K. Kobayashi, and S. Moriai, “Best differential characteristic search of FEAL,” in Proc. of 4th International Workshop on Fast Software Encryption (FSE’97), Haifa, pp.41–53, 1997. [11] Z. Z. Bao, W. T. Zhang, and D. D. Lin, “Speeding up the search algorithm for the best differential and best linear trails,” in Proc. of the 10th International Conference on Information Security and Cryptology (Inscrypt 2014), Beijing, pp.259–285, 2014. [12] F. L. Ji, W. T. Zhang, and T. Y. Ding, “Improving Matsui’s search algorithm for the best differential/linear trails and its applications for DES, DES(L) and GIFT,” The Computer Journal, vol.64, no.4, pp.610–627, 2021. [13] N. Mouha, Q. J. Wang, et al, “Differential and linear cryptanalysis using mixed-integer linear programming,” in Proc. of the 7th International Conference on Information Security and Cryptology (Inscrypt 2011), Beijing, 57–76, 2011. [14] S. W. Sun, L. Hu, P. Wang, et al., “Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers,” in Proc. of the 20th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2014), Kaoshiung, pp.158–178, 2014. [15] S. W. Sun, L. Hu, M. Q. Wang, et al., “Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties,” Cryptology ePrint Archive, https://eprint.iacr.org/2014/747.pdf, 2015. [16] B. Y. Zhu, X. Y. Dong, H. B. Yu, “MILP-based differential attack on round-reduced GIFT,” in Proc. of the Cryptographers' Track at the RSA Conference 2019, San Francisco, CA, pp.372–390, 2019. [17] L. C. Li, W. L. Wu, Y. F. Zheng, et al, “The relationship between the construction and solution of the MILP models and applications”, Cryptology ePrint Archive, https://eprint.iacr.org/2019/049.pdf, 2019. [18] S. Kölbl, G. Leander, and T. Tiessen, “Observations on the SIMON block cipher family,” in Proc. of the 35th Annual Cryptology Conference on Advances in Cryptology (CRYPTO 2015), Santa Barbara, CA, pp.161–185, 2015. [19] Y. W. Liu, Q. J. Wang, et al, “Automatic search of linear trails in ARX with applications to SPECK and Chaskey,” in Proc. of the 14th International Conference on Applied Cryptography and Network Security (ACNS 2016), Guildford, pp.485–499, 2016. [20] R. Ankele and S. Kölbl. “Mind the gap - A closer look at the security of block ciphers against differential cryptanalysis,” in Proc. of the 25th International Conference on Selected Areas in Cryptography (SAC 2018), Calgary, AB, pp.163–190, 2018. [21] L. Sun, W. Wang, and M. Q. Wang, “More accurate differential properties of LED64 and Midori64,” IACR Trans. Symmetric Cryptol, vol.2018, no.3, pp.93–123, 2018. [22] Y. Liu, H. C. Liang, M. Z. Li, et al, “STP models of optimal differential and linear trail for s-box based ciphers”, Cryptology ePrint Archive, https://eprint.iacr.org/ 2019/025.pdf, 2019. [23] A. A. Selçuk, “On probability of success in linear and differential cryptanalysis,” Journal of Cryptology, vol.21, no.1, pp.131–147, 2008.

### Catalog

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

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

Tables(12)