Difference between revisions of "Spectral Hash"

From The ECRYPT Hash Function Website
(→‎Cryptanalysis)
m (updated with eprint paper)
 
(8 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
* Author(s): Gokay Saldamlı, Cevahir Demirkıran, Megan Maguire, Carl Minden, Jacob Topper, Alex Troesch, Cody Walker, Çetin Kaya Koç
 
* Author(s): Gokay Saldamlı, Cevahir Demirkıran, Megan Maguire, Carl Minden, Jacob Topper, Alex Troesch, Cody Walker, Çetin Kaya Koç
 +
* Website: [http://www.cs.ucsb.edu/~koc/shash/index.html http://www.cs.ucsb.edu/~koc/shash/index.html]
 +
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Spectral_Hash.zip Spectral_Hash.zip]
  
−
* Website: [http://www.cs.ucsb.edu/~koc/shash/index.html http://www.cs.ucsb.edu/~koc/shash/index.html]
 
−
* Specification:
 
  
 
<bibtex>
 
<bibtex>
Line 15: Line 15:
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
−
Brandon Enright: Near and truncated collisions in Spectral Hash (shash-###). NIST mailing list 2008-11-15 [http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt  Local link]
+
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
|  Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference
 +
|-                                     
 +
|  | near-collision || hash || 224,512 || reference impl. || example || - || [http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt Enright]
 +
|-                  
 +
|  | truncated collision || hash || 512 || reference impl. || example || - || [http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt Enright]
 +
|-                   
 +
|  | collision || hash ||  || reference impl. || example || - || [http://ehash.iaik.tugraz.at/uploads/6/64/Spectralhash.txt Bjørstad]
 +
|-
 +
| style="background:red" |collision || hash || ||  || example || - || [http://eprint.iacr.org/2009/415.pdf Heilman]
 +
|-                                 
 +
|}                   
 +
 
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 
 +
 
 +
<bibtex>
 +
@misc{spectralhashE08,
 +
  author    = {Brandon Enright},
 +
  title    = {Near and truncated collisions for the Reference Implementation of Spectral Hash},
 +
  url = {http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt},
 +
  howpublished = {NIST mailing list (local link)},
 +
  year = {2008},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{StreamHashB08,
 +
  author    = {Tor E. Bjørstad},
 +
  title    = {Collision for the Reference Implementation of SpectralHash},
 +
  url = {http://ehash.iaik.tugraz.at/uploads/6/64/Spectralhash.txt},
 +
  howpublished = {NIST mailing list (local link)},
 +
  year = {2008},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{StreamHashH09,
 +
  author    = {Ethan Heilman},
 +
  title    = {Attacks Against Permute-Transform-Xor Compression Functions and Spectral Hash Spectral Hash Collisions},
 +
  url = {http://eprint.iacr.org/2009/415.pdf},
 +
  howpublished = {Cryptology ePrint Archive, Report 2009/415},
 +
  year = {2009},
 +
  note = {\url{http://eprint.iacr.org/}},
 +
  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.},
 +
}
 +
</bibtex>
 +
 
 +
 
 +
=== Archive ===
 +
 
 +
<bibtex>
 +
@misc{StreamHashH09,
 +
  author    = {Ethan Heilman},
 +
  title    = {Spectral Hash Collisions},
 +
  url = {http://ehash.iaik.tugraz.at/uploads/4/4b/Spectralhash_heilman.txt},
 +
  howpublished = {NIST mailing list (local link)},
 +
  year = {2009},
 +
}
 +
</bibtex>

Latest revision as of 14:10, 10 September 2009

1 The algorithm


Gokay Saldamlı, Cevahir Demirkıran, Megan Maguire, Carl Minden, Jacob Topper, Alex Troesch, Cody Walker, Çetin Kaya Koç - Spectral Hash

,2008
http://www.cs.ucsb.edu/~koc/shash/sHash.pdf
Bibtex
Author : Gokay Saldamlı, Cevahir Demirkıran, Megan Maguire, Carl Minden, Jacob Topper, Alex Troesch, Cody Walker, Çetin Kaya Koç
Title : Spectral Hash
In : -
Address :
Date : 2008


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
near-collision hash 224,512 reference impl. example - Enright
truncated collision hash 512 reference impl. example - Enright
collision hash reference impl. example - Bjørstad
collision hash example - Heilman

A description of this table is given here.


Brandon Enright - Near and truncated collisions for the Reference Implementation of Spectral Hash

,2008
http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt
Bibtex
Author : Brandon Enright
Title : Near and truncated collisions for the Reference Implementation of Spectral Hash
In : -
Address :
Date : 2008

Tor E. Bjørstad - Collision for the Reference Implementation of SpectralHash

,2008
http://ehash.iaik.tugraz.at/uploads/6/64/Spectralhash.txt
Bibtex
Author : Tor E. Bjørstad
Title : Collision for the Reference Implementation of SpectralHash
In : -
Address :
Date : 2008

Ethan Heilman - Attacks Against Permute-Transform-Xor Compression Functions and Spectral Hash Spectral Hash Collisions

,2009
http://eprint.iacr.org/2009/415.pdf
Bibtex
Author : Ethan Heilman
Title : Attacks Against Permute-Transform-Xor Compression Functions and Spectral Hash Spectral Hash Collisions
In : -
Address :
Date : 2009


2.1 Archive

Ethan Heilman - Spectral Hash Collisions

,2009
http://ehash.iaik.tugraz.at/uploads/4/4b/Spectralhash_heilman.txt
Bibtex
Author : Ethan Heilman
Title : Spectral Hash Collisions
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Spectral_Hash&oldid=3227"