Stream/block ciphers, difference equations and algebraic attacks (Q820950)

Many stream and block ciphers are defined as recursive rules determining the evolution of a vector with entries in a finite field, which is called the state or register of the cipher. This evolution runs along a discrete time corresponding to clocks or rounds. In this connection, the natural models of such ciphers are often described by systems of algebraic difference equations. The authors of the paper under review call them ``difference ciphers'' and show that many ciphers considered in applications, such as systems of LFSRs with a combiner, TRIVIUM and KEELOQ, belong to this class. The paper introduces the concept of a state transition endomorphism and applies methods of difference algebra (in particular the technique of difference Gröbner bases developed in [\textit{V. Gerdt} and \textit{R. La Scala}, J. Algebra 423, 1233--1261 (2015; Zbl 1327.12003)] and [\textit{R. La Scala}, Math. Comput. 84, No. 292, 959--985 (2015; Zbl 1328.12014)]) to obtain some fundamental properties of the considered ciphers such as their invertibility and periodicity. The authors then describe general cryptanalytic methods for difference ciphers that follow from the obtained properties and are useful to assess the security. The developed algebraic attacks are illustrated by their applications to the ciphers BIVIUM and KEELOQ.