Paper 2012/141

Bicliques for permutations: collision and preimage attacks in stronger settings

Dmitry Khovratovich

Abstract

We extend and improve biclique attacks, which were recently introduced for the cryptanalysis of block ciphers and hash functions. While previous attacks required a primitive to have a key or a message schedule, we show how to mount attacks on the primitives with these parameters fixed, i.e. on permutations. We introduce the concept of sliced bicliques, which is a translation of regular bicliques to the framework with permutations. The new framework allows to convert preimage attacks into collision attacks and derive the first collision attacks on the reduced SHA-3 finalist Skein in the hash function setting up to 11 rounds. We also demonstrate new preimage attacks on the reduced Skein and the output transformation of the reduced Grøstl. Finally, the sophisticated technique of message compensation gets a simple explanation with bicliques.

Note: Corrected complexity for the attack on Grostl

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2012
Keywords
SkeinSHA-3hash functioncollision attackpreimage attackbicliquepermutationGrøstl
Contact author(s)
khovratovich @ gmail com
History
2014-02-06: last of 2 revisions
2012-03-22: received
See all versions
Short URL
https://ia.cr/2012/141
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/141,
      author = {Dmitry Khovratovich},
      title = {Bicliques for permutations: collision and preimage attacks in stronger settings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/141},
      year = {2012},
      url = {https://eprint.iacr.org/2012/141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.