19 Pages
English

Message Freedom in MD4 and MD5 Collisions: Application to APOP

-

Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 15
Language English
MessageFreedominMD4andMD5Collisions:ApplicationtoAPOPGaëtanLeurentLaboratoired’Informatiquedel’ÉcoleNormaleSupérieure,Départementd’Informatique,45rued’Ulm,Paris75230Cedex05,Francegaetan.leurent@ens.frAbstract.InWang’sattack,messagemodificationsallowtodeterministicallysatisfycer-tainsufficientconditionstofindcollisionsefficiently.Unfortunately,messagemodificationssignificantlychangethemessagesandonehaslittlecontroloverthecollidingblocks.Inthispaper,weshowhowtochoosesomepartofthemessageswhichcollide.Consequently,webreakasecuritycountermeasureproposedbySzydloandYinatCT-RSA’06,wheretheyaddedafixedpaddingattheendofeachblock.Furthermore,wealsoapplythistechniquetopartiallyrecoverthepasswordsintheAu-thenticationProtocolofthePostOfficeProtocol(POP).Thisshowsthatcollisionattackscanbeusedtoattackrealprotocols,whichmeansthatfindingcollisionsisarealthreat.Keywords:Hashfunction,MD4,MD5,Wang,messagemodificationformeaningfulcol-lisions,APOPsecurity1IntroductionAtEUROCRYPT’05andCRYPTO’05,Wangetal.describedanewclassofattackonmostofthehashfunctionsoftheMD4family,MD4,MD5,HAVAL,RIPEMD,SHA-0andSHA-1in[20,22,23,21],whichallowstofindcollisionsforthesehashfunctionsveryefficiently.However,eventhoughfindingcollisionbreaksthesecurityofthesehashfunc-tions,itisnotclearwhathappensinpracticewhenhashfunctionsareusedinrealprotocols.Doesitmeanthatanyuseofhashfunctionisbroken?Theanswerisnotclear.OnedrawbackoneWang’sattackswhenusedagainstpracticalschemesisthatduetothemessagemodificationtechnique,theblockswhichcollidescannotbechosenandlookrandom.However,theseattacksworkswithanyIV,soonecanchooseacommonprefixforthetwocollidingmessages,andtheMerkle-Damgårdconstructionallowstoaddacommonsuffixtothecollidingmessages.Therefore,anattackercanchooseaprefixandasuffix,buthemustsomehowhidethecollidingblocks(1blockinMD4andSHA-0,and2blocksinMD5andSHA-1).ThishasbeenusedtocreatetwodifferentPostScriptfileswhosedigestsareequalbutresultingindifferenttextswhentheyarescreeningin[6]withthepoisonedmessageattack.Forthisapplication,thetwodifferenttextsareinbothPSfilesandthecollisionblocksareusedbyaif-then-elsetochoosewhichparttodisplay.Thisattackwasextendedtootherfileformatsin[8].LenstraanddeWegeralsoappliedasimilartechniquetocreatedifferentX.509certificatesforthesameDistinguishedNamebutwithdifferentsecureRSAmoduliin[12].Here,thecollidingblocksarehiddeninthesecondpartoftheRSAmoduli.