Cryptology ePrint Archive: Report 2010/506

Quantum Preimage and Collision Attacks on CubeHash

Gaëtan Leurent

Abstract: In this paper we show a quantum preimage attack on CubeHash-512-normal with complexity 2^192 . This kind of attack is expected to cost 2^256 for a good 512-bit hash function, and we argue that this violates the expected security of CubeHash. The preimage attack can also be used as a collision attack, given that a generic quantum collision attack on a 512-bit hash function require 2^256 operations, as explained in the CubeHash submission document.

This attack only uses very simple techniques, most of which are borrowed from previous analysis of CubeHash: we just combine symmetry based attacks [1,8] with Grover's algorithm. However, it is arguably the first attack on a second-round SHA-3 candidate that is more efficient than the attacks considered by the designer.

Category / Keywords: secret-key cryptography / Hash functions, SHA-3, CubeHash

Date: received 3 Oct 2010, last revised 30 Nov 2010

Contact author: gaetan leurent at ens fr

Available formats: PDF | BibTeX Citation

Version: 20101130:173502 (All versions of this report)

Discussion forum: Show discussion | Start new discussion