# 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:

1. 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
2. communicating parties should be programmed explicitly to allow hash trees
3. 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)
4. if the leaves are too big, you need a whole lot of information before you could start with the next leaf
5. 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.

-
Btw. constructing a MAC with such a property is much easier. We know several such MACs. –  CodesInChaos Mar 1 '13 at 6:48

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.

-
"hence the group members must be twice as big in order to keep the second-preimage problem as difficult as expected" - Actually, they have to be a lot bigger than that (for typical groups, such as addition modulo a large number). The birthday attack you describe is one attack, but it is not optimal. Generalized birthday attacks are even more efficient. Resisting them requires even larger group elements. Therefore, following the advice in your answer ("use twice-as-wide group elements") is likely to lead to an insecure scheme. See my answer for more. –  D.W. Nov 29 '12 at 21:47
@D.W.: Did I say "must be twice as big"? My bad -- I ought to have said "at least twice as big"; as you point out, there's no indication that the attack I outlined is optimal –  poncho Nov 29 '12 at 22:40

You should look at AdHash, by Bellare et al. It computes something like $\sum_i H(i,M_i) \bmod n$ where $M_i$ is the $i$th block of the message. I think this is almost exactly the sort of thing you were suggesting.

The problem with AdHash is that, for it to be secure, $n$ needs to be quite large, e.g., 1600 bits or more. This hurts efficiency. (If $n$ is small, then it can be broken with a generalized birthday attack.) Therefore, AdHash might not be terribly attractive in practice.

Summary: I know of good parallelized MAC algorithms, but I don't know (off the top of my head) of any good parallelized hash algorithms.

References:

-
Thanks for the additional info, I did hear about the hash functions that use large numbers to accomplish "my" requirements, but they do indeed seem to be too impractical to achieve performance benefits over a generic hash. That said, there are likely special benefits e.g. when some parts of the data is only available after a certain amount of time. –  Maarten Bodewes Nov 29 '12 at 21:36
@owlstead, thanks for your comments. Well, all I can say is: You asked "I cannot find if it has been tried". I'm telling you it has been tried ... and the results have been found to be unsatisfactory. As you say, the resulting schemes are too slow to be very practical. The takeaway is that the kind of approach you sketch does not appear to be promising -- or, at least, no one knows how to make it work in a way that is secure and efficient enough to be terribly useful. –  D.W. Nov 29 '12 at 21:50
That said, I don't think the problem has been studied well enough that it doesn't merit more attention. But I also have to admit that my current knowledge dictates that it won't be me that is making a proposal anytime soon :). –  Maarten Bodewes Nov 29 '12 at 21:55
@owlstead: Look, let me put it another way. If you want to innovate, the starting point is to start by understanding what has already been done and what has already been tried. That is what I am trying to outline in my answer. What I'm saying is that there is existing research on this topic, and reading about the past work would be a good place to start for anyone who is interested in the topic. (Maybe you've heard the saying: "a month in the lab can save you a day in the library".) –  D.W. Nov 29 '12 at 22:08
Again thanks, I'm trying to get access but the first promising link in Google seem to be down. Maybe I should push some cash some way to get to the paper. So be it. –  Maarten Bodewes Nov 29 '12 at 22:20

I think the problem lies generally with your commutative compression function.

The simplest such function (XOR) gives an easy way to craft messages with arbitrary hash codes by collecting blocks and using linear algebra to chose a subset - I could imagine that this problem would show (with more complicated calculations) for other such functions, too.

This is not to say that this has to be impossible, but commutativity in cryptographic functions gives much more structure to attack, and finding a good commutative compression function seems hard.

-