Practical near-collisions on the compression function of BMW

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

Standard

Practical near-collisions on the compression function of BMW. / Leurent, Gaëtan; Thomsen, Søren Steffen.

Lecture Notes in Computer Science. ed. / Antoine Joux. Vol. 6733 Springer, 2011. p. 238-251.

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

Harvard

Leurent, G & Thomsen, SS 2011, 'Practical near-collisions on the compression function of BMW'. in A Joux (ed.), Lecture Notes in Computer Science. vol. 6733, Springer, pp. 238-251.

APA

Leurent, G., & Thomsen, S. S. (2011). Practical near-collisions on the compression function of BMW. In A. Joux (Ed.), Lecture Notes in Computer Science. (Vol. 6733, pp. 238-251). Springer.

CBE

Leurent G, Thomsen SS. 2011. Practical near-collisions on the compression function of BMW. Joux A, editor. In Lecture Notes in Computer Science. Springer. pp. 238-251.

MLA

Leurent, Gaëtan and Søren Steffen Thomsen "Practical near-collisions on the compression function of BMW". Joux, Antoine (editors). Lecture Notes in Computer Science. Springer. 2011. 238-251.

Vancouver

Leurent G, Thomsen SS. Practical near-collisions on the compression function of BMW. In Joux A, editor, Lecture Notes in Computer Science. Vol. 6733. Springer. 2011. p. 238-251.

Author

Leurent, Gaëtan; Thomsen, Søren Steffen / Practical near-collisions on the compression function of BMW.

Lecture Notes in Computer Science. ed. / Antoine Joux. Vol. 6733 Springer, 2011. p. 238-251.

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

Bibtex

@inbook{d68a6ee513bf4df9b4a6269c36506df6,
title = "Practical near-collisions on the compression function of BMW",
publisher = "Springer",
author = "Gaëtan Leurent and Thomsen, {Søren Steffen}",
year = "2011",
editor = "Antoine Joux",
volume = "6733",
pages = "238-251",
booktitle = "Lecture Notes in Computer Science",

}

RIS

TY - GEN

T1 - Practical near-collisions on the compression function of BMW

A1 - Leurent,Gaëtan

A1 - Thomsen,Søren Steffen

AU - Leurent,Gaëtan

AU - Thomsen,Søren Steffen

PB - Springer

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

VL - 6733

BT - Lecture Notes in Computer Science

T2 - Lecture Notes in Computer Science

A2 - Joux,Antoine

ED - Joux,Antoine

SP - 238

EP - 251

ER -