# Difference between revisions of "Sarmal"

From The ECRYPT Hash Function Website

Mschlaeffer (talk | contribs) (added preimage attack with chosen salt) |
(Added the Mouha/Bjørstad/Preneel result) |
||

Line 30: | Line 30: | ||

|- | |- | ||

| | 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] | | | 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] | ||

|- | |- | ||

|} | |} | ||

Line 56: | Line 58: | ||

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\}$.}, | 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 speciﬁc 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

- Author(s): Kerem Varıcı, Onur Özen and Çelebi Kocair
- Website: http://www.metu.edu.tr/~e127761/sarmal_hash.html
- NIST submission package: Sarmal.zip

*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(2^{512-s},2^{256+s}) |
2^{s} |
Nikolić | |

collision with salt | hash | 224,256,384 | 2^{n/3} |
2^{n/3} |
Mendel,Schläffer | |

preimage with salt | hash | 224,256 | 2^{n/2+x} |
2^{n/2-x} |
Mendel,Schläffer | |

preimage with salt | hash | 384,512 | 2^{n-128+x} |
2^{128-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**