0
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ How far have you gotten so far? $\endgroup$
    – poncho
    Commented Dec 23, 2014 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$
    – 0xh8h
    Commented Dec 23, 2014 at 16:16
  • $\begingroup$ What 89 bit string would you be brute-forcing? You know R1... $\endgroup$
    – poncho
    Commented Dec 23, 2014 at 17:52

1 Answer 1

Reset to default
0
$\begingroup$

$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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wouldn't you really just need $2^{40}$ guesses on average? $\endgroup$
    – Guut Boy
    Commented Dec 26, 2014 at 16:07

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.