3
$\begingroup$

Question: Are multiple outputs of a Merkle-Damgård hash function (or specifically SHA-256, if this can only be said for a specific algorithm) on unknown data unlinkable? If yes: Can this be formally proven or only said "from experience" / on a basis of "no attack has been found yet"?

Bonus question: Does anything change if we use a sponge-based hash function like SHA-3 / Keccak instead?

Example: $x$ and $y$ are initiated with random values and kept secret.

Let: $r_0 = h(x||y)$,
$r_1 = h(x||y+1)$,
...
$r_n = h(x||y+n)$.

If $h$ is a Merkle-Damgård hash function like SHA-256, are any two $r_a$ and $r_b$ (for $a,b \in [0,n]$) unlinkable, using the definition by Pfitzmann et al.:

Unlinkability of two or more items of interest [...] from an attacker’s perspective means that within the system (comprising these and possibly other items), the attacker cannot sufficiently distinguish whether these IOIs are related or not.

Background: I've been reading up on random oracles and found a proof in the random oracle model for a system I am building for my master thesis. One of the first things you learn about the random oracle model is that you cannot instantiate the random oracle with a Merkle-Damgård hash function due to the length extension attack.

Assume the system I am building is not susceptible to length extension attacks (the inputs are constant-length and hashed twice), and the property I am interested in is not "the output looks like perfectly random data" but only "the output of multiple iterations of my algorithm is unlinkable". I am currently wondering if I can instantiate the random oracle with a Merkle-Damgård hash function like SHA-256 in this case without loosing the security proof for the unlinkability, or if I have to fall back to the uncomfortable position of "rel[ying] on the fervent hope that the parts where the actual function is not a random oracle do not impact security".

My current intuition would be that, from experience, the output should be unlinkable, but there is no way to formally prove it. However, any input (ideally with citable sources) would be appreciated.

Edit: This is related to this question, and an alternative way to formulate the unlinkability goal would be correlated-input secure, or more accurately selective correlated-input indistinguishable and -pseudorandom, as defined in the linked paper. So, this may be more of an open research question than I had initially assumed. Still, if someone has an answer I missed, feel free to add it.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ The point of "unlinkability" in this case would be that if I use $r_0$,...,$r_n$ in a key-value-store, the store itself could not tell if they were all generated by the same person and belonged together (hence unlinkability). I'm using the definition of Pfitzmann et al (§4). $\endgroup$ – malexmave Mar 13 '16 at 17:14
  • $\begingroup$ @malexmave If you add the unlinkability tag, the least you could also do is to provide a clear wiki entry for it. As far as I'm concern. I don't think it is worth it to add such tag. :/ $\endgroup$ – Biv Mar 23 '16 at 15:00
  • $\begingroup$ Why only the Merkle-Damgård construction ? If I take MD5, this satisfy your condition, and given it is broken... In my opinion, this is similar to the DDH problem. $\endgroup$ – Biv Mar 23 '16 at 15:14
  • $\begingroup$ @Biv: Thank you for your edit. However, the equation you wanted to edit in did not match what I wanted to achieve (at least in my understanding). I edited your edit to clarify things further and hope that it is now clear what my goal is. $\endgroup$ – malexmave Mar 23 '16 at 15:18
  • $\begingroup$ @Biv: I also proposed a tag wiki for the unlinkability tag, which is waiting for review now. Thanks for pointing this out to me. $\endgroup$ – malexmave Mar 23 '16 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.