Cryptographic puzzles are a method of protecting against DoS attacks. The idea behind cryptographic puzzles is the following: for a client to connect to a server under attack, he must solve a mathematical puzzle. The difficulty of the puzzle will be directly proportional to the number of connections initiated by the client. Thus, a legitimate client will not notice a big difference when connecting to a server, while an attacker will connect more and more slowly. The idea of the cryptographic puzzle belongs to Merkle, but Merkle used cryptographic puzzles to set keys.
Cryptographic puzzles have been used to counteract attacks on TCP/IP by Juels and Brainard, who has mentioned that SSL can be protected similarly. Aura, Nikander, and Leiwo applied cryptographic puzzles to authentication protocols in general. They describe how the cryptographic puzzles proposed by Jules and Brainard can be used to prevent DoS attacks. In their paper, he states the following design principle: the client must first use his resources in an authentication process and the server must be able to check the client before allocating his own resources. The main rule is that at each point before authentication, the cost of running the protocol on the client is higher than the cost of running the protocol on the server.
Cost per customer may be artificially increased by being required to resolve cryptographic puzzles that are easy to generate but whose difficulty solving can be adjusted at any level. The server must refuse to perform any complex cryptographic operations until it verifies the validity of the client’s solution to the cryptographic puzzle. Dwork and Naor presented the cryptographic puzzles as a general solution to controlling the use of resources, especially to control spam. Their scheme has developed in a different direction, primarily motivated by their desire to use a shortcut to solving their puzzles when using a secret password. Frankyn and Malkhi used cryptographic puzzles based on inversion of powerful hash functions for use in web traffic monitoring applications.
A first study of the Cryptographic Puzzles study to prevent DoS attacks is that of B. Waters. In their paper there is a method of distributing cryptographic puzzles through a robust external service, which they call a bastion. Many servers can rely on puzzles distributed by a single bastion. They show how the bastion does not need to know what servers are based on the service it provides. In their proposed work, the bastion is based on a random, random data source rather than a dedicated server. Their solution helps make the distribution of puzzles no longer a point of compromise.
Their design has three advantages: Firstly, it is more resistant to DoS attacks targeted to the puzzle-generating mechanism itself. Secondly, the schema can be applied very easily at the IP level, although it also works at higher levels of the stack of protocols. Third, puzzles can be solved off-line. In the paper the authors present a prototype of implementation of their approach and some experimental results. In their implementation, cryptographic puzzles are sent to customers only when the server is under attack, time determined based on server load. The difficulty of puzzles is depending on server load. When the server is under attack, it sends cryptographic puzzles to all clients, both legitimate and illegitimate.
It is noticed that in this way the server will be able to get out of a DoS attack by making fewer complex cryptographic calculations, eventually succeeding in serving legitimate clients, but they still lose some time in solving cryptographic jigsaws.