MILP-Based Linear Attacks on Round-Reduced GIFT

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 \boldsymbol2^-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 \boldsymbol2^-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.