1
$\begingroup$

I want to use a cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data.

This question was already asked on SO - "Additive" hash function, but without the requirement that the hash-function function is cryptographically strong.

Mathematically speaking I want to find a hash-function $h$ and a hash-hash function $hh$ such that:

For every two sequences $d_1$ (length $n_1$) and $d_2$ (length $n_2$), the hash code of the combined sequence $d$ (length $n_1+n_2$) $d$ can be calculated both directly (hash function $h$) and using only hashes of $d_1$ and $d_2$ (hash-hash function $hh$): $h(d) = hh(h(d1), h(d2))$

Another take: For any sequence $d$ of length $n$, its hash $h(d)$ can be calculated by breaking it in any position $n_1<n$ into two sequences $d_1$ (length $n_1$) and $d_2$ (length $n_2 = n - n_1$), taking the hashes of the sub-sequences - $h_1=h(d_1)$, $h_2=h(d_2)$ and calculating the hash of full sequence using only the sub-sequence hashes: $h(d) = hh(h_1, h_2)$

Trivial solutions like $h(d)=d$ or $XOR$ satisfy the above requirements. Many checksums like CRC32 satisfy it too. But I'm looking for an irreversible cryptographic hash function.

I seek:

  1. A simplified "mathematical" property that the functions should hold to satisfy my criteria. I guess, some function must be associative, but it's a bit hard for me to think about associativity when the inputs have variable length.
  2. A cryptographic hash function that satisfies my criteria (it can be build on top of some common cryptographic hash-function) OR a proof that it cannot exist.

P.S. I intended to use such hash-function for a version-control system to allow addressing parts of files.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Basically what you're looking for is a monoid structure on the set of possible hashes that in some appropriate sense is "hard to reason backwards about". The monoid structure consists of the hash-combining function and the hash of the empty string (which must be a left and right identity). The only thing you need to add to this is to select a hash for each string of length 1. (There can be some nice principle for selecting them, but from a safety point of view you might as well choose them at random and put them in a table). $\endgroup$ – Henning Makholm Apr 20 '14 at 19:58
  • $\begingroup$ I'm not sure what an appropriate level of "hard to reason backwards about" would be -- requiring that the monoid operation is itself collision-resistant is clearly out of the question, since each instance of the associative law would violate that. Perhaps some variation of second preimage resistance for the monoid operation could to the trick (though one would have to exclude the identity, of course), but it's not clear that it would. $\endgroup$ – Henning Makholm Apr 20 '14 at 20:01
1
$\begingroup$

Just a few observations and formalizations. So we have some (finite) set $\Omega$, and to find a function $$ h \,:\, \Omega^\mathbb{N}_\textrm{fin} \to [0,N] \text{,} $$ where $\Omega^\mathbb{N}_\textrm{fin}$ means the set set of all finite sequences of elements from $\Omega$. We additional want a has-combining operator $$ \oplus \,:\, [0,N] \times [0,N] \to [0,N] $$ such that $$ h(\omega_1,\ldots,\omega_k,\ldots,\omega_n) = h(\omega_1,\ldots,\omega_k) \oplus h(\omega_{k+1},\ldots,\omega_n) $$ for all sequences $\omega_1,\ldots,\omega_n$ and all $1 \leq k < n$.

In particular, that implies that $$\begin{eqnarray} h(\omega_1,\omega_2,\omega_3) &=& h(\omega_1) &\oplus& h(\omega_2,\omega_3) &=& h(\omega_1) &\oplus& \bigg(h(\omega_2) &\oplus& h(\omega_3)\bigg) \\ h(\omega_1,\omega_2,\omega_3) &=& h(\omega_1,\omega_2) &\oplus& h(\omega_3) &=& \bigg(h(\omega_1) &\oplus& h(\omega_2)\bigg) &\oplus& h(\omega_3) \end{eqnarray}$$ meaning that $\oplus$ is associative (i.e., we don't have to worry about parenthesis when chaining multiple $\oplus$ invocations). It follows that for every sequence $\omega_1,\ldots,\omega_n$, $$ h(\omega_1,\ldots,\omega_n) = h(\omega_1) \oplus \ldots \oplus h(\omega_n) \text{.} $$

That's a very strong property, and certainly seems to make an attacker's life unnecessary easy.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Well, the $N^3$ (the size of the combination operator table) can be quite big for 1024-bit hashes. But I guess, some forms of rainbow tables could make brute-forcing faster. I wanted to use such hash for a version-control system to allow addressing parts of files. $\endgroup$ – Ark-kun Apr 20 '14 at 20:38
  • $\begingroup$ @Ark-kun Yeah, I can see how such a thing would be usefull. I'm also not saying that such a thing can't exist, just that it seems that it'd be easier to attack than a non-associative hash. Once thing that you can say is that $\oplus$ cannot be an exponentation operation over some finite fields, because $a^{b^c} \neq \left(a^b\right)^c$. That's a bummer, because we know that exponentation is hard to invert. Multiplication would work, but then $\oplus$ additionally becomes commutative, and multiplication is easy to invert. $\endgroup$ – fgp Apr 20 '14 at 20:59
  • $\begingroup$ What do you think about matrix multiplication or some form of concatenation+hash (cannot think a proper function right now)? $\endgroup$ – Ark-kun Apr 20 '14 at 21:40
  • $\begingroup$ @Ark-kun Concatenation+hash won't in generally be associative, no? Matrix multiplication would, but if the the matrices are non-invertible, you drop information in every step, and otherwise it's not much harder to invert than multiplication I think. Though dunno if invertibility really is such a big problem - I think one would need to look more closely at the potential kinds of attacks one wants to protect against. $\endgroup$ – fgp Apr 20 '14 at 22:29
1
$\begingroup$

There is a talk from FP-Syd titles "FP-Syd - Hashing with SL2: Hash Functions as Monoid Homomorphisms by Sam Reis (Nov 2015)" on YouTube which discusses hashes with this property if I remember correctly, and they're using it for exactly the use case you mention, "...version-control[just file storage] system to allow addressing parts of file". There is an implementation in Haskell in the hwsl2 package.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

That doesn't work, as it would allow to replace parts of the message rather easily. Cryptographic hash functions are designed to not allow this.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Could you explain in more detail how that "would allow to replace parts of the message rather easily"? $\endgroup$ – Henning Makholm Apr 20 '14 at 19:47
  • $\begingroup$ Why would that allow it? Suppose $h(d) = md5(md5(d[0..n/2]),md5(d[n/2+1..n]))$ $hh(h1, h2) = md5(h1, h2)$. How would that compromise the security? $\endgroup$ – Ark-kun Apr 20 '14 at 20:21

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.