Reference : Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64
Perrin, Léo Paul mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Khovratovich, Dmitry mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Fast Software Encryption - 21th International Workshop, FSE 2014, London, March 3-5, 2014
Lecture Notes in Computer Science; 8540
21st International Workshop on Fast Software Encryption
from 03-03-2014 to 05-03-2014.
United Kingdom
[en] Random function ; Collision Probability Spectrum ; GLUON
[en] In this paper, we investigate the security provided by iterative non-injective functions. We introduce the Collision Probabilities Spectrum (CPS) to quantify how far from a permutation a function is. In particular, we show that the size of the iterated image of such a function decreases linearly with the number of iterations and that collision trees of quadratic size appear.

We discuss the influence of the CPS over collision search efficiency by connecting it with the function's balance. We then show that the security of a so-called T-Sponge is only marginally impacted by the number of collisions occurring because of the update function. However, the loss of entropy in the update function can lead to a greatly simplified preimage search for a particular family of messages if the rate is small. Consequences of the entropy loss when duplexing the sponge to provide one-pass authenticated encryption and for Davies-Meyer construction are also studied.

Finally, we use a heuristic method to estimate the CPS of the update function of GLUON-64. Applying our results, we prove for instance that if a message is only known to end with a sequence of 1 Mb (respectively 1 Gb) of zero bytes, then it is possible to find a preimage for its digest in time $2^{115.3}$ (respectively $2^{105.3}$) instead of $2^{128}$.
Fonds National de la Recherche - FnR
I2R-DIR-PFN-12ACRY > CORE 2012 C12/IS/4009992 ACRYPT - APllied Cryptography for I > 01/07/2013 - 30/06/2016 > BIRYUKOV Alex

File(s) associated to this reference

Fulltext file(s):

Open access
223.pdfAuthor preprint456.21 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.