What is a cryptographic puzzle?

Question

On the wikipedia page on TCP under Denial of Service the following paragraph is found:

By using a spoofed IP address and repeatedly sending purposely assembled SYN packets, attackers can cause the server to consume large amounts of resources keeping track of the bogus connections. This is known as a SYN flood attack. Proposed solutions to this problem include SYN cookies and cryptographic puzzles.

I am interested in learning more about cryptographic puzzles. I assume that it is some task the server can send back to the client before it will proceed with establishing the tcp connection. This task probably has the property that it takes a lot of resources to find the solution, but it is easy to check if a solution is valid (for the server.) Is this correct? (Kind of like what is proposed for spam-mitigation.)

Where can I read more about cryptographic puzzles? Googling the term does not return anything useful, neither are there any wikipedia pages with that name.

Are there any software libraries readily available for creating and solving these puzzles that I can use?

Answer 1

Your guess is head-on. Proof of Work may be a more useful search term: http://en.wikipedia.org/wiki/Proof-of-work_system

To my knowledge, there are mainly patent issues that prevent these systems from being used in modern Internet protocols like IPsec/IKE/SSL. I also heard from some researchers that in their practical evaluation, there was basically zero gain from deploying such protocols to prevent DoS on a typical key exchange protocol. But it could be that they had other scalability issues. Would be interesting to see some real-world evaluation.