Varol Cagdas Tok

Personal notes and articles.

Algorithmic Complexity Attacks

The worst-case complexity of an algorithm is a theoretical construct. In textbooks and complexity analyses, it describes the maximum cost the algorithm can incur across all possible inputs of a given size. In security, worst-case complexity is an attack surface. If an algorithm has a worst case that is significantly worse than its average case, and if an attacker can construct inputs that trigger the worst case, they can exploit the algorithm to exhaust server resources with inputs that appear reasonable in size.

This category of denial of service is distinct from volumetric flooding and protocol exhaustion. The attack does not require high traffic volume. It requires knowledge of the algorithm being executed on user-supplied data and the ability to construct inputs that force the worst-case execution path. A single request, or a small number of requests, may be sufficient to consume server resources for an extended period.

Regular Expression Denial of Service (ReDoS)

Regular expression engines in most languages use Non-deterministic Finite Automaton (NFA)-based backtracking engines. These engines are convenient and support backreferences and lookahead assertions that pure DFA-based engines cannot handle, but they have a pathological failure mode: for certain patterns and inputs, backtracking causes exponential time complexity.

The Backtracking Explosion

Consider the regex ^(a+)+\(` applied to the string `aaaaaaaaaaaaaaaaaab`. The NFA engine attempts to match the input. The outer group `(a+)+` can be satisfied in multiple ways: the inner `a+` might consume all the 'a' characters, or it might consume subsets, with the outer `+` iterating over multiple inner matches. When the final 'b' fails to match the `\) anchor, the engine backtracks and tries a different assignment of 'a' characters to inner vs. outer repetitions.

The number of different ways to partition n characters across a nested repetition is exponential in n. For a string of 30 'a' characters followed by a non-matching character, the number of backtracking paths is approximately 2^30. On a typical CPU, this exhausts available computation time before completing.

The engine is working as specified. The engine is exploring all possible match paths to determine definitively that no match exists. The problem is the combination of the pattern structure (exponential ambiguity) with the backtracking evaluation strategy.

Vulnerable Pattern Classes

Several regex pattern structures reliably produce catastrophic backtracking on adversarial inputs:

Nested quantifiers: (a+)+, (a), (a|aa)+, patterns where an outer repetition contains an inner repetition over overlapping character classes.

Alternation with overlap: (a|a)+, (ab|a)+b, patterns where alternatives can match the same input characters, creating ambiguity about which alternative applies.

Exponential patterns with multiple paths: (a|b|c)*d applied to a long string of 'a', 'b', 'c' characters followed by 'e', the engine must verify that no assignment of characters to the alternatives matches 'd' at the end.

The key diagnostic is whether the pattern can match a prefix of the input in multiple different ways. If it can, and if the suffix fails to match, the engine must try all of those ways, which may be exponential in the prefix length.

Real-World Occurrences

ReDoS vulnerabilities have been found in production systems across most major programming languages and in widely-used libraries. The OWASP list of documented ReDoS vulnerabilities includes findings in:

The Node.js ecosystem has been particularly affected because of the language's single-threaded event loop: a single ReDoS attack that occupies the event loop blocks all other request handling simultaneously. In multi-threaded environments, a single ReDoS attack only occupies one thread, allowing other threads to continue serving requests.

Detection and Mitigation

Static analysis of regex patterns for catastrophic backtracking potential is an active research area. Tools like regexploit, vulnregex-detector, and academic implementations of the Weideman et al. vulnerability detection algorithm can identify patterns with exponential or polynomial worst-case complexity. These tools model the NFA and look for patterns where the state graph has "super-linear" properties.

The implementation mitigations are:

Timeout enforcement: wrap regex evaluation in a timeout and abort if it exceeds a threshold. This prevents a single match from consuming unbounded time but adds latency to all matches that approach the threshold. Node.js provides worker_threads for running regex in a separate thread with timeout; most other environments require external timeout enforcement.

Non-backtracking engines: RE2 (from Google) implements a DFA/NFA hybrid that guarantees linear time in the length of the input string. It cannot support backreferences or lookahead assertions, which limits its applicability, but for patterns that do not require these features it is immune to catastrophic backtracking. RE2 bindings are available for most major languages.

