Marıa Naya Plasencia1 Andrea Rock2 Jean Philippe Aumasson3 Yann Laigle Chapuy1 Gaetan Leurent4 Willi Meier5
20 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Marıa Naya Plasencia1 Andrea Rock2 Jean Philippe Aumasson3 Yann Laigle Chapuy1 Gaetan Leurent4 Willi Meier5

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
20 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Doctorat, Bac+8
Cryptanalysis of ESSENCE? Marıa Naya-Plasencia1, Andrea Rock2,†, Jean-Philippe Aumasson3,‡, Yann Laigle-Chapuy1, Gaetan Leurent4, Willi Meier5,, and Thomas Peyrin6 1 INRIA project-team SECRET, France 2 Aalto University School of Science and Technology, Finland 3 Nagravision SA, Cheseaux, Switzerland 4 Ecole Normale Superieure, Paris, France 5 FHNW, Windisch, Switzerland 6 Ingenico, France Abstract. ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly paral- lelizable design. Previous analysis showed some non-randomness in the compression function which could not be extended to an attack on the hash function and ESSENCE remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanal- ysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a man- ually found differential characteristic and an advanced search algorithm, we obtain collision attacks on the full ESSENCE-256 and ESSENCE- 512, with respective complexities 267.4 and 2134.7. In addition, we show how to use these attacks to forge valid (message, MAC) pairs for HMAC- ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision. Keywords: cryptanalysis, hash functions, SHA-3 1 Introduction Since the results [1–4] on the two most deployed hash functions, MD5 and SHA- 1, recent years have seen a surge of research on cryptographic hashing.

  • k1 k0

  • k4 k3

  • k3 k2

  • output word

  • k6 k5

  • essence

  • full hash functions


Sujets

Informations

Publié par
Nombre de lectures 19
Langue English

Extrait

CryptanalysisofESSENCEMarı´aNaya-Plasencia1,AndreaRo¨ck2,,Jean-PhilippeAumasson3,,YannLaigle-Chapuy1,Gae¨tanLeurent4,WilliMeier5,§,andThomasPeyrin61INRIAproject-teamSECRET,France2AaltoUniversitySchoolofScienceandTechnology,Finland3NagravisionSA,Cheseaux,Switzerland4E´coleNormaleSupe´rieure,Paris,France5FHNW,Windisch,Switzerland6Ingenico,FranceAbstract.ESSENCEisahashfunctionsubmittedtotheNISTHashCompetitionthatstandsoutasahardware-friendlyandhighlyparal-lelizabledesign.Previousanalysisshowedsomenon-randomnessinthecompressionfunctionwhichcouldnotbeextendedtoanattackonthehashfunctionandESSENCEremainedunbroken.Preliminaryanalysisinitsdocumentationarguesthatitresistsstandarddifferentialcryptanal-ysis.Thispaperdisprovesthisclaim,showingthatadvancedtechniquescanbeusedtosignificantlyreducethecostofsuchattacks:usingaman-uallyfounddifferentialcharacteristicandanadvancedsearchalgorithm,weobtaincollisionattacksonthefullESSENCE-256andESSENCE-512,withrespectivecomplexities267.4and2134.7.Inaddition,weshowhowtousetheseattackstoforgevalid(message,MAC)pairsforHMAC-ESSENCE-256andHMAC-ESSENCE-512,essentiallyatthesamecostasacollision.Keywords:cryptanalysis,hashfunctions,SHA-31IntroductionSincetheresults[1–4]onthetwomostdeployedhashfunctions,MD5andSHA-1,recentyearshaveseenasurgeofresearchoncryptographichashing.TheconsequentlackofconfidenceinthecurrentNISTstandardSHA-2[5],stemmingfromitssimilaritywiththosealgorithms,motivatedNISTtolaunchtheNISTHashCompetition,apubliccompetitiontodevelopanewhashstandard,whichwillbecalledSHA-3andannouncedby2012[6,7].NISTreceived64submissions,ThisworkissupportedinpartbyEuropeanCommissionthroughtheICTpro-grammeundercontractICT-2007-216676ECRYPTIIandbytheFrenchAgenceNa-tionaledelaRechercheundercontractANR-06-SETI-013-RAPIDE.TheworkwasstartedduringmyPhDatINRIAproject-teamSECRET,France.WorkdonewhilethisauthorwaswithFHNW,Switzerland,andsupportedbytheSwissNationalScienceFoundationunderprojectno.113329.§SupportedbyGEBERTRU¨FSTIFTUNG,projectno.GRS-069/07.
accepted51asfirstroundcandidates,andinJuly2009,selected14secondroundcandidates[7,8].Thatcompetitioncatchestheattentionnotonlyfrommanyacademics,butalsofromindustry—withcandidatesfromIBM,Hitachi,Intel,Sony—andfromgovernmentalorganizations.ESSENCE[9,10]wasafirstroundcandidateintheNISTHashCompeti-tionthatlikemanyothershastwomaininstances,operatingon32-and64-bitwords,respectively:ESSENCE-256andESSENCE-512.Thesefunctionsprocessmessagesusingabinarytreestructure,anduseasimplecompressionalgorithmbasedontwononlinearfeedbackshiftregisters(NFSR’s).ThispaperpresentscollisionattacksonthefullhashfunctionsESSENCE-256andESSENCE-512.Attheheartofourattacksisasingledifferentialcharac-teristic,foundmanually.Ourmaintechnicalachievementisanoriginalmethodforsearchinginputsconformingtothischaracteristicatareducedcost.Supple-mentary,wedescribehowtousetheseattacksforforgingvalidmessage/MACpairsforHMAC-ESSENCE-256andHMAC-ESSENCE-512infarfewerthan2n/2trials.ThesefindingsshowthatESSENCEdoesnotsatisfythesecurityrequirementssetbyNISTforthefutureSHA-3.Inaparallelwork,Mouhaetal.[11]presentedresultsonreducedversionsofESSENCE,includingapseudo-collisionattackonESSENCE-512reducedto31steps.Theyexploitedadifferentialcharacteristicofadifferenttypethanours,andalsousedifferenttechniquestosearchforconforminginputs.Preprintsof[11]andofthepresentpaperwerepublishedsimultaneouslyinJune2009,andinJulyESSENCEwasnotselectedasasecondroundcandidatebyNIST.Therestofthepaperisorganizedasfollows:§2brieflyintroducesESSENCE;§3describesourmethodforsearchingcollisionsanditscomplexityanalysis;§4showshowtoattacktheHMACconstructionwheninstantiatedwithESSENCE,andfinally§5concludes.2BriefdescriptionofESSENCEWegiveabriefdescriptionoftheESSENCEhashfunctions,whichshouldbesufficienttounderstandourattacks.Acompletespecificationcanbefoundin[9,10].Henceforthstatementsof(non)linearityarewithrespecttothefieldGF(2)={0,1}anditsextensions.2.1StructureESSENCEprocessesamessagebyconstructingabalancedbinarytreeofboundeddepthwhoseleavescorrespondtocallstoacompressionfunctionwithmessagechunksasinput.Thesizeofthemessagechunksandtheheightofthetreearetunableparameters.Moreprecisely,eachleafcorrespondstoahashdonebyaMerkleDamga˚rd(MD)construction[12,13]andauniqueinitialvalueforeachleafthatdependsonseveralparametersofthehashfunction.Likewise,nodescorrespondtoacombinationbyaMDconstructionofthechildrenschaningvalueandauniqueIV.
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents