Difference between revisions of "Hamsi"
m |
Mschlaeffer (talk | contribs) m (Cryptanalysis updated) |
||
(21 intermediate revisions by 6 users not shown) | |||
Line 3: | Line 3: | ||
* Author(s): Özgül Kücük | * Author(s): Özgül Kücük | ||
* Website: [http://homes.esat.kuleuven.be/~okucuk/hamsi/ http://homes.esat.kuleuven.be/~okucuk/hamsi/] | * Website: [http://homes.esat.kuleuven.be/~okucuk/hamsi/ http://homes.esat.kuleuven.be/~okucuk/hamsi/] | ||
− | * NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/ | + | * NIST submission package: |
− | + | **round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Hamsi_Round2.zip Hamsi_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Hamsi.zip Hamsi.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/HamsiUpdate.zip HamsiUpdate.zip]) | |
+ | |||
+ | <bibtex> | ||
+ | @misc{sha3Kucuk09, | ||
+ | author = {Özgül Küçük}, | ||
+ | title = {The Hash Function Hamsi}, | ||
+ | url = {http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf}, | ||
+ | howpublished = {Submission to NIST (updated)}, | ||
+ | year = {2009}, | ||
+ | } | ||
+ | </bibtex> | ||
<bibtex> | <bibtex> | ||
@misc{sha3Kucuk08, | @misc{sha3Kucuk08, | ||
− | author = {Özgül | + | author = {Özgül Küçük}, |
title = {The Hash Function Hamsi}, | title = {The Hash Function Hamsi}, | ||
url = {http://ehash.iaik.tugraz.at/uploads/9/95/Hamsi.pdf}, | url = {http://ehash.iaik.tugraz.at/uploads/9/95/Hamsi.pdf}, | ||
Line 17: | Line 27: | ||
</bibtex> | </bibtex> | ||
+ | == 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 [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here]. | ||
+ | |||
+ | Recommended security parameters: '''(3,6)''' P,P<sub>f</sub> rounds (n=224,256); '''(6,12)''' P,P<sub>f</sub> rounds (n=384,512). | ||
+ | |||
+ | === Hash function === | ||
+ | |||
+ | Here we list results on the actual hash function. The only allowed modification is to change the security parameter. | ||
+ | |||
+ | {| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center" | ||
+ | |- style="background:#efefef;" | ||
+ | | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference | ||
+ | |- | ||
+ | | 2nd-preimage || hash function || 256 || (3,6) || 2<sup>247</sup> || ? || [http://eprint.iacr.org/2010/602.pdf Dinur,Shamir] | ||
+ | |- | ||
+ | | 2nd-preimage || hash function || 256 || (3,6) || 2<sup>251.3</sup> || ? || [http://dx.doi.org/10.1007/978-3-642-17373-8_2 Fuhr] | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | |||
+ | === 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). | |
− | {| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center" | + | {| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center" |
|- 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] | ||
+ | |- | ||
+ | | 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] | ||
|- | |- | ||
− | | | + | | 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 || 384, 512 || 12 rounds || 2<sup>729</sup> || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier] |
|- | |- | ||
− | | | + | | 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] |
|- | |- | ||
− | | | + | | 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] |
|- | |- | ||
− | | | + | | 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] | ||
+ | |- | ||
+ | | pseudo-2nd-preimage || hash function || 256 || (3,6) rounds || 2<sup>254.25</sup> || || [http://eprint.iacr.org/2010/057.pdf Calik,Turan] | ||
|- | |- | ||
|} | |} | ||
− | |||
+ | <bibtex> | ||
+ | @misc{hamsiDS10, | ||
+ | author = {Itai Dinur and Adi Shamir}, | ||
+ | title = {An Improved Algebraic Attack on Hamsi-256}, | ||
+ | howpublished = {Cryptology ePrint Archive, Report 2010/602}, | ||
+ | year = {2010}, | ||
+ | note = {\url{http://eprint.iacr.org/}}, | ||
+ | url = {http://eprint.iacr.org/2010/602.pdf}, | ||
+ | abstract = {Hamsi is one of the $14$ second-stage candidates in NIST's SHA-3 competition. The only previous attack on this hash function was a very marginal attack on its 256-bit version published by Thomas Fuhr at Asiacrypt $2010$, which is better than generic attacks only for very short messages of fewer than $100$ 32-bit blocks, and is only $26$ times faster than a straightforward exhaustive search attack. In this paper we describe a different algebraic attack which is less marginal: It is better than the best known generic attack for all practical message sizes (up to $4$ gigabytes), and it outperforms exhaustive search by a factor of at least $512$ for all messages with at least $40$ blocks. The attack is based on the observation that in order to discard a possible second preimage, it suffices to show that one of its hashed output bits is wrong. Since the output bits of the compression function of Hamsi-256 can be described by low degree polynomials, it is actually faster to compute a small number of output bits by a fast polynomial evaluation technique rather than via the official algorithm.}, | ||
+ | } | ||
+ | </bibtex> | ||
+ | |||
+ | <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> | ||
+ | @misc{blakeTU10, | ||
+ | author = {Meltem Sönmez Turan, Erdener Uyan}, | ||
+ | title = {Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH}, | ||
+ | howpublished = {Second SHA-3 Candidate Conference}, | ||
+ | year = {2010}, | ||
+ | url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf}, | ||
+ | abstract = {A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. We also observed practical collisions and near-collisions for reduced versions of F-256 function used in Fugue.} | ||
+ | } | ||
+ | </bibtex> | ||
+ | |||
+ | <bibtex> | ||
+ | @misc{Fuhr-asiacrypt10, | ||
+ | author = {Thomas Fuhr}, | ||
+ | title = {Finding Second Preimages of Short Messages for Hamsi-256}, | ||
+ | url = {http://dx.doi.org/10.1007/978-3-642-17373-8_2}, | ||
+ | howpublished = {In Advances in Cryptology - ASIACRYPT 2010, Proceedings}, | ||
+ | editor = {Masayuki Abe}, | ||
+ | year = {2010}, | ||
+ | pages = {20-37}, | ||
+ | publisher = {Springer}, | ||
+ | series = {Lecture Notes in Computer Science}, | ||
+ | volume = {6477} | ||
+ | } | ||
+ | </bibtex> | ||
+ | |||
+ | <bibtex> | ||
+ | @misc{hamsiGli10, | ||
+ | author = {Danilo Gligoroski}, | ||
+ | title = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains}, | ||
+ | url = {http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf}, | ||
+ | howpublished = {NIST mailing list}, | ||
+ | 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> | <bibtex> | ||
Line 83: | Line 208: | ||
url = {http://eprint.iacr.org/2009/484.pdf}, | url = {http://eprint.iacr.org/2009/484.pdf}, | ||
abstract = {Hamsi-256 is designed by Özgül Kücük and it has been a candidate Hash function for the second round of SHA-3. The compression function of Hamsi-256 maps a 256-bit chaining value and a 32-bit message to a new 256-bit chaining value. As hashing a message, Hamsi-256 operates 3-round except for the last message it operates 6-round. In this paper, we will give the pseudo-near-collision for 5-round Hamsi-256. By the message modifying, the pseudo-near-collision for 3, 4 and 5 rounds can be found with $2^5$, $2^{32}$ and $2^{125}$ compression function computations respectively.}, | abstract = {Hamsi-256 is designed by Özgül Kücük and it has been a candidate Hash function for the second round of SHA-3. The compression function of Hamsi-256 maps a 256-bit chaining value and a 32-bit message to a new 256-bit chaining value. As hashing a message, Hamsi-256 operates 3-round except for the last message it operates 6-round. In this paper, we will give the pseudo-near-collision for 5-round Hamsi-256. By the message modifying, the pseudo-near-collision for 3, 4 and 5 rounds can be found with $2^5$, $2^{32}$ and $2^{125}$ compression function computations respectively.}, | ||
+ | } | ||
+ | </bibtex> | ||
+ | |||
+ | <bibtex> | ||
+ | @misc{hamsiWWJW09, | ||
+ | author = {Cagdas Calik and Meltem Sonmez Turan}, | ||
+ | title = {Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256}, | ||
+ | howpublished = {Cryptology ePrint Archive, Report 2010/057}}, | ||
+ | year = {2010}, | ||
+ | note = {\url{http://eprint.iacr.org/}}, | ||
+ | url = {http://eprint.iacr.org/2010/057.pdf}, | ||
+ | abstract = {Hamsi is one of the second round candidates of the SHA-3 | ||
+ | competition. In this study, we present non-random differential proper- | ||
+ | ties for the compression function of the hash function Hamsi-256. Based | ||
+ | on these properties, we first demonstrate a distinguishing attack that | ||
+ | requires a few evaluations of the compression function and extend the | ||
+ | distinguisher to 5 rounds with complexity 2^83 . Then, we present a mes- | ||
+ | sage recovery attack with complexity of 2^10.48 compression function evaluations. Also, we present a pseudo-preimage attack for the compression | ||
+ | function with complexity 2^254.25 . The pseudo-preimage attack on the | ||
+ | compression function is easily converted to a pseudo second preimage | ||
+ | attack on Hamsi-256 hash function with the same complexity.}, | ||
} | } | ||
</bibtex> | </bibtex> |
Latest revision as of 11:04, 7 December 2010
1 The algorithm
- Author(s): Özgül Kücük
- Website: http://homes.esat.kuleuven.be/~okucuk/hamsi/
- NIST submission package:
- round 1/2: Hamsi_Round2.zip (old versions: Hamsi.zip, HamsiUpdate.zip)
Özgül Küçük - The Hash Function Hamsi
- ,2009
- http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf
BibtexAuthor : Ö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
BibtexAuthor : Ö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) | 2247 | ? | Dinur,Shamir |
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 |
Itai Dinur, Adi Shamir - An Improved Algebraic Attack on Hamsi-256
- ,2010
- http://eprint.iacr.org/2010/602.pdf
BibtexAuthor : Itai Dinur, Adi Shamir
Title : An Improved Algebraic Attack on Hamsi-256
In : -
Address :
Date : 2010
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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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