3
$\begingroup$

What are some examples of an iterative hash function, where permutations along

A ---> B ---> C ---> D

can be compared, for example D/B, to see if D is a trail from B, and possibly the distance in steps from C to D

$\endgroup$
1
  • 2
    $\begingroup$ I guess you can use any hash function, you just try to hash B Until you get D and count the number. $\endgroup$
    – eckes
    Nov 13, 2017 at 7:16

1 Answer 1

2
$\begingroup$

SHA-256 or any at least as wide unbroken cryptographic hash will do, if the elements can be that wide (except the first A which is unconstrained). With a $w$-bit ideal hash, probability of entering a cycle in $n\ge1$ steps are $p<n^2/2^{w+1}$, by the Birthday problem. E.g. $w=256$, $n\le2^{100}$ gives residual odds of entering a cycle $p<2^{-57}$, and that's good enough in practice.

Things are not quite as easy when $w$ must be smaller; e.g. for $w=160$. In this case, we want a hash function less likely to iterate than random; that's not a common beast (to be continued after thinking about it).

$\endgroup$

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.