Practical Near Collisions on the Compression Function of BMW

Gaetan Leurent1

Description

Practical Near-Collisions on the Compression Function of BMW Gaëtan Leurent1 and Søren S. Thomsen2? 1 University of Luxembourg 2 Technical University of Denmark Abstract. Blue Midnight Wish (BMW) is one of the fastest SHA-3 can- didates in the second round of the competition. In this paper we study the compression function of BMW and we obtain practical partial col- lisions in the case of BMW-256: we show a pair of inputs so that 300 pre-specified bits of the outputs collide (out of 512 bits). Our attack re- quires about 232 evaluations of the compression function. The attack can also be considered as a near-collision attack: we give an input pair with only 122 active bits in the output, while generic algorithm would require 255 operations for the same result. A similar attack can be developed for BMW-512, which will gives message pairs with around 600 colliding bits for a cost of 264. This analysis does not affect the security of the iterated hash function, but it shows that the compression function is far from ideal. We also describe some tools for the analysis of systems of additions and rotations, which are used in our attack, and which can be useful for the analysis of other systems. 1 Introduction Blue Midnight Wish (BMW) is a candidate in the SHA-3 hash function com- petition [7] which made it to the second round of the competition, but was not selected as a

• compression function


• bit


• specified output


• obtain practical partial


• word length


• evaluations before finding


• such automaton

Sujets

• Thomsen
• Institute of technology
• Word (computing)

Informations

• Publié par: pefav
• Nombre de lectures: 19
• Langue: English

Extrait

PracticalNear-Collisions ontheCompressionFunctionofBMW GaëtanLeurent 1 andSørenS.Thomsen 2? 1 UniversityofLuxembourg [e-mail] 2 TechnicalUniversityofDenmark [e-mail] Abstract.BlueMidnightWish(BMW)isoneofthefastestSHA-3can- didatesinthesecondroundofthecompetition.Inthispaperwestudy thecompressionfunctionofBMWandweobtainpracticalpartialcol- lisionsinthecaseofBMW-256:weshowapairofinputssothat300 pre-specifiedbitsoftheoutputscollide(outof512bits).Ourattackre- quiresabout2 32 evaluationsofthecompressionfunction.Theattackcan alsobeconsideredasanear-collisionattack:wegiveaninputpairwith only122activebitsintheoutput,whilegenericalgorithmwouldrequire 2 55 operationsforthesameresult.Asimilarattackcanbedeveloped forBMW-512,whichwillgivesmessagepairswitharound600colliding bitsforacostof2 64 .Thisanalysisdoesnotaffectthesecurityofthe iteratedhashfunction,butitshowsthatthecompressionfunctionisfar fromideal. Wealsodescribesometoolsfortheanalysisofsystemsofadditionsand rotations,whichareusedinourattack,andwhichcanbeusefulforthe analysisofothersystems. 1Introduction BlueMidnightWish(BMW)isacandidateintheSHA-3hashfunctioncom- petition[7]whichmadeittothesecondroundofthecompetition,butwasnot selectedasafinalist.Itisoneofthefastestsecondroundcandidatesinsoftware, andbelongstotheARXfamily,usingonlyadditions,rotations,andxors. BMWisbuiltbyiteratingacompressionfunction,similarlytotheubiquitous Merkle-Damgårdparadigm[5,9].Moreprecisely,BMWusesachainingvalue twiceaslargeastheoutputofthehashfunction(thisisknownaswide-pipe,or Chop-MD),andusesafinaltransformationsimilartotheHMACconstruction. Thereareseveralsecurityproofsforthismodeofoperationandsimilarmodes[2– 4],whichessentiallyshowthatifthecompressionfunctionbehaveslikearandom function,thenthehashfunctionwillbehavelikearandomfunction(uptosome leveldeterminedbythewidthofthechainingvariable). Inthispaperweexplainhowtofindpartial-collisionsintheBMW-256com- pressionfunction.Thesametechniquecouldbeusedtofindpartial-collisionsin ? SupportedbyagrantfromtheVillumKannRasmussenFoundation. 1