What challenge should I use in a challenge-response proof-of-work?

Question

In order to guard against denial-of-service attacks, I want to require clients to do some work (more work than the server does fulfilling the request) before talking to them.

1. Client connects

2. Server sends a challenge, including a piece of data

   "Find bytes x such that hash(challengeData + x) has n zeros at the beginning"

3. Client finds x, sends it to the server

4. Server verifies that hash(challengeData + recv()) has n zeros at the beginning

5. The actual request is handled

I found a few different methods to generate this "challengeData" thing, and some problems with each of them:

• Random bytes

  Here, the client can just exhaust the server's PRNG by repeatedly connecting to it. Which brings us back to square one (denial of service).

• Current time of day

  This seems like a good idea to me, but I'd like to know what attacks you could have against it.

• A string involving something dependent on this particular request (like hashcash)

  In order to make sure evil connections are dropped as soon as possible, I'd like to avoid handing anything about the request before making sure the client has done some work. The idea is that the client should always do much more work than the server before it starts handling the request.

I have some constraints: firstly I'd like the server to be completely stateless. I don't want to save "hashcash" and make sure it isn't spent twice, instead I want to challenge the client to do work that, inherently, can't be pre-computed. Secondly I don't want to know anything about the request itself at this stage (such as authentication). This is so the server sends and recieves as little data as possible. For instance, the current time (nanosecond or millisecond precision, depending on the OS, hardware and implementation) is 8 bytes (a double), and 2^64-1 tries (i.e. an 8-byte response) should be more than enough before resetting the connection (for the foreseeable future).

In short:

• What properties does this challenge need to have?
• What easily generated data has all of these properties? Is the current time any good?

As usual when I ask something about protocol-design, this may well be reinventing the wheel. If there are any existing protocols that do this, I don't know about them yet.

Answer 1

Using time of day is predictable. Challenges should be unpredictable to an adversary. If they were not (as you sort of say), the adversary could solve a set of challenges ahead of time and then use them in rapid succession to cause a DOS. You want to meter access to the service, which is about not only ensuring clients do some work, but that work is done at the time they want to connect. Similarly, challenges should time-out after a certain period of time.

That said, it is fine to include the time as one parameter (as well as any other connection details) that goes into constructing the challenge to ensure the answer is timely.

I would construct the challenge by combining (eg hashing) the date with a randomly generated nonce (PRNGs won't repeat in the lifetime of the universe). If you then MAC the challenge with your secret key, you won't have to record the value of the nonce. The client should return the date, nonce, challenge, solution, and MAC. The server will verify the date is within a valid time period, the date & nonce generate the challenge (finding a different date & nonce reduces to finding collisions in the hash function), the MAC on the challenge is valid (using your secret key), and the solution to the challenge is valid.

In this case, the only "state" the server needs to retain is a clock and secret key, which is constant overhead independent of the number of connections. It does increase the communication complexity (number of components sent to and from the server) though.

This is a much simplified version of the stateless protocol in this paper, which you can use for stronger security guarantees.

You may also consider using a different puzzle then the hash-based one. Hash-based puzzles are trivially parallelizable. There are ones based on modular exponentiation/repeated squaring that are inherently sequential. See this recent paper and the cited related work for more.

Answer 2

A good PRNG can't be exhausted, so your argument against random bytes doesn't matter.

firstly I'd like the server to be completely stateless.

Sounds impossible to me.

1. a PRNG needs state. A clock needs state.
2. An open connection is state too
3. You probably want to store open challenges too. This part isn't strictly necessary, but very convenient.

---

You might also want to include something unique to the server in the challenge(for example its domain or IP address) so clients can't be tricked by one server into solving the challenge for another.

I'd go with the server sending 16 random bytes as challenge, and the client responding with something like ServerIP || HMAC(proof, Challenge || ServerID)