2
$\begingroup$

Let $h$ signify the hash (Merkle–Damgård construction) generated from some input of known length $n$. Given $h$ and an input $k$ of length $n_1$, is there a way to prove that there exists (does not exist) some (any) $r$ of length $(n-n_1)$ such that $h=H(r||k)$?

$\endgroup$
2
$\begingroup$

It depends on what exactly do you ask for:

  1. You know such $r$ that $h$=$H(r||k)$ and want to provide someone proof that you know it or
  2. You have only $h$, $H$, $n$ and $k$ and you want to check if $r$ exists

First case should be possible with something like zkSNARKs.

In second case there's no way to do it in polynomial time for any $H$ that is second-preimage attack resistant. Proof:

Let $n_a$ means bit length of $a$. We have some secret input $M$ and $h=H(M)$. Let's assume there exists algorithm $A(H, h, n, k)$, polynomial in terms of security parameter $n$, that :

returns $1$ if there is $r$ such that $h=H(r||k)$ and $n_r=n-n_k$

returns $0$ otherwise.

We can use $A$ to efficiently create collision with $M$ with the same length. In pseudocode:

$M' = \{\}$

for each $1\le i \le n$ do: $M'=A(h, n_M, 1||M')||M'$

After that you have $M'$ that satisfies $H(M')=h=H(M)$ and $n_{M'}=n_M$. So $H$ wouldn't be second-preimage attack resistant.

You can of course iterate through every value of $r$ and check if $h=H(r||k)$ but that takes $2^{n_r}$ steps (in case there's no such $r$).

$\endgroup$
  • $\begingroup$ Thanks for the clarification. I was looking for the second case. $\endgroup$ – robinw Jan 21 '18 at 3:57

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.