Client Puzzles and HMAC

Question

I'm learning about client puzzles for DoS (Denial of Services) Protection, and I came across this question.

For each request, the server sends the client a freshly generated random challenge r and and a difficulty parameter n, and the client has to produce a solution s such that HMAC(s) with key r ends in n zero bits."

What is the expected number of HMAC computations for the client to compute the solution, and the server to check the solution?

I know that the server only needs to compute 1 HMAC, as it has s, r and n. So it would just take the clients solution s, and compute the required HMAC, and see if it has the required number of zero bits at the end.

How would I calculate the answer for the client? I assume the client has to brute force it, so he would keep calculating an HMAC until he gets the required n zero bits at the end. How do I do this computation?

Answer 1

Here is a small scheme how this works :

 Server         Client
   |              |
   |     r,n      |  S: Find s such as HMAC(s,r) = xxxx0000
   |  ==========> |   
   |              |  C: *compute HMAC(0,r) = 123456789*
   |              |  C: *compute HMAC(1,r) = 124687946*
   |              |  C: *compute HMAC(2,r) = 164946518*
   |              |  C: *compute HMAC(3,r) = 165498451*
   |              |  ...
   |              |  C: *compute HMAC(42,r) = 16540000*
   |              |  
   |    s = 42    |  C: Found it ! s is 42
   | <=========== | 
   |              |  S: *compute HMAC(42,r) = 16540000*
   |      OK      |  S: Ok, access granted for you !
   |  ==========> |   
   V              V  

As an example, lets assume you want only the last digit to be 0. What are the chances if you were to compute the HMAC for a random number ? well $\frac{1}{10}$. So if you try 10 random numbers, the chances that you got at least one HMAC ending with 0 is pretty decent:

$P = 1 - ((1-\frac{1}{10})^{10}) \approx 65\%$.

However, the more 0 you ask at the end the harder it will be to find a solution. e.g. if you were to ask for 4 zeroes at then end, the chances that you would find $s$ after 1000 trials are :

$P = 1 - ((1-\frac{1}{10000})^{1000}) \approx 9,5\%$.

And after 10000 trials :

$P = 1 - ((1-\frac{1}{10000})^{10000}) \approx 63\%$.

Thus simply by increasing the number of zeros demanded, you increase a lot the time required to find the solution.

Why it is "secure", because you change the $r$ at each tentative. Therefore the client cannot pre-compute the solution.