An Analysis of the XSL Algorithm

-

Documents
20 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

An Analysis of the XSL Algorithm Carlos Cid?1 and Gaetan Leurent2 1 Information Security Group, Royal Holloway, University of London Egham, Surrey TW20 0EX, United Kingdom 2 Ecole Normale Superieure, Departement d'Informatique, 45 rue d'Ulm, Paris 75230 Cedex 05, France Abstract. The XSL “algorithm” is a method for solving systems of multivariate polynomial equations based on the linearization method. It was proposed in 2002 as a dedicated method for exploiting the structure of some types of block ciphers, for example the AES and Serpent. Since its proposal, the potential for algebraic attacks against the AES has been the source of much speculation. Although it has attracted a lot of atten- tion from the cryptographic community, currently very little is known about the effectiveness of the XSL algorithm. In this paper we present an analysis of the XSL algorithm, by giving a more concise description of the method and studying it from a more systematic point of view. We present strong evidence that, in its current form, the XSL algorithm does not provide an efficient method for solving the AES system of equations. Keywords: XSL algorithm, T? method, Linearization, AES. 1 Introduction In 2002 Courtois and Pieprzyk showed that recovering an AES encryption key was equivalent to solving a large system of multivariate quadratic equations over a small finite field [10, 11].

  • equations

  • compact xsl

  • equations when

  • encryption key

  • w13x12 w12x12

  • t? method

  • key schedule

  • xsl algorithm

  • monly applied techniques


Sujets

Informations

Publié par
Nombre de visites sur la page 25
Langue English
Signaler un problème
AnAnalysisoftheXSLAlgorithmCarlosCid?1andGae¨tanLeurent21InformationSecurityGroup,RoyalHolloway,UniversityofLondonEgham,SurreyTW200EX,UnitedKingdomcarlos.cid@rhul.ac.uk2E´coleNormaleSupe´rieure,De´partementd’Informatique,45rued’Ulm,Paris75230Cedex05,Francegaetan.leurent@ens.frAbstract.TheXSL“algorithm”isamethodforsolvingsystemsofmultivariatepolynomialequationsbasedonthelinearizationmethod.Itwasproposedin2002asadedicatedmethodforexploitingthestructureofsometypesofblockciphers,forexampletheAESandSerpent.Sinceitsproposal,thepotentialforalgebraicattacksagainsttheAEShasbeenthesourceofmuchspeculation.Althoughithasattractedalotofatten-tionfromthecryptographiccommunity,currentlyverylittleisknownabouttheeffectivenessoftheXSLalgorithm.InthispaperwepresentananalysisoftheXSLalgorithm,bygivingamoreconcisedescriptionofthemethodandstudyingitfromamoresystematicpointofview.Wepresentstrongevidencethat,initscurrentform,theXSLalgorithmdoesnotprovideanefficientmethodforsolvingtheAESsystemofequations.0Keywords:XSLalgorithm,Tmethod,Linearization,AES.1IntroductionIn2002CourtoisandPieprzykshowedthatrecoveringanAESencryptionkeywasequivalenttosolvingalargesystemofmultivariatequadraticequationsoverasmallfinitefield[10,11].Theyexploitedthefactthattheonlynon-linearcomponentofthecipher(theS-Box)isbasedontheinversemapoverthefi-nitefieldF28,andwereabletoobtainasetofmultivariatequadraticequationsthatcompletelydescribedtheS-Boxtransformation.Bycombiningallequationsthroughoutthecipher,theywereabletoexpressthefullencryptiontransforma-tionasalarge,sparseandoverdefinedsystemofmultivariatequadraticequationsoverF2(intotal8000equationswith1600variablesfortheAESwith128-bitkeys).TheproblemofsolvingsystemsofmultivariatequadraticequationsoverafinitefieldisknowntobeNP-complete,anditiswidelybelievedthatthecom-monlyappliedtechniques(suchasGro¨bnerBasisalgorithms)cannotgenerallybeusedforefficientlysolvingsystemswithmorethanahandfulofvariables.?ThisauthorwassupportedbyEPSRCGrantGR/S42637.
HoweverthesystemderivedfromtheAESisverystructured,andthehopeisthatadedicatedmethodcanexploitthisrichstructure.Withthatinmind,amethodcalledXSLwasproposedin[10,11],whichitwasclaimedcouldprovideanefficientwaytorecovertheencryptionkeyforcertaintypesofblockciphers.Accordingtotheestimatespresentedin[10],withtheXSLalgorithmonecouldmounta(atleasttheoretical)successfulattackagainsttheAESwith256-bit.syekAroundthesametime,MurphyandRobshaw[13]showedhowtoexpresstheAESencryptionasafarsimplersystemofequationsoverF28.Itwasnoticedthenthat,ifXSLworkedaspredicted,thissystemshouldbeeasiertosolvethantheoriginaloneoverF2,andintheorycouldprovideanefficientattackagainsttheAESwith128-bitkeys[13,14].SincetheintroductionoftheXSLalgorithm,thepotentialforalgebraicat-tacksagainstblockciphers(andinparticulartheAES)hasbeenthesourceofmuchspeculation.Althoughithasattractedalotofattentionfromthecrypto-graphiccommunity,currentlyverylittleisknownabouttheeffectivenessoftheXSLalgorithm,andofalgebraicattacksingeneral,againstblockciphers.InthispaperwepresentananalysisoftheXSLalgorithm.Basedonourresultsweconcludethat,aspresentedin[11],theXSLalgorithmshouldnotprovideanefficientmethodforsolvingtheAESsystemofequations.2LinearizationMethodsTheXSLalgorithmwasintroducedin[10,11],anditisderivedfromanearlieralgorithmcalledXL[8].TheXLalgorithmanditsmanyvariants[7,9,11]areallbasedonthemethodoflinearization,awell-knowntechniqueforsolvinglargesystemsofmultivariatepolynomialequations.Inthismethodweconsiderallmonomialsinthesystemasindependentvariablesandtrytosolveitusinglinearalgebratechniques.Notethatthelinearizationmethodcanonlybesuccessfulifthenumberoflinearlyindependentequationsisapproximatelythesameasthenumberofmonomialsinthesystem.TheXLalgorithmanditsvariantsattempttogenerateenoughequationswhenthisisnotthecase.TheXLisasimplealgorithm:ifweconsiderasystemofmquadraticequa-tionsandnvariablesoverafinitefieldK,f1(x1,...,xn)=0,...,fm(x1,...,xn)=0,(1)thealgorithmsimplymultipliestheoriginalequationsbyallmonomialsMiuptoaprescribeddegreeD2,andattemptstosolvethesystemofallresultingequationsMifj(x1,...,xn)=0(2)ofdegreeatmostDbylinearization.Althoughnotfullyunderstoodwhenfirstintroduced,currentlythereseemstobeamuchbetterunderstandingofthebehaviouroftheXLalgorithm,includingitsmeritsandlimitations[1–4,12].Inparticularithasbeenshownthatsomeof