What are the consequences if someone finds the accessible 1600-bit block $X$ and $R$-bit block $V$ such that $\text{Keccak-}f[1600](X \oplus V) = X$?

Question

Let $H$ denote any hash function based on the sponge construction. Let $F$ denote its underlying function that transforms the $L$-bit state (for SHA-3, $F = \text{Keccak-}f[1600]$ ). Let $R$ denote the bitrate.

Note that the padded message $M$ has the following form:

$$\text{pad}(M) = B_1 \mathbin\Vert B_2 \mathbin\Vert \ldots \mathbin\Vert B_{N-1} \mathbin\Vert B_N,$$

where $B_i$ denote $R$-bit blocks.

Consider the possibility that there exists some $L$-bit block $X$ and $R$-bit block $V$ such that $F(X \oplus V) = X$ (obviously, assuming that the xoring takes place in the same position where the padded message blocks are xored into the state). Moreover, there exists some sequence of $R$-bit blocks $$S = B_1 \mathbin\Vert B_2 \mathbin\Vert \ldots B_{Y-1} \mathbin\Vert B_Y$$ that lead to the state $X$. Doesn’t this mean that if someone knows $S$ and $V$, it would be very easy to choose any suitable sequence of $nR$ bits (where $n$ is any natural number greater than 0), denote it by $T$ and generate arbitrarily many different messages such that $$\begin{array}{l} {\text{pad}(M_1)} = S\mathbin\Vert T,\\ {\text{pad}(M_2)} = S \mathbin\Vert V \mathbin\Vert T,\\ {\text{pad}(M_3)} = S \mathbin\Vert V \mathbin\Vert V \mathbin\Vert T,\\ {\text{pad}(M_4)} = S \mathbin\Vert V \mathbin\Vert V \mathbin\Vert V \mathbin\Vert T,\\ \ldots? \end{array}$$

But this means that $H(\text{pad}(M_i))$ is always the same for any $i$. What are practical consequences for $H$ if someone manages to find such a combination of $S$ and $V$, and then publishes it immediately (so that this combination is in open access for everyone)? That is, what practical applications (use cases) of $H$ will be impacted?

Answer 1

Such block would allow extension attacks. This would be very limited attack vector (because such block would be constant) but still some attack.

To mitigate this problem it would be required to pad message with it's length, which is used in SHA-1 and SHA-2 but SHA-3 do not use length-dependant padding and it is left up to the user.

So this would "break" function in way that one could generate extended strings in form you have presented, however it would be quite easy to mitigate such attacks (ex. by appending big-endian encoded length in bits to the message before padding).

So in my humble opinion it would be interesting thing but it shouldn't pose real threat to users as mitigation would be quite simple and straightforward.

Answer 2

Then you've found a collision in SHA-3, and you get a prize.

There is a choice of prizes:

• You could get your name on a virtual piece of paper that makes a lot of people excited and causes exceptionally insufferably tedious debates on Hacker News.
• You could get a large number of unmarked bills in small denominations and possibly an unwanted piece of lead in your head by selling the collision on the black market.
• You could get the fruit of exploiting the collision in real-world applications, with a lot more effort, and who has time for that kind of effort anyway?