Pattern rewriting: in many cases, a pattern with exponential worst-case behavior can be rewritten to an equivalent pattern with linear worst-case behavior. Atomic groups and possessive quantifiers (supported by PCRE but not all engines) prevent backtracking out of a successful match, eliminating the ambiguity that causes exponential behavior.

Hash Collision Attacks in Depth

The HashDoS vulnerability discovered by Klink and Wälde in 2011 exploited a specific property of commonly deployed hash functions: their determinism. If the hash function used by a language's runtime hash table is known and deterministic (no random seed), an attacker can precompute a large set of keys that all hash to the same bucket.

How Hash Collisions Exhaust CPU

A hash table with a good hash function and n entries distributes them approximately uniformly across k buckets, yielding average bucket occupancy of n/k. Lookup time is O(1) amortized. With all n entries in the same bucket, the table degenerates to a linked list. Lookup time becomes O(n). Inserting all n entries becomes O(n^2) in total, each insertion must traverse the existing entries in the bucket to check for duplicates.

HTTP POST body parsing in PHP, Java, Python, Ruby, and .NET (all of which used unseeded or known-seeded hash functions in 2011) involved inserting all form field names into a hash map as part of parsing. A POST request with 100,000 form fields, all with names precomputed to collide in the target's hash function, required O(10^10) operations to parse, several minutes of CPU time per request.

The Murmur Hash and Seeding

The specific hash functions in use at the time of the Klink/Wälde disclosure varied by language. Java used a polynomial hash with a known multiplier. PHP used a similar polynomial hash. The hash functions were designed for performance, not unpredictability. Once the algorithm is known, generating collisions is a combinatorial problem that can be solved offline.

The fix universally adopted was hash randomization: seeding the hash function with a value chosen at process startup (or at each hash table creation), unknown to the attacker. With an unknown seed, precomputed collision sets do not work, the attacker cannot know which inputs will collide until they know the seed, which they do not.

In practice, this is implemented as:

Residual Vulnerabilities

Hash randomization addresses known-function attacks but does not address all hash-based denial of service. Hash tables that use weak randomization (e.g., a predictable seed derived from process start time) can still be attacked if the attacker can determine the seed. Timing side channels in hash table operations can leak information about the number of collisions, potentially allowing adaptive attacks that test candidate collision sets.

Furthermore, hash randomization does not protect against worst-case behavior arising from legitimate key distributions. If an application uses hash tables with extremely high key counts in a single bucket due to natural data characteristics, not adversarial input, performance degrades regardless of randomization. Java 8's HashMap was updated to use balanced BSTs for buckets that exceed a threshold occupancy, replacing O(n) linked list traversal with O(log n) tree traversal. This does not eliminate the attack but bounds its worst case.

Decompression and Serialization Bombs

Any operation that transforms input of size n into output of size f(n), where f can be made arbitrarily large by input choice, is a potential amplification vector for algorithmic complexity attacks. Compression and serialization formats often have this property.

Zip and Gzip Bombs

Compression algorithms achieve compression by exploiting redundancy in the input. The theoretical maximum compression ratio for a given algorithm is determined by the information content of the input. A file consisting entirely of a single repeated byte has very high redundancy and compresses to a very small fraction of its original size.

A zip bomb constructs a compressed archive by compressing highly redundant data. The simplest form is a single compressed file: dd if=/dev/zero bs=1M count=10240 | gzip > bomb.gz produces a gzip file of approximately 10 MB that decompresses to 10 GB of null bytes. A more extreme form uses zip's support for multiple files and nesting: 10 files, each containing 10 files, each containing a 1 GB compressed null file, produces a multi-level bomb with extreme expansion at multiple decompression steps.

Applications that accept user-submitted archives and decompress them without size limits, file upload handlers, attachment processors, static analysis tools, are vulnerable. The defense is straightforward: enforce a maximum decompression output size and abort if it is exceeded. Most compression libraries provide a means to read decompressed output incrementally rather than in full, allowing size checks before full expansion.

