According to the documentation of HighwayHash, for finding a collision are expected $m \over 2$ guesses, being $m$ the message.

By contrast, 'strong' hashes such as SipHash or HighwayHash require infeasible attacker effort to find a hash collision (an expected $2^{32}$ guesses of $m$ per the birthday paradox) or recover the seed ($2^{63}$ requests). These security claims assume the seed is secret. It is reasonable to suppose $s$ is initially unknown to attackers, e.g. generated on startup or even per connection.

They are talking above about a keyed hash function with input/output of 64-bits, having the key the same size.

But what if a hash a message of 32-bits in size and a 32-bits key, and keep the message and the key secret, does the effort for finding a collision is $m+k \over 2$? $m$ is the message, $k$ is the key?

What would be the formula to calculate the expected numbers of guesses of key + message for finding a collision?

  • $\begingroup$ You are conflating the terms key / key size and message / message size. What's the point of finding a collision under a different key? Are you looking for a key commitment scheme? $\endgroup$
    – Maarten Bodewes
    Mar 19, 2023 at 8:36
  • $\begingroup$ @MaartenBodewes Yes, I'm looking for that. If you know how to answer I would appreciate. I'm thinking on a cryptographic scheme in which the point is to have a myriad of collisions to lure an adversary. I would like to know if key+message in hash functions share the same propriety, collisions. Thanks. $\endgroup$
    – alpominth
    Mar 19, 2023 at 20:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.