Difference between revisions of "ESSENCE"

From The ECRYPT Hash Function Website
m (→‎Cryptanalysis)
m (fixed bibtex entry)
 
(16 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
* Authors: Jason Worth Martin
 
* Authors: Jason Worth Martin
 
* Website: [http://www.math.jmu.edu/~martin/essence/ http://www.math.jmu.edu/~martin/essence/]  
 
* Website: [http://www.math.jmu.edu/~martin/essence/ http://www.math.jmu.edu/~martin/essence/]  
−
* Specification:
+
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/ESSENCE.zip ESSENCE.zip]
  
  
 +
<bibtex>
 +
@misc{sha3Martin08,
 +
  author    = {Jason Worth Martin},
 +
  title    = {ESSENCE: A Candidate Hashing Algorithm for the NIST Competition},
 +
  url        = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_NIST.pdf},
 +
  howpublished = {Submission to NIST},
 +
  year      = {2008},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{sha3Martin08a,
 +
  author    = {Jason Worth Martin},
 +
  title    = {ESSENCE: A Family of Cryptographic Hashing Algorithms},
 +
  url        = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_compression.pdf},
 +
  howpublished = {Submission to NIST},
 +
  year      = {2008},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{sha3Martin08b,
 +
  author    = {Jason Worth Martin},
 +
  title    = {ESSENCE: Errata},
 +
  url        = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_errata.pdf},
 +
  howpublished = {Submission to NIST},
 +
  year      = {2008},
 +
}
 +
</bibtex>
  
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
−
* None yet
+
{| 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
 +
|-                   
 +
| observation || compression function || all ||  || - || - || [http://www.mat.dtu.dk/people/S.Thomsen/essence/Essence-obs.pdf Mouha,Thomsen,Turan]
 +
|-
 +
| observation || compression function || all ||  || - || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
 +
|-
 +
| key recovery || block cipher || 256 || 14 rounds || 2<sup>225</sup> || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
 +
|-
 +
| key recovery || block cipher || 512 || 14 rounds || 2<sup>450</sup> || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
 +
|-
 +
| pseudo-collision || hash || 512 || 31 rounds || 2<sup>254.6</sup> || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
 +
|-      
 +
| style="background:orange" | collision || hash || 224/256 ||  || 2<sup>67.4</sup> || - || [http://www.131002.net/data/papers/NRALLMP09.pdf Naya-Plasencia et al.]
 +
|-
 +
| style="background:orange" | collision || hash || 384/512 ||  || 2<sup>134.7</sup> || - || [http://www.131002.net/data/papers/NRALLMP09.pdf Naya-Plasencia et al.]
 +
|-
 +
|}                   
 +
 
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 
 +
 
 +
<bibtex>
 +
@misc{essenceMTT09,
 +
author = {Nicky Mouha and Søren S. Thomsen and Meltem Sönmez Turan},
 +
title  = {Observations of non-randomness in the ESSENCE compression function},
 +
url    = {http://www.mat.dtu.dk/people/S.Thomsen/essence/Essence-obs.pdf},
 +
howpublished = {Available online},
 +
year  = {2009},
 +
abstract= {ESSENCE is a candidate for the SHA-3 hash function competition initiated by NIST. In this note we describe some non-random behaviour in the ESSENCE compression function, including an input leading to the all-zero output. The results do not seem directly extensible to the full hash function, and hence they do not seem to break any security claims of ESSENCE.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{essenceMSAPTMP09,
 +
author = {Nicky Mouha and Gautham Sekar and Jean-Philippe Aumasson and Thomas Peyrin and Søren S. Thomsen and Meltem Sönmez Turan and Bart Preneel},
 +
title  = {Cryptanalysis of the ESSENCE Family of Hash Functions},
 +
url    = {http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf},
 +
howpublished = {Available online},
 +
year  = {2009},
 +
abstract = {ESSENCE is a family of cryptographic hash functions, accepted to the first round of NIST’s SHA-3 competition. This paper presents the first known attacks on ESSENCE. We present a pseudo-collision attack on 31 out of 32 rounds of ESSENCE-512, invalidating the design claim that at least 24 rounds of ESSENCE are secure against differential cryptanalysis. We develop a novel technique to satisfy the first nine rounds of the differential characteristic. Non-randomness in the outputs of the feedback function F is used to construct several distinguishers on a 14-round ESSENCE block cipher and the corresponding compression function, each requiring only 2^17 output bits. This observation is extended to key-recovery attacks on the block ciphers. Next, we show that the omission of round constants allows slid pairs and fixed points to be found. These attacks are independent of the number of rounds. Finally, we suggest several countermeasures against these attacks, while still keeping the design simple and easy to analyze.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{essenceNRALLMP09,
 +
    author = {María Naya-Plasencia and Andrea Röck and Jean-Philippe Aumasson and Yann Laigle-Chapuy and Gaëtan Leurent and Willi Meier and Thomas Peyrin},
 +
    title = {Cryptanalysis of ESSENCE},
 +
    howpublished = {Cryptology ePrint Archive, Report 2009/302},
 +
    year = {2009},
 +
    url = {http://eprint.iacr.org/2009/302.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abstract = {ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design, and that has thus far remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential path and a nontrivial search algorithm, we obtain shortcut collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities $2^{67.4}$ and $2^{134.7}$. As an aside, we show how to use these attacks for forging valid message/MAC pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.},
 +
}

Latest revision as of 09:45, 11 September 2009

1 The algorithm


Jason Worth Martin - ESSENCE: A Candidate Hashing Algorithm for the NIST Competition

,2008
http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_NIST.pdf
Bibtex
Author : Jason Worth Martin
Title : ESSENCE: A Candidate Hashing Algorithm for the NIST Competition
In : -
Address :
Date : 2008

Jason Worth Martin - ESSENCE: A Family of Cryptographic Hashing Algorithms

,2008
http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_compression.pdf
Bibtex
Author : Jason Worth Martin
Title : ESSENCE: A Family of Cryptographic Hashing Algorithms
In : -
Address :
Date : 2008

Jason Worth Martin - ESSENCE: Errata

,2008
http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_errata.pdf
Bibtex
Author : Jason Worth Martin
Title : ESSENCE: Errata
In : -
Address :
Date : 2008


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
observation compression function all - - Mouha,Thomsen,Turan
observation compression function all - - Mouha et al.
key recovery block cipher 256 14 rounds 2225 - Mouha et al.
key recovery block cipher 512 14 rounds 2450 - Mouha et al.
pseudo-collision hash 512 31 rounds 2254.6 - Mouha et al.
collision hash 224/256 267.4 - Naya-Plasencia et al.
collision hash 384/512 2134.7 - Naya-Plasencia et al.

A description of this table is given here.


Nicky Mouha, Søren S. Thomsen, Meltem Sönmez Turan - Observations of non-randomness in the ESSENCE compression function

,2009
http://www.mat.dtu.dk/people/S.Thomsen/essence/Essence-obs.pdf
Bibtex
Author : Nicky Mouha, Søren S. Thomsen, Meltem Sönmez Turan
Title : Observations of non-randomness in the ESSENCE compression function
In : -
Address :
Date : 2009

Nicky Mouha, Gautham Sekar, Jean-Philippe Aumasson, Thomas Peyrin, Søren S. Thomsen, Meltem Sönmez Turan, Bart Preneel - Cryptanalysis of the ESSENCE Family of Hash Functions

,2009
http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf
Bibtex
Author : Nicky Mouha, Gautham Sekar, Jean-Philippe Aumasson, Thomas Peyrin, Søren S. Thomsen, Meltem Sönmez Turan, Bart Preneel
Title : Cryptanalysis of the ESSENCE Family of Hash Functions
In : -
Address :
Date : 2009

<bibtex> @misc{essenceNRALLMP09, 

   author = {María Naya-Plasencia and Andrea Röck and Jean-Philippe Aumasson and Yann Laigle-Chapuy and Gaëtan Leurent and Willi Meier and Thomas Peyrin},
   title = {Cryptanalysis of ESSENCE},
   howpublished = {Cryptology ePrint Archive, Report 2009/302},
   year = {2009},
   url = {http://eprint.iacr.org/2009/302.pdf},
   note = {\url{http://eprint.iacr.org/}},
   abstract = {ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design, and that has thus far remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential path and a nontrivial search algorithm, we obtain shortcut collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities $2^{67.4}$ and $2^{134.7}$. As an aside, we show how to use these attacks for forging valid message/MAC pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.},

}

Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=ESSENCE&oldid=3231"