The "quine" variant of the zip bomb is more sophisticated: a zip file that contains itself, or a zip file that recursively expands when extracted. This is primarily an issue for archive utilities that follow archive members recursively, less common in web application upload contexts.

XML Entity Expansion (Billion Laughs)

XML entities allow a string to be defined once and referenced multiple times. The XML specification requires that entity references be expanded recursively. This creates the opportunity for exponential expansion:

<!ENTITY a "x">
<!ENTITY b "&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;">  <!-- 10x -->
<!ENTITY c "&b;&b;&b;&b;&b;&b;&b;&b;&b;&b;">  <!-- 100x -->
<!-- ... -->
<!ENTITY j "&i;&i;&i;&i;&i;&i;&i;&i;&i;&i;">  <!-- 10^10 x -->

A document referencing &amp;j; requires a parser to expand the reference through 10 levels of entity references, producing 10^10 copies of the original string. The memory required is catastrophic.

Defenses include:

In Python's xml.etree.ElementTree, entity expansion is limited by default since 2.7.17/3.8.6 via the xml.etree.ElementTree.XMLParser defusedxml-style limits. The defusedxml library provides hardened parsing that disables entity expansion and several other vectors.

YAML and Python Pickle

YAML's merge keys (&lt;&lt;) and anchors (&amp;) provide a mechanism similar to XML entity references. A YAML document with deeply nested merge keys can produce exponential processing time:

a: &a ["lol","lol","lol","lol","lol","lol","lol","lol","lol","lol"]
b: &b [*a,*a,*a,*a,*a,*a,*a,*a,*a,*a]
c: &c [*b,*b,*b,*b,*b,*b,*b,*b,*b,*b]

Python's pickle format is a separately serious case. Pickle allows arbitrary Python code execution during deserialization via the __reduce__ method. This is not strictly a complexity attack, it is remote code execution, but the threat model is related: any deserialization of untrusted data in a format that supports code execution is catastrophically insecure, not merely a DoS risk.

Sorting and Worst-Case Input

Comparison-based sorting algorithms have well-understood worst-case complexity. Quicksort's average case is O(n log n) but its worst case for naive pivot selection is O(n^2). If an application sorts user-supplied data with a naive quicksort implementation, an attacker who knows the pivot selection strategy can construct an input sequence that degrades sorting to quadratic time.

Classic quicksort with a fixed pivot (e.g., always selecting the first or last element) degrades on sorted or reverse-sorted input. For an array of n elements, this produces n recursive calls each processing a subarray of n-1, n-2, ... elements, summing to O(n^2) total work.

Most modern standard library sort implementations use either randomized pivot selection (which makes worst-case inputs impossible to precompute, since the pivot selection is unpredictable) or an introsort variant (quicksort that switches to heapsort when recursion depth exceeds a threshold, guaranteeing O(n log n) worst case). The vulnerability is primarily in custom sorting code, language runtimes with naive implementations in older versions, or sorting code in environments where library implementations are not used.

Path Traversal in Graph Algorithms

Graph algorithms operating on user-controlled graphs have complexity dependent on graph structure. An algorithm with O(V + E) average-case complexity may have O(V^2) or worse complexity on specific graph structures.

Applications that allow users to define workflow graphs, dependency graphs, or any other structure where the application then traverses the graph (cycle detection, topological sort, reachability analysis) are vulnerable to constructed adversarial graphs. A graph with pathological structure for the specific algorithm in use can exhaust CPU.

For example, a dependency resolver using a naive DFS for cycle detection processes each edge once in the average case. For a specific graph structure designed to maximize backtracking in the DFS, a graph where the last-processed path is always the one that eventually leads to a cycle, the performance may degrade significantly.

The Unifying Property

The common thread across all these cases: an algorithm applied to user-controlled input with a worst case far worse than its average case, and no bounds checking to prevent the worst case from triggering.

Worst-case complexity is rarely documented. Developers do not annotate functions with worst-case complexity assumptions about their inputs. Security reviews that examine algorithmic complexity require both knowledge of algorithm theory and the ability to trace user-controlled data through application processing to identify where it is fed into algorithms with unfavorable worst-case characteristics.

Related Articles