Let $F$ be a PRF.

The $XOR\text{-hash}$ is defined as:

XOR-hash(k, m):    //m=(a₀, a₁, ..., aᵥ)
    t = 0ⁿ
    for each aᵢ ∈ m:
        t = t ⊕ F(k, aᵢ)
    return t

Suppose an attacker $\mathcal{A}$ can send 3-uples $(m_0, m_1, \delta)$.

A function $f$ will be difference-unpredictable if $\mathcal{A}$ cannot guess a 3-uple such that $f(k,m_0) - f(k,m_1) = \delta \;$ with more than negligible chance.

How can I show that $XOR\text{-hash}$ is difference-unpredictable?

I think the argument relies on the fact that $\oplus$ keep all the bits pseudo-random, so that the difference $d$ will look like a subtraction of two random results, hence the probability of some bit of $d$ match some bit of $\delta$ will be $\small\sim$$0.5$ and the probability of $d = \delta$ would be negligible.

  • 1
    $\begingroup$ I assume $m_0$ and $m_1$ must be distinct. $(0 \mathbin\Vert 1, 1 \mathbin\Vert 0, 0)$? $\endgroup$ – Squeamish Ossifrage May 15 '18 at 3:32

You cannot prove that this is difference unpredictable since it is not. Take $\delta=0$ and set $m_0=(a_0,a_1)$ and $m_1=(a_1,a_0)$.

  • $\begingroup$ That's true... I was trying to prove it was unpredictable and I forgot to think about a counter-example to show that it could not be proved. $\endgroup$ – Daniel May 15 '18 at 14:56

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.