Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64

Léo Perrin and Dmitry Khovratovich

Abstract

In this paper, we investigate the properties of iterative non-injective functions and the security of primitives where they are used. First, we introduce the Collision Probability Spectrum (CPS) parameter to quantify how far from a permutation a function is. In particular, we show that the output size decreases linearly with the number of iterations whereas the collision trees grow quadratically. Secondly, we investigate the T-sponge construction and show how certain CPS and rate values lead to an improved preimage attack on long messages. As an example, we find collisions for the GLUON-64 internal function, approximate its CPS, and show an attack that violates the security claims. For instance, if a message ends with a sequence of 1~Mb (respectively 1~Gb) of zeros, then our preimage search takes time $2^{115.3}$ (respectively $2^{105.3}$) instead of $2^{128}$.

Metadata
Available format(s)
Category
Secret-key cryptography
Publication info
Published by the IACR in FSE 2014
Keywords
random functionCollision Probability Spectrumcollision treeT-spongeGLUONcollision search
Contact author(s)
leo perrin @ uni lu
History
2014-03-28: received
Short URL
https://ia.cr/2014/223
License

CC BY

BibTeX

@misc{cryptoeprint:2014/223,
author = {Léo Perrin and Dmitry Khovratovich},
title = {Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64},
howpublished = {Cryptology ePrint Archive, Paper 2014/223},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/223}},
url = {https://eprint.iacr.org/2014/223}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.