How Risky is the Random Oracle Model

Gaetan Leurent1

Description

Niveau: Supérieur, Master
How Risky is the Random-Oracle Model? Gaetan Leurent1 and Phong Q. Nguyen2 1 DGA and ENS, France. 2 INRIA and ENS, France. Abstract. RSA-FDH and many other schemes secure in the Random- Oracle Model (ROM) require a hash function with output size larger than standard sizes. We show that the random-oracle instantiations proposed in the literature for such cases are weaker than a random oracle, including the proposals by Bellare and Rogaway from 1993 and 1996, and the ones implicit in IEEE P1363 and PKCS standards: for instance, we obtain a practical preimage attack on BR93 for 1024-bit digests (with complexity less than 230). Next, we study the security impact of hash function defects for ROM signatures. As an extreme case, we note that any hash collision would suffice to disclose the master key in the ID-based cryptosystem by Boneh et al. from FOCS '07, and the secret key in the Rabin-Williams signature for which Bernstein proved tight security at EUROCRYPT '08. We also remark that collisions can be found as a precomputation for any instantiation of the ROM, and this violates the security definition of the scheme in the standard model. Hence, this gives an example of a natural scheme that is proven secure in the ROM but that in insecure for any instantiation by a single function.

• collision


• oracle


• hash functions


• hmac-md5


• security proof


• secret key


• random-oracle instantiations


• hash function defects


• output size


• md5

Sujets

• Oracle
• Narman
• Collision
• Hash function
• HMAC
• Provable security
• Key (cryptography)

Informations

• Publié par: profil-mupheg-2012
• Nombre de lectures: 23
• Langue: English

Extrait

HowRiskyistheRandom-OracleModel? Gae¨tanLeurent 1 andPhongQ.Nguyen 2 1 DGAandENS,France. http://www.eleves.ens.fr/leurent/ 2 INRIAandENS,France. http://www.di.ens.fr/~pnguyen/ Abstract.RSA-FDHandmanyotherschemessecureintheRandom- OracleModel(ROM)requireahashfunctionwithoutputsizelargerthan standardsizes.Weshowthattherandom-oracleinstantiationsproposed intheliteratureforsuchcasesareweakerthanarandomoracle,including theproposalsbyBellareandRogawayfrom1993and1996,andtheones implicitinIEEEP1363andPKCSstandards:forinstance,weobtaina practicalpreimageattackonBR93for1024-bitdigests(withcomplexity lessthan2 30 ).Next,westudythesecurityimpactofhashfunctiondefects forROMsignatures.Asanextremecase,wenotethatanyhashcollision wouldsufficetodisclosethemasterkeyintheID-basedcryptosystemby Bonehetal.fromFOCS’07,andthesecretkeyintheRabin-Williams signatureforwhichBernsteinprovedtightsecurityatEUROCRYPT’08. Wealsoremarkthatcollisionscanbefoundasaprecomputationforany instantiationoftheROM,andthisviolatesthesecuritydefinitionof theschemeinthestandardmodel.Hence,thisgivesanexampleofa naturalschemethatisprovensecureintheROMbutthatininsecure foranyinstantiationbyasinglefunction.Interestingly,forbothofthese schemes,aslightmodificationcanpreventtheseattacks,whilepreserving theROMsecurityresult.WegiveevidencethatinthecaseofRSAand Rabin/Rabin-Williams,anappropriatePSSpaddingismorerobustthan allotherpaddingsknown. 1Introduction TheRandom-OracleModel(ROM),inwhichhashfunctionsareviewedasran- domoracles,goesbacktoatleastFiatandShamir[17].PopularizedbyBellare andRogaway[1],ithasbeenthesubjectofmuchdebate.Ontheonehand,itis widespreadinresearchpapersandstandards,becauseROMschemesareusually moreefficient,theirsecurityproofscanbebasedonwell-studiedassumptions, andcansometimesbetight.Infact,manystandardizedpublic-keyschemesare, atbest,onlyprovensecureintheROM,e.g.RSA-OAEP[2]andRSA-PSS[3]. Ontheotherhand,theROMisnotanassumption(onthehashfunction): thereisnorandom-oracledefinitionwhichapublicfunctioncanhopetosatisfy.A securityproofinthestandardmodel(SM)preciselygivesassumptionswhichare sufficienttoensuresecurityproperties.Bycontrast,aROMsecurityproofonly showsthatanattackwhichdoesnotbreaktheproofassumptionsmustexploita propertynotsatisfiedbytherandom-oraclesimulationofthesecurityproof.This allowedCanettietal.[10]tobuildsignatureandencryptionschemeswhichare

