Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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:
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.
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.
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.
