Cryptology ePrint Archive: Report 2009/302
Cryptanalysis of ESSENCE
Maria Naya-Plasencia and Andrea Röck and Jean-Philippe Aumasson and Yann Laigle-Chapuy and Gaëtan Leurent and Willi Meier and Thomas Peyrin
Abstract: ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design. Previous analysis showed some non-randomness in the compression function which could not be extended to an attack on the hash function and ESSENCE 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 characteristic and an advanced search algorithm, we obtain collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities 2^67.4 and 2^134.7. In addition, we show how to use these attacks to forge valid (message, MAC) pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.
Category / Keywords: secret-key cryptography / hash function, collision, SHA-3, NIST hash competition
Date: received 23 Jun 2009, last revised 27 Jan 2010
Contact author: maria naya plasencia at gmail com, jeanphilippe aumasson@gmail com
Available formats: PDF | BibTeX Citation
Note: To appear at FSE 2010.
Version: 20100127:094227 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]