Stream/block ciphers, difference equations and algebraic attacks
This work addresses security assessment for cryptographic ciphers, but it is incremental as it applies existing difference algebra to known ciphers.
The paper tackles the problem of modeling stream and block ciphers as systems of difference equations over finite fields, showing that ciphers like LFSRs, Trivium, and Keeloq belong to this class, and it results in defining properties like invertibility and periodicity, with practical attacks demonstrated on Bivium and Keeloq.
In this paper we model a class of stream and block ciphers as systems of (ordinary) explicit difference equations over a finite field. We call this class "difference ciphers" and we show that ciphers of application interest, as for example systems of LFSRs with a combiner, Trivium and Keeloq, belong to the class. By using Difference Algebra, that is, the formal theory of difference equations, we can properly define and study important properties of these ciphers, such as their invertibility and periodicity. We describe then general cryptanalytic methods for difference ciphers that follow from these properties and are useful to assess the security. We illustrate such algebraic attacks in practice by means of the ciphers Bivium and Keeloq.