3
$\begingroup$

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?

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, but using length-dependent padding will definitely require a modification to the specification of $H$ with the additional security proofs. I don't think that it is left to the user. $\endgroup$ – lyrically wicked May 30 '18 at 4:32
  • $\begingroup$ This isn't a length extension attack: it does not enable someone who knows $H(m)$ but not $m$ to predict $H(m \mathbin\Vert m')$ for any nontrivial family of suffixes $m'$. Rather, it is a collision attack, and although you could mitigate it with length-tagged padding, if you found such a collision there would be many questions about the security of Keccak in the first place. $\endgroup$ – Squeamish Ossifrage May 30 '18 at 15:40
-1
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ This question is not about prizes, it's about the world-wide consequences for $H$ that the found (and published) combination will entail. $\endgroup$ – lyrically wicked May 25 '18 at 5:03
  • $\begingroup$ @lyricallywicked If you're asking about the cryptographic consequences, it would be quite clear that you'd found a property that totally violates the security conjectures of SHA-3, and would be publishable in cryptography journal or conference. If you're asking about the social consequences, that's too much of a matter of opinion and sociological conjecture to be fitting for crypto.SE. $\endgroup$ – Squeamish Ossifrage May 25 '18 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.