Why xor the message into the state for sponge hashes?

Question

Sponge hashes like Keccak(SHA-3) and CubeHash, xor a message block into part of the internal state. Why use a reversible operation like xor for that, instead of replacing that part of the state with the message block?

1. It clearly has no effect on pre-image and collision resistance. It's trivial to transform collisions/pre-images between the different mixing schemes.
2. It causes some weirdness if the attacker learns the internal state of the hash. This shouldn't happen, but makes me slightly uncomfortable.
3. Perhaps it increases security in a universal hashing scenario. Might make it impossible to construct key independent collisions. But my understanding of this is pretty foggy.
4. When replacing it's not necessary to store that part of the state between permutations. Reduces the memory usage in some scenarios.
5. When replacing instead of xor-ing the truncated permutation seems like a pretty normal compression function, with the sponge becoming a standard MD style construction with a tagged last block.

Answer 1

Section 4.3 of the paper Cryptographic sponge functions analyzes the Overwrite-mode for a sponge, which does just what you propose: instead of XORing the next part of the message into the non-hidden part of the state, replace the non-hidden part of the state by it.

They show that it can be implemented on top of the Duplex mode (which outputs the non-hidden part of the state), and for this reason has equivalent security as the usual Sponge mode (which XORs the message part), with the cost of two bits of capacity or bitrate used for padding and a frame bit.

This is also intuitively clear: All the security claims of a sponge are relative to the capacity, i.e. the size of the hidden part of the state. What you do with the non-hidden part doesn't really matter, as long as your new data somehow comes into play.

Answer 2

As a simplified case, consider a sponge hash function made from an ideal 160-bit block cipher with a 256-bit key, and mixes in a 32-bit word each round. It would be better to use an LFSR to generate the sequence of keys for each round, but let's say this simplified hash function is

$$ \begin{align} H(0) &= 0 \\ H(N) &= E(0, H(N-1) \oplus \mathtt{words}[N-1]) \\ \end{align} $$

where $\oplus$ is 160-bit exclusive-or and words[] is the message suitably padded and represented as an array of 32-bit integers.

You're correct that this construction provides 128-bits of state that an attacker can't directly manipulate. Now, consider the sequence of states generated by hashing a very long message where each $\mathtt{word}[ N ]$ is identical (say zero). This construction will, after an average of $2^{80}$ steps enter into a cycle with an average length of $2^{80}$ steps. That is, it will act as an ideal permutation of 160-bit values. Note that for a fixed value of the final word in the words array, there are $2^{160}$ possible values for the final $H$ hash value.

Consider the alternative construction $$ \begin{align} G(0) &= 0 \\ G(N) &= E(0, \mathsf{mask128}( G(N-1) ) \oplus \mathtt{words}[ N-1 ] ) \\ \end{align} $$

where $\mathsf{mask128}(V)$ returns a copy of $V$ with its least significant 32 bits all set to zero. This is equivalent to the remove-instead-of-xor case.

Consider again how this $G$ function behaves when words is a very long sequence of identical values. After an average of $2^{64}$ iterations, it will go into a cycle of size $2^{64}$. In other words, it acts as a random permutation of 128-bit values. Note that for a constant value of the final word in the words array, there are only $2^{128}$ possible final $G$ hash values. (The possible final $G$ hash values are the values for which $D(0, G(N-1)) \mathbin\& (2^{32}-1) = \mathtt{word}[N-1]$ where $\&$ is bitwise and.)

Consider the following attack that generates two messages $M$ and $M'$ with identical hash values (a weak collision of the hash): begin with $K$ and $K'$, the beginnings of the two messages you want to collide. Generate $K$ from $M$ by appending 320 random bits (call this the $K$-seed), and then iteratively append a constant 32-bit word (say zero). Do the same to generate $K'$ from $M$ using random $K'$-seeds. Keep a mapping $J$ of $H(M)$ hash values to the $K$-seed values (and number of appended words) that generated them and a mapping $J'$ of $H(M')$ values to the $K'$-seed values (and number of appended words) that generated them. Stop as soon as $J$ and $J'$ have one key in common. You have found a week collision on $H$ or $G$.

The average complexity of this attack for $H$:
An average of $2^{80}$ values in $J$ and $2^{80}$ values in $J'$. This means a work factor of $2^{81}$ in time and $2^{81}$ in space required.

The average complexity of this attack for $G$:
An average of $2^{64}$ values in $J$ and $2^{64}$ values in $J'$. This means a work factor of $2^{65}$ in time and $2^{65}$ in space required.

Now, the work factor of the attack against $H$ can be brought down to $2^{65}$ by choosing a value of $\mathtt{word}[N-1]$ that has a constant value when XOR-ed with the least significant bits of $H(N-1)$.

We see that for an active attacker, this simple attack isn't any more difficult against $H$ than $G$. However, for non-adversarial uses (for instance, checksumming and de-duplicating long constant-length documents with a constant 32-bit footer) $H$ is superior to $G$, and there may arise other real-world use cases where an attacker is similarly constrained in the values he or she may inject into the words[] array. Using replace-instead-of-XOR may be the tiniest of footholds to give an attacker, but there's no reason to give an attacker even such a tiny foothold.