Cryptology ePrint Archive: Report 2009/415

Attacks Against Permute-Transform-Xor Compression Functions and Spectral Hash

Ethan Heilman

Abstract: This paper presents an attack on the strong collision resistance of the Spectral Hash SHA-3 candidate. Spectral-Hash (shash) is a Merkle-Damg\r{a}rd based hash function, carefully designed to resist all known cryptographic attacks. To best of our knowledge, our attack is the only known attack against the shash algorithm. We exploit the fundamental structure of the algorithm, completely bypassing the hash function's formidable cryptographic protections. Our attack is presented in three stages. First, we define the family of functions which have the structure we wish to exploit. We call members of this family PTX functions. Next, we show that all PTX functions, including functions which use random oracles, are vulnerable to our collision attack. Finally, we reformulate the shash compression function showing that it is a PTX function and thus vulnerable. We present results on a practical implementation of our attack, generating collisions for shash in less than a second on a typical desktop computer.

Category / Keywords: cryptanalysis, hash functions,

Date: received 26 Aug 2009

Contact author: ethan at geographicslab org

Available format(s): PDF | BibTeX Citation

Version: 20090901:065431 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]