1Deamplification of DoS Attacks via PuzzlesJacob Beal and Tim [email protected], [email protected]: Please do not redistributeOctober 15, 2004Abstract—Puzzles have been proposed as a mechanismto deamplify denial of service attacks against a server’smemory and processing resources. For example, HIP im-plements a cookie puzzle mechanism to protect the serverfrom wasting resources performing Diffie-Hellman expo-nentiation in response to spurious requests. We examinecookie puzzle mechanisms of this type.We find that careful attention is needed in serverimplementation to ensure that an attacker does not retainopportunities to amplify the attack despite the puzzle mech-anism, and present a design which addresses these issues.We compare vulnerability to bandwidth and processingattacks, determining when one dominates the other. Finally,we quantify the deamplification of DoS attacks provided bya cookie puzzle mechanism and determine the best settingfor puzzle difficulty under a steady-state attack.I. INTRODUCTIONDenial of service attacks can be targeted at anyexhaustible resource, such as bandwidth1, memory, orprocessing power. Although recently most attention hasbeen focused on denial of service attacks which targetbandwidth, the potential impact of attacks on processingpower is as great or greater in some cases, such as keyexchange protocols (e.g. Diffie-Hellman key agreementprotocol).Key exchange protocols used to establish session keysusing public key cryptography require the respondingcomputer to perform an expensive exponentiation opera-tion. Because an expensive operation must be performedbefore the responder can authenticate the identity ofthe initiator, an attacker might consume the responder’sprocessing power with a flood of bogus requests.This is an instance of the more general problem ofprotecting processing power, which is simpler in thiscase because every request consumes an approximatelyequal amount of computation. Additionally, a solutionin the case of key-exchange protocols may open up amuch wider range of potential solutions to the general1We use the term bandwidth throughout this paper not in its literalsense, but rather in its figurative sense, meaning communication capac-ity, that has become commonplace in writing on computer networking.problem, because authenticated connections might beused to establish accountability for resources consumed.One defense, used by IKEv2[8], is for the responderto perform a return routability test before committingresources to the initiator’s request. Although this pre-vents simple spoofing, return routability cannot distin-guish between a single attacking machine which controlsmultiple IP addresses (easily available in IPv6) and agroup of legitimate users, nor between a single attackingmachine and a large pool of legitimate users sharing asingle address via a NAT2box (common in IPv4).Thus even with a return routability test, an attackerwilling to expose one or more routable locations (e.g.hijacked machines) can amplify an attack by simulatinga large group of legitimate users, thereby tricking the re-sponder into a disproportionate expenditure of resources.The HIP protocol[12] attempts to solve this problemby means of a cookie puzzle mechanism[3], in whichthe cookie sent by the responder to test return routabilityincludes a cryptographic puzzle which the initiator mustsolve in order to obtain service. The hope is that, byadjusting the difficulty of the puzzle, the respondercan deamplify attacks, while not significantly burdeninglegitimate clients.In this paper we address three issues of cookie puzzlesystem design and implementation:• Design: We find that the mechanisms suggestedin the HIP drafts are, by themselves, insufficient.Careful server implementation is required to ensurethat an attacker does not retain opportunities toamplify the attack despite the puzzle mechanism.In Section III we explain the threats and presenta server design which uses persistent-dropping todefend itself.• Dominance: The more asymmetric an attack, themore attackers can gather sufficient resources, andthe less exposed an attacker must be in order toexecute it. In Section V we compare the asymmetryof attacks against processing resources and band-2Network Address Translationwidth. When processing vulnerability dominates,cookie puzzle mechanisms are useful in decreasingthe asymmetry of attack.• Deamplification: In Section VI, we quantify thereduction of attack intensity provided by a well-designed cookie puzzle system. Furthermore, wedetermine how to set puzzle difficulty to optimizeservice to legitimate clients under steady-state at-tack conditions.II. THE HOST IDENTITY PROTOCOLThe Host Identity Protocol Architecture [13] is pro-posed within the IETF to fill a gap between DNS namesand IP addresses. It provides for a new namespace, HostIdentity, to enable trusted communication between ma-chines which do not have stable network addreses. Oneof its components is the Host Identity Protocol (HIP)[12], which allows two hosts to establish authenticatedcommunication by means of a four-packet exchange.At the present time, there are four open source imple-mentations that have demonstrated interoperability [1],[14], [9], [10]. To date, interoperability demonstrationhas been the goal of these implementation efforts, andthese implementations are not yet complete with respectto HIP’s designed defenses against DoS attacks.We will sketch the key points of a HIP exchange forthis paper; for a proper treatment, see [12].First, the client sends a request to the server, askingto establish an association. In response, the server ini-tiates a Diffie-Hellman key exchange, conducted in thesecond and third packets. Rather than risk its memoryby keeping any state3, the server includes all necessaryassociation information in its reply packet. The clientsends this information back to the server with its halfof the key exchange, and the server completes theassociation.To protect itself from fake packets and colludingattackers, the server includes a cookie consisting of arandom number and a correlated value, partially de-termined by the client’s identity and the time of therequest.4This allows the server to verify that the returnedcookie is genuine and was sent from it to this particu-lar client before running the computationally expensivekey exchange calculation following the third packet orallocating memory for the association.The optional puzzle component of