Paper 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å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.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- cryptanalysishash functions
- Contact author(s)
- ethan @ geographicslab org
- History
- 2009-09-01: received
- Short URL
- https://ia.cr/2009/415
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/415,
author = {Ethan Heilman},
title = {Attacks Against Permute-Transform-Xor Compression Functions and Spectral Hash},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/415},
year = {2009},
url = {https://eprint.iacr.org/2009/415}
}
