Results on Linear Models in Cryptography

Abstract

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.

Useat kryptoanalyyttiset menetelmät perustuvat salausmenetelmien lineaarisuusominaisuuksien hyödyntämiseen. Eräs tällainen menetelmä on Matsuin vuonna 1993 esittämä lineaarinen kryptoanalyysi. Se kehitettiin alun perin FEAL- ja DES-lohkosalausmenetelmille, mutta siitä on tullut standardi menetelmä kaikentyyppisten symmetristen salausmenetelmien analysointiin. Lohkosalausmenetelmän perinteinen lineaarinen kryptoanalyysi perustuu jonkun syöte- ja tulostebittien lineaariyhdistelyn tilastolliseen vinoumaan. Matemaattisesti tällainen yhdistely voidaan nähdä lineaarisena kuvauksena yksiulotteiselle binääriselle vektoriavaruudelle. Useat tutkijat ovat tarkastelleet myös muunlaisten lineaarikuvausten käyttämistä, kuten moniulotteisia ja ei-binäärisia kuvauksia. Sopivien kuvausten löytämiseksi täytyy tavallisesti analysoida salausmenetelmässä käytettyjen yksittäisten komponenttien lineaarisuusominaisuuksia. Mitä enemmän komponentit muistuttavat lineaarisia funktioita sitä turvattomampi salausmenetelmä on lineaarista kryptoanalyysia vastaan. Lineaarinen kryptoanalyysi on menetelmä, jolla analysoidaan kryptografisen primitiivin muodollista kuvausta. Toisen tyyppisen menetelmäluokan muodostavat sivukanavahyökkäykset, joilla muodollisen kuvauksen asemesta analysoidaan primitiivin toteutusta. Ne perustuvat fysikaalisiin mittauksiin, jotka voivat paljastaa kriittistä tietoa primitiivin sisäisestä tilasta. Tässä väitöskirjassa esitetään useita kryptografisten primitiivien lineaarisuuteen liittyviä kryptoanalyyttisia tuloksia. Työ sisältää tuloksia sekä primitiivien muodollisista kuvauksista että niiden todellisista toteutuksista. Edelliseen kryptoanalyysin alueeseen liittyen esitetään viitekehys vastustuskyvyn arvioimiseksi lineaarista kryptoanalyysia vastaan tilanteessa, jossa käytetään lineaarisia kuvauksia mielivaltaisissa äärellisissä Abelin ryhmissä. Sovelluksena esitetään lineaarisia erotteluhyökkäyksiä Shannon-jonosalausmenetelmää ja DEAN-lohkosalausmenetelmää vastaan. Sen lisäksi tutkitaan erillisiä salausteknisiä komponentteja ja esitetään niiden lineaarisuusominaisuuksia koskevia tuloksia erilaisissa määrittelyjoukoissa. Erityisesti esitetään tiettyjen diskreettiin logaritmiin perustuvien funktioiden epälineaarisuutta tukevia tuloksia. Kryptografisten toteutusten puolelta esitetään tekniikka sivukanavadatan automaattiseksi analysoimiseksi ja osoitetaan että se toimii käytännössä hyökkäyksessä OpenSSL-järjestelmän ECDSA-toteutusta vastaan. Tekniikka perustuu toteutuksen mallintamiseen lineaarisena dynaamisena järjestelmänä, joka mahdollistaa tilanteen tehokkaan analyysin.