1
$\begingroup$

For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$ where $\log_2(T)$ is length of hash output. Then, what would be the number of queries requried to find an $n$-collision ($H(A_1) = H(A_2) = ..... = H(A_n)$).

$\endgroup$
2
  • $\begingroup$ Is this a Merkle-Daamgard hash, or a generic hash? For MD hashes (at least, the ones without output truncation), there are known ways to compute multiway collisions faster than expected. $\endgroup$
    – poncho
    Dec 13 '14 at 5:01
  • $\begingroup$ Consider this as an ideal hash function. Generic. $\endgroup$ Dec 13 '14 at 5:02
5
$\begingroup$

is $T^{1-1/n}$


Proof:

Suppose we have a sample set $M$, with $|M| = m$. We choose a set $N$ with $|N| = n$ among the set $M$, which is $O(m^n)$ (you know $O(m^n)=m\cdot(m-1)\cdot...\cdot(m-n+2)\cdot(m-n+1)$). In particular, we suppose $A_1, A_2, ...., A_n$ make a $n$-collision $H(A_1)=H(A_2) , H(A_2)=H(A_3) , ... , H(A_{n-1})=H(A_n)$ just as you want. Since each one of these $n-1$ events happens with probability $1/|T|$, the probability that a particular set $N$ chosen from $M$ is a $n$-collision is $O(1/|T|^{n-1}))$.Using the union bound, the probability that some set $N$ is an $n$-collision is $O(m^n/|T|^{n-1})$ and since we want this probability to be close to 1, the bound on $m$ is $T^{1-1/n}$

$\endgroup$
2
  • $\begingroup$ The answer is fine if we are content with the statement's For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$. $\;$ But this is less than precise; rather, the number of queries to reach an $n$-collision with odds $1/2$ (or any fixed probability in range $]0,1[$ ) is $\mathcal O(T^{1-1/n})$ when $T$ goes to infinity. $\endgroup$
    – fgrieu
    Dec 14 '14 at 15:39
  • $\begingroup$ The exact work factor is worked out in Suzuki et al: $(n!)^{1/n}\cdot T^{1-1/s}$. $\endgroup$ Dec 17 '14 at 2:38

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.