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?