Edon-R (SHA-3 submission) - Revision history

Fmendel: Detectable correlations in Edon-R

2009-08-06T07:35:20Z

Detectable correlations in Edon-R

Fmendel: Key Recovery Attack against Secret-prefix Edon-R

2009-03-27T08:24:44Z

Key Recovery Attack against Secret-prefix Edon-R

Mschlaeffer: criticism of Khovratovich et. al's attack added

2009-03-25T09:27:22Z

criticism of Khovratovich et. al's attack added

Crechberger: added V. Klima as co-author

2009-02-11T07:51:23Z

added V. Klima as co-author

Mschlaeffer at 20:11, 29 December 2008

2008-12-29T20:11:36Z

Fmendel: /* The algorithm */

2008-12-11T09:18:58Z

‎The algorithm

Fmendel: /* Cryptanalysis */

2008-12-01T14:55:51Z

‎Cryptanalysis

Fmendel: /* Cryptanalysis */

2008-12-01T10:53:23Z

‎Cryptanalysis

JAumasson at 13:55, 25 November 2008

2008-11-25T13:55:16Z

Fmendel: /* Cryptanalysis */

2008-11-19T07:38:03Z

‎Cryptanalysis

@@ Line 36: / Line 36: @@
 |-
 | key recovery || secret-prefix MAC||  ||  || 2<sup>5n/8</sup> || - || [http://eprint.iacr.org/2009/135.pdf Leurent]
 |-
 |}
@@ Line 85: / Line 87: @@
      url = {http://eprint.iacr.org/2009/135.pdf},
      abstract = {Edon-R is a SHA-3 candidate. In this paper we show that using Edon-R as a MAC with the secret prefix construction is unsafe. Our attack requires 2 queries, $2^{5n/8}$ computations, and negligible memory.},
+}
 </bibtex>

@@ Line 34: / Line 34: @@
 |-
 | preimage || compression ||  ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
 |-
 |}
@@ Line 72: / Line 74: @@
    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>

@@ Line 23: / Line 23: @@
 | 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]
@@ Line 38: / Line 38: @@
 A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
@@ Line 59: / Line 61: @@
    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.},
+}
 </bibtex>

@@ Line 1: / Line 1: @@
 == The algorithm ==
-* Author(s): Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal
+* 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 http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r]
 * NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/EDON-R.zip EDON-R.zip]
@@ Line 8: / Line 8: @@
 <bibtex>
 @misc{sha3G+08,
-   author    = {Danilo Gligoroski and Rune Steinsmo Ødegård and Marija Mihova and Svein Johan Knapskog and Ljupco Kocarev and Aleš Drápal},
+   author    = {Danilo Gligoroski and Rune Steinsmo Ødegård and Marija Mihova and Svein Johan Knapskog and Ljupco Kocarev and Aleš Drápal and Vlastimil Klima},
    title     = {Cryptographic Hash Function EDON-R},
    url        = {http://people.item.ntnu.no/~danilog/Hash/Edon-R/Supporting_Documentation/EdonRDocumentation.pdf},

@@ Line 4: / Line 4: @@
 * Website: [http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r]
 * NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/EDON-R.zip EDON-R.zip]
-* Specification:
 <bibtex>
@@ Line 15: / Line 15: @@
+}
 </bibtex>
 == Cryptanalysis ==
 <bibtex>
@@ Line 28: / Line 50: @@
+}
 </bibtex>
 <bibtex>

@@ Line 21: / Line 21: @@
    author    = {Dmitry Khovratovich and Ivica Nikolić and Ralf-Philipp Weinmann},
    title     = {Cryptanalysis of Edon-R},
-   url        = {http://lj.streamclub.ru/papers/hash/edon-r.pdf},
+   url        = {http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf},
    howpublished = {Available online},
    year      = {2008},

@@ Line 17: / Line 17: @@
 == Cryptanalysis ==
-* D. Khovratovich, I. Nikolic, R.-Ph. Weinmann, Cryptanalysis of Edon-R. Details: [http://lj.streamclub.ru/papers/hash/edon-r.pdf here]
+<bibtex>
-* V. Klima, Multicollisions of EDON-R hash function and other observations. Details: [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf here]

← Older revision		Revision as of 07:38, 19 November 2008
Line 18:		Line 18:

	* D. Khovratovich, I. Nikolic, R.-Ph. Weinmann, Cryptanalysis of Edon-R. Details: [http://lj.streamclub.ru/papers/hash/edon-r.pdf here]		* D. Khovratovich, I. Nikolic, R.-Ph. Weinmann, Cryptanalysis of Edon-R. Details: [http://lj.streamclub.ru/papers/hash/edon-r.pdf here]
		+
		+	* V. Klima, Multicollisions of EDON-R hash function and other observations. Details: [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf here]