secureintheROM,butinsecureforany(efficient)implementationoftherandom oracle,becausesuchimplementationscanbesimulatedbyaUniversalTuring machine,andthereforebedistinguished[33]fromarandomoracle.However,the constructions[10,33,20,4]showingthelimitationsoftheROMarearguably“un- natural”andsignificantlydifferfromreal-worldconstructions.Still,oneshould becarefulwithidealizedsecuritymodels:likeallMerkle-Damga˚rd/Davies-Meyer hashfunctions,MD5wasprovablycollision-resistant[50,7](uptothebirthday bound)intheidealciphermodel(withrespecttotheblockcipherunderlyingthe compressionfunction);yet,computingMD5collisionsonlycostsafewseconds now[43]. Thisstressestheimportanceofstudyingtheactualsecurityofschemesproven intheROM.Unfortunately,veryfewROMschemeshavealsobeenprovensecure intheSM[42,8];andforseveralcases,thereisevidencethatasecurityproof intheSMisunlikely[34,39,15,28].Recentbreakthroughsinthecryptanalysis ofhashfunctions[48,47,45]haveshownthatstandardhashfunctionslikeMD5 orSHA-1arefarfrombehavinglikerandomoracles.However,theimpacton thepublic-keyworldhasbeenlimitedsofar,withtheexceptionof[45],which constructstwocollidingX.509certificatesfordifferentidentitiesandpublickeys, andhasrecentlybeenextendedin[43]toconstructarogueCAcertificate. Buttostudytheactualsecurity,oneneedstoknowhowtherandomora- clewillbeinstantiatedinpractice,shouldtheschemeeverbeused.Often,the random-oracleoutputsizematchesthatofstandardhashfunctions(like160 bitsforSHA-1)ortheupcomingSHA-3.Inthiscase,standardhashfunctions aremostlikelytobeused,despitewell-knownpropertiesofMD-iteratedhash functions(suchasthederivationofh(m 1 || m 2 )fromh(m 1 )andm 2 )whichmake themeasilydifferentiablefromrandomoracles.ButRSA-FDH[3]andmany otherROMschemes(suchas[24,12,13,27,6,19,9])actuallyrequirea“non- standard”hashfunction.First,theoutputmaynotbeauniformallydistributed bitstring:itcouldberesidueclasses,orellipticcurvepoints,etc.,fortunately itisknownhowtodealwithsuchsituationsgivenaninstantiationwitharbi- traryoutput { 0,1 } n .Butiftheoutputbit-lengthislargerthanstandardsizes (e.g.RSA-FDHwhichneedsatleast1024bits),itisunclearhowtheoraclewill beinstantiated.Tothebestofourknowledge,theonlyproposalsofrandom- oracleinstantiationssupportingarbitraryoutbitbit-lengtharethefollowing: twohistoricalinstantiationsproposedbyBellareandRogawayintheirseminal papers[1](ontheROM)and[3](onFDHandPSS),recentconstructionsby Coronetal.inthefullversionof[14],andtheinstantiationsimplicitinPKCS#1 v2.1[41]andIEEEP1363[23]standards.Itseemsthatnoneoftheseinstanti- ationshavebeenanalyzedintheliterature,except[14]intheindifferentiability frameworkofMaureretal.[33]. Thisalsoraisesthequestionoftheimpactofpotentialdefectsinrandom- oracleinstantiations.WhenanarticleprovidesaROMsecurityproof,itusually doesnotsayhowtoinstantiatetherandomoracle,neitherwhatmighthappen ifthehashfunctiondoesnotbehavelikearandomoracle.AssumethatAlice implementsaschemeROM-secureunderawell-knowncomputationalassump-