Denial-of-service (DoS) attacks continue to disrupt the flow of traffic on the Internet. Proofs-of-work or "client puzzles" are a mechanism for protecting a number of protocols against DoS attacks. A puzzle is a cryptographically or combinatorially difficult problem that is generated by a server and must be solved by a client before it receives service. The difficulty of the puzzle is determined by the server as a function of previous client behavior, server load, etc. While puzzles have been used mostly at the application layer (and even there with only limited success), we argue that to prevent DoS attacks protection must exist in a layer common to all applications: the IP layer. Before this can be realized, there are a number of significant challenges that puzzle mechanisms must overcome, including efficiency, fairness, tamper-resistance, and control. More fundamentally, we believe that puzzles will not realize their full potential until there is a solid theoretical foundation for them. To date, one does not exist.
In this project we will address each of these challenges. First, we will give the puzzle problem a full provable-security treatment. Specifically, we will give a formal definition of what is a puzzle scheme, formal definitions of security for puzzles, and build puzzle mechanisms that provably meet these definitions. As part of this, we will formally analyze existing puzzle mechanisms based on previous work by us and others. In addition, we will explore new designs, with special attention given to puzzles constructed from T-functions, which show promise for being a basis for fast and effective puzzles. Our work will also address control-plane issues for intelligently setting puzzle difficulties. Finally, we will demonstrate the utility of our approaches by building a smart "Internet Tar Pit", a device that employs IP puzzles to selectively slow down DoS attacks, spam, port scans, and other undesirable network communication.
