# Multiple Hash Functions that work in either nesting

Are there any hashing functions that, if two are used in conjunction (with the same salts) will return the same response regardless of ordering?

I.e. are there hash-functions $H_1$, $H_2$ such that for all suitable salts $s_1$, $s_2$ and all passwords $x$ we have

$$H_1(s_1, H_2(s_2, x)) = H_2(s_2, H_1(s_1, x))$$

-
Is it acceptable if instead of two hash functions, we have four? Such that H1(s1,H2(s2,x)) = H3(s2,H4(s1,x))? – David Schwartz Jul 1 '12 at 5:49
@DavidSchwartz Sure, that would work – topherg Jul 1 '12 at 18:39

[Take 4.2, back to requiring only the PRP to be secret]

Improving on the line of thought in that other answer, we will craft two efficiently computable functions $H_1$ and $H_2$ each accepting two arbitrary strings as input, with output a fixed-size string, say 512 bit; and (I conjecture) indistinguishable from a random function (under the assumption that some parameters are secret) except for this superset of the desired property: $$\forall(i,j)\in\{1,2\}^2,\forall(s_1,s_2,x), H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$$

We'll use as building blocks three 512-bit PRFs $P_0()$, $P_1()$ and $P_2()$ accepting an arbitrary bit string as input, and one 512-bit PRP $E()$ with $D()$ its reverse function, such that $D(E(a))=a$.
We can build the PRFs as $P(m)=\mathtt{HMAC}_\mathtt{SHA­512}(k,m)$ and three arbitrary distinct $k$. And by this famous result we can build the PRP as the four-rounds Feistel cipher with round functions $\mathtt{HMAC}_\mathtt{SHA­256}(k,m)$ and four arbitrary distinct $k$.

For $i\in\{1,2\}$, define $H_i(s,x)$ as $$H_i(s,x)=E\big(\text{ }D(P_i(s))+D(x)\bmod{2^{512}}\text{ }\big)\text{ when }x\text{ is a 512-bit string,}$$ $$H_i(s,x)=E\big(\text{ }D(P_i(s))+P_0(x)\bmod{2^{512}}\text{ }\big)\text{ otherwise.}$$Notice that in the above, $P_0(x)$ is now added without going through $D$; this avoid that knowledge of $P_0$ would allows creating collisions of the form $H_i(s,P_0(x))=H_i(s,x)$

The desired property $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ follows from commutativity and associativity of addition in $\mathbb Z_{2^{512}}$, and the $H_i$ functions appears much like random oracles, except for consequences of that property, to an adversary ignoring the PRP (but possibly knowing the PRFs).

By querying the functions/oracles $H_i$, it seems impossible to internally add 0, or otherwise create collisions, other than by chance. Computing $H_1(s,H_1(s,\cdots H_1(s,H_1(s,x))\cdots))$, where $x$ is a 512-bit string and there are $2^n$ iterations, has odds only $2^{n-511-k}$ to return to $x$; if we had used XOR instead of modular addition, we'd have $H_1(s,H_1(s,x))=x$.

Note: to an adversary knowing the PRP and PRF, the problem of finding collisions on $H_1$ unrelated to the property is tractable: it is a knapsack problem in $\mathbb Z_{2^{512}}$ with unlimited supply of random values to choose from.

Open problems:

• Can this be proven secure (e.g. collision-resistant except per application of the required property); or broken?
• Can we make a scheme secure yet fully public?
• We do not need a full group operation (on the contrary, the neutral element and existence of an opposite are a risk), any commutative semi-group will do; is something more suitable than $\mathbb Z_{2^{512}}$?
• Is $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ a consequence of $H_1(s_1,H_2(s_2,x)) = H_2(s_2,H_1(s_1,x))$?
• If not, can we make a construction with only the originally asked property?
-

No. Hash functions are maps of a variable-length input to a random value from a set of fixed-length outputs. Combining two random mappings shouldn't result in the same output for both orders of application. (Hash functions are deterministic and functions of only one input, so the inclusion of salts doesn't really matter.)

-
Here's a better question. $\:$ Would that provably break collision-resistance for at least one of the hashes? – Ricky Demer Jun 29 '12 at 21:10

It's possible to achieve something very similar. Specifically, let $H$ be a cryptographic hash function whose outputs belong to the set $X$, and let $f: X^2 \to X$ be a function satisfying $f(a, f(b, c)) = f(b, f(a,c))$ for all $a,b,c \in X$. Then $$f(s_1, f(s_2, H(m))) = f(s_2, f(s_1, H(m))).$$

An easy way to construct such a function $f$ is to let $X$ be an abelian group and let $f(a,b) = a \bullet b$, where $\bullet$ denotes the group operation on $X$. (Actually, we only need a weak form of commutativity here, and preferably also the existence of left inverses. We may even generalize and let $f(a,b) = g(a) \bullet b$, where $g$ is an arbitrary function taking values in $X$.) There are several groups that might work here, but the choice rather depends on exactly what security properties you expect this construction to satisfy.

(In particular, if all you want is for $F_{s_1,s_2}(m) = f(s_1, f(s_2, H(m)))$ to be first preimage resistant as a function of $m$, which is what basic password hashing requires, then pretty much any choice of $X$ and $f$ will do; a simple one would be to e.g. let $X = \{0,1\}^n$ with XOR as the group operation. However, depending on what you want to do with this construction, it's quite likely that you may need some other security properties too.)

-
You don't need a group structure here (i.e. that all elements are invertible), but you need $a \bullet (b \bullet c) = b \bullet (a \bullet c)$, i.e. commutativity between $a$ and $b$ (in addition to some kind of associativity property). E.g. your $g$ should map to an commutative sub-halfgroup of $X$ – Paŭlo Ebermann Jun 30 '12 at 20:24
Thanks, corrected. You're right that some commutativity is needed here, and that some of the group axioms are not, although it would at least be nice to have the map $x \mapsto a \bullet x$ be invertible for all $a$. Still, all the obvious examples I actually have in my head are, in fact, abelian groups, although that might of course just be due to my limited imagination. – Ilmari Karonen Jun 30 '12 at 20:42
Yeah, this is the "problem" with finite sets ... all injective functions from a finite set onto itself are automatically bijective, too. This makes most interesting finite half groups into groups, too. – Paŭlo Ebermann Jun 30 '12 at 20:51