Practical near-collisions on the compression function of BMW

Gaëtan Leurent, Søren Steffen Thomsen

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    Blue Midnight Wish (BMW) is one of the fastest SHA-3 candidates in the second round of the competition. In this paper we study the compression function of BMW and we obtain practical partial collisions 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 requires 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.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science
    EditorsAntoine Joux
    Publication date2011
    Publication statusPublished - 2011
    Event18th International Workshop on Fast Software Encryption - Lyngby, Denmark
    Duration: 14 Feb 201116 Feb 2011


    Workshop18th International Workshop on Fast Software Encryption
    Internet address


    Dive into the research topics of 'Practical near-collisions on the compression function of BMW'. Together they form a unique fingerprint.

    Cite this