Results on Linear Models in Cryptography
Risto M. Hakala · Aaltodoc (Aalto University) · 2013
Many cryptanalytic techniques are based on exploiting linearity properties of cryptosystems. One of such techniques is linear cryptanalysis, invented by Matsui in 1993. Originally developed for block ciphers FEAL and DES, it has become a standard method for analyzing all kinds of symmetric ciphers. Linear cryptanalysis of a block cipher is traditionally based on a biased linear combination of the input and output bits of the cipher. Mathematically speaking, such a combination can be seen as a linear mapping to a one-dimensional binary vector space. Several authors have considered the use of other types of linear mappings as well, such as multidimensional and nonbinary mappings. To find suitable mappings, one usually has to analyze linearity properties of the individual components used in the cipher. The more the components resemble linear functions, the less secure the cipher is against linear cryptanalysis. Linear cryptanalysis is a method for analyzing the formal description of a cryptographic primitive. Side-channel attacks form another class of cryptanalytic methods in which an implementation of the primitive is analyzed instead of the description. They are based on doing physical measurements which may reveal critical information about the internal state of the primitive. This dissertation presents several cryptanalytic results related to linearity of cryptographic primitives. The work contains results concerning both formal specifications and real-life implementations of primitives. Related to the former area of cryptography, we describe a framework for estimating resistance against general linear cryptanalysis in which linear mappings over arbitrary finite Abelian groups can be used. As applications, we present a linear distinguishing attack on the stream cipher Shannon and on the block cipher DEAN. In addition, we study individual cryptographic components and present results regarding their linearity properties in different domains. In particular, we give evidence that certain functions based on discrete logarithm are highly nonlinear. Related to the implementation side of cryptography, we present a technique for automated analysis of side-channel data and show that it works in practice by using it to attack the ECDSA implementation in OpenSSL. The technique is based on modeling the implementation as a linear dynamical system which allows efficient analysis of the situation.