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

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}$.