6
$\begingroup$

My hashing algorithm computes the SHA-256 for each of 12 input strings and XORs them to get the final hash.

Is there a risk of an attacker being able to forge 2 sets of inputs that yield the same final hash?

To avoid trivial attacks by feeding in the same input twice and make this scheme order-dependent, I prepend each input with its index (binary 0 to 11).

For the case of 256 inputs there is an easy attack (as each hash can be used to control a single output bit using matrix calculus), this makes me wonder whether there are similar attacks for just 12 inputs.

I'm aware that there are more secure alternatives such as Merkle trees but I really need maximum performance especially for when just a single input is modified.

Improve this question
$\endgroup$
9
  • $\begingroup$ If you never do partial verifications (i.e., always compute all twelve), I don't see an immediate problem (but I didn't think longer than 12 seconds). When you decide to rely on an attacker supplying you partial data though, you have trivial forgery. $\endgroup$
    – Ruben De Smet
    Commented Jul 6, 2019 at 16:41
  • $\begingroup$ @RubenDeSmet I don't understand what you mean by partial data and how that could lead to forgery, can you please elaborate on that? $\endgroup$
    – Kabuto
    Commented Jul 7, 2019 at 8:37
  • $\begingroup$ Suppose an attacker sends you twelve hashes $h_1, \dots h_{12}$ and their xor $x=h_1\oplus \dots h_{12}$. If you have no way to verify that the attacker has $x_1,\dots,x_{12}$ s.t. their hashes match $\forall i: h_i=H(x_i)$, then the attacked may as well have lied about one or more of the hashes, because he can perfectly compute the hash from the XOR $x$ with which the adversary wants a collision. It's not a full collision, so probably doesn't matter to your case. $\endgroup$
    – Ruben De Smet
    Commented Jul 8, 2019 at 6:56
  • 1
    $\begingroup$ If an attacker generates and hashes 2^11 candidate strings for each of the 12 positions, there are enough combinations of them to that they're very likely to contain a collision. I can't think of an efficient way to find the combinations that collide, but I also don't see why an efficient search shouldn't exist. $\endgroup$
    – Gordon Davisson
    Commented Jul 8, 2019 at 7:09
  • 1
    $\begingroup$ @GordonDavisson Good point, thanks... thinking about it I found a weakness, I added it to the question $\endgroup$
    – Kabuto
    Commented Jul 8, 2019 at 11:32

2 Answers 2

Reset to default
1
$\begingroup$

Let tne hashlength be $d$. With $k=12,$ this is the $k-$ XOR problem. Fix $k.$ If the vectors are randomly generated and form a list of size roughly at least $2^{d/k},$ there exists a solution with constant probability bounded away from zero. This is because a list of size $M$ contains $$F:=\binom{M}{k}$$ subsets of size $k,$ and thus as $\{x_1,\ldots,x_k\}$ ranges over these subsets the function $f(x_1,\ldots,x_k):=x_1\oplus \cdots \oplus x_k$ ranges over $\{0,1\}^d.$

This is a $F$ balls into $2^d$ bins problem and if $F\geq 2^d,$ the probability that $f$ misses the bin corresponding to your given hash value $h_0 \in \{0,1\}^d$ is roughly $e^{-1}\approx 0.37.$ Taking $M=\Omega(k 2^{d/k})$ is enough here. However, finding the solution is computationally more expensive.

Wagner (see here ) has a recursive binary tree based algorithm for the $k-$ XOR problem $$x_1\oplus \cdots \oplus x_k=0 \qquad (1)$$ with $k=2^m,$ with time and memory complexity essentially $$O(k 2^{d/(1+m)}).$$ The zero vector on the right hand side of (1) can be replaced by any constant vector.

Let $x_9,\ldots,x_{12},$ be arbitrary and use Wagner with $k=8$ to solve the $8-$ XOR problem

$$x_1\oplus \cdots \oplus x_8=c,$$ with $c=x_9\oplus x_{10} \oplus x_{11} \oplus x_{12}\oplus h_0.$ This can be done with complexity $$O(k 2^{d/(m+1)})=O(8 \times 2^{256/4})=O(2^{67}).$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Good solution, but I see room for improvement. I'm specificially looking for a collision of 2 input vectors a and b, i.e. h0(a0) ⊕ ... ⊕ h11(a11) ⊕ h0(b0) ⊕ ... ⊕ h11(b11) = 0, this could be solved with Wagner's algorithm with 16 inputs which is more efficient than your choice of using 8 inputs. Also, since 2 input lists each are identical, we can make the final Wagner stage get 2 identical inputs, thus skipping half of the computation effort, and the final stage itself a simple list search (though it would need to be longer by a factor of sqrt(2) to find the same number of collisions). $\endgroup$
    – Kabuto
    Commented Jul 11, 2019 at 12:08
  • $\begingroup$ Also, since Wagner's scheme is only well-suited for input counts that are powers of 2, we can use the remaining 8 inputs for improvements. I couldn't see how anything in the 3XOR paper mentioned by lacker could be applied; but similar to how 256 inputs could be used for trivial preimage attacks (resp. 128 inputs for trivial collisions) through matrix transforms, those 8 remaining inputs can probably be used for building a matrix transform that simplifies this task to finding a collision on 248-bit hashes as the 8 additional bits can then effectively be controlled using these 8 inputs. $\endgroup$
    – Kabuto
    Commented Jul 11, 2019 at 12:10
  • $\begingroup$ ok, now i see i misread your problem statement, and you are right, you can apply the 16 input wagner. $\endgroup$
    – kodlu
    Commented Jul 11, 2019 at 22:38
0
$\begingroup$

This seems like a version of the 3XOR problem. Roughly speaking, the 3XOR problem is whether there is a faster way to detect xor collisions from pseudorandom sets of bit strings than just iterating through all the possibilities. Currently there are some speedups but not enormous ones, but it's still an open question.

For more information see: https://hal.inria.fr/hal-01655907

If a better algorithm was discovered for 3XOR, you could use it to crack this by generating a small number of SHA256's and finding xor collisions. Based on the uncertain state of that problem alone, I wouldn't use this for cryptographic purposes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.