6533b82bfe1ef96bd128e0c7

RESEARCH PRODUCT

Algorithmic Complexity Vulnerability Analysis of a Stateful Firewall

subject

description

Algorithmic complexity vulnerabilities are an opportunity for an ad-versary to conduct a sophisticated kind of attack i.e. on network infrastructure services. Such attacks take advantage of worst case time or space complexity of algorithms implemented on devices in their software. In this paper we address potential risks introduced by such algorithmic behavior in computer networks in particular on a stateful firewall. First we introduce the idea and theoretical background for the attack. We then describe in full detail a successfully con-ducted attack which takes advantage of the worst case computational complexi-ty of O(n2) of a hash table data structure used to store active sessions. The at-tack at hand is initiated from a network protected by an stateful firewall router feature to a remote server causing a DoS (Denial of Service) on an industry grade router. Our experimental results using a real life network topology show that by generating undetected low bandwidth but malicious network traffic causing collisions in the firewall’s hash table we cause the firewall to become unreachable or even announce a segmentation fault and reboot itself.