FFT‐based multidimensional linear attack on PRESENT using the 2‐bit‐fixed characteristic

Abstract Linear cryptanalysis is one of the most important cryptanalysis methods and remains vital in the cryptography research up to now. Many derivatives, improvements, and generations of linear cryptanalysis have been introduced to attack the ciphers of different designs. This paper defines a new characteristic of the cryptographic function, called 2‐bit‐fixed characteristic, as a generation of the linear characteristic. Compared with the linear characteristic, it restricts the input more severely to obtain a larger output bias. Using the characteristic, this paper gives a multidimensional linear attack on 27‐round PRESENT with a computation complexity of 274 encryptions, where the fast Fourier transform is employed to deduct the computation complexity. The attack is the first attack on the 27‐round PRESENT of 80 bits master key, verified by experiments for reduced‐round versions, in which we successfully attack 14‐round and 15‐round PRESENT with data complexities of 228 and 231, respectively. Copyright © 2015 John Wiley & Sons, Ltd.