7
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ What properties do you want this to have? The word ‘hash’ can have many meanings. Pick a random function $H_0\colon P \to (\Z/q\Z)^\times$ for some large prime $q$; then the function $\{p_i\}_i \mapsto \prod_i H_0(p_i)$ might do what you want. But it's hard to say unless you specify what you mean by ‘hash’. $\endgroup$ – Squeamish Ossifrage Sep 2 '17 at 1:22
  • 2
    $\begingroup$ You should take a look at accumulators (c.f., this survey). $\endgroup$ – Occams_Trimmer Sep 2 '17 at 7:11
6
$\begingroup$

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).

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Just wondering, how do you calculate $H(a || b)$ using $H(a)$ with your method? $\endgroup$ – VincBreaker Sep 3 '17 at 16:53
  • 2
    $\begingroup$ This construction is block-oriented; so instead of computing $ H(a||b) $ from $ H(a) $, it computes $ H(a_1, ..., a_n, a_{n+1}) = H(a_1, ..., a_n)^{a_{n+1}} \text{ (mod n)} $. $\endgroup$ – Ethan White Sep 4 '17 at 0:47
  • $\begingroup$ @EthanWhite - since I'm not supposed to leave comments just saying thank you. I will say thank you and say that this approach seems to work and was very simple to implement. For anyone finding this later, I should point out that our use case does not require security guarantees and is not open to deliberate user exploitation. So please don't take this as meaning we have performed more than functional tests on our problem domain. $\endgroup$ – Ian Sep 4 '17 at 19:59
  • $\begingroup$ @Ian: If you only need a non-cryptographic hash, simply XORing the hashes of the set members (or adding them modulo some number, or whatever) would be a lot faster. That's basically Zobrist hashing. It's vulnerable to simple collision or preimage attacks using linear algebra, but as long you're not concerned about deliberate attacks, it should be just as resistant to accidental collisions as Ethan's scheme. $\endgroup$ – Ilmari Karonen Dec 21 '17 at 4:11
1
$\begingroup$

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.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.