Difference between revisions of "Sarmal"

From The ECRYPT Hash Function Website
(Collisions and Pseudo-Collisions for Sarmal)
(Added the Mouha/Bjørstad/Preneel result)
 
(2 intermediate revisions by 2 users not shown)
Line 4: Line 4:
 
* Website: [http://www.metu.edu.tr/~e127761/sarmal_hash.html http://www.metu.edu.tr/~e127761/sarmal_hash.html]
 
* Website: [http://www.metu.edu.tr/~e127761/sarmal_hash.html http://www.metu.edu.tr/~e127761/sarmal_hash.html]
 
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Sarmal.zip Sarmal.zip]
 
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Sarmal.zip Sarmal.zip]
−
* Specification:
+
 
  
 
<bibtex>
 
<bibtex>
Line 15: Line 15:
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
 +
 +
{| 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
 +
|-                                       
 +
|  style="background:yellow" | preimage || hash || 512 ||  || max(2<sup>512-s</sup>,2<sup>256+s</sup>) || 2<sup>s</sup> || [http://ehash.iaik.tugraz.at/uploads/7/77/Sarmal.pdf Nikolić]
 +
|-                   
 +
|  | collision with salt || hash || 224,256,384 ||  || 2<sup>n/3</sup> || 2<sup>n/3</sup> || [http://ehash.iaik.tugraz.at/uploads/d/d1/Salt-collision.pdf Mendel,Schläffer]
 +
|-                   
 +
|  | preimage with salt || hash || 224,256 ||  || 2<sup>n/2+x</sup> || 2<sup>n/2-x</sup> || [http://ehash.iaik.tugraz.at/uploads/d/d1/Salt-collision.pdf Mendel,Schläffer]
 +
|-                   
 +
|  | preimage with salt || hash || 384,512 ||  || 2<sup>n-128+x</sup> || 2<sup>128-x</sup> || [http://ehash.iaik.tugraz.at/uploads/d/d1/Salt-collision.pdf Mendel,Schläffer]
 +
|-
 +
|  | non-randomness || compression function || all ||  || 2 || - || [http://ehash.iaik.tugraz.at/uploads/8/8c/Sarmal.new.pdf Mouha,Bjørstad,Preneel]
 +
|-                                   
 +
|}                   
 +
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
  
 
<bibtex>
 
<bibtex>
Line 32: Line 52:
 
@misc{sarmalMS08,
 
@misc{sarmalMS08,
 
   author    = {Florian Mendel and Martin Schläffer},
 
   author    = {Florian Mendel and Martin Schläffer},
−
   title    = {Collisions and Pseudo-Collisions for Sarmal},
+
   title    = {Collisions and Preimages for Sarmal},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/d/d1/Salt-collision.pdf},
 
   url        = {http://ehash.iaik.tugraz.at/uploads/d/d1/Salt-collision.pdf},
 
   howpublished = {Available online},
 
   howpublished = {Available online},
 
   year      = {2008},
 
   year      = {2008},
−
   abstract  = {In this paper, we show a collision attack on the hash function of Sarmal with different salt. The attack has a complexity of 2^{n/3} compression function evaluations and memory requirement of 2^{n/3}. Since the salt of Sarmal is only 256 bits the attack works only for variants of Sarmal up to 384 bits. Note that we can choose the messages in our attack and hence we can even construct meaningful collisions for the hash function.},
+
   abstract  = {In this paper, we show a collision attack on the hash function of Sarmal with different salt. The attack has a complexity of $2^{n/3}$ compression function evaluations and memory requirement of $2^{n/3}$. Since the salt of Sarmal is only 256 bits the attack works only for variants of Sarmal up to 384 bits. Note that we can choose the messages in our attack and hence we can even construct meaningful collisions for the hash function.
 +
Furthermore, we show how to construct preimages for Sarmal faster than brute force search if the attacker can choose the salt value. The attack works for all output sizes of Sarmal and with a complexity of $2^{n/2+x}$ compression function evaluations and memory requirements of $2^{n/2-x}$ for $n=\{224,256\}$, and $2^{n-128+x}$ compression function evaluations and memory requirements of $2^{128-x}$ for $n=\{384,512\}$.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{sarmalMBP09,
 +
  author    = {Nicky Mouha and Tor E. Bjørstad and Bart Preneel},
 +
  title    = {Non-randomness in the Sarmal compression function},
 +
  url        = {http://ehash.iaik.tugraz.at/uploads/8/8c/Sarmal.new.pdf},
 +
  howpublished = {Available online},
 +
  year      = {2009},
 +
  abstract  = {Sarmal is a hash function submitted to the NIST SHA-3 hash function competition. The
 +
design and structure of Sarmal is quite similar to that of ARIRANG, another SHA-3 candidate. We
 +
analyse the impact and applicability of recent attacks by Guo et al. on ARIRANG, with respect to
 +
Sarmal. Our results indicate that Sarmal is less vulnerable against this line of attack; in particular
 +
we were not able to obtain pseudo-collisions for Sarmal faster than using a generic attack. However,
 +
we have found that the compression function of Sarmal can be distinguished from a pseudorandom
 +
function with probability one, using only two compression function calls. This result is specific to
 +
the compression function, and does not seem extensible to the full hash function.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Latest revision as of 19:00, 16 April 2009

1 The algorithm


Kerem Var\i c\i \, Onur \"Ozen, \cCelebi Kocair - Sarmal: SHA-3 Proposal

,2008
http://www.metu.edu.tr/~e127761/Supporting_Documentation/SarmaL.pdf
Bibtex
Author : Kerem Var\i c\i \, Onur \"Ozen, \cCelebi Kocair
Title : Sarmal: SHA-3 Proposal
In : -
Address :
Date : 2008


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
preimage hash 512 max(2512-s,2256+s) 2s Nikolić
collision with salt hash 224,256,384 2n/3 2n/3 Mendel,Schläffer
preimage with salt hash 224,256 2n/2+x 2n/2-x Mendel,Schläffer
preimage with salt hash 384,512 2n-128+x 2128-x Mendel,Schläffer
non-randomness compression function all 2 - Mouha,Bjørstad,Preneel

A description of this table is given here.


Ivica Nikolić - Preimage attack on Sarmal-512

,2008
http://ehash.iaik.tugraz.at/uploads/7/77/Sarmal.pdf
Bibtex
Author : Ivica Nikolić
Title : Preimage attack on Sarmal-512
In : -
Address :
Date : 2008

Florian Mendel, Martin Schläffer - Collisions and Preimages for Sarmal

,2008
http://ehash.iaik.tugraz.at/uploads/d/d1/Salt-collision.pdf
Bibtex
Author : Florian Mendel, Martin Schläffer
Title : Collisions and Preimages for Sarmal
In : -
Address :
Date : 2008

Nicky Mouha, Tor E. Bjørstad, Bart Preneel - Non-randomness in the Sarmal compression function

,2009
http://ehash.iaik.tugraz.at/uploads/8/8c/Sarmal.new.pdf
Bibtex
Author : Nicky Mouha, Tor E. Bjørstad, Bart Preneel
Title : Non-randomness in the Sarmal compression function
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Sarmal&oldid=3092"