Results on Linear Models in Cryptography

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2013-03-08
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2013
Major/Subject
Mcode
Degree programme
Language
en
Pages
80 + app. 91
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 29/2013
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.
Description
Supervising professor
Nyberg, Kaisa, Prof., Aalto University, Finland
Thesis advisor
Nyberg, Kaisa, Prof., Aalto University, Finland
Keywords
cryptography, linear cryptanalysis, distinguishing attack, side-channel analysis, linearity, nonlinearity, kryptografia, lineaarinen kryptoanalyysi, erotteluhyökkäys, sivukanava-analyysi, lineaarisuus, epälineaarisuus
Other note
Parts
  • [Publication 1]: Risto M. Hakala and Atle Kivelä and Kaisa Nyberg. Estimating Resistance against Multidimensional Linear Attacks: An Application on DEAN. Accepted for publication in Inscrypt 2012, 17 Pages, December 2012.
  • [Publication 2]: Risto M. Hakala. An upper bound for the linearity of Exponential Welch Costas functions. Finite Fields and Their Applications, Volume 18, Issue 4, Pages 855–862, July 2012.
  • [Publication 3]: Risto M. Hakala and Kaisa Nyberg. On the Nonlinearity of Discrete Logarithm in F2n. In SETA 2012, Volume 6338 of Lecture Notes in Computer Science, Pages 333–345, September 2010.
  • [Publication 4]: Zahra Ahmadian and Javad Mohajeri and Mahmoud Salmasizadeh and Risto M. Hakala and Kaisa Nyberg. A practical distinguisher for the Shannon cipher. Journal of Systems and Software, Volume 83, Issue 4, Pages 543–547, April 2010.
  • [Publication 5]: Billy Bob Brumley and Risto M. Hakala. Cache-Timing Template Attacks. In ASIACRYPT 2009, Volume 5912 of Lecture Notes in Computer Science, Pages 667–684, December 2009.
  • [Publication 6]: Billy Bob Brumley and Risto M. Hakala and Kaisa Nyberg and Sampo Sovio. Consecutive S-box Lookups: A Timing Attack on SNOW 3G. In ICICS 2010, Volume 6476 of Lecture Notes in Computer Science, Pages 171–185, December 2010.
Citation