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

From The ECRYPT Hash Function Website
m (criticism of Khovratovich et. al's attack added)
(Detectable correlations in Edon-R)
 
(One intermediate revision by the same user not shown)
Line 34: Line 34:
 
|-                     
 
|-                     
 
| 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]
 
|-                     
 
|-                     
 
|}                     
 
|}                     
Line 72: Line 76:
 
   year      = {2009},
 
   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$.},
 
   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>
 
</bibtex>

Latest revision as of 09:35, 6 August 2009

1 The algorithm


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 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
key recovery secret-prefix MAC 25n/8 - Leurent
correlation analysis hash all - - Novotney, Ferguson

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

,2009
http://eprint.iacr.org/2009/120.pdf
Bibtex
Author : Danilo Gligoroski, Rune Steinsmo Ødegård
Title : On the Complexity of Khovratovich et. al's Preimage Attack on EDON-R
In : -
Address :
Date : 2009

Gaëtan Leurent - Key Recovery Attack against Secret-prefix Edon-R

,2009
http://eprint.iacr.org/2009/135.pdf
Bibtex
Author : Gaëtan Leurent
Title : Key Recovery Attack against Secret-prefix Edon-R
In : -
Address :
Date : 2009

Peter Novotney, Niels Ferguson - Detectable correlations in Edon-R

,2009
http://eprint.iacr.org/2009/378.pdf
Bibtex
Author : Peter Novotney, Niels Ferguson
Title : Detectable correlations in Edon-R
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Edon-R_(SHA-3_submission)&oldid=3216"