What is the collision resistance of a 2048-bit hash based on SHA-3?

Question

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?

Answer 1

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.