Improved and Multiple Linear Cryptanalysis of Reduced Round Serpent

摘要

This paper reports on the improved and multiple linear cryptanalysis of reduced round Serpent by mean of a branch-and-bound characteristic search within the algorithm. We first present a 9-round linear characteristic with probability 1/2 + 2~(-50) that involves a reduction of the estimated data complexity of the best reported attack by a factor of 16. Then, we investigate the possibility to take advantage of multiple linear approximations for improving the linear cryptanalysis of Serpent. According to the framework of Biryukov et al. from Crypto 2004, we provide estimations of the improved data complexity of such attacks and derive practical cryptanalysis scenarios. For computational reasons, the branch-and-bound search is not guaranteed to be optimal. However, these are the best reported complexities of a linear attack against Serpent.