An Analysis of the XSL Algorithm

Gaetan Leurent2

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

• Kingdom
• Information Security Group
• Équation
• Encryption
• Key schedule
• multiplication

Informations

• Publié par: pefav
• Nombre de lectures: 25
• Langue: English

Extrait

AnAnalysisoftheXSLAlgorithm CarlosCid ?1 andGae¨tanLeurent 2 1 InformationSecurityGroup, RoyalHolloway,UniversityofLondon Egham,SurreyTW200EX,UnitedKingdom [e-mail] 2 E ´ coleNormaleSupe´rieure, De´partementd’Informatique, 45rued’Ulm,Paris75230Cedex05,France [e-mail] Abstract.TheXSL“algorithm”isamethodforsolvingsystemsof multivariatepolynomialequationsbasedonthelinearizationmethod.It wasproposedin2002asadedicatedmethodforexploitingthestructure ofsometypesofblockciphers,forexampletheAESandSerpent.Since itsproposal,thepotentialforalgebraicattacksagainsttheAEShasbeen thesourceofmuchspeculation.Althoughithasattractedalotofatten- tionfromthecryptographiccommunity,currentlyverylittleisknown abouttheeffectivenessoftheXSLalgorithm.Inthispaperwepresent ananalysisoftheXSLalgorithm,bygivingamoreconcisedescription ofthemethodandstudyingitfromamoresystematicpointofview.We presentstrongevidencethat,initscurrentform,theXSLalgorithmdoes notprovideanefficientmethodforsolvingtheAESsystemofequations. 0 Keywords:XSLalgorithm,Tmethod,Linearization,AES. 1Introduction In2002CourtoisandPieprzykshowedthatrecoveringanAESencryptionkey wasequivalenttosolvingalargesystemofmultivariatequadraticequations overasmallfinitefield[10,11].Theyexploitedthefactthattheonlynon-linear componentofthecipher(theS-Box)isbasedontheinversemapoverthefi- nitefieldF 28 ,andwereabletoobtainasetofmultivariatequadraticequations thatcompletelydescribedtheS-Boxtransformation.Bycombiningallequations throughoutthecipher,theywereabletoexpressthefullencryptiontransforma- tionasalarge,sparseandoverdefinedsystemofmultivariatequadraticequations overF 2 (intotal8000equationswith1600variablesfortheAESwith128-bit keys). Theproblemofsolvingsystemsofmultivariatequadraticequationsovera finitefieldisknowntobeNP-complete,anditiswidelybelievedthatthecom- monlyappliedtechniques(suchasGro¨bnerBasisalgorithms)cannotgenerally beusedforefficientlysolvingsystemswithmorethanahandfulofvariables. ? ThisauthorwassupportedbyEPSRCGrantGR/S42637.

HoweverthesystemderivedfromtheAESisverystructured,andthehopeis thatadedicatedmethodcanexploitthisrichstructure.Withthatinmind,a methodcalledXSLwasproposedin[10,11],whichitwasclaimedcouldprovide anefficientwaytorecovertheencryptionkeyforcertaintypesofblockciphers. Accordingtotheestimatespresentedin[10],withtheXSLalgorithmonecould mounta(atleasttheoretical)successfulattackagainsttheAESwith256-bit .syek Aroundthesametime,MurphyandRobshaw[13]showedhowtoexpress theAESencryptionasafarsimplersystemofequationsoverF 2 8 .Itwasnoticed thenthat,ifXSLworkedaspredicted,thissystemshouldbeeasiertosolvethan theoriginaloneoverF 2 ,andintheorycouldprovideanefficientattackagainst theAESwith128-bitkeys[13,14]. SincetheintroductionoftheXSLalgorithm,thepotentialforalgebraicat- tacksagainstblockciphers(andinparticulartheAES)hasbeenthesourceof muchspeculation.Althoughithasattractedalotofattentionfromthecrypto- graphiccommunity,currentlyverylittleisknownabouttheeffectivenessofthe XSLalgorithm,andofalgebraicattacksingeneral,againstblockciphers. InthispaperwepresentananalysisoftheXSLalgorithm.Basedonour resultsweconcludethat,aspresentedin[11],theXSLalgorithmshouldnot provideanefficientmethodforsolvingtheAESsystemofequations. 2LinearizationMethods TheXSLalgorithmwasintroducedin[10,11],anditisderivedfromanearlier algorithmcalledXL[8].TheXLalgorithmanditsmanyvariants[7,9,11]areall basedonthemethodoflinearization,awell-knowntechniqueforsolvinglarge systemsofmultivariatepolynomialequations.Inthismethodweconsiderall monomialsinthesystemasindependentvariablesandtrytosolveitusinglinear algebratechniques.Notethatthelinearizationmethodcanonlybesuccessfulif thenumberoflinearlyindependentequationsisapproximatelythesameasthe numberofmonomialsinthesystem.TheXLalgorithmanditsvariantsattempt togenerateenoughequationswhenthisisnotthecase. TheXLisasimplealgorithm:ifweconsiderasystemofmquadraticequa- tionsandnvariablesoverafinitefieldK, f 1 (x 1 ,...,x n )=0,...,f m (x 1 ,...,x n )=0,(1) thealgorithmsimplymultipliestheoriginalequationsbyallmonomialsM i up toaprescribeddegreeD−2,andattemptstosolvethesystemofallresulting equations M i ∙f j (x 1 ,...,x n )=0(2) ofdegreeatmostDbylinearization. Althoughnotfullyunderstoodwhenfirstintroduced,currentlythereseemsto beamuchbetterunderstandingofthebehaviouroftheXLalgorithm,including itsmeritsandlimitations[1–4,12].Inparticularithasbeenshownthatsomeof