Using Puzzles to Stop DDoS Attacks

[allan]

Here is an interesting idea:

http://www.newscientist.com/news/news.jsp?id=ns99993729

Not sure how practical it is, or what type of impact it would have on legitmate traffic, but it is fascinating to think about.

Here is the abstract of the paper:

http://www.computer.org/proceedings/sp/1940/19400078abs.htm

You can buy it from IEEE for $19

[DizixCom]

I don't really get how this would help. We know that a local software firewall will do little against a solid DDoS attack, the real work must be done upstream to null route the attackers.

Forcing them to solve a puzzle to get through? Why not just ask the target machine to keep sending more and more puzzles without ever solving the first one? Kinda like this:

Attacker:
>-- Hi! I want access, what's my puzzle? -->

Victim: (thinks up a new puzzle)
<-- Solve pi to the 40th digit, and you may pass. <--

Attackers next request:
>-- Hi! I want access, what's my puzzle? -->

Victim: (thinks up a new puzzle)
<-- Calculate the square root of -1 <--

Etc. etc. etc (as the bald guy once said). What I could see is one of two situations occuring:

Either 1, the victim is so overwhelmed with generating new puzzles that it is effectively in a "service denied" state.

Or 2, the victim has a trust relationship with the upstream network provider and says "Hey stop these idiots for five minutes. They're not even trying to solve my puzzles!"

Option 1 just makes matters worse and option 2 adds a whole new layer of complexity to an already overly complex set of networking dialog.

Any more insights on this? It is an interesting topic, and I may (as usual) just be completely out of focus.

[allan]

I'm sure you know that specifically in a DDoS you have multiple requests from the same hosts to a server. Since the puzzles, as I understand the way they work, operate in a gradient fashion it puts an increasing load back on the requesting host while adding minimum overhead to the server.

Lets say that a server can effectively juggle 1000 HTTP requests, and 10,000 TCP requests -- which are built up and broken down very quickly. Using the examples you gave above, an attack machine sends a request and the server responds with "Solve pi to the 40th digit", the attack machine cannot send another request unitl it solves that problem. The attack machine quickly solves that problem, sends the next request, and the server responds with "Calculate the square root of -1".

This takes a little longer to solve, so now the requests coming in from the attack machine are every 2 seconds, instead of several a second, as the puzzles get increasingly complex the requests from the attack machine are spread further apart. This makes room for legitimate traffic on the server and, if the puzzle is complex enough, has the added advangtage of possibly craching the remote computer :).

[no1v2]

The point is the attacking computers don't have to solve the puzzles. They're not actually trying to load the site, just overload the server, which the puzzle "solution" would help them do. Taking your 10,000 TCP requests example, this does nothing to stop a syn flood. Or just looking at it practically, the server has to know what the correct answers are. Either it needs a database of them (which would introduce its own problems), or it needs to compute them as well. While it's busy computing them the attacker would just keep on sending more requests. You could only block that by ignoring clients until they answer the original question correctly, but that could easily drop legitimate traffic as well. Not to mention it wouldn't do anything for the syn flood...

[allan]

Actually, the the puzzle is specifically designed for dealing with Syn attacks. Based on my understanding of how it works the puzzle algorithm is compiled into the TCP stack so. When the server receives the first Syn request from the attacking computer it sends the puzzle, then it does not accept any other connections from the attacking computer until it returns an answer. So, the attacking computer is either blocked or forced to solve the puzzles, which signicantly slows down the number of connections it can make.