Counter mode secure hash algorithm Ever since the SHA-3 competition, I've been wondering if it is possible to create a hash algorithm that is easier to parallelize. The current algorithms all seem to require building a tree of hashes. This has however rather serious drawbacks:


as they requires a tree with certain parameters (such as the size of nodes and branches), it needs to be explicitly defined what the tree looks like
communicating parties should be programmed explicitly to allow hash trees
the tree is likely to be optimized for certain configurations, and not all parties will have the same configuration (e.g. an 8 or 16 bit processor checking the hash created by a 64 bit server machine with GPU acceleration)
if the leaves are too big, you need a whole lot of information before you could start with the next leaf
with the exception of Skein, none of the remaining candidates seem to define how the hash tree should even be constructed


Now I am wondering if you could construct a hash algorithm using a PRF that has a counter as input. In this construct, you would have a relatively strong PRF that is fed both the counter and a block plain text, resulting in an output of a known size (step1). This output would then be compressed together with the other transformed blocks in (step 2). Finally, as usual for a hash, you would have a finalization step which avoids length extension attacks (step3).

To allow for easy parallelism, I think that step 2 should be associative. In other words, it should not matter in which order the output of step 1 is given to the function in step 2. If it is associative, it would even be possible to distribute step 2 between the processes as well. In that case, step 2 may even be relatively heavy (sponge like?). The trick, obviously, is to create collision resistance for the combination of step 1 and step 2. This is where my perfect scheme begins to crumble, and I am wondering if it is even possible to create a solution for the problem.

The advantages of such a scheme are obvious: it would have none of the drawbacks of the tree hash scheme. Anybody could generate a hash using as many threads or computing blocks as they want. Only the block size, the output size of step 1 and the state of step2 would be restraining implementations.

The algorithm would of course not be able to use the Merkle–Damgård construction, as it assumes that each block is processed in a sequential fashion - which introduces the problem in the first place. It seems that Merkle–Damgård and variations on Merkle–Damgård  still rule supreme in the SHA-3 competition (at least with most of the final candidates).

[EDIT: By now Keccak has been chosen as winner of the SHA-3 competition, and one of the reasons is that it was the candidate within the 5 remaining candidates that was using a sponge instead of a Merkle–Damgård construction, so I guess that this paragraph is out of date by now]

Unfortunately, I'm not introduced to mathematics enough to see the correct solution, I cannot find if it has been tried, and I'm certainly not able to prove that my scheme would be impossible. Hopefully, this is where you can give me some hints.
First of all, I think I want to correct you at one point; in step 2, you aren't actually that interested in whether the operation is commutative, what you're actually interested in is that the operation is associative, that is, if $(a \oplus b) \oplus c = a \oplus (b \oplus c)$.  In essence, your operator $\oplus$ in step 2 turns out to be a group operation.

Hence, your proposed hash function can be expressed as:

$H(P_1, ..., P_n) = G( \sum_i F( P_i, i ) )$

where:


F is the your so-called 'cipher mimicking counter-mode encryption' (bad terminology, btw) in step 1, which outputs group members
$\sum$ is the group operation sum over all the group members
G is finalization operation in step 3, which takes as input a group member, and outputs the actual hash (and may also take the file length as input; that detail is irrelevant)


Now, assuming that F and G are well-chosen (for example, that it's infeasible to find collisions or preimages in F), the obvious way to attack this construct is to find a collision at the summation step;


for second-preimage on a hash of $P_i$, find a distinct set of blocks $Q_i$ such that $\sum_i F(P_i, i) = \sum_i F(Q_i, i)$
for a collision attack, find distinct sets of blocks $P_i$, $Q_i$ such that $\sum_i F(P_i, i) = \sum_i F(Q_i, i)$


Now, I have good news, and I have bad news.

The good news is that there exists groups where the above problems are NP-hard (!), and even better, one such group is integer addition modulo a large number.  There are also groups where the above problems are easy (such as the group of bitstrings where the group operation is bit-wise exclusive or's), so we'll need to be careful when choosing a group.

Now, the bad news; just because the problem is NP-hard doesn't mean that there aren't shortcuts.  One such short-cut to the second-preimage problem is a square-root attack which works by dividing the blocks $Q_1, ..., Q_n$ into two sets $Q_1, ..., Q_{n/2}$ and $Q_{n/2+1}, ..., Q_n$, collecting sums from both subsets, and scanning the sums for a pair that sum to the target value.  This attack allows us to find a set that sums to the target N-bit value in $\sqrt N$ time; hence the group members must be — at least — twice as big in order to keep the second-preimage problem as difficult as expected.

The update of this observation is that for an $N$ bit hash, the internal sum must be over $2N$ bit values; that means that your $F$ function must generate strong $2N$ bit values, and so ends up being considerably harder to compute than the leaf compression function in a hash-tree construction.