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

Original Publication (with minor differences): IACR-ASIACRYPT-2012

Date: received 15 Mar 2012, last revised 6 Feb 2014

Contact author: khovratovich at gmail com

Available format(s): PDF | BibTeX Citation

Note: Corrected complexity for the attack on Grostl

Version: 20140206:100631 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]