There are a wide variety of challenge/response protocols used in computer security. Many of them, however, have the unfortunate disadvantage that they require significant CPU time to issue each challenge or evalutate each response, they require the server to keep track of each challenge issued, or both.
In most cases, such resource utilization would not be a problem. Unfortunately, if a server is being hit with a denial-of-service attack, a protocol that requires significant resources may easily overwhelm even a powerful server.
To avoid this problem, I would suggest equipping servers with a preliminary security layer which would require that a client wishing to connect perform a certain amount of work before the server will allocate any persistent resources or spend too much time on authentication. Once the client performed that amount of work, it would be allocated some server resources and allowed one attempt to enter the main security system.
The protocol would require the definition of a fast, non-invertible function f(n) which would hash 64 bits of data, yielding 64 bits of hash. The actual specifics of such function are not relevant here beyond the fact that it should be fast and non-invertible. The protocol would also require a means of generating unpredictable 64-bit random numbers on an occasional basis. There would be some global state variables to keep track of how many intrusion attempts there have been recently; these would be distilled into a value 'k' which would increase when there were too many intrusion attempts that passed preliminary security and decrease when there were not. Depending upon the complexity of the hash function and the amount of intrusion, 'k' might range from 8 to 24 or so.
Once per second, the protocol handler would generate a 64-bit random number and store it in a table using a 16-bit index. The items could be stored in slot 0, slot 1, etc. wrapping at some convenient number, or in any other order desired.
When a computer asks to connect to the server, the server should xor the IP of the client with the last random number and compute the hash of that (call this H1). The server should compute the hash of H1 (called H2), clear the rightmost 'k' bits of H1, and set the (k+1)th bit. Finally, it should send the index of the last random number, H1 (as altered), and H2. Once it has done these things, need remember nothing about the request.
The client should take the received H1 value and try different values for the least-significant bit until it finds a value which, when hashed, yields H2. It should send the server a packet containing the index and the H1 value it found.
The server will then take the index, find the appropriate random number in the table, xor it with the client IP address, and hash it. The result of that hash should match what the client sent.
The preliminary security layer would not be designed to be invulnerable, but rather to minimize the effect of denial-of-service attacks. The expectation would be that the server could afford to allocate resources every time an intruder got through the first layer, provided that didn't happen too often; there would be a big difference between having to allocate resources to a few bogus connection attempts per second, versus allocating them for many thousands.
Responding to a challenge request would only require computing two hashes; validating a response would require one. The time required for the server to handle the requests would be independent of 'k', even though the client-side time required would increase exponentially.
If it was deemed acceptable for the server to be confronted with 100 packets/second that pass the first layer, and it was acceptable to force a user to take a minute for authentication during a denial-of-service attack, an attacker would have to have 6,000 times as much computing horsepower as a legitimate user in order to prevent those targets from being met. Although some attackers would be able to muster that sort of power against some targets, it would almost certainly be beyond the abilities of most "script kiddies".