Paper 2011/620

Provable Security of BLAKE with Non-Ideal Compression Function

Elena Andreeva, Atul Luykx, and Bart Mennink

Abstract

We analyze the security of the SHA-3 finalist BLAKE. The BLAKE hash function follows the HAIFA design methodology, and as such it achieves optimal preimage, second preimage and collision resistance, and is indifferentiable from a random oracle up to approximately 2^{n/2} assuming the underlying compression function is ideal. In our work we show, however, that the compression function employed by BLAKE exhibits a non-random behavior and is in fact differentiable in only 2^{n/4} queries. Our attack on the indifferentiability of the BLAKE compression function seriously undermines the security strength of BLAKE not only with respect to its overall indifferentiability, but also its collision and (second) preimage security in the ideal model. Our next contribution is the restoration of the security results for BLAKE in the ideal model by refining the level of modularity and assuming that BLAKE's underlying block cipher is an ideal cipher. We prove that BLAKE is optimally collision, second preimage, and preimage secure (up to a constant). We go on to show that BLAKE is still indifferentiable from a random oracle up to the old bound of 2^{n/2} queries, albeit under a weaker assumption: the ideality of its block cipher.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
SHA-3BLAKEcollision resistance(second) preimage resistanceindifferentiability
Contact author(s)
bmennink @ esat kuleuven be
History
2011-11-21: received
Short URL
https://ia.cr/2011/620
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/620,
      author = {Elena Andreeva and Atul Luykx and Bart Mennink},
      title = {Provable Security of BLAKE with Non-Ideal Compression Function},
      howpublished = {Cryptology ePrint Archive, Paper 2011/620},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/620}},
      url = {https://eprint.iacr.org/2011/620}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.