Paper 2018/152

Related-Key Linear Cryptanalysis on SIMON

Jung-Keun Lee and Bonwook Koo and Woo-Hwan Kim

Abstract

We present a general framework of the related-key linear attack that can be applied to a class of block ciphers including the key-alternating iterative ones with linear or affine key schedules. In contrast with the existing linear attacks that use linear characteristics with linear correlations up to around \pm 2^{−n/2}, where n is the block length of the block cipher, the proposed attack can use linear characteristics with linear correlations up to around \pm 2^{−k/2}, where k is the key length, by exploiting related-key linear approximations introduced in this work. The attack utilizes the key differences as the additional data source so it can use data of size larger than the codebook size. Thus it can cover more rounds than the current linear attacks when the key length is much larger than the block length. The attack is meaningful when the product of the computational complexity and the data size is less than 2^{k+n} considering the generic known related-key attack mentioned by J. Kelsey et al. at Crypto '96 that is an extension of the chosen related-key attack by R. Winternitz et al. Our new attack has significance even when it requires more computation and data than the single-key linear attacks since it can utilize related-key data such that the number of data entries for each related key is not large. We also present a method of the related-key linear attack using multiple independent linear trails that provides a way to estimate the computational complexity, the data complexity, and the success probability of the attack in terms of the capacity of the system of the linear approximations. It is based on hypothesis testing with new decision rule and can be regarded as an alternative approach of the attack provided by A. Biryukov et al. at Crypto 2004 that is based on maximum likelihood approach and cannot estimate the success probability. By applying the framework to SIMON, we get various attack results. Then we justify our claims by presenting experimental results that are close to expected ones with a small-scale variant of SIMON.