Reference Document: https://eprint.iacr.org/2016/027.pdf

According to appendix D section 4 definition 27

each vertex in V has predecessors sampled independently and uniformly at random from the set U

It appears from the pseudo-code in section 3.1 step 2b, and the reference code given on GitHub hash_state_mix(), that this has been implemented by the authors as some form of squeezing bits out of the hash function; however my question is could it just as easily have been done with Mersenne Twister or is there another reason why the hash is required?


1 Answer 1


If you use the Mersenne twister or any other non-cryptographic PRNG, then it is conceivable that an adversary could exploit some pattern in the Mersenne twister's outputs to find a shortcut to reversing the resulting hash. Cryptographic PRNGs are designed so that despite decades of efforts, cryptanalysts have been unable to find any patterns in their outputs that are even detectable, let alone exploitable in context.

Don't use the Mersenne twister! It's also bad as a non-cryptographic PRNG because it is expensive to initialize and requires a multi-kilobyte state, so it discourages parallelism and reproducible subtrees of computations.

  • $\begingroup$ I'm not so sure that the PRNG in this case must be a CS one since the only thing the PRNG does is select which blocks to pull out; however Mersenne Twister as you point out has other issues which makes it a poor choice. Is there maybe another low-overhead PRNG that's uniformly random over uint64_t $\endgroup$
    – Gregor y
    Jun 12, 2019 at 2:14
  • $\begingroup$ @Gregory What motivates you to change the PRNG? Any change to a non-cryptographic PRNG requires careful analysis to determine whether it affects security, and renders your balloon-hash variant incompatible with everyone else's idea of balloon-hash. $\endgroup$ Jun 12, 2019 at 2:26
  • $\begingroup$ The lack of implementation documentation. As far as I can tell the PRNG used is hash(salt)[i..i+d];i+=d+1, but what happens when d runs off the end? $\endgroup$
    – Gregor y
    Jun 12, 2019 at 2:33
  • $\begingroup$ besides it's already going to be 'incompatible' because in the GitHub code: neighbor % s->n_blocks has pigeonholes $\endgroup$
    – Gregor y
    Jun 12, 2019 at 2:54

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.