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 11: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
BibtexAuthor : 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 | 22n/3 | 22n/3 | Khovratovich,Nikolić,Weinmann | ||
| multi-collision (2K) | hash | 256,512 | K*2n/2 | 2n/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
BibtexAuthor : 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
BibtexAuthor : 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
