Difference between revisions of "Hamsi"

From The ECRYPT Hash Function Website
m (Cryptanalysis updated)
(Cryptanalysis updated)
Line 57: Line 57:
 
|- style="background:#efefef;"                   
 
|- style="background:#efefef;"                   
 
|  Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
|  Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 +
|-
 +
|    distinguisher || output transformation || 256 || 6 rounds || 2<sup>10</sup> || - || [http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf Boura,Canteaut]
 
|-
 
|-
 
| semi-free-start near-collisions || compression function || 256 || 2 rounds || example || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan]
 
| semi-free-start near-collisions || compression function || 256 || 2 rounds || example || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan]
 
|-
 
|-
 
|    observations || hash function || all || ||  ||  || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
 
|    observations || hash function || all || ||  ||  || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
 +
|-
 +
|    distinguisher || output transformation || 224, 256 || 6 rounds || 2<sup>124.3</sup> ||  || [http://131002.net/data/papers/AKKMOPS10.pdf Aumasson et al.]
 +
|-
 +
|    distinguisher || permutation || 224, 256 || 6 rounds || 2<sup>28</sup> ||  || [http://131002.net/data/papers/AKKMOPS10.pdf Aumasson et al.]
 +
|-
 +
|    free-start near-collision || compression function || 224, 256 || 3 rounds || 2<sup>26</sup> ||  || [http://131002.net/data/papers/AKKMOPS10.pdf Aumasson et al.]
 
|-
 
|-
 
|    non-randomness || compression function || 224, 256 || 5 rounds ||  ||  || [http://ehash.iaik.tugraz.at/uploads/d/db/Hamsi_nonrandomness.txt Aumasson]
 
|    non-randomness || compression function || 224, 256 || 5 rounds ||  ||  || [http://ehash.iaik.tugraz.at/uploads/d/db/Hamsi_nonrandomness.txt Aumasson]
 
|-
 
|-
−
|  near-collision || compression function || 224, 256 || 3 rounds || 2<sup>21</sup> ||  || [http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf Nikolic]
+
|  free-start near-collision || compression function || 224, 256 || 3 rounds || 2<sup>21</sup> ||  || [http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf Nikolic]
 
|-
 
|-
 
|  distinguisher || compression function || 224, 256 || 6 rounds || 2<sup>27</sup> ||  || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
 
|  distinguisher || compression function || 224, 256 || 6 rounds || 2<sup>27</sup> ||  || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
Line 70: Line 78:
 
|    distinguisher || compression function || 384, 512 || 12 rounds || 2<sup>729</sup> ||  || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
 
|    distinguisher || compression function || 384, 512 || 12 rounds || 2<sup>729</sup> ||  || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
 
|-
 
|-
−
|    near-collision || compression function || 224, 256 || 3 rounds || 2<sup>5</sup> ||  || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
+
|    free-start near-collision || compression function || 224, 256 || 3 rounds || 2<sup>5</sup> ||  || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
 
|-
 
|-
−
|    near-collision || compression function || 224, 256 || 4 rounds || 2<sup>32</sup> ||  || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
+
|    free-start near-collision || compression function || 224, 256 || 4 rounds || 2<sup>32</sup> ||  || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
 
|-
 
|-
−
|    near-collision || compression function || 224, 256 || 5 rounds || 2<sup>125</sup> ||  || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
+
|    free-start near-collision || compression function || 224, 256 || 5 rounds || 2<sup>125</sup> ||  || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
 
|-
 
|-
 
|    message-recovery || compression function || 224, 256 || 3 rounds || 2<sup>10.48</sup> ||  || [http://eprint.iacr.org/2010/057.pdf Calik,Turan]
 
|    message-recovery || compression function || 224, 256 || 3 rounds || 2<sup>10.48</sup> ||  || [http://eprint.iacr.org/2010/057.pdf Calik,Turan]
Line 82: Line 90:
 
|}
 
|}
  
 +
 +
<bibtex>
 +
@inproceedings{sacBC10,
 +
  author = {Christina Boura, Anne Canteau},
 +
  title = {Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256},
 +
  url = {http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf},
 +
  booktitle  = {SAC},
 +
  year      = {2010},
 +
  series    = {LNCS},
 +
  publisher  = {Springer},
 +
  note = {To appear}
 +
  abstract = {The zero-sum distinguishers introduced by Aumasson and Meier are investigated. First, the minimal size of a zero-sum is established. Then, we analyze the impacts of the linear and the nonlinear layers in an iterated permutation on the construction of zero-sum partitions. Finally, these techniques are applied to the Keccak-f permutation and to Hamsi-256. We exhibit several zero-sum partitions for 20 rounds (out of 24) of Keccak-f and some zero-sum partitions of size $2^{19}$ and $2^{10}$ for the finalization permutation in Hamsi-256.}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 117: Line 138:
 
   year      = {2010},
 
   year      = {2010},
 
}
 
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{acispAKKMOPS10,
 +
  author = {Jean-Philippe Aumasson, Emilia Käsper, Lars Ramkilde Knudsen, Krystian Matusiewicz, Rune Ødegaard, Thomas Peyrin, Martin Schläffer},
 +
  title = {Distinguishers for the compression function and output transformation of Hamsi-256},
 +
  url = {http://131002.net/data/papers/AKKMOPS10.pdf},
 +
  booktitle  = {ACISP},
 +
  year      = {2010},
 +
  series    = {LNCS},
 +
  publisher  = {Springer},
 +
  pages      = {87-103},
 +
  volume    = {6168},
 +
  abstract = {Hamsi is one of 14 remaining candidates in NIST’s Hash Competition for the future hash standard SHA-3. Until now, little analysis has been published on its resistance to differential cryptanalysis, the main technique used to attack hash functions. We present a study of Hamsi’s resistance to differential and higher-order differential cryptanalysis, with focus on the 256-bit version of Hamsi. Our main results are efficient distinguishers and near-collisions for its full (3-round) compression function, and distinguishers for its full (6-round) finalization function, indicating that Hamsi’s building blocks do not behave ideally.}
 
</bibtex>
 
</bibtex>
  

Revision as of 11:00, 7 December 2010

1 The algorithm


Özgül Küçük - The Hash Function Hamsi

,2009
http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf
Bibtex
Author : Özgül Küçük
Title : The Hash Function Hamsi
In : -
Address :
Date : 2009

Özgül Küçük - The Hash Function Hamsi

,2008
http://ehash.iaik.tugraz.at/uploads/9/95/Hamsi.pdf
Bibtex
Author : Özgül Küçük
Title : The Hash Function Hamsi
In : -
Address :
Date : 2008

2 Cryptanalysis

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given here.

Recommended security parameters: (3,6) P,Pf rounds (n=224,256); (6,12) P,Pf rounds (n=384,512).

2.1 Hash function

Here we list results on the actual hash function. The only allowed modification is to change the security parameter.

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
2nd-preimage hash function 256 (3,6) 2251.3 ? Fuhr


2.2 Building blocks

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
distinguisher output transformation 256 6 rounds 210 - Boura,Canteaut
semi-free-start near-collisions compression function 256 2 rounds example - Turan,Uyan
observations hash function all Gligoroski
distinguisher output transformation 224, 256 6 rounds 2124.3 Aumasson et al.
distinguisher permutation 224, 256 6 rounds 228 Aumasson et al.
free-start near-collision compression function 224, 256 3 rounds 226 Aumasson et al.
non-randomness compression function 224, 256 5 rounds Aumasson
free-start near-collision compression function 224, 256 3 rounds 221 Nikolic
distinguisher compression function 224, 256 6 rounds 227 Aumasson,Meier
distinguisher compression function 384, 512 12 rounds 2729 Aumasson,Meier
free-start near-collision compression function 224, 256 3 rounds 25 Wang,Wang,Jia,Wang
free-start near-collision compression function 224, 256 4 rounds 232 Wang,Wang,Jia,Wang
free-start near-collision compression function 224, 256 5 rounds 2125 Wang,Wang,Jia,Wang
message-recovery compression function 224, 256 3 rounds 210.48 Calik,Turan
pseudo-2nd-preimage hash function 256 (3,6) rounds 2254.25 Calik,Turan


Christina Boura, Anne Canteau - Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256

SAC ,2010
http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf
Bibtex
Author : Christina Boura, Anne Canteau
Title : Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256
In : SAC -
Address :
Date : 2010

Meltem Sönmez Turan, Erdener Uyan - Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH

,2010
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf
Bibtex
Author : Meltem Sönmez Turan, Erdener Uyan
Title : Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH
In : -
Address :
Date : 2010

Thomas Fuhr - Finding Second Preimages of Short Messages for Hamsi-256

,2010
http://dx.doi.org/10.1007/978-3-642-17373-8_2
Bibtex
Author : Thomas Fuhr
Title : Finding Second Preimages of Short Messages for Hamsi-256
In : -
Address :
Date : 2010

Danilo Gligoroski - Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains

,2010
http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf
Bibtex
Author : Danilo Gligoroski
Title : Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains
In : -
Address :
Date : 2010

Jean-Philippe Aumasson, Emilia Käsper, Lars Ramkilde Knudsen, Krystian Matusiewicz, Rune Ødegaard, Thomas Peyrin, Martin Schläffer - Distinguishers for the compression function and output transformation of Hamsi-256

ACISP 6168:87-103,2010
http://131002.net/data/papers/AKKMOPS10.pdf
Bibtex
Author : Jean-Philippe Aumasson, Emilia Käsper, Lars Ramkilde Knudsen, Krystian Matusiewicz, Rune Ødegaard, Thomas Peyrin, Martin Schläffer
Title : Distinguishers for the compression function and output transformation of Hamsi-256
In : ACISP -
Address :
Date : 2010

Jean-Philippe Aumasson - On the pseudorandomness of Hamsi

,2009
http://ehash.iaik.tugraz.at/uploads/d/db/Hamsi_nonrandomness.txt
Bibtex
Author : Jean-Philippe Aumasson
Title : On the pseudorandomness of Hamsi
In : -
Address :
Date : 2009

Ivica Nikolic - Near Collisions for the Compression Function of Hamsi-256

,2009
http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf
Bibtex
Author : Ivica Nikolic
Title : Near Collisions for the Compression Function of Hamsi-256
In : -
Address :
Date : 2009

Jean-Philippe Aumasson, Willi Meier - Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi

,2009
http://www.131002.net/data/papers/AM09.pdf
Bibtex
Author : Jean-Philippe Aumasson, Willi Meier
Title : Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi
In : -
Address :
Date : 2009

Meiqin Wang, Xiaoyun Wang, Keting Jia, Wei Wang - New Pseudo-Near-Collision Attack on Reduced-Round of Hamsi-256

,2009
http://eprint.iacr.org/2009/484.pdf
Bibtex
Author : Meiqin Wang, Xiaoyun Wang, Keting Jia, Wei Wang
Title : New Pseudo-Near-Collision Attack on Reduced-Round of Hamsi-256
In : -
Address :
Date : 2009

Cagdas Calik, Meltem Sonmez Turan - Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256

http://eprint.iacr.org/2010/057.pdf
Bibtex
Author : Cagdas Calik, Meltem Sonmez Turan
Title : Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256
In : -
Address :
Date :
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Hamsi&oldid=3648"