1
$\begingroup$

I am having trouble trying to understand if the function is collision resistant. As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the same digest, and second preimage resistance means it is hard for an adversary to find a message that produces the same digest for a given digest. And collision resistance just implies both things. So for the following problem, I don't understand how I would determine if the function exhibits any of the resistances?

The function f(x1,x2,...,xn) = x1 ⊕ x2 ⊕ ... ⊕ xn takes an input of n blocks, each m bits long, and produces an output of length m bits. Is this function: preimage resistant, second preimage resistant, or collision resistant?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the same digest

Nope: collision resistance means that it is hard for an adversary to find two (distinct) messages that produce the same digest. Preimage resistance means that, given a hash output, it is hard for an adversary to find a message that hashes to that value.

second preimage resistance means it is hard for an adversary to find a message that produces the same digest for a given digest.

Close; second preimage resistance means that, given a message, it is hard to find another message that hashes to the same value.

Is this function: preimage resistant...

Let's consider this; suppose we get a target value $M$; how hard is it to find inputs $x_1, x_2, ..., x_n$ with $f(x_1, x_2, ..., x_n) = x_1 \oplus x_2 \oplus ... \oplus x_n = M$ ? Hint: suppose we select $x_2, ..., x_n$ to be 0, how difficult would it be to find an $x_1$ with $f(x_1, 0, 0, ..., 0) = M$?

Improve this answer
$\endgroup$
1
  • $\begingroup$ So x1 would just be 0 as well. So this would be similar if there were two x's, x1 and x2, and they were the same because then that would XOR to 0. Therefore, this function isn't collision resistant. But does preimage resistance and second preimage resistance imply collision resistance? Also, from what you said, I think that the function is second preimage resistant, but like I said earlier, if you XOR the same number it XORs to 0 which means that the function is not preimage resistant? $\endgroup$
    – winsticknova
    Commented Feb 10, 2016 at 5:22

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.