Is there such thing as an order independent, updatable hash?

Question

I have an application where I have a set of primitive units, $P = \{p_0 ... p_n\}$ (they are byte-arrays, in my application).

I want to be able to create a hash value $H(S)$ for any subset $S \subset P$, such that:

1. I can update a hash without knowing what it hashes. So given $H(S)$ and $T$ (where $S, T \subset P$), there is some function $f(H(S), T) = H(S \cup T)$. Note this works without knowing the contents of S, only its hash.

2. The hash value is independent of the order. So $f(H(S), T) = f(H(T), S)$.

Answer 1

The answer largely depends on what security properties you want.

The scheme I would use here is to hash all of the individual parts, then take some Diffie-Hellman group, and then raise the generator of that group to the power of the product of the individual hashes. That is,

$ H(a_1, ..., a_n) = g^{\operatorname{SHA256}(a_1) * ... * \operatorname{SHA256}(a_n)} \bmod p $

for $ * $ being multiplication and $ g $, $ p $ being the generator and modulus of the Diffie-Hellman group. (This could also be done with an elliptic curve group to the same effect).

This provides a number of properties:

• It is secure given a reasonable Diffie-Hellman group (if you're using Diffie-Hellman based on modular arithmetic, then $ g $ needs to be reasonably large, or $ g^{a} $ may not be larger than $ n $), and reasonable assumptions similar to DDH
• It is communitive; that is, the hash value is independent of the order of the hash (and it can be updated after it's computed by raising the computed hash to the power of a new block)
• It is reasonably fast

You may also want to consider using a block chain; it's faster, although it isn't communitive, which is one of the properties you asked for. (I also initially considered using XOR in place of exponentiation in a group, but I quickly realized that can be defeated with Gaussian Elimination. It's possible I'm missing something there, though).

Answer 2

Next to Ethan White's answer, I want to add that you could use the Merkle-Demgrad by performing a length extension attack. To do so, let's define the hash function $H$ as $H(x) = C(P(x))$ where $C$ is the compression function and $P$ is the padding function. The way $C$ works within a Merkle-Demgrad construction is splitting the input into blocks $B$ and then applying $S = M(B_i, S)$ where $S$ is the state of the compression function and $M$ mixes the current block and the state in some magic way. The most hash functions, like SHA-256 or SHA-512, directly return $S$ which can be abused for extending the hash:

Length extension attacks try to build the hash of $P(X) || Y$ only using $H(X)$ and information needed to recreate the padding of $P(X)||Y$ which often is the length of $P(X)$. The first step to extend the hash is to pad $Y$ so it can be applied to the compression function. Since the most padding functions rely on the message's length, you have to take care of that by assuming the length of the message is the length of $P(X)$ plus the length $Y$. Once $Y$ is padded correctly, we set $S$ to $H(X)$ and then continue to apply $C$ to the forged padding of $Y$ as it would be usual input. That way, we created $H(P(X) || Y) = C(P(X) || Y)$ which equals to $C(FP(Y))$ when $FP$ is the forged padding and $S = H(X)$.

In practise, I would use SHA-256, which can be attacked that way, and store it with the information about the length of each part which is included into the hash so you can reconstruct the input into the compression function later for validating data.

EDIT: Unlike in Ethan White's answer, the order does matter when applying this method, but a length extension should be ways faster since no powMod is involed.