# Difference between revisions of "Edon-R (SHA-3 submission)"

From The ECRYPT Hash Function Website

Crechberger (talk | contribs) m (added V. Klima as co-author) |
Mschlaeffer (talk | contribs) m (criticism of Khovratovich et. al's attack added) |
||

Line 23: | Line 23: | ||

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

|- | |- | ||

− | | style="background:yellow" | preimage || hash || || || 2<sup>2n/3</sup> || 2<sup>2n/3</sup> || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann] | + | | style="background:yellow" | preimage<sup>(1)</sup> || hash || || || 2<sup>2n/3</sup> || 2<sup>2n/3</sup> || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann] |

|- | |- | ||

| multi-collision (2<sup>K</sup>) || hash || 256,512 || || K*2<sup>n/2</sup> || 2<sup>n/2</sup> || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima] | | multi-collision (2<sup>K</sup>) || hash || 256,512 || || K*2<sup>n/2</sup> || 2<sup>n/2</sup> || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima] | ||

Line 38: | Line 38: | ||

A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here]. | A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here]. | ||

+ | |||

+ | <sup>(1)</sup> [http://eprint.iacr.org/2009/120.pdf Gligoroski,Ødegård] dispute the validity of the model in which the attack of Khovratovich et. al is compared to generic attacks. | ||

Line 59: | Line 61: | ||

year = {2008}, | year = {2008}, | ||

abstract = {The main principle how to make n-bit EDON-R hash functions [1] resistant to generic multicollisions and multipreimages attacks ([2], [3]) is the 2n-bit width of internal chaining value. We show how to degenerate 2n-bit chaining value to n-bit chaining value (for n = 256, 512) by keeping the half of chaining value constant from the beginning. It circumvents the main principle and make EDON-R hash functions (for n = 256, 512) vulnerable to generic multicollisions and multipreimages attacks ([2], [3]) with small additional work factor. We show several properties of EDON-R compression function, which could be interesting for the next study of collisions and preimages. The first cryptanalysis of EDON-R was made in [4]. We present an independent research, partially overlaping with [4]. We want to note that this is preliminary version, that we present here only sketches of the proofs and that not all of the accompanied problems are completely solved.}, | abstract = {The main principle how to make n-bit EDON-R hash functions [1] resistant to generic multicollisions and multipreimages attacks ([2], [3]) is the 2n-bit width of internal chaining value. We show how to degenerate 2n-bit chaining value to n-bit chaining value (for n = 256, 512) by keeping the half of chaining value constant from the beginning. It circumvents the main principle and make EDON-R hash functions (for n = 256, 512) vulnerable to generic multicollisions and multipreimages attacks ([2], [3]) with small additional work factor. We show several properties of EDON-R compression function, which could be interesting for the next study of collisions and preimages. The first cryptanalysis of EDON-R was made in [4]. We present an independent research, partially overlaping with [4]. We want to note that this is preliminary version, that we present here only sketches of the proofs and that not all of the accompanied problems are completely solved.}, | ||

+ | } | ||

+ | </bibtex> | ||

+ | |||

+ | <bibtex> | ||

+ | @misc{edonGO09, | ||

+ | author = {Danilo Gligoroski and Rune Steinsmo Ødegård}, | ||

+ | title = {On the Complexity of Khovratovich et. al's Preimage Attack on EDON-R}, | ||

+ | url = {http://eprint.iacr.org/2009/120.pdf}, | ||

+ | howpublished = {Available online}, | ||

+ | year = {2009}, | ||

+ | abstract = {Based on the analysis made by van Oorschot and Wiener for the complexity of parallel memoryless collision search [5], we show that the memoryless meet-in-the-middle attack which is one part of the whole preimage attack of Khovratovich et. al. [3] on EDON-R hash function has complexity bigger than $2^n$.}, | ||

} | } | ||

</bibtex> | </bibtex> |

## Revision as of 10:27, 25 March 2009

## 1 The algorithm

- Author(s): Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal, Vlastimil Klima
- Website: http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r
- NIST submission package: EDON-R.zip

*Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal, Vlastimil Klima* - **Cryptographic Hash Function EDON-R**

- ,2008
- http://people.item.ntnu.no/~danilog/Hash/Edon-R/Supporting_Documentation/EdonRDocumentation.pdf

Bibtex**Author :**Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal, Vlastimil Klima**Title :**Cryptographic Hash Function EDON-R**In :**-**Address :****Date :**2008

## 2 Cryptanalysis

Type of Analysis | Hash Function Part | Hash Size (n) | Parameters/Variants | Compression Function Calls | Memory Requirements | Reference |

preimage^{(1)} |
hash | 2^{2n/3} |
2^{2n/3} |
Khovratovich,Nikolić,Weinmann | ||

multi-collision (2^{K}) |
hash | 256,512 | K*2^{n/2} |
2^{n/2} |
Klima | |

multi-preimage | hash | 256,512 | ? | ? | Klima | |

collision | compression | - | - | Khovratovich,Nikolić,Weinmann | ||

2nd preimage | compression | - | - | Khovratovich,Nikolić,Weinmann | ||

preimage | compression | - | - | Khovratovich,Nikolić,Weinmann |

A description of this table is given here.

^{(1)} Gligoroski,Ødegård dispute the validity of the model in which the attack of Khovratovich et. al is compared to generic attacks.

*Dmitry Khovratovich, Ivica Nikolić, Ralf-Philipp Weinmann* - **Cryptanalysis of Edon-R**

- ,2008
- http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf

Bibtex**Author :**Dmitry Khovratovich, Ivica Nikolić, Ralf-Philipp Weinmann**Title :**Cryptanalysis of Edon-R**In :**-**Address :****Date :**2008

*Vlastimil Klima* - **Multicollisions of EDON-R hash function and other observations**

- ,2008
- http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf

Bibtex**Author :**Vlastimil Klima**Title :**Multicollisions of EDON-R hash function and other observations**In :**-**Address :****Date :**2008

*Danilo Gligoroski, Rune Steinsmo Ødegård* - **On the Complexity of Khovratovich et. al's Preimage Attack on EDON-R**