Improved Rebound Attack on the Finalist Grøstl

María Naya - Plasencia2

Description

Improved Rebound Attack on the Finalist Grøstl Jérémy Jean1,?,??, María Naya-Plasencia2,?, and Thomas Peyrin3,? ? ? 1 École Normale Supérieure, France 2 University of Versailles, France 3 Nanyang Technological University, Singapore Abstract. Grøstl is one of the five finalist hash functions of the SHA-3 competition. For entering this final phase, the designers have tweaked the submitted versions. This tweak renders inapplicable the best known distinguishers on the compression function presented by Peyrin [18] that exploited the internal permutation properties. Since the beginning of the final round, very few analysis have been published on Grøstl. Currently, the best known rebound-based results on the permutation and the compression function for the 256-bit version work up to 8 rounds, and up to 7 rounds for the 512-bit version. In this paper, we present new rebound distinguishers that work on a higher number of rounds for the permutations of both 256 and 512-bit versions of this finalist, that is 9 and 10 respectively. Our distinguishers make use of an algorithm that we propose for solving three fully active states in the middle of the differential characteristic, while the Super-Sbox technique only handles two. Keywords: Hash Function, Cryptanalysis, SHA-3, Grøstl, Rebound Attack. 1 Introduction Hash functions are one of the main families in symmetric cryptography.

• super-sbox technique


• internal state


• grøstl


• improved rebound


• using rebound-like


• function using


• like substitution-permutation


• bit version


• permutation

Sujets

• Target
• Agence nationale de la recherche
• Memory
• France 2
• Nanyang Technological University
• Grøstl

Informations

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

Extrait

ImprovedReboundAttackontheFinalist Grøstl JérémyJean 1,?,?? ,MaríaNaya-Plasencia 2,? ,andThomasPeyrin 3,??? 1 ÉcoleNormaleSupérieure,France 2 UniversityofVersailles,France 3 NanyangTechnologicalUniversity,Singapore Abstract. Grøstl isoneofthefivefinalisthashfunctionsofthe SHA-3 competition.Forentering thisfinalphase,thedesignershavetweakedthesubmittedversions.Thistweakrendersinapplicable thebestknowndistinguishersonthecompressionfunctionpresentedbyPeyrin[18]thatexploited theinternalpermutationproperties.Sincethebeginningofthefinalround,veryfewanalysishave beenpublishedon Grøstl .Currently,thebestknownrebound-basedresultsonthepermutation andthecompressionfunctionforthe256-bitversionworkupto8rounds,andupto7roundsfor the512-bitversion.Inthispaper,wepresentnewrebounddistinguishersthatworkonahigher numberofroundsforthepermutationsofboth256and512-bitversionsofthisfinalist,thatis9 and10respectively.Ourdistinguishersmakeuseofanalgorithmthatweproposeforsolvingthree fullyactivestatesinthemiddleofthedifferentialcharacteristic,whiletheSuper-Sboxtechnique onlyhandlestwo. Keywords: HashFunction,Cryptanalysis, SHA-3 , Grøstl ,ReboundAttack. 1Introduction Hashfunctionsareoneofthemainfamiliesinsymmetriccryptography.Theyarefunctionsthat, givenaninputofvariablelength,produceanoutputofafixedsize.Theyhavemanyimportant applications,likeintegritycheckofexecutables,authentication,digitalsignatures. Since2005,severalnewattacksonhashfunctionshaveappeared.Inparticular,thehashstan- dards MD5 and SHA-1 werecryptanalysedbyWangetal.[21,22].Duetotheresemblanceofthe standard SHA-2 with SHA-1 ,theconfidenceintheformerhasalsobeensomewhatundermined. ThisiswhytheAmericanNationalInstituteofStandardsandTechnology(NIST)decidedto launchin2008acompetitionforfindinganewhashstandard, SHA-3 .Thiscompetitionreceived 64hashfunctionsubmissionsandaccepted51toenterthefirstround.Now,threeyearsandtwo roundslater,only5hashfunctionsremaininthefinalphaseofthecompetition. Amongstthesefinalists,thereisonlyone AES -basedfunction,thoughmanywereproposed. Thishashfunctionis Grøstl [2],andisattheoriginoftheintroductionofanewcryptanalysis techniquethathasbeenwidelydeployed,improvedandappliedtoalargenumberof SHA-3 candidates,hashfunctionsandothertypesofconstructions.Thisnewtechnique,calledrebound attack,wasintroducedbyMendeletal.[11]andhasbecomeoneofthemostimportanttools usedtoanalyzethesecuritymarginofmany SHA-3 candidatesaswellastheirbuildingblocks. Asfor Grøstl itself,ithasbeenappliedandimprovedinseveraloccasions[3,12,13,15,18]. Grøstl isundoubtedlyoneofthe SHA-3 candidatesthathavereceivedthelargestamount ofcryptanalysis.Whenenteringthefinalround,atweakofthefunctionwasproposed,which preventstheapplicationoftheattacksfrom[18];wedenote Grøstl-0 theoriginalsubmissionof thealgorithmand Grøstl itstweakedversion.Apartfromthereboundresults,theothermain ?SupportedbytheFrenchAgenceNationaledelaRecherchethroughtheSAPHIR2projectunderContract ANR-08-VERS-014. ??SupportedbytheFrench DélégationGénéralepourl’Armement (DGA). ???TheauthorissupportedbytheLeeKuanYewPostdoctoralFellowship2011andtheSingaporeNational ResearchFoundationFellowship2012.