Given a cryptographic hash function $h$, for example SHA256, how hard is it to find plaintexts $a,b,c$ such that $$h(a)\oplus h(b)=h(c) \text?$$
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
9
This partial answer establishes (rather trivial) lower and upper bounds for the asymptotic hardness of the problem, assuming $h$ behaves like an $n$-bit wide random function.
If one hashes $m$ messages $M$, then computes $f(i,j,k)=h(M_i)\oplus h(M_j)\oplus h(M_k)$ for $(i,j,k)\in\mathbb {Z_m}^3$, that's $m^3$ results, with most values duplicated at least 6 times for large $m$. Odds that zero is never reached by any $f(i,j,k)$ are about $(1-2^{-n})^{m^3/6}$ for large $m$, for any choice of the $M$ by an adversary who can't distinguish $h$ from a random function.
Therefore, if $m\approx2^{n/3}$ hashes have been computed, that can not lead to a solution of the problem with odds better than 16% for large parameters.
The expected hardness of the problem in the question is thus at least $\mathcal O(2^{n/3})$ times the work for a hash. Also, an infinitely powerful adversary could succeed with $\mathcal O(2^{n/3})$ queries to an oracle implementing the hash.
The above leads to an explicit algorithm with non-vanishing odds of success that performs $(2^{n/3})^3=2^n$ evaluations of $f$, thus has cost $\mathcal O(2^n)$ $n$-bit operations; it requires $\mathcal O(2^{n/3})$ $n$-bit words of memory. We can do much better.
One option is to fix $a$, then find collisions for the function $$g(x)=\begin{cases}h(x) & \text{if }x\text{ is even}\\h(x)\oplus h(a) & \text{if }x\text{ is odd}\end{cases}$$ This search can be can be made with cost $\mathcal O(2^{n/2})$ hashes and modest memory, using Floyd's cycle-finding, or Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).
Notice that if $g(b)=g(c)$ with $b\ne c$, then $(a,b,c)$ is a solution of the problem of the question if $b$ and $c$ have different parity, which (for random $h$) has odds about $1/2$ for each collision exhibited.
The expected hardness of the problem in the question is thus at most $\mathcal O(2^{n/2})$ times the work for a hash.
-
3$\begingroup$ And it's easy to show that it's at most $O(2^{n/2})$ -- how can we establish where in that range the answer is? $\endgroup$– ponchoCommented Jan 30, 2015 at 18:51
-
$\begingroup$ @Poncho: Did you think to Birthday attack when you claim $O(2^{n/2})$ ? $\endgroup$ Commented Jan 30, 2015 at 22:36
-
2$\begingroup$ Not true for all cryptographic hash functions, there are cryptographically strong hash functions for which generating triples of this form are downright trivial. notably SWIFFT where f(a + b) = f(a) + f(b) your answer is valid for cryptographic hashes that are also psuedorandom though, because if there were an easier than brute force way to generate the triples it would distinguish the function from a random function. $\endgroup$ Commented Jan 31, 2015 at 2:01
-
3$\begingroup$ @JohnMeacham, I'm not familiar with SWIFFT, but if it satisfies $f(a+b)=f(a)+f(b)$, I would not call it a cryptographic hash function. The question specifically asks about cryptographic hash functions (and mentions SHA256 as an example); the term "cryptographic hash function" is often understood to require that the hash is effectively pseudorandom. So I think your criticism is debatable. If you have questions about what the OP meant by "cryptographic hash function", I suggest posting a comment underneath the question to ask the original poster to clarify. $\endgroup$– D.W.Commented Feb 1, 2015 at 20:13
-
1$\begingroup$ @Hyperflame: Ah, I now see what you mean. I have changed the answer to clarify that I meant cost in units of work for a hash, and added discussion of number of (queries to an oracle implementing the) hash for an infinitely powerful adversary. $\endgroup$– fgrieu ♦Commented Feb 7, 2015 at 14:49
$\begingroup$
$\endgroup$
This is basically something that is called a 3-XOR problem, and was studied for some time.
In short, the best known time complexity is $2^{n/2}$ for $n$-bit hash. However, naive approach requires lots of memory, and there are methods to reduce the memory complexity (sometimes at the cost of more time).
For details see recent work [1], slides are also available.
Note: Current record for SHA256 is a 3-XOR with 119 zero bits, made using mass computations ;) See [2] to have some fun.
[1] Bouillaguet et al. (TOSC 2018 (1)) Revisiting and Improving Algorithms for the 3XOR Problem.
[2] Gaëtan Leurent. Cryptanalysis Records. FSE 2018 Rump Session Slides, p.160. https://fse.iacr.org/2018/files/proceedings_rumpsession.pdf
