Paper 2010/043

Differential and invertibility properties of BLAKE (full version)

Jean-Philippe Aumasson, Jian Guo, Simon Knellwolf, Krystian Matusiewicz, and Willi Meier

Abstract

BLAKE is a hash function selected by NIST as one of the 14 second round candidates for the SHA-3 Competition. In this paper, we follow a bottom-up approach to exhibit properties of BLAKE and of its building blocks: based on differential properties of the internal function G, we show that a round of BLAKE is a permutation on the message space, and present an efficient inversion algorithm. For 1.5 rounds we present an algorithm that finds preimages faster than in previous attacks. Discovered properties lead us to describe large classes of impossible differentials for two rounds of BLAKE’s internal permutation, and particular impossible differentials for five and six rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear and rotation-free model, we describe near-collisions for four rounds of the compression function. Finally, we discuss the problem of establishing upper bounds on the probability of differential characteristics for BLAKE.

Note: Corrected near-collision attack, with revised complexity 2^56.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Full version of paper presented at FSE 2010.
Keywords
BLAKEcryptanalysishash functionsSHA-3
Contact author(s)
jeanphilippe aumasson @ gmail com
History
2010-05-06: revised
2010-01-29: received
See all versions
Short URL
https://ia.cr/2010/043
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/043,
      author = {Jean-Philippe Aumasson and Jian Guo and Simon Knellwolf and Krystian Matusiewicz and Willi Meier},
      title = {Differential and invertibility properties of BLAKE (full version)},
      howpublished = {Cryptology ePrint Archive, Paper 2010/043},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/043}},
      url = {https://eprint.iacr.org/2010/043}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.