I have a problem that I don't know how to solve

Assume that H is a cryptographic hash function with output size 80 bits. Assume that ABC123 is a specifically designed line of hardware chips for computing H. where ABC123 can create 10000 hash values a second. This product line is the best, fastest and affordable, in the market, priced at 1000$. Consider the following Bit-Commitment protocol which is used for applications in betting in football matches.

  1. A create R1 and R2 as 2 random binary strings with length 48 bits and 40 bits, respectively
  2. A send host B: M = H(R1 || R2 || b) || R1
  3. To announce bit b, A send host B: (R2, b) (b is a bit, 0 or 1, that A choose indicate that a football team win or lose, for simplify)
  4. B check validity by re-hashing H(R1 || R2 || b) and comparing with the value received from step 2

Question: how much money the host B has to invest in order to correctly guess b in 5 minutes?

Thank you very much. Any help is appreciated!

  • 1
    $\begingroup$ How far have you gotten so far? $\endgroup$ – poncho Dec 23 '14 at 16:02
  • $\begingroup$ I've thought of brute force attack on 89 bits string. And to find at least 1 collision (can't use Birthday principle), so it need 2^89 + 1 time to hash. But it's still an enormous number. And it's just to find a collision, not the bit b exactly $\endgroup$ – Hoang Trinh Dec 23 '14 at 16:16
  • $\begingroup$ What 89 bit string would you be brute-forcing? You know R1... $\endgroup$ – poncho Dec 23 '14 at 17:52

$M = H(R_1 || R_2 || b) || R_1$

You already know $R_1$ and you need to find $R_2$ and $b$.

$R_2$ is 40 bits long and $b$ is 1 bit, so you need on average $2^{41}$ guesses to find $R_2$ and $b$ which will give the hash you want.

You know that each chip can do 10,000 hashes per second, so you need to find out how many chips you'll need to do $2^{41}$ hashes in 5 minutes.

$\dfrac{2^{41}}{300seconds} = 7,330,077,518.51 hashes/second$

Since each chip can peform 10,000 hashes per second, we need

$\dfrac{7,330,077,518.51}{10000} = 733,008$ chips (rounded up)

At \$1000 per chip, that is \$733,008,000

  • $\begingroup$ Wouldn't you really just need $2^{40}$ guesses on average? $\endgroup$ – Guut Boy Dec 26 '14 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.