Security issues with computing parallel hashes?

Question

One issue with most hash algorithms like SHA-256 is that it is inherently serial. You can't effectively use SIMD to parallelize a single SHA-256 calculation.

However, you can calculate multiple SHA-256 hashes in parallel efficiently, because you can keep each algorithm in a lane of the SIMD registers.

Take SSE as an example: each register has four 32-bit lanes. Computing SHA-256 four times in parallel makes sense. We can define a new hash algorithm for computing the hash of a single file as slicing the input into four pieces, computing the hash of each of the four pieces (in parallel), then produce the final result by hashing the final four sub-hashes together. Obviously, this would be a new hash function, not matching a normal SHA-256.

Are there security problems with such a design that wouldn't exist with a normal hash algorithm?

Answer 1

Are there security problems with such a design that wouldn't exist with a normal hash algorithm?

At least not for collision resistance.

Suppose you could come up with a collision for the composite construction $H_p$ based on the hash function $H$. Then you'd have two inputs $x\neq x'$ such that $H_p(x)=H_p(x')$. Then either there is a collision on the final hash invocation and we can reconstruct the relevant inputs following the description of $H_p$. Alternatively all the inputs to the final invocation are equal between $x,x'$ and then the slices that differ produced a collision in $H$ which we can reconstruct.

So every collision for $H_p$ implies a collision for $H$, but because we assume $H$ to be collision-resistant there is no efficiently findable collision for $H_p$.