The use of d-truncated Gröbner bases in cryptanalysis of symmetric ciphers
Master thesis
Permanent lenke
http://hdl.handle.net/11250/143930Utgivelsesdato
2010Metadata
Vis full innførselSamlinger
Sammendrag
ENGELSK: Solving systems of multivariate polynomial equations is hard, even NP-hard in the general case.
The method of Göbner bases can be used to solve such systems, and thus has a running time complexity
at least that of solving systems of polynomial equations. The running time complexity is
often expressed as exponential in D, where D is the largest degree of a polynomial during computation.
Even though the method of Gröbner bases belongs to the complexity class PSPACE
for zero-dimensional ideals, it still implies a need for huge amounts of computer memory. Computational
algebra systems utilizing Gröbner bases algorithms are well known to crash during
computation due to a lack of computer memory.
In this thesis we investigate the use of d-truncated Gröbner bases over a Boolean ring, applied
to systems of equations induced from symmetric ciphers. A Gröbner basis algorithm based
on Buchbergers Homogeneous Algorithm is implemented, and we apply this algorithm on systems
of equations induced from the ciphers LILI-128 and KASUMI. We show that we can solve a
system of equations, induced from 3 rounds KASUMI, in over 9000 unknowns using 3-truncated
Gröbner bases in both reasonable time and reasonable amounts of computer memory. For systems
of equations induced from LILI-128, using 4-truncated Gröbner bases, we experienced an
exponential increase in the number of output bits needed for finding a solution. NORSK: Å løse systemer av ikke-lineære polynomer i flere variable er et vanskelig problem, og det generelle
problemet tilhører klassen av NP-komplette problemer. Gröbner baser kan benyttes for å
løse slike ligningssystemer, og har dermed minst like høy tids kompleksitet. Tids kompleksiteten
for konstruksjon av Gröbner baser er ofte gitt som eksponentiell i D, der D er graden til det største
polynomet under eksekvering. Selv om konstruksjon av Gröbner baser tilhører kompleksitetsklassen
PSPACE for 0-dimensjonale ideal, betyr det allikevel at det vil være behov for store mengder
dataminne. Systemer for symbolsk beregning av algebraiske problemer som bruker Gröbner base
metoder er kjent for å krasje på grunn av minne problemer.
I dette prosjektet undersøker vi bruk av d-begrensede Gröbner baser over boolske ringer, og
anvender det på systemer av ikke-lineære polynomligninger som beskriver symmetriske krypto
algoritmer. En Gröbner base algoritme, basert på Buchbergers Homogene algoritme, er implementert
og vi anvender denne på systemer av ligninger fra krypto algoritmene LILI-128 og KASUMI.
Vi viser at det er mulig å løse ligningssystemer fra 3 runder KASUMI med over 9000
variable på overkommelig tid og overkommelig bruk av dataminne. For ligningssystemer fra
LILI-128, der 4-begrensede Gröbner baser er benyttet, fant vi en eksponentiell økning i antallet
ut bits som behøves for å løse ligningssystemene.