Cryptology ePrint Archive: Report 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{\o}stl. Finally, the sophisticated technique of message compensation gets a simple explanation with bicliques.

Category / Keywords: Skein, SHA-3, hash function, collision attack, preimage attack, biclique, permutation, Gr{\o}stl

Publication Info: submitted

Date: received 15 Mar 2012, last revised 1 Jun 2012

Contact author: khovratovich at gmail com

Available formats: PDF | BibTeX Citation

Note: Description of the method completely revised.

Version: 20120601:173222 (All versions of this report)

Discussion forum: Show discussion | Start new discussion