Paper 2016/689

New Automatic Search Tool for Impossible Differentials and Zero-Correlation Linear Approximations

Tingting Cui, Shiyao Chen, Keting Jia, Kai Fu, and Meiqin Wang

Abstract

Impossible differential and zero-correlation linear cryptanalysis are two of the most powerful cryptanalysis methods in the field of symmetric key cryptography. There are several automatic tools to search such trails for ciphers with S-boxes. These tools focus on the properties of linear layers, and idealize the underlying S-boxes, i.e., assume any input and output difference pairs are possible. In reality, such S-box never exists, and the possible output differences with any fixed input difference can be at most half of the entire space. Hence, some of the possible differential trails under the ideal world become impossible in reality, possibly resulting in impossible differential trails for more rounds. In this paper, we firstly take the differential and linear properties of non-linear components such as S-box into consideration and propose a new automatic tool to search impossible differential trails for ciphers with S-box. We then generalize the tool to modulo addition, and apply it to ARX ciphers. To demonstrate the usefulness of the tool, we apply it to HIGHT, SHACAL-2, LEA, LBlock. As a result, it improves the best existing results of each cipher.