How Risky is the Random Oracle Model

pages

English

Documents

Écrit par
Gaetan Leurent1

Publié par
profil-mupheg-2012

Lire un extrait

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

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

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

Publié par

profil-mupheg-2012

Nombre de lectures

Langue

English

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

Voir

Publié par

profil-mupheg-2012

Nombre de lectures

Langue

English

HowRiskyistheRandom-OracleModel?Gae¨tanLeurent1andPhongQ.Nguyen21DGAandENS,France.http://www.eleves.ens.fr/leurent/2INRIAandENS,France.http://www.di.ens.fr/~pnguyen/Abstract.RSA-FDHandmanyotherschemessecureintheRandom-OracleModel(ROM)requireahashfunctionwithoutputsizelargerthanstandardsizes.Weshowthattherandom-oracleinstantiationsproposedintheliteratureforsuchcasesareweakerthanarandomoracle,includingtheproposalsbyBellareandRogawayfrom1993and1996,andtheonesimplicitinIEEEP1363andPKCSstandards:forinstance,weobtainapracticalpreimageattackonBR93for1024-bitdigests(withcomplexitylessthan230).Next,westudythesecurityimpactofhashfunctiondefectsforROMsignatures.Asanextremecase,wenotethatanyhashcollisionwouldsuﬃcetodisclosethemasterkeyintheID-basedcryptosystembyBonehetal.fromFOCS’07,andthesecretkeyintheRabin-WilliamssignatureforwhichBernsteinprovedtightsecurityatEUROCRYPT’08.WealsoremarkthatcollisionscanbefoundasaprecomputationforanyinstantiationoftheROM,andthisviolatesthesecuritydeﬁnitionoftheschemeinthestandardmodel.Hence,thisgivesanexampleofanaturalschemethatisprovensecureintheROMbutthatininsecureforanyinstantiationbyasinglefunction.Interestingly,forbothoftheseschemes,aslightmodiﬁcationcanpreventtheseattacks,whilepreservingtheROMsecurityresult.WegiveevidencethatinthecaseofRSAandRabin/Rabin-Williams,anappropriatePSSpaddingismorerobustthanallotherpaddingsknown.1IntroductionTheRandom-OracleModel(ROM),inwhichhashfunctionsareviewedasran-domoracles,goesbacktoatleastFiatandShamir[17].PopularizedbyBellareandRogaway[1],ithasbeenthesubjectofmuchdebate.Ontheonehand,itiswidespreadinresearchpapersandstandards,becauseROMschemesareusuallymoreeﬃcient,theirsecurityproofscanbebasedonwell-studiedassumptions,andcansometimesbetight.Infact,manystandardizedpublic-keyschemesare,atbest,onlyprovensecureintheROM,e.g.RSA-OAEP[2]andRSA-PSS[3].Ontheotherhand,theROMisnotanassumption(onthehashfunction):thereisnorandom-oracledeﬁnitionwhichapublicfunctioncanhopetosatisfy.Asecurityproofinthestandardmodel(SM)preciselygivesassumptionswhicharesuﬃcienttoensuresecurityproperties.Bycontrast,aROMsecurityproofonlyshowsthatanattackwhichdoesnotbreaktheproofassumptionsmustexploitapropertynotsatisﬁedbytherandom-oraclesimulationofthesecurityproof.ThisallowedCanettietal.[10]tobuildsignatureandencryptionschemeswhichare

secureintheROM,butinsecureforany(eﬃcient)implementationoftherandomoracle,becausesuchimplementationscanbesimulatedbyaUniversalTuringmachine,andthereforebedistinguished[33]fromarandomoracle.However,theconstructions[10,33,20,4]showingthelimitationsoftheROMarearguably“un-natural”andsigniﬁcantlydiﬀerfromreal-worldconstructions.Still,oneshouldbecarefulwithidealizedsecuritymodels:likeallMerkle-Damga˚rd/Davies-Meyerhashfunctions,MD5wasprovablycollision-resistant[50,7](uptothebirthdaybound)intheidealciphermodel(withrespecttotheblockcipherunderlyingthecompressionfunction);yet,computingMD5collisionsonlycostsafewsecondsnow[43].ThisstressestheimportanceofstudyingtheactualsecurityofschemesprovenintheROM.Unfortunately,veryfewROMschemeshavealsobeenprovensecureintheSM[42,8];andforseveralcases,thereisevidencethatasecurityproofintheSMisunlikely[34,39,15,28].Recentbreakthroughsinthecryptanalysisofhashfunctions[48,47,45]haveshownthatstandardhashfunctionslikeMD5orSHA-1arefarfrombehavinglikerandomoracles.However,theimpactonthepublic-keyworldhasbeenlimitedsofar,withtheexceptionof[45],whichconstructstwocollidingX.509certiﬁcatesfordiﬀerentidentitiesandpublickeys,andhasrecentlybeenextendedin[43]toconstructarogueCAcertiﬁcate.Buttostudytheactualsecurity,oneneedstoknowhowtherandomora-clewillbeinstantiatedinpractice,shouldtheschemeeverbeused.Often,therandom-oracleoutputsizematchesthatofstandardhashfunctions(like160bitsforSHA-1)ortheupcomingSHA-3.Inthiscase,standardhashfunctionsaremostlikelytobeused,despitewell-knownpropertiesofMD-iteratedhashfunctions(suchasthederivationofh(m1||m2)fromh(m1)andm2)whichmakethemeasilydiﬀerentiablefromrandomoracles.ButRSA-FDH[3]andmanyotherROMschemes(suchas[24,12,13,27,6,19,9])actuallyrequirea“non-standard”hashfunction.First,theoutputmaynotbeauniformallydistributedbitstring:itcouldberesidueclasses,orellipticcurvepoints,etc.,fortunatelyitisknownhowtodealwithsuchsituationsgivenaninstantiationwitharbi-traryoutput{0,1}n.Butiftheoutputbit-lengthislargerthanstandardsizes(e.g.RSA-FDHwhichneedsatleast1024bits),itisunclearhowtheoraclewillbeinstantiated.Tothebestofourknowledge,theonlyproposalsofrandom-oracleinstantiationssupportingarbitraryoutbitbit-lengtharethefollowing:twohistoricalinstantiationsproposedbyBellareandRogawayintheirseminalpapers[1](ontheROM)and[3](onFDHandPSS),recentconstructionsbyCoronetal.inthefullversionof[14],andtheinstantiationsimplicitinPKCS#1v2.1[41]andIEEEP1363[23]standards.Itseemsthatnoneoftheseinstanti-ationshavebeenanalyzedintheliterature,except[14]intheindiﬀerentiabilityframeworkofMaureretal.[33].Thisalsoraisesthequestionoftheimpactofpotentialdefectsinrandom-oracleinstantiations.WhenanarticleprovidesaROMsecurityproof,itusuallydoesnotsayhowtoinstantiatetherandomoracle,neitherwhatmighthappenifthehashfunctiondoesnotbehavelikearandomoracle.AssumethatAliceimplementsaschemeROM-secureunderawell-knowncomputationalassump-

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

How Risky is the Random Oracle Model

YouScribe

Le catalogue

Le service

Les conditions