How can I make something that is fast for the server to compute, but slow for the client to compute?

Something that would take the server a few milliseconds or less to compute, and take the client a few hundred milliseconds?

The server would create a challenge, send it to the client, the client would compute the answer and send it to the server, then the server would verify the answer.

UPDATE: Why? The server has a function that uses significant processing power. I don't want a clie开发者_运维问答nt to be able to maliciously overload the server by simply sending 100s of requests per second to this function. By requiring an answer to the challenge, an attacker can only send requests as fast as they can compute the answers.

Let me start by saying I think you are headed down the wrong road.

With that said, one way to do what you are describing would be to put together a simple puzzle that is brute forcible by the receiving end. For instance, you could send the hash of a 3 or 4 character password (solved reasonably quickly), the client is required to figure out the password (by brute force) and send it back (possibly encrypted with a pre-shared key if you are trying to authenticate).

Please understand that this will not prevent anyone from maliciously overloading the server. A malicious attacker can still just disconnect once they've received the puzzle (without solving it) and connect again. If the attack is distributed, it gets even worse.

EDIT:

@Nick Johnson is right. You want to also include a random salt to prevent precomputation attacks. Send the salt along with the hash. It gets concatenated with each password that the client tries.

What you're asking for is called a "proof of work". Here's a really simple one:

1. The server generates a random nonce, n, and picks a number of bits, b, and sends both to the client.
2. The client calculates h = sha1(n + x), where x is an arbitrary suffix, and h ends with b '0' bits.
3. The client sends x back to the server as a proof-of-work.

This works because predicting the output of a secure hash function is difficult, so your only option is brute force. If the server asks for one with b trailing 0s, one average one in 2^b hashes will meet that criteria, meaning they will have to do on average O(2^(b-1)) work.

One caveat to this approach: If you're dealing with a web client, you need to make the proof of work easy enough that it's doable quickly in Javascript. But javascript is slow compared to native code, and your attacker will be able to write native code to compute the proof of work much faster - so he has a substantial advantage over your legitimate clients.

The standard alternative, as unpleasant as it is, is to require a CAPTCHA.