3
$\begingroup$

I have to answer the following question for a homework assignment:

You have a hash algorithm that converts a $2\cdot n$ bit number to an n bit number. How many hash values do you have to calculate to find a collision for $h(x) \oplus h(y) = h(r) \oplus h(s)$

I know that a you can find a collision after $2^{n/2}$ evaluations. But I don't know how this is affected by the fact that a $2\cdot n$ bit number is hashed to a $n$ bit number and the $\oplus$ of the hashes.

$\endgroup$
5
$\begingroup$

We first need to refine the definition of the problem.

The most natural assumption in a cryptographic context is that "How many hash values do you have to calculate" implies that we consider a strategy that minimizes that number of hashes.

In theoretical cryptography, a common assumption is that we are allowed arbitrarily large amount of memory, and use of arbitrary computing power. We'll assume we use that to cache the hash computation, but healthily check the required amount of memory and processor time in the end, for bonus points.

We'll also assume that we are actually asked the expected number of hash calculations required by one of the best possible strategies. And as common in cryptography, we'll be content with approximations, and/or disregarding low $n$, if that helps.

We need to define "collision". When talking about collision in a hash, it is understood $x$ and $y\ne x$ with $h(x)=h(y)$. But here the later condition is replaced by $h(x)\oplus h(y)=h(r)\oplus h(s)$, so what about the rest? That could be:

  1. $(x,y)\ne(r,s)$. In that case the answer is zero assuming $n>0$ : we take any two distinct $x$ and $r$ and we know that $(x,x)$ and $(r,r)$ is a solution, without making any hash. $(x,r)$ and $(r,x)$ does the trick too. We'll disregard that option 1 from now on.
  2. Distinct $x$, $y$, $r$, $s$; at least four hashes are required.
  3. $x$, $y$, $r$, $s$ such that possible equality between terms does not result in a collision irrespective of the hash lagorithm; for $n=3$ that can be (showing inputs and outputs in binary)
    • $x=\mathtt{000000}$ with $h(x)=\mathtt{010}$
    • $y=\mathtt{000001}$ with $h(y)=\mathtt{001}$
    • $r=\mathtt{000010}$ with $h(r)=\mathtt{010}$
    • $s=y$; that works specifically because $x=r$.

Options 2 and 3 are not equivalent; option 2 falsely looks simpler (we fall into this trap later..).

The result obviously depends on the particular "hash algorithm", which in a cryptographic context is assumed known. Perhaps we could find an answer by looking at this algorithm. But it is not given in the question, thus in a cryptographic context our default fallback option is to consider that the expected number of hashes is for a random function $h:\{0,1\}^{2n}\to\{0,1\}^n$ (that notation merely states the size in bit of input an output of $h$). There are $2^{(n2^{2n})}$ such functions, thus $2^4=16$ for $n=1$, $2^{32}$ for $n=2$, and a whooping $2^{192}$ for $n=3$.


There's an easy way to plausibly justify that $2^{n/4+1/2}$ hashes allow to find a collision with fair odds for all but small $n$. Argument:

  • Evaluate $h(i)=h_i$ for $2^{n/4+1/2}$ incremental values of $i$ starting from $0$, assimilating integers to bitstrings in big-endian binary (as common in cryptography); that is, for $n=4$, $h_5=8$ means that $h(\mathtt{00000101})=\mathtt{0100}$.
  • For all $(x,y)$ with $0\le x<y<2^{n/4+1/2}$ consider $h'(x\|y)\gets h(x)\oplus h(y)$ and tabulate the nearly $2^{n/2}$ values $h'(x\|y)$.
  • $h'$ is not a random function, but if we nevertheless abuse the birthday problem for cryptographic hashing (a common thing in cryptography), that tells us there are near 40% odds of collision for $h'$ in the standard definition of that for hashes.
  • Such collision would allow one for $h$ as asked, always matching our option 3.
  • The collision is not quite always one per option 2; but odds that is does not are vanishingly low, considering that it occurs only if we found a collision for $h$ in the standard definition of that for hashes, after a mere $2^{n/4+1/2}$ hashes.

By turning that strategy into one that searches for collision of $h'$ for incremental values of $i$ (rather than having computed all hashes $h_i$), we can make the resulting strategy optimum for a near complete subset of option 3, including option 2; see below.


We now proceed to reason about what an optimum strategy must do.

  • It must computes hashes only for different inputs (otherwise we could devise a better strategy that does).
  • And since the function $h$ is random, what said different inputs are does not matter to the desired expected number of hashes (that is, the mean number of hashes for all possible $h$). So we can restrict to strategies always using inputs in lexicographic orders, as we did in example 3. We can safely state that the "..a $2\cdot n$ bit number.." part of the question is large enough that this strategy won't run out of input values; that would still hold if we removed the factor of two, including for $n=1$.
  • After having computed $h_i$, the strategy must stop if the computed hashes now allows to exhibit distinct $x$, $y$, $r$, $s$ at most $i$ with $h_x\oplus h_y=h_r\oplus h_s$. At least one of $x$, $y$, $r$, $s$ must be $i$ (otherwise the strategy would not be optimum), and reordering $x$, $y$, $r$, $s$ in non-decreasing order leaves a strategy valid and optimal.
  • An optimum strategy as restricted must thus try increasing $s$ and stop precisely
    • for option 2, when $s>2$ and the $h_s$ just computed and cached matches $h_x\oplus h_y\oplus h_r$ for some $x$, $y$, $r$ such that$0\le x<y<r<s$; which case $x$, $y$, $r$, $s$ is a collision.
    • for option 3, additionaly
      • when $s\ge2$ and the $h_s$ just computed mathches an earlier $h_r$ with $0<r<s$, in which case $x=0$, $y=0$, $r$, $s$ is a non-trivial collision;
      • or when $s>1$ and $h_s=h_0$, in which case $x=0$, $y=1$, $r=1$, $s$ is a non-trivial collision;
      • or when $s=1$ and $h_s=h_0$, in which case $x=0$, $y=0$, $r=0$, $s=1$ is a non-trivial collision.

One implementation option for option 2 is four nested loops with $s$ growing starting from $0$ at the outer, computing and caching $h_s$, then for $r$ from $2$ to $s-1$, $y$ from $1$ to $r-1$, $x$ from $0$ to $y-1$, terminating if the newly computed $h_s=h_x\oplus h_y\oplus h_r$, in which case $x$, $y$, $r$, $s$ is a collision.

There are $s(s-1)(s-2)\over6$ combinations of $x$, $y$, $r$ for a given $s$. Each corresponds to some $h_x\oplus h_y\oplus h_r$, these are not necessarily different, and finding a collision among these does not by itself allow the algorithm to stop. We consider all $h$, thus for each new $h_s$, odds $p_s$ that the strategy stops having computed $h_s$ assuming that it did not previously stop are (at most) $\tilde{p_s}={s(s-1)(s-2)\over6}\,2^{-n}$. It holds that $p_s\lessapprox\tilde{p_s}$, with equality when it happens that the $s(s-1)(s-2)\over6$ values of $h_x\oplus h_y\oplus h_r$ all are distinct.

Odds of stopping before computing $h_j$ (that is, having computed $j$ hashes or less) are $$q_j\;=\;1-\prod_{3\le s<j}(1-p_s)\;\lessapprox\;\sum_{3\le s<j}p_s\;\lessapprox\;\sum_{3\le s<j}\tilde{p_s}\;\lessapprox\;{6\over2^n}\sum_{3\le s<j}(s-1)(i−2)(i−3)$$ with that approximation tight as long as $j\ge4$ is small enough that $q_s$ remains small and there are few collisions among the $(j-1)(j−2)(j−3)\over6$ values of $h_x\oplus h_y\oplus h_r$ previously computed when $h_{j-1}$ gets computed.

Further, induction shows that $$\sum_{3\le s<j}(s-1)(i−2)(i−3)\;=\;{j(j-1)(j−2)(j−3)\over4}\lessapprox{j^4\over4}$$ and that approximation is tight for all except small values of $j$.

Therefore odds of stopping having computed $j$ hashes or less are $q_j\lessapprox{3\over2}j^4 2^{-n}$, and this approximation is tight as long as $k$ is not too small, but is small enough that said odds remain small and there are few collisions among the $\approx{j^3\over6}$ values of $h_x\oplus h_y\oplus h_r$ considered.

Thus the best algorithm for option 2 can not find a collision with sizable odds faster than $O(2^{n/4})$; this shows that our simple algorithm has the right assymptotic.


Moreover, $j\le{1\over\sqrt[4]3}2^{n/4}\implies q_j\le{1\over2}$ holds. Beware that this later approximation is far from tight: we expect more than few collisions among the values of $h_x\oplus h_y\oplus h_r$ (by abusing the birthday problem for cryptographic hashing, consciously ignoring the fact that the $\approx{j^3\over6}$ values are not independent); and the approximation where we changed the product into sum is no longer tight. That establises some upper bound (not approximation) for the median of the number of hashes required by any optimum strategy; we aim at the mean, which is slightly higher.

mean vs median
Image credit: Cmglee; source; Creative Commons license.


We have shown nearly rigorously that the expected number of hashes for an optimum strategy and large $n$ must be $k=O(2^{n/4})$ as $n$ grows; and have plausible argument that $2^{n/4+1/2}$ gives nearly 40% odds of collision.

Because that $k$ is well under the birthday bound $\approx2^{n/2}$, it is very unlikely that for large $n$ a hash collision for $h$ alone is reached before $k$ steps, and the distinction between the two definitions of "collision" that we did not reject matters only for small $n$.

We know various strategies leading to the minimum number of hashes according to 2 or 3, plausibly running in $O(2^n)$ time with $O(2^{n/4})$ or $O(2^{n/2})$ words of memory (for a computer with words of at least $n$ bits; beside this, a multiplicative factor of $\log n$ applies for both). We could make exact calculations of the expectancy for very small $n$ (but that will depend on the definition of collision). We could make randomized simulations for up to perhaps $n=32$. Finding strategies requiring less work (perhaps at the expense of more memory, or computing somewhat more hashes than needed) in order to tackle larger $n$ is an interesting problem.


This answer is incomplete (we still miss a rigorous and tight bound), overly long and complex with the potential to be confusing (especially from the moment we seek an optimum strategy), and spoils an interesting homework assignment (asked in vague terms, but perhaps that's on purpose by the teacher, or OP). I hope that at least the redaction will differ, and that the OP will make the aforementioned exact and simulated computations. After all, it is all too possible that I left a serious error somewhere.

$\endgroup$
  • 2
    $\begingroup$ Can't you also use Wagner's $k$-list algorithm for $k=4$ here? The OP asks for $x, y, r, s$ so that $h(x) \oplus h(y) = h(r)\oplus h(s)$, or equivalently $h(x) \oplus h(y) \oplus h(r) \oplus h(s) = 0$ $\endgroup$ – pg1989 Jun 23 '17 at 17:14

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.