Summary of “Denial of Service via Algorithmic Complexity Attacks”
Abstract. In this paper, the authors present a class of low-bandwidth denial-of-service attacks that exploit algorithmic deficiencies in the data structures of many applications. Many frequently used data structures are designed in a way that average-case expected running time is much more efficient than the worst-case running time. The assumption is that the worst case rarely occurs and therefore users can enjoy the saving of efficiency in the average cases. However, as the authors point out in the paper, if an adversary is aware of the data structures used in the target applications, it is possible that the adversary can choose some specific inputs to launch a low-bandwidth denial-of-service attack against these applications. For example, both binary trees and hash tables can degenerate to linked lists with carefully chosen inputs. To justify their claim, the authors show how an adversary can effectively compute such inputs to attack hash table implementations in two versions of Perl, the Squid web proxy, and the Bro intrusion detection system.In many hash table implementations, a linked list is used by each hash bucket to hold all the objects whose hash value, modulo the bucket count, maps to the same hash bucket. The authors discuss how to first find a few generators that hash to the initial state of 0 and then use arbitrary combinations of these generators to overflow the linked list of a hash bucket. Under such attack, their Bro server was found to drop as much as 71% of traffic and consume all of its CPU resource. In the end, the authors suggest the use of algorithms that do not have predictable worst-case inputs and the use of universal hash functions in order to counter this type of attacks.
Contributions. This paper identifies a new class of denial-of-service attack that is different from most denial-of-service attacks that are based on high-rate stream of messages. The strength of this class of attacks is that they do not need to congest the network to bring down a target server. Also, the authors suggest practical ways to counter this class of attacks.
Weaknesses.A weakness of this paper is that there is no universal theorem given by this paper that can apply to all applications. The attacks described in this paper are highly implementation-dependent, and if the hash algorithm used by applications is carefully designed to incorporate some dynamics, this class of attack shall not prevail. Another problem with this paper is that the attack discussed in this paper exploits the initial state of 0, which is a very special case. It is not likely that an adversary can be often so lucky to encounter this special case. Moreover, the inserted messages produced by combining the generators are meaningless and it is very likely that they will be detected before they reach the target. However, it is possible to find some other algorithmic weaknesses that were not discussed by the authors but can be exploited by an adversary.