How to estimate the collision resistance of a hash function if a secondary key is used (keyed hash function)?

alpominth

3/17/24, 11:15 PM

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?

0 + 2

collision-resistance

Maarten Bodewes

3/19/24, 8:36 AM

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?

alpominth

3/19/24, 8:52 PM

@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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to estimate the collision resistance of a hash function if a secondary key is used (keyed hash function)?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.