builtx

HerdingHashFunctionsandtheNostradamusAttackJohnKelsey1andTadayoshiKohno21NationalInstituteofStandardsandTechnology,john.
kelsey@nist.
gov2CSEDepartment,UCSanDiego,tkohno@cs.
ucsd.
eduAbstract.
Inthispaper,wedevelopanewattackonDamgard-Merklehashfunctions,calledtheherdingattack,inwhichanattackerwhocanndmanycollisionsonthehashfunctionbybruteforcecanrstpro-videthehashofamessage,andlater"herd"anygivenstartingpartofamessagetothathashvaluebythechoiceofanappropriatesux.
Wefocusonapropertywhichhashfunctionsshouldhave–ChosenTar-getForcedPrex(CTFP)preimageresistance–andshowthedistinctionbetweenDamgard-Merkleconstructionhashesandrandomoracleswithrespecttothisproperty.
Wedescribeanumberofwaysthatviolationofthispropertycanbeusedinarguablypracticalattacksonreal-worldapplicationsofhashfunctions.
Animportantlessonfromtheseresultsisthathashfunctionssusceptibletocollision-ndingattacks,especiallybrute-forcecollision-ndingattacks,cannotingeneralbeusedtoproveknowledgeofasecretvalue.
1IntroductionCryptographichashfunctionsareusuallyassumedtohavethreeproperties:Col-lisionresistance,preimageresistance,andsecondpreimageresistance.
Andyetmanyadditionalproperties,relatedtotheaboveinunclearways,arealsore-quiredofhashfunctioninpracticalapplications.
Forexample,hashfunctionsaresometimesusedin"commitment"schemes,toprovepriorknowledgeofsomeinformation,priorityonaninvention,etc.
Whentheinformationtakesonmorethanasmallnumberofpossiblevalues,theredoesnotappeartobeanobviouswaytoextendacollisionndingattacktobreakthecommitmentscheme;there-fore,collisionresistancedoesnotseemtobenecessarytousethehashfunctioninthisway.
Thisappearsfortunateinlightofthemanyrecentattacksoncolli-sionresistanceofexistinghashfunctions[2,3,13,19,21–24]andthewidespreaduseofhashfunctionsshortenoughtofalltobrute-forcecollisionattacks[20].
Weshowthatthenaturalintuitionaboveisincorrect.
Namely,weuncover(whatwebelievetobe)subtlewaysofexploitingtheiterativepropertyofDamgard-Merkle[6,16]hashfunctionstoextendcertainclassesofcollision-ndingattacksagainstthecompressionfunctiontoattackcommitmentschemesandotherusesofhashfunctionthatdonotinitiallyappeartoberelatedtocollisionresistance.
1.
1Example:ProvingPriorKnowledgewithaHashFunctionConsiderthefollowingexample.
Onedayinearly2006,thefollowingadappearsintheNewYorkTimes:I,Nostradamus,herebyprovidetheMD5hashHofmanyimportantpredictionsaboutthefuture,includingmostimportantly,theclosingpricesofallstocksintheS&P500asofthelastbusinessdayof2006.
Afewweeksafterthecloseofbusinessin2006,Nostradamuspublishesamessage.
ItsrstfewblockscontainthepreciseclosingpricesoftheS&P500stocks.
Itthencontinueswithmanyramblingandvaguepronouncementsandprophecieswhichhaven'tcometrueyet.
ThewholemessagehashestoH.
ThemainquestionweaddressinthispaperiswhetherthisshouldbetakenasevidencethatNostradamusreallyknewtheclosingpricesoftheS&P500manymonthsinadvance.
MD5hasbeenthesubjectofcollisionattacks,andindeedissusceptibletobruteforcecollisionattacks,buttherearenoknownpreimageattacks.
Andyet,itseemsthatapreimageattackonMD5wouldbenecessarytoallowNostradamustorstcommittoahash,andthenproduceamessagewhichsopreciselydescribesthefutureafterthefact.
1.
2ChosenTargetForcedPrex(CTFP)PreimageResistanceTherstquestiontoaddresswhenconsideringthesituationoutlinedaboveistoaskexactlywhatpropertyofahashfunctionwouldhavetobeviolatedbyNostradamusinordertofalsely"prove"priorknowledgeoftheseclosingprices.
Thepropertyisnotdirectlyoneofthecommonlydiscussedpropertiesofhashfunctions(collisionresistance3,preimageresistance,andsecondpreimageresis-tance).
Instead,weneedanatypicalproperty,whichwewillcall"chosentargetforcedprex"(CTFP)preimageresistance4.
InordertofalselyprovehisknowledgeoftheclosingpricesoftheS&P500,Nostradamuswouldrsthavetochooseatargethashvalue,H.
HethenwouldhavetowaituntiltheclosingvaluesoftheS&P500stocksfor2006wereavail-able.
Finally,hewouldhavetondsomewaytoformamessagethatstartedwithadescriptionofthoseclosingvalues,P,andendedupwiththeoriginallycommitted-tohashH.
Followingthisexample,wecandeneCTFPpreimageresistanceasfollows:IntherstphaseofhisattackNostradamusperformssomeprecomputationandthenoutputsann-bithashvalueH;Hishis"chosentarget".
Thechallenger3Collisionresistancewouldprecludetheattack,butdoesnotappeartobenecessaryfortheattacktofail.
4WeareindebtedtoDanBrownforpointingoutaprevioususeofthesameidea:InoneofthreeindependentproofsofthesecurityofPinstov-Vanstonesignatures,thesamepropertywithadierentname,"targetvalueresistance,"wasused.
See[4],inwhichitwasconjecturedthatSHA1hadthisproperty;ourresultshowsthatitdoesnotifonecanndcollisionsstartingfromtwoarbitraryIVs.
thenselectssomeprexPandsuppliesittoNostradamus;Pisthe"forcedprex.
"InourinformalsecuritydenitionweplacenorestrictiononhowthechallengerpicksP,butforsimplicitywemayassumethatthechallengerpicksPuniformlyatrandomfromsomelargebutnitesetofstrings.
Inthesecondphaseofhisattack,NostradamuscomputesandoutputssomestringS.
Nos-tradamuscompromisestheCTFPpreimageresistanceofthehashfunctionifhash(PS)=H.
Ifwemodelthehashfunctionasarandomoracle[1],thenun-lessNostradamusisluckyandguessesPintherstphaseofhisattack,wewouldexpecthimtohavetotryO(2n)valuesforSinthesecondphasebeforendingonesuchthathash(PS)=H.
Consequently,itmightseemreasonabletoexpectthatNostradamuswouldhavetoperformO(2n)hashfunctioncomputationstocompromisetheCTFPpreimageresistanceofarealhashfunction.
(WhileonecouldconsideramoreformaldenitionofCTFPforhashfunctionfamilies,andconsidertherelationshipbetweenCTFP-resistanceandothersecuritygoals,wedonotdosoherebutinsteadfocusonourattacks.
)Asdescribedindetailbelow,theabilitytoviolatetheCTFPpreimagere-sistancepropertyallowsanattackertocarryoutanumberofsurprisingattacksonapplicationsofahashfunction.
Almostanyuseofahashfunctiontoproveknowledgeofsomeinformationcanbeattackedbysomeonewhocanviolatethisproperty.
Manyapplicationsofhashingforsignaturesorforngerprintingsomeinformationwhicharenotvulnerabletoattackbystraightforwardcollision-ndingtechniquesarebrokenbyanattackerwhocanviolateCTFPpreimageresistance.
Further,whentheCTFPdenitionisrelaxedsomewhat(forexample,byallowingNostradamussomepriorlimitedknowledgeorcontrolovertheformatofP,givinghimpriorknowledgeofthefull(large)setofpossiblePstringsthatmightbepresented,orallowinghimtouseanyofalargenumberofencodingsofPwiththesamemeaning),theattacksbecomestillcheaperandmorepractical.
1.
3HerdingAttacksThemajorresultofthispaperisasfollows:ForDamgard-Merkle[6,16]con-structionhashfunctions,CTFPpreimageresistancecanalwaysbeviolatedbyrepeatedapplicationofbrute-forcecollision-ndingattacks.
Moreecientcollision-ndingalgorithmsforthehashfunctionbeingattackedmaybeusedtomaketheattackmoreecient,ifthedetailsofthecollision-ndingalgorithmssupportthis.
Anattackthatviolatesthispropertyeectively"herds"agivenprextothedesiredhashvalue;wethuscallanysuchattackviolatingtheCTFPpreimageresistancepropertya"herdingattack.
"TheherdingattackshowsthattheCTFPpreimageresistanceofahashfunctionlikeMD5orSHA1isultimatelylimitedbythecollisionresistanceofthehashfunction.
Atahighlevel,andinitsbasicvariant,theattackisparameterizedbysomepositiveintegerk,e.
g.
,k=50,andbytheoutputsizenofthehashfunction.
Intherstphaseofaherdingattack,theattacker,Alice,repeatedlyappliesacollision-ndingattackagainstahashfunctiontobuildadiamondstructure,whichisadatastructurereminiscentofabinarytree.
Withhighprobabilityittakesatmost2k/2+n/2+2applicationsofthehashcompressionfunction(andpossiblyfewer,dependingondetailsofmoreecientcollision-ndingattacks5)tocreateadiamondstructurewith2k+12intermediatehashstates,ofwhich2kareusedinthebasicformoftheattack.
Inthesecondphaseoftheattack,AliceexhaustivelysearchesforastringSsuchthatPScollideswithoneofthediamondstructure'sintermediatestates;thissteprequirestryingO(2nk)possibilitiesforS.
HavingfoundsuchastringS,AlicecanconstructasequenceofmessageblocksQfromthediamondstructure,andthusbuildasuxS=SQsuchthathash(PS)=H;thissteprequiresanegligibleamountofwork,andtheresultingsuxSwillbek+1-blockslong.
WestressthatAlicecanhavesignicantcontroloverthecontentsofS,whichmeansthatSmaynotbe"randomlooking"butmayinsteadcontainstructureddatasuitablefortheapplicationthatAliceistryingtoattack.
Table1presentsomeparametersforaversionofourattack.
Table1.
HerdingwithShortSuxesoutputexamplediamondsuxlengthworksizewidth(k)(blocks)128MD54148287160SHA152592108192Tiger63702129256SHA25684922172512Whirlpool1691782343n(n5)/3k+lg(k)+12nk1.
4PracticalImpactOurtechniquesforcarryingoutherdingattackshavemuchincommonwiththelongmessagesecondpreimageattacksof[12].
However,thoseattacksrequiredimplausiblylongmessages,andsoprobablycouldneverbeappliedinpractice.
Bycontrast,ourherdingattacksrequirequiteshortsuxes,andappeartobepracticalinmanysituations.
Similarly,manyrecentcryptanalyticresultsonhashfunctions,suchas[22,23],requireverycarefulcontrolovertheformatofthemessagestobeattacked.
Thisisnotgenerallytrueofourherdingattacks,thoughmoreecientvariantsthatmakeuseofcryptanalyticresultsonthe5Thecollisionndingattacksneededforconstructingthediamondstructurearesome-whatdierentthanthoseinrecentresultsonMD5,SHA0,andSHA1[22,23].
Weareuncertainwhethertheseattackscanbeadaptedtotherequirementsofconstruct-ingthediamondstructure,thoughitseemsplausiblethatitmightwork.
ForthediamondstructureweneedcollisionsbetweentwomessagesstartingwithdierentIVs.
underlyinghashfunctionswillnaturallyhavetofollowthesamerestrictionsasthoseattacks.
Neartheendofthispaper,wedescribeanumberofwaysinwhichourherdingattacksandvariationsonthemcanbeexploited.
Indevelopingtheherdingattack,wealsodescribeanewmethodofbuildingmulticollisionsforDamgard-Merklehashfunctionswhichwebelievetobeofindependentinterest,andwhichmaybeusefulinmanyotherhashfunctionattacks.
1.
5RelatedWorkTheherdingattackiscloselyrelatedtothelongmessagesecondpreimageattacksin[8]and[12],andisultimatelybuiltuponthemulticollision-ndingtechniqueof[10].
OurtechniqueforherdingisrelatedtotheresultofLaiandMassey[14]showingameet-in-the-middlesecondpreimageattackwhenpseudopreimagescanbefoundcheaperthanexhaustivesearch;inourattack,insteadofndingpseudopreimages,weconstructamessagebyrepeatedcollisionsearches,andthendoameet-in-the-middletypeattacktondalargesetofpossiblesecondpreimagesonourownchosenmessage.
OurresultscomplementCoron,Dodis,Malinaud,andPuniya'swork[5],whichdoesnotpresentattacksliketheoneswepresent,butwhichshowsthatiterativehashfunctionslikeMD5andSHA1arenotrandomoracles,evenwhentheircompressionfunctionsare.
VariantsofourattacksworksagainstCoron,etal'sxesbutdonotviolatetheirprovablesecuritybounds.
Morebroadly,ourresultre-enforcesthelessonsthatmightsensiblybetakenfrom[7,10–12,15]onthemanywaysinwhichseeminglyimpracticalhashfunc-tioncollisionsmaybeappliedinpractice.
ThesecuritypropertiesofDamgard-Merklehashfunctionsagainstattackerswhocanndcollisionsarecurrentlynotwellunderstood.
2TheDiamondStructure:ABuildingBlockforHerdingInthissectionweintroducethediamondstructure.
Thisisastructureofmes-sagesconstructedtoproducealargemulticollisionofaquitedierentformatthanthatofJoux[10].
Ourmulticollisionismoreexpensive,andthesamelength.
Forexample,a2kdiamond-structuremulticollisioncostsabout2n/2+k/2+2work,relativetoJoux'k*2n/2work.
TherearetworeasonswhythediamondstructureletsanattackerdothingswhicharenotpossiblewithonlyaJouxmulticollision:1.
Thediamondstructureallows2kchoicesfortherstblockofa2kmulticol-lision,whereasJouxmulticollisionsinvolveasequenceofpairsofchoicesforeachpartofthemessage.
2.
Thediamondstructurecontains2k+12intermediatehashvalues,makingtheherdingattackpossiblewithshortsuxes.
AdiamondstructureisessentiallyaMerkletreebuiltbybruteforce.
Fig.
1.
TheBasicDiamondStructureFigure1describesthebasicidea,whereedgesrepresentmessagesandvalueslikeh[i,j]representintermediatehashstates.
Inthediagram,theattackerstartswitheightdierentrstmessageblocks,eachleadingtoadierenthashvalue;hethensearchesforcollisionsbetweenpairsofthesehashvalues,yieldingfourresultingintermediatehashvalues(atthecostofabout8*2n/2workusinganaivealgorithm).
Herepeatstheprocesswiththefourremainingvalues,thenthetworemainingones.
Theresultisadiamondstructurewhichis2kstateswide,andcontains2k+11statestotal.
ProducingaSuxfromanIntermediateHashValue.
Consideranyofthestartinghashvalues.
AsuxwhichmapsthathashvaluetothenalhashHisconstructedbywalkingdownthetreefromtheleavestotheroot,appendingthemessageblocksfromeachedgeinthetreetoproduceasux.
Consideranyintermediatehashvalue.
Similarly,walkingfromthatnodedowntotherootofthetreeyieldsasuxwhichmapstheintermediatehashvaluetothenalhashH.
Subsequentlywediscusshowtoaugmentthesuxifthehashfunctionincludesthelengthofthemessageinitslastblock.
BuildingtheStructure.
Buildingthestructureismoreecientthananaiveapproachsuggests.
Insteadofxingthepositionofeachnodewithinthetreeandthensearchingforcollisions,theattackerdynamicallybuildsthetreestructureduringthecollisionsearch.
Tomap2khashvaluesdownto2k1,shegeneratesabout2n/2+1/2k/2candidatemessageblocksfromeachstartinghashvalueinasinglelevelofthestructure,andthenndscollisionsbetweenthedierentstartingvaluesdynamically.
Thetotalworkdonetoreduce2khashvaluesto2k1isabout2n/2+k/2+1/2,andthustheworkdonetoconstructafulldiamondstructurewith2khashvaluesatitswidestpointisabout2n/2+k/2+2.
Theworkdonetobuildthediamondstructureisbasedonhowmanymes-sagesmustbetriedfromeachof2kstartingvalues,beforeeachhascollidedwithatleastoneothervalue.
Intuitively,wecanmakethefollowingargument,whichmatchesexperimentaldataforsmallparameters:Whenwetry2n/2+k/2+1/2messagesspreadoutfrom2kstartinghashvalues(lines),weget2n/2+k/2+1/2kmessagesperline,andthusbetweenanypairofthesestartinghashvalues,weexpectabout(2n/2+k/2+1/2k)2*2n=2n+k+12kn=2k+1collisions.
Wethusexpectabout2k+k+1=21=2otherhashvaluestocollidewithanygivenstartinghashvalue.
Ifthissearchisdoneonasingleprocessor,theneachtimeapairoflinescollide,nofurthersearchingisdonefromthoselines.
Theremaybecaseswheretwopairsoflinescollideonthesamehashvalue.
Thisveryslightlydecreasesthenumberofreachablehashvalues,buttheexpectednumberoftheseisextremelysmall.
Forexample,ina255diamondstructure,thereareabout256intermediatehasheswhicharetheresultsofthesecollisionsearches.
Fora160-bithash,wethusexpectroughly249suchcollisions,sowecanignoretheeectofthemonourresult.
Parallelizeability.
Itiseasytoadapttheparallelcollisionsearchalgorithmof[20]totheconstructionofadiamondstructure.
Theresultofeachiterationofthesearchalgorithmyieldsbothaseedforthenextmessageblocktotry,andalsoachoiceofwhichofthe2kstartingchainingvalueswillbeused.
EmployingCryptanalyticAttacks.
Theabovediscussionhasfocusedonbrute-forcesearchasawaytobuildthediamondstructure.
Analternativeistousesomecryptanalyticresultsonthehashfunction.
Whetherthiswillworkdependsondetailsofthecryptanalysis:1.
Acollision-ndingalgorithmwhichproducesapairofmessagesfromthesameinitialvalueisnotusefulinconstructingthediamondstructure.
Simi-larly,analgorithmthatcanndcollisionsonlyfrominitialchainingvalueswithasingledierenceisnotuseful.
2.
AnalgorithmwhichworksforanyknownIVdierencecanbedirectlyap-pliedtobuildthediamondstructure,thoughonemustxthepositionsofthenodeswithinthediamondstructureinadvance.
Iftheworktondacollisionpairis2w,thenthisalgorithmshouldbeusedtoreduce2klinesofhashvaluesto2k1linessolongasw+k1xtramessageblockateachlayerofthedia-mondstructure,andusingthistoforceselectedpairsoflinestoinitialvaluesfromwhichthecollision-searchalgorithmwillwork.
Theworknecessarytondonecollisionbetweenlinesisnow2p/2+1+2w.
Thisalgorithmshouldbeusedtoreduce2klinesto2k+1solongaslg(2p/2+1+2w)+k1xpandableMessages.
Usingthenotationfrom[12],an(a,b)-expandablemessageisasetofmessagesofvaryinglengths,betweenaandbinclusive,allofwhichyieldthesameintermediatehash.
Expandablemessagesmaybefoundfromanyinitialhashvalueusingthetechniquesfoundin[12],andmoreecientlyfoundforsomehashfunctions,includingMD5anSHA1,usingtechniquesfrom[8];inthelattercase,thecostisaroundtwicethatofabrute-forcecollisionndingattack.
Ifall2k+12intermediatehashvaluesfromthediamondstructureareusedinthelaterstepsofherding,thena(1,k+1)-expandablemessagemustbeproducedattheendofthediamondstructure,toensurethatthenalherdedmessageisalwaysaxedlength.
Thisisnecessarysinceweassumethatthelengthofthemessagewillbeincludedinthelastblock.
Ifonlythewidestlayerof2khashvaluesisused,noexpandablemessageisrequired.
PrecomputationofthePrex.
Ifthefullsetofprexesareknownandsmallenough,thediamondstructurecanbecomputedfromtheirresultingintermedi-atehashes.
Thisfollowsfromthefactthatthestartinghashvaluesarearbitrary.
ThisisdiscussedatmoredepthinSections3.
1and4.
Variant:TheElongatedDiamondStructure.
Usingideasfrom[12],longmessagesoeranaivewaytomounttheattack;thediamondstructureoersmuchshortersuxes.
However,theattackercanbuildadiamondstructurewithmanyintermediatehashesmorecheaplythanabove,ifsheiswillingtotolerateunreasonablylongmessages.
Thewidestlayerofthediamondstructureischosen,with2khashvalues.
Then,theattackercomputes2rmessageblocksforeachofthe2khashvalues,thusproducingatotalof2k+rreachableintermediatestates.
Hethenconstructsthecollisiontreeasdescribedabove.
Thetotalworkdonetobuilda2r-longelongateddiamondstructurewith2kvaluesatitswidestpointisabout2r+k+2k/2+n/2+2;thisstructurecontains2k+rintermediatehashvalues,andyieldssuxesofabout2r1messageblocksonaverage.
Ingeneral,forreasonablesuxlengths,theelongateddiamondstruc-turehasonlyasmalladvantageoverregulardiamondstructures.
Anelongateddiamondstructuremusthavean(r,2r+r)-expandablemessageappendedtoitsend,toensurethatthenalherdedmessagesarealwaysthesamelength,andsoalwayshavethesamenalhashvalue.
Itispossibletoparallelizemuchoftheproductionofanelongateddiamondstructure.
Ifthewidthis2khashvaluesatthebeginning,thentheconstructionofthestructurecanbeparallelizedupto2kways.
3HowtoHerdaHashFunctionTheherdingattackallowsanattackertocommittothehashofamessageshedoesn'tyetfullyknow,atthecostofalargecomputation.
Thisattackiscloselyrelatedtothelongmessagesecond-preimageattacksof[8,12]andthemulticollision-ndingtechniquesof[10].
Atahighlevel,theattackworksasfollows:1.
BuildtheDiamondStructure:Aliceproducesasearchstructurewhichcon-tainsmanyintermediatehashvalues.
Fromanyoftheseintermediatehashvalues,amessagecanbeproducedwhichwillleadtothesamenalhashH.
AlicemaycommittoHatthispoint.
2.
DeterminethePrex:Later,AlicegainsknowledgeofP.
3.
FindaLinkingMessage:Alicenowsearchesforasingle-blockwhich,ifap-pendedtoP,wouldyieldanintermediatehashvaluewhichappearsinhersearchstructure.
4.
ProducingtheMessage:Finally,AliceproducesasequenceofmessageblocksfromherstructuretolinkthisintermediatehashvaluebacktothepreviouslysentH.
Attheendofthisprocess,AlicehasrstcommittedtoahashH,thendecidedwhatmessageshewillprovidewhichhashestoHandwhichbeginswiththeprexP.
BuildingtheDiamondStructure.
ThisstepisdescribedinSection2.
FindingaLinkingMessage.
OnceadiamondstructureisconstructedanditshashHiscommittedto,theattackerlearnstheprexP.
Shemustthenndalinkingmessage–amessagewhichallowshertolinktheprexPintothediamondstructure.
SeeFigure2.
Whenthereare2kintermediatehashvaluesinthediamondstructure,theattackerexpectstotryabout2nktrialmessagesinordertondalinkingmessage.
Fig.
2.
FindingaLinkingMessageandProducingtheSuxThestartingchainingvaluesforthediamondstructurecanbechosenarbi-trarily.
Thismakesiteasytoparallelizethesearchforlinkingmessageswhenherdingaprexintotherst(widest)layerofthediamondstructure.
Forex-ample,thestartingchainingvaluesmaybechosentohavetheirlow64bitsallzeros[18];theneachprocessorsearchingforalinkingmessageneedonlycheckthelistofstartinghashvaluesaboutonceper264trials.
ProducingtheMessage.
OncealinkingmessagefromP,Mlink,isfound,thesuxisproducedasdescribedabove–basically,theattackerwalksupthetreefromthelinked-tohashvaluetotheroot,producinganothermessageblockoneachstep.
SeeFigure2.
Ifall2k+12intermediatehashvaluesfromthediamondstructureareusedwhenndingMlink,thenthepre-determinedex-pandablemessagemustbeappendedtotheendofthesux.
3.
1WorkDoneforHerdingAttacksAmaximallyshortsuxfortheherdingattackisfoundbyproducinga2khashvaluewidediamondstructure,andonlysearchingforlinkingmessagestotheoutermost(widest)levelofhashvaluesinthediamondstructure,sothatnoexpandablemessageisneeded.
Inthiscase,thelengthofthesuxisk+1messageblocks,andtheworkdonefortheherdingattackisapproximately2nk+2n/2+k/2+2.
(1)Searchingforlinkingmessagestoall2k+12intermediatehashesinthestructurerequiresaddinganadditionallg(k)+1messageblocksfora(lg(k),k+lg(k))-expandablemessage,anddecreasestheworkrequiredto2nk1+2n/2+k/2+2+k*2n/2+1,(2)thek*2n/2+1termarisingfromthesearchforanexpandablemessage[12].
Thecheapestherdingattackwithareasonablyshortsuxescanbedeter-minedbysettingtheworkdoneforconstructingthediamondstructureandndingthelinkingmessageequal.
Wethusgetadiamondstructureofwidth2k,suxlengthL,andtotalworkW,where:k=n53(3)L=lg(k)+k+1(4)W=2nk1+2n/2+k/2+2+k*2n/2+1≈2nk.
(5)Thus,usinga160-bithashfunction,thecheapestattackwithareasonablyshortsuxinvolvesadiamondstructurewithabout252messagesatitswidestpoint,producinga59-blocksux,andwithatotalworkfortheattackofabout2108compressionfunctioncalls.
SeeTable1foradditionalexamples.
WorkforHerdingAttackswiththeElongatedDiamondStructure.
Thecheapestherdingattackwithasuxofslightlymorethan2rblockscanbedeterminedbyonceagainsettingtheworkdoneforconstructingthediamondstructureandndingthelinkingmessageequal,solongask+rxlengthL,andtotalworkW,where:k=n2r33(6)L=lg(k+2r)+k+1+2r(7)W=2nkr+2n/2+k/2+2+k*2n/2+1+2k+r≈2nkr+1.
(8)Thus,witha160-bithashfunctionanda255blocksux(aboutaslongasisallowedforSHA1orRIPEMD-160),anattackerwouldendupdoingabout290worktotaltoherdanyprexintothepreviouslypublishedhashvalue.
WorkforHerdingfromPrecomputedPrexes.
Ifthesetofpossiblepre-xescontains2kpossiblemessages,thediamondstructurecanbebuiltfromtheresulting2kintermediatehashes.
Inthiscase,thereisnosearchforalink-ingmessage,andthetotalworkfortheattackisdoneinbuildingthediamondstructure.
3.
2MakingMessagesMeaningfulTheseattacksallinvolveproducingasuxtosomeforcedprex,whichforcesthecompletemessagetohaveaspecichashvalueH.
Inordertouseherdinginarealdeception,however,theattackerprobablycannotjustappendabunchofrandomblockstotheendofherpredictionsorothermessages.
Instead,sheneedstoproduceasuxwhichisatleastsomewhatmeaningfulorplausible.
Thereareanumberoftricksfordoingthis.
UsingYuval'sTrick.
UsingYuval'sclevertrick[25],theattackercanprepareabasiclongdocumentappropriatetoherintendeddeception,andproducemanyindependentvariationpointsinthedocument.
Thisallowstheuseofmeaningful-lookingmessagesformostcontexts.
Forexample,eachmessageblockinlayeriofthediamondstructurecouldbeavariationonthesametheme,usingaboutn/2possiblevariationpoints.
Inpractice,thislikelywillmakethesuxlonger,sinceitishardtoput80variationpointsina64-charactermessage.
However,thishasalmostnoeectontheherdingattack.
Iftheattackerneedstenmessageblocks(640characters)foreachcollision,hersuxeswillbetentimeslonger,butnohardertond.
Thealgorithmforndingthemworksthesameway.
Thecontentsofthesesuxesmustbeprettygeneral.
Thenaturalwaytohandlethisinmostapplicationsofherdingistowritesomecommontextdis-cussinghowtheresultsaresupposedtohavebeenobtained("Iconsultedmycrystalball,andspentmanyhoursporingoverthemanuscriptsoftheancientprophets.
.
.
.
").
Thesecanthenbevariedatmanydierentpoints,independently,toyieldmanypossiblebitstringsallhavingthesamemeaning.
CommittingtoMeaning,NotBits.
Formanyoftheattacksforwhichherdingisuseful,thegoalistofalselycommittosomeactualmeaning,notnecessarilysomespecicmessagestring.
Forexample,anattackertryingtoproveherabilitytopredictthestockmarketisnotreallyforcedtouseanyxedformatforthecontentsofherstockmarketpredictions,solongasanyonereadingthemwillunambiguouslybeabletotellwhethershegotherpredictionsright.
ThisprovidesagreatdealofextraexibilityfortheattackerinusingYuval'strick,andalsoinarrangingthedierentpartsofthemessagetobecommittedto,inordertomaximizeherconvenience.
4ExploitingPriorKnowledgeofthePrexSpaceAssuggestedinSections2and3.
1,theattackbecomesmuchmoreecientiftheprexcanbeprecomputed.
Infact,itisoftenpossibletoprecomputethemessagepiecemealinwaysthatleaveahugenumberofpossibleprexesavailable,withoutrequiringahugeamountofwork.
Justaswiththefullherdingattack,theprecomputedversionwouldnotbeusefulagainstarandomoracle–wemakeuseoftheiterativestructureofexistinghashfunctionstomaketheattackwork.
PrecomputingAllPossiblePrexes.
Intheherdingattack,theattackermayreasonablyexpecttoproduceadiamondstructurewith250ormorepossiblehashvalues.
Foragreatmanypossibleapplicationsoftheherdingattack,thismaybemorethanthepossiblenumberofprexmessages.
Theattackermaynowtakeadvantageofaninterestingfeatureofthediamondstructure:Thereisnorestrictiononthechoiceofstartinghashvaluesforthestructure.
Let2k,thewidthofthediamondstructure,bethenumberofpossibleprexmessagesthattheattackermayneedtoherdtoherxedhashvalue.
(Iftherearefewerprexmessages,theattackerappendsoneblocktoallthepossibleprexmessages,andvariesthatblocktoproduceasetofprexmessagesthatisexactlytherightsize.
)Shecomputestheintermediatehashafterprocessingeachprexmessage,andusestheseintermediatehashesasthestartinghashvaluesforthediamondstructure.
Theinitialworktoconstructthediamondstructureinthiswayisthesameasforthemoregeneralherdingattack.
However,theattackernowhastheabilitytoimmediatelyproduceamessagewhichstartswithanypossibleprexwiththedesiredhashvalue.
Thatis,sheneednotdoasecondexpensivecomputationtoherdtheprexsheisgiven.
Theattackerwhohasalargersetofpossibleprexesthanthisisnotlost;shemayprecomputethehashesofthemostlikely2kprexes.
Then,ifanyofthoseprexesispresentedtoher,shecanherditimmediately;otherwise,shemustdothelargecomputation,orsimplyallowherpredictionorotherdeceptiontofailwithsomeprobability.
UsingJouxMulticollisions.
Jouxmulticollisionsarenotsucientforthegeneralherdingattack.
However,whenthesetofpossiblemessagestobecom-mittedtoisoftherightformandcanbeprecomputed,Jouxmulticollisionscanbeusedtomountaweakerformoftheherdingattack.
Considerthecasewheretheattackerwishestocommittoasequenceof"yes"or"no"predictions,withoutknowingwhichshewillneedtoreveallater.
Anexampleofthiswouldbealistoffamouspeoplewhowillorwillnotmarryduringtheyear.
Intheprecomputationphaseoftheattack,theattackerdeterminesalistoffamouspeopleandtheorderinwhichshewillpredictwhethertheywillmarry.
FollowingtheJouxmulticollisiontechnique,sheproducesalistofabout2n/2variationsona"Yes,thispersonwillmarrythisyear"predictionandabout2n/2variationsona"No,thispersonwillnotmarrythisyear"prediction.
Eachpredictionisindependent;theattackerndsacollidingyes/nopredictionfortherstfamousperson,thenforthesecond,andsoon.
SeeFigure3.
Whennished,shepublishesherlistoffamouspeopleandthehashofherpredictionsforthefuture.
Attheendoftheyear,she"reveals"herpredictions,choosingforeachpairofcollidingblockstheonethatreectswhatdidhappenthatyear.
Fig.
3.
UsingJouxMulticollisionstoPredictWhoWillGetMarriedThisvariantoftheattackismuchcheaperthanthosebasedonthediamondstructure,butisalsomuchlessexible.
Itcanuseexistingcryptanalytictech-niquesonSHA1andMD5since,ateachstage,theattackerislookingfortwomessagesthatcollidestartingfromthesameIV;ofcourse,theuseofexistingcryptanalytictechniquesmightinuencethestructureoftheattacker'syes/nopredictions.
Precomputationsofenormoussetsofprexesbecomepossibleusingthistechnique.
Mostimportantly,itcanbecombinedwiththediamondstruc-tureandvariationsoftheJouxmulticollisiontoprovideevenmoreexibilitytotheattacker,aswediscussbelow.
CombiningPrecomputationsandJouxMulticollisions.
Insomecases,somelargepartoftheinformationtobecommittedtowilltcleanlyintotheJouxmulticollisionstructure,butotherpartswillnot.
Forexample,considerapredictionofthecourseandoutcomeofanationalelectionintheUnitedStates6.
Beforetheelectionisrun,theattackerproducesasetof32prexeswhichdescribethecourseoftheelectioninbroadterms,e.
g.
,"Smithwonadecisivevictory,""Jonesnarrowlycarriedthecriticalswingstatesandwon,"etc.
Afterthis,eachstate'soutcomeislisted,e.
g.
,"AlabamawentforSmith,AlaskawentforJones,.
.
.
.
"Therstpartofthemessageisaprecomputeddiamondstructure;thesecondpartisaJouxmulticollisionallowing250dierentoutcomes.
ApplyingtheJouxMulticollisionIdeatoDiamondStructures.
Anevenmorepowerfulwaytostructurethesepredictionsistoconcatenateprecomputeddiamondstructuresinakindofsuper-Jouxcollision.
Considertheabovedescription,butnowsupposewewantedtospecifyoneof32possibledescriptionsofhowtheelectionwentineachstate,e.
g.
,"InAlabama,Smithwonaresoundingvictory,"or"InMaryland,Jonesnarrowlywonafteraseriesofviciousattackads.
"Theattackercanstringtogether51diamondstructurestotal,onetodescribethewholeelection,oneforeachstate.
Thisallowstheattackerto"commit"toapredictionwith2255possiblevalues(requiring2127.
5+n/2+2workwithann-bithashfunctionusingastraightforwardprecomputeddiamondstructure),whiledoingmuchlesswork(51*22.
5+n/2+2).
TheattackeralsogainsenormousexibilitybybeingabletoavoidthestrictformatoftheJouxmulticollisions.
6TheonlydetailaboutUSpoliticsneededtounderstandthisexampleisthatallelectionsultimatelyproduceexactlyonevictor.
5ApplyingtheAttacks:HerdingforFunandProphetsInthissection,wedescribehowtheherdingattackcanbeusedinmanydierentcontextstodo(whatwebelievetobe)surprisingthings.
PredictingtheFuture:TheNostradamusAttack.
The"Nostradamusat-tack"istheuseofherdingtocommittothehashofamessagethattheattackerdoesn'tevenknow.
Thisdestroystheabilitytousehashes,forwhichcollisionscanbefound,toprovepriorknowledgeofanyinformation.
TheNostradamusattackiscarriedoutinordertoconvincepeoplethattheattackercantellthefuture.
Thiscouldbebasedonsomeclaimedpsychicpower,butalsoonsomeclaimedimprovedunderstandinginscienceoreconomics,al-lowingdetailedpredictionoftheweather,elections,markets,etc.
Thiscanalsobeusedto"prove"accesstosomeinsideinformation,aswithsomeattackerat-temptingtoconvinceareporterorintelligenceagentthatshehasinsideaccesstoaterroristcellorsecretivegovernmentagency.
Ataverygenerallevel,thisattackworksasfollows:1.
TheattackerpresentsthevictimwithahashH,alongwithaclaimaboutthekindofinformationthisrepresents.
Shepromisestoproducethemessagethatyieldsthehashaftertheeventspredictedhaveoccurred.
2.
Theattackerwaitsfortheeventstounfold,justasthevictimdoes.
3.
Theattackerherdsadescriptionoftheeventsastheydidunfoldintoherhashoutput,andprovidestheresultingmessagetothevictim,thus"proving"herpriorknowledge.
Therearemanyvariationsonthistheme;thepredictionscanbefullyprecom-puted,completelyunpredictableuntiltheycometopass,orsomemixofthetwo.
CommittingtoanOrdering.
ThetechniquesformanyofthevariantsoftheNostradamusattackfollowfromthediscussionsinSections3and4.
Herewesuggestanotherpossibility,whichuseswhatwecalla"hashrouter;"seeFigure4.
Alicedecidestoprove(perhapsinagamblingcontext)thatshecanpredicttheoutcomeofaracewith32entrants.
Shecommitstoasequenceof32hashoutputs,H0,1,.
.
.
,31.
Aftertheraceisover,sheproduces32strings,S0,1,.
.
.
,31suchthatSidescribestheentrantintheracewhonishedinithplace,andHi=hash(Si).
Alicebuildsaprecomputeddiamondstructurestartingfromthenamesofthe32entrants.
WhenthediamondstructureyieldsanalhashH,sheproduces32newmessagestrings(probablysimplystringslike"1stplace","2ndplace",etc.
),andprocessesthemfromHtoget32dierenthashoutputs.
Shecommitstothesehashoutputs.
Whenthetimecomestorevealherchoices,sheproduces32stringswhichcommithertothecorrectorderingofentrantsintherace.
NotethatAlicecanrouteanyofherstartingprecomputedprexestoanyofthehashoutputs.
RetroactiveCollisions.
Undernormalcircumstances,someonecreatingahashcollisionmustbroadlyknowtowhatheiscommitting.
WhilesomecleverattacksFig.
4.
CommittingtoanOrderingUsinga"HashRouter"havegottenaroundthisbyusingsomebitsofthetwocollidingmessagestochangethemeaningoflaterpartsofamessage[7,9],theseattacksareeasytodetectbylookingattheunderlyingdata.
Theherdingattackmaybeusedto"backdate"acollision.
Thatis,theat-tackersetsupacollisiontoday,andcommitstoitshashandperhapsonemessagewiththathash.
Later,shedecideswhatdocumentshewishescollidedwiththeoneshecommittedto,andsosheherdsthatdocumenttothesamehash.
Thepropertyofthehashfunctionbeingviolatedisidenticalasinthecaseof"prov-ing"priorknowledge,buttheapplicationsarequitedierent.
StealingCreditforInventions.
Theattackercanusethesameideatoclaimtobeabrilliantinventor,whileactuallystealingotherpeoples'work.
Hesubmitshashestoadigitaltimestampingserviceperiodically.
Afterheseessomenewinventionhewantstoclaim,heherdsadescriptionoftheinventiontosomeoldhashvalue.
Tosavetheattackerfrombuildingmultiplediamondstructures,theattackercouldconstructasinglediamondstructure,andappendasinglemessageblockwhichwouldvaryforeachsubmission.
TweakingaSignedDocument.
ConsiderthecasewhereAlicehasaveryreasonabledocumentwhichshehassigned,makingsomesensiblepredictionsaboutthefutureorstatementsoffactortermsofagreement.
Shewantstomakesureshecanlater"tweak"thisdocumentinsomeways.
Herdingwillpermitthis:1.
UsingtheprecomputedvariantwithJouxmulticollisions,shecanproducetwoalternativesforeachparagraphorsectionofthedocument.
2.
UsingtheprecomputeddiamondwithJouxmulticollisions,shecanproducemanyvariationsforsomesections,andpairsofvariationsforothers.
Shechoosesonetoproduceinitially,butcanchangetoanotherwithoutchangingthehash.
3.
Usingthefullherdingattack,shecanproduceone"herded"document.
Anyvariationinthe"prex"partofthedocumentshewishestomakelatercanbemadebycarryingoutanotherherdingattack.
Thisattackcanbeusedtotweakmessages,contracts,newsstories,signed/hashedsoftware,etc.
RandomNumberFixing.
AliceandBobwanttoagreeonasharedrandomsequenceforsomegame.
Alicesendshash(X1),thenBobrespondswithX2.
Fi-nally,AlicerevealsX1,andAliceandBobeachderiverandombitsbycombiningX1andX2insomeway.
TheherdingattacksanditsvariationscanbeusedtoallowAlicetoexertsubstantialcontrolovertheresultingrandombitsequence.
Ifthefullherdingattackisn'tpracticalinthisscenario,AlicecanatleastusetheJouxmulticollisionvarianttoallowherselftwochoicesperagreedrandomnumber,whereBobhasnochoice.
6FindingMultiblockFixedPointsAttacksoncommitmentschemesarenottheonlyapplicationsofthediamondstructureandherdingattackideas.
Wecanalsondshortcyclesinhashfunc-tions.
Thisisdoneinasimpleway:Werstconstructadiamondstructure,whereeachofthestartinghashvaluesinthestructurearefoundbygeneratingarandommessageblock,andcomputingthecompressionfunctionresultofthatmessageblockfromthehashfunction'sinitialvalue.
Ifthediamondstructureis2kwide,wethencompute2nktrialmessageblocksfromtheendofthedi-amondstructure.
Weexpectanintermediatecollision,whichyieldsak-blockxedpointforthehashalgorithm.
Thiscanbeextended;with2nk+rwork,weexpectabout2rdierentk-blockxedpoints,allreachablefromalegitimatemessage.
Thesecanbeconcatenatedtogether;wecanchoosewhichofthe2rk-blockchunksofmessagewewishtoappendtothemessagenext,withoutreferencetopreviouschoices.
Further,anymessagecanbe"herded"tothissetofxedpointswithabout2nkworkandkappendedblocks.
Forcompleteness,werecallthat[17]showhowtondsingle-blockxedpointsinDavies-Meyerconstructionsand[12]showhowtondsingle-blockxedpointsinSnefru.
7ConclusionsInthispaper,wehavedenedapropertyofahashfunction,ChosenTargetForcedPrex(CTFP)preimageresistance,whichisbothsurprisinglyimportantforreal-worldapplicationsofhashfunctions,andalsosurprisinglydependentoncollisionresistanceofthehashfunction.
WehavedescribedavariationontheJouxmulticollisiontechniqueforbuildingtree-likestructuresofmulticollisionscalled"diamondstructures,"andenumeratedanumberoftechniquesmadepos-siblebythesestructures.
Wehavedescribedanumberofarguablypracticalattackswhichusethesetechniques.
Ataverybasiclevel,webelievethatthemostimportantlessonthereadercantakefromthispaperisthatusingiteratedhashfunctionswhosecollisionresistancehasbeenviolatedisverydicult,evenwhentherelevantsecuritypropertydoesnotappeartodependoncollisionresistance.
Agreatdealofresearchremainstobedoneinthisarea.
Thediamondstruc-tureseemslikelytoustobeaboutasusefulindevelopingnewattacksastheJouxmulticollisionresult,andwehopetoseeothersbuildingontheworkinthispaperbyndingothersurprisingthingstodotoiteratedhashfunctionsusingherdingattacksandthediamondstructure.
Additionally,theremaybemanyothersurprisingwaysinwhichiteratedhashfunctionsbuiltontheDamgard-Merkleconstructionmaybeattackedwhentheattackercanndintermediatecollisions.
8AcknowledgmentsTheauthorswishtothankDanBrown,MorrisDworkin,NielsFerguson,HalFinney,StuartHaber,UlrichKuehn,BartPreneel,ChristianRechberger,BruceSchneier,themanyparticipantsoftheNISThashworkshop,andtheanony-mousrefereesforhelpfulcommentsanddiscussionsonthesubjectofthispaper.
T.
KohnowassupportedbyNSFCCR-0208842,NSFANR-0129617,andNSFCCR-0093337.
PartofthisresearchwasperformedwhileT.
KohnowasvisitingtheUniversityofCaliforniaatBerkeley.
References1.
M.
BellareandP.
Rogaway.
Randomoraclesarepractical:Aparadigmfordesigningecientprotocols.
InACMCCS93,pages62–73.
ACMPress,1993.
2.
E.
BihamandR.
Chen.
Near-collisionsofSHA-0.
InM.
Franklin,editor,CRYPTO2004,volume3152ofLNCS,pages290–305.
Springer-Verlag,Berlin,Germany,2004.
3.
E.
Biham,R.
Chen,A.
Joux,P.
Carribault,C.
Lemuet,andW.
Jalby.
CollisionsofSHA-0andReducedSHA-1.
InR.
Cramer,editor,EUROCRYPT2005,volume3494ofLNCS.
Springer-Verlag,Berlin,Germany,2005.
4.
D.
R.
BrownandD.
B.
Johnson.
Hashfunctionsbasedonblockciphers.
InD.
Naccache,editor,CT-RSA2001,volume2020ofLNCS.
Springer-Verlag,Berlin,Germany,2001.
5.
J.
-S.
Coron,Y.
Dodis,C.
Malinaud,andP.
Puniya.
Merkle-Damgardrevisited:Howtoconstructahashfunction.
InV.
Shoup,editor,CRYPTO2005,volume3621ofLNCS.
Springer-Verlag,Berlin,Germany,2005.
6.
I.
Damgard.
Adesignprincipleforhashfunctions.
InG.
Brassard,editor,CRYPTO'89,volume435ofLNCS,pages416–427.
Springer-Verlag,Berlin,Ger-many,1989.
7.
M.
DaumandS.
Lucks.
Attackinghashfunctionsbypoisonedmessages:ThestoryofAliceandherboss,2005.
http://www.
cits.
rub.
de/MD5Collisions.
8.
R.
D.
Dean.
FormalAspectsofMobileCodeSecurity.
PhDthesis,PrincetonUniversity,Jan.
1999.
9.
M.
Gebhardt,G.
Illies,andW.
Schindler.
Anoteonpracticalvalueofsinglehashcollisionsforspecialleformats.
NISTCryptographicHashWorkshop,2005.
Nopublishedproceedings,availableonlineathttp://www.
csrc.
nist.
gov/pki/HashWorkshop/2005/Oct31_Presentations/Illies_NIST_05.
pdf.
10.
A.
Joux.
Multicollisionsiniteratedhashfunctions.
Applicationtocascadedcon-structions.
InM.
Franklin,editor,CRYPTO2004,volume3152ofLNCS,pages306–316.
Springer-Verlag,Berlin,Germany,2004.
11.
D.
Kaminsky.
MD5tobeconsideredharmfulsomeday.
CryptologyePrintArchive,Report2004/357,2004.
http://eprint.
iacr.
org/.
12.
J.
KelseyandB.
Schneier.
Secondpreimagesonn-bithashfunctionsformuchlessthan2nwork.
InR.
Cramer,editor,EUROCRYPT2005,volume3494ofLNCS,pages474–490.
Springer-Verlag,Berlin,Germany,2005.
13.
V.
Klima.
FindingMD5collisionsonanotebookPCusingmulti-messagemod-ications.
CryptologyePrintArchive,Report2005/102,2005.
http://eprint.
iacr.
org/.
14.
X.
LaiandJ.
L.
Massey.
Hashfunctionsbasedonblockciphers.
InR.
A.
Rueppel,editor,EUROCRYPT'92,volume658ofLNCS.
Springer-Verlag,Berlin,Germany,1992.
15.
A.
Lenstra,X.
Wang,andB.
deWeger.
CollidingX.
509certicates.
CryptologyePrintArchive,Report2005/067,2005.
http://eprint.
iacr.
org/.
16.
R.
C.
Merkle.
OnewayhashfunctionsandDES.
InG.
Brassard,editor,CRYPTO'89,volume435ofLNCS,pages428–446.
Springer-Verlag,Berlin,Ger-many,1989.
17.
S.
Miyaguchi,K.
Ohta,andM.
Iwata.
Conrmationthatsomehashfunctionsarenotcollisionfree.
InI.
Damgard,editor,EUROCRYPT'90,volume473ofLNCS.
Springer-Verlag,Berlin,Germany,May1990.
18.
B.
Preneel,2005.
Personalcommunication.
19.
V.
RijmenandE.
Oswald.
UpdateonSHA-1.
InA.
Menezes,editor,CT-RSA2005,volume3376ofLNCS,pages58–71.
Springer-Verlag,Berlin,Germany,2005.
20.
P.
vanOorschotandM.
Wiener.
Parallelcollisionsearchwithcryptanalyticappli-cations.
JournalofCryptology,12(1):1–28,1999.
21.
X.
Wang,X.
Lai,D.
Feng,H.
Chen,andX.
Yu.
CryptanalysisofthehashfunctionsMD4andRIPEMD.
InR.
Cramer,editor,EUROCRYPT2005,volume3494ofLNCS.
Springer-Verlag,Berlin,Germany,2005.
22.
X.
Wang,Y.
L.
Yin,andH.
Yu.
FindingcollisionsinthefullSHA-1.
InV.
Shoup,editor,CRYPTO2005,volume3621ofLNCS.
Springer-Verlag,Berlin,Germany,2005.
23.
X.
WangandH.
Yu.
HowtobreakMD5andotherhashfunctions.
InR.
Cramer,editor,EUROCRYPT2005,volume3494ofLNCS,pages19–35.
Springer-Verlag,Berlin,Germany,2005.
24.
X.
Wang,H.
Yu,andY.
L.
Yin.
EcientcollisionsearchattacksonSHA-0.
InV.
Shoup,editor,CRYPTO2005,volume3621ofLNCS.
Springer-Verlag,Berlin,Germany,2005.
25.
G.
Yuval.
HowtoswindleRabin.
Cryptologia,3(3):187–189,1979.