Message Freedom in MD4 and MD5 Collisions: Application to APOP

Gaëtan Leurent

Description

Niveau: Supérieur, Doctorat, Bac+8
Message Freedom in MD4 and MD5 Collisions: Application to APOP Gaëtan Leurent Laboratoire d'Informatique de l'École Normale Supérieure, Département d'Informatique, 45 rue d'Ulm, Paris 75230 Cedex 05, France Abstract. In Wang's attack, message modifications allow to deterministically satisfy cer- tain sufficient conditions to find collisions efficiently. Unfortunately, message modifications significantly change the messages and one has little control over the colliding blocks. In this paper, we show how to choose some part of the messages which collide. Consequently, we break a security countermeasure proposed by Szydlo and Yin at CT-RSA '06, where they added a fixed padding at the end of each block. Furthermore, we also apply this technique to partially recover the passwords in the Au- thentication Protocol of the Post Office Protocol (POP). This shows that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat. Key words: Hash function, MD4, MD5, Wang, message modification for meaningful col- lisions, APOP security 1 Introduction At EUROCRYPT'05 and CRYPTO'05, Wang et al. described a new class of attack on most of the hash functions of the MD4 family, MD4, MD5, HAVAL, RIPEMD, SHA-0 and SHA-1 in [20,22,23,21], which allows to find collisions for these hash functions very efficiently.

• collision


• o?ine hash


• efficient when


• full recovery


• his attack


• functions very


• functions


• block md4

Sujets

• Collision
• Function

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 15
• Langue: English

Extrait

MessageFreedominMD4andMD5Collisions: ApplicationtoAPOP GaëtanLeurent Laboratoired’Informatiquedel’ÉcoleNormaleSupérieure, Départementd’Informatique, 45rued’Ulm,Paris75230Cedex05,France [e-mail] Abstract. InWang’sattack, messagemodifications allowtodeterministicallysatisfycer- tainsufficientconditionstofindcollisionsefficiently.Unfortunately,messagemodifications significantlychangethemessagesandonehaslittlecontroloverthecollidingblocks.In thispaper,weshowhowtochoosesomepartofthemessageswhichcollide.Consequently, webreakasecuritycountermeasureproposedbySzydloandYinatCT-RSA’06,where theyaddedafixedpaddingattheendofeachblock. Furthermore,wealsoapplythistechniquetopartiallyrecoverthepasswordsintheAu- thenticationProtocolofthePostOfficeProtocol(POP).Thisshowsthatcollisionattacks canbeusedtoattackrealprotocols,whichmeansthatfindingcollisionsisarealthreat. Keywords: Hashfunction,MD4,MD5,Wang,messagemodificationformeaningfulcol- lisions,APOPsecurity 1Introduction AtEUROCRYPT’05andCRYPTO’05,Wang etal. describedanewclassofattackon mostofthehashfunctionsoftheMD4family,MD4,MD5,HAVAL,RIPEMD,SHA-0 andSHA-1in[20,22,23,21],whichallowstofindcollisionsforthesehashfunctionsvery efficiently.However,eventhoughfindingcollisionbreaksthesecurityofthesehashfunc- tions,itisnotclearwhathappensinpracticewhenhashfunctionsareusedinreal protocols.Doesitmeanthatanyuseofhashfunctionisbroken?Theanswerisnotclear. OnedrawbackoneWang’sattackswhenusedagainstpracticalschemesisthatdueto themessagemodificationtechnique,theblockswhichcollidescannotbechosenandlook random.However,theseattacksworkswithanyIV,soonecanchooseacommonprefix forthetwocollidingmessages,andtheMerkle-Damgårdconstructionallowstoadda commonsuffixtothecollidingmessages.Therefore,anattackercanchooseaprefixand asuffix,buthemustsomehowhidethecollidingblocks(1blockinMD4andSHA-0,and 2blocksinMD5andSHA-1).ThishasbeenusedtocreatetwodifferentPostScriptfiles whosedigestsareequalbutresultingindifferenttextswhentheyarescreeningin[6]with thepoisonedmessageattack.Forthisapplication,thetwodifferenttextsareinbothPS filesandthecollisionblocksareusedbya if-then-else tochoosewhichparttodisplay. Thisattackwasextendedtootherfileformatsin[8].LenstraanddeWegeralsoapplied asimilartechniquetocreatedifferentX.509certificatesforthesame DistinguishedName butwithdifferentsecureRSAmoduliin[12].Here,thecollidingblocksarehiddeninthe secondpartoftheRSAmoduli.