Generic Attacks on Double Block Length Sponge Hashing

The sponge construction is one of the main modes of operation for hash functions. Using a permutation of width b = r + c, the sponge construction with rate r and capacity c is indifferentiable up to Ω(2c/2) permutation calls. In this paper we study variants of the sponge construction that use two permutations in parallel in order to increase the state size: the XOR combiner, and the double sponge construction of Lefevre and Mennink. We focus on the indifferentiability security, and we obtain new distinguishers on these constructions based on a variant of the 4-sum problem that we denote the multiple 4-sum problem.First, we show that the XOR combiner does not increase the indifferentiability bound when applied to sponge hash functions, with a tight generic attack with complexity ˜Õ(2c/2). This improves over folklore results that require ˜Õ(2b/2) operations to find internal state collisions, and justifies the more involved double sponge construction. Indeed, by mixing the two internal states after every permutation call, the double sponge achieves security beyond the birthday bound, with a security proof up to Ω(22c/3) permutation calls. However, the proof is not tight: the best generic attack has complexity O(2c+r/2), and Lefevre and Mennink show a simulator-specific attack with complexity O(22c/3+r/3). We reduce this gap by showing a dedicated attack against the double sponge, with complexity O(2c) in general, and O(max(23c/4, 2c−r/3)) with the specific mixing matrix used by Lefevre and Mennink. In particular, we observe that the complexity of our attack decreases with r (for a fixed c), while previous attacks have a complexity that increases with r.