Provably fair Heads or Tails: hash collisions

Let's recall our provably fair Heads or Tails protocol:

• Assume an agreed upon seedable random generator and bet amount.
• The casino selects a random seed part \(s_C\), and sends its signed hash to Alice, along with a proof that twice the bet amount has been put in escrow. This is the commitment.
• Alice concatenates a random seed part \(s_A\) to the commitment, signs the result, and sends it back to the casino, along with her bet money.
• The casino seeds the random generator with \(s_A \oplus s_C\), tosses the coin and either pays Alice or keeps her bet money.
• The casino reveals \(s_C\) to prove the fairness of the toss.

We have already seen how Alice could exploit the fact that the hash function may not truly be a one-way function.

A weak hash function can also benefit the Casino.

Finding the argument to a hash function which results in a specific hash is very difficult, even for algorithms obsoleted decades ago. For example, to the best of my knowledge, as of <2025-01-03 Fri>, it is still practically infeasible to do pre-image attacks on MD5 and MD4.

However, the birthday paradox makes it so it is actually quite easy to find a collision, where you don't care about the actual value of either of the colliding arguments. SHA1, which is used by git, is broken this way.

If the casino can easily find collisions, i.e. two values \(s_{C_1}\) and \(s_{C_2}\) whose hash is the same, then it stands a better than half chance that one of the two seeds \(s_A\oplus s_{C_1}\) or \(s_A \oplus s_{C_2}\) yields a victory for itself and a defeat for Alice.

It can then reveal the winning \(s_C\) without Alice being aware of the existence of another \(s_C\) which may have yielded a victory for her.

It is therefore important to use a very secure hash function.