View source for Edon-R (SHA-3 submission)

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


<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 and Vlastimil Klima},
  title     = {Cryptographic Hash Function EDON-R},
  url        = {http://people.item.ntnu.no/~danilog/Hash/Edon-R/Supporting_Documentation/EdonRDocumentation.pdf},
  howpublished = {Submission to NIST},
  year      = {2008},
}
</bibtex>


== 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<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-preimage || hash || 256,512 ||  || ? || ? || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima]
|-
| collision || compression ||  ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-                    
| 2nd preimage || compression ||  ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-                    
| preimage || compression ||  ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-                    
| key recovery || secret-prefix MAC||  ||  || 2<sup>5n/8</sup> || - || [http://eprint.iacr.org/2009/135.pdf Leurent]
|-
| correlation analysis || hash || all ||  || - || - || [http://eprint.iacr.org/2009/378.pdf Novotney, Ferguson]
|-                    
|}                    

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.


<bibtex>
@misc{edonKNW08,
  author    = {Dmitry Khovratovich and Ivica Nikolić and Ralf-Philipp Weinmann},
  title     = {Cryptanalysis of Edon-R},
  url        = {http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf},
  howpublished = {Available online},
  year      = {2008},
  abstract  = {We present various types of attacks on the hash family Edon-R. In a free start attack scenario, with the initial chaining value not xored, all three main attacks (collisions, second preimage, and preimage) can be launched on Edon-R with negligible effort. In these attacks we exploit the asymmetrical diffusion of the chaining values in the compression function. Also, by partially inverting the compression function and xoring one part of the chaining value, we launch a meet-in-the-middle attack on Edon-R-n to find real preimages. The attack requires $2^{2n/3}$ effort and the same amount of memory. The attacks are applicable to all digest sizes.},
}
</bibtex>

<bibtex>
@misc{edonK08,
  author    = {Vlastimil Klima},
  title     = {Multicollisions of EDON-R hash function and other observations},
  url        = {http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf},
  howpublished = {Available online},
  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>

<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>
@misc{cryptoeprint:2009:135,
    author = {Gaëtan Leurent},
    title = {Key Recovery Attack against Secret-prefix Edon-R},
    howpublished = {Cryptology ePrint Archive, Report 2009/135},
    year = {2009},
    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>

<bibtex>
@misc{cryptoeprint:2009:378,
    author = {Peter Novotney and Niels Ferguson},
    title = {Detectable correlations in Edon-R},
    howpublished = {Cryptology ePrint Archive, Report 2009/378},
    year = {2009},
    url={http://eprint.iacr.org/2009/378.pdf},
    note = {\url{http://eprint.iacr.org/}},
    abstract = {The Edon-R compression function has a large set of useful differentials that produce easily detectable output bit biases. We show how to construct such differentials, and use them to create a distinguisher for Edon-R-512 that requires around $2^{54}$ compression function evaluations (or $2^{28}$ evaluations after a pre-computation of $2^{66}$ evaluations). The differentials can also be used to attack a variety of MAC and KDF constructions when they use Edon-R-512.},
}
</bibtex>