4
$\begingroup$

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?$$

$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 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$ – poncho Jan 30 '15 at 18:51
  • $\begingroup$ @Poncho: Did you think to Birthday attack when you claim $O(2^{n/2})$ ? $\endgroup$ – Robert NACIRI Jan 30 '15 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$ – John Meacham Jan 31 '15 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 understand to require that the hash is effectively pseudorandom. So I think your criticism is debateable. 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. Feb 1 '15 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 Feb 7 '15 at 14:49

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.