5
$\begingroup$

Let $M$ denote the message. Let $B_i$ denote eight different bitstrings (chosen arbitrarily or randomly) such that $$0 \le \text{length}(B_i) \le 12345678.$$ Consider the following function (it outputs a 2048-bit hash of the input): $$H(M) = {H_1} \mathbin\Vert {H_2} \mathbin\Vert {H_3} \mathbin\Vert {H_4},$$ where $\mathbin\Vert$ denotes concatenation and $$\begin{array}{l} {h_1} &= \text{SHA-3-512}({B_1} \mathbin\Vert M),\\ {h_2} &= \text{SHA-3-512}({B_2} \mathbin\Vert M),\\ {H_1} &= \text{SHA-3-512}({h_1} \mathbin\Vert {h_2}),\\ {h_3} &= \text{SHA-3-512}({B_3} \mathbin\Vert M),\\ {h_4} &= \text{SHA-3-512}({B_4} \mathbin\Vert M),\\ {H_2} &= \text{SHA-3-512}({h_3} \mathbin\Vert {h_4}),\\ {h_5} &= \text{SHA-3-512}({B_5} \mathbin\Vert M),\\ {h_6} &= \text{SHA-3-512}({B_6} \mathbin\Vert M),\\ {H_3} &= \text{SHA-3-512}({h_5} \mathbin\Vert {h_6}),\\ {h_7} &= \text{SHA-3-512}({B_7} \mathbin\Vert M),\\ {h_8} &= \text{SHA-3-512}({B_8} \mathbin\Vert M),\\ {H_4} &= \text{SHA-3-512}({h_7} \mathbin\Vert {h_8}). \end{array}$$

Since all values of $h_i$ are the outputs of a simple MAC (which is known to be secure enough for SHA-3) and all values of $H_i$ are taken by extracting one cryptographically secure 512-bit hash of two independent 512-bit bitstrings, I would expect that the collision resistance of $H(M)$ is close to 1024 bits of security. Is this assumption correct?

$\endgroup$
5
$\begingroup$

No.

It turns out that for a tree composition and concatenation of $n$-bit hash functions, collisions can be found at $O(2^{n/2}\operatorname{poly}(n))$ cost. So it still has pretty much 256-bit collision resistance. The additional complexity buys you essentially nothing.

Note that 256-bit collision resistance is already obscenely high, against all plausible attackers (and there's no advantage even if you have a quantum computer); anything beyond it is completely meaningless.

Side note: If the adversary knows the $B_i$, the antiforgery property of a MAC, derived from the prefix-PRF $m \mapsto \operatorname{SHA3-512}(k \mathbin\Vert m)$, is not relevant. If the adversary doesn't know the $B_i$, then this is not the scenario of collision resistance—but you're not going to get better than ‘512-bit security’ anyway, which is already (completely meaningless)^2.

Rather than worry about how to obtain (completely meaningless)^4 security levels from the cryptography, you should focus on writing a clear statement of your application's security model, making sure it's easy to audit and understand in the context of what you're trying to achieve, and making sure you've covered all possibly relevant threat models.

$\endgroup$
  • $\begingroup$ Thank you for the link! It's not that I worry about how to obtain 1024-bits security level, I am just interested in theoretical properties of a possible hashing construction. $\endgroup$ – lyrically wicked Apr 26 '18 at 3:43

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.