~/learn / algorithms
Algorithms for Security
Why complexity, data structures, and algorithms matter to security, from denial of service through worst-case inputs and integer overflow to the graph theory behind Active Directory attack paths.
You can go a long way in security without studying algorithms formally. Sooner or later, though, you meet bugs that only make sense once you think about how much work code does for a given input, and tools that only make sense once you think in graphs. The unifying idea is small and powerful: in security, the attacker, not the average user, picks the input, so the worst case is the case that matters.
Big-O in one minute
Big-O describes how the work grows as the input grows, ignoring constants.
| Complexity | Name | 10x more input means |
|---|---|---|
| O(1) | Constant | Same work |
| O(log n) | Logarithmic | A little more work |
| O(n) | Linear | 10x the work |
| O(n log n) | Linearithmic | A bit more than 10x |
| O(n²) | Quadratic | 100x the work |
| O(2ⁿ) | Exponential | Unbounded, effectively |
The subtlety that matters for security is the gap between average and worst case. Hash table lookup is O(1) on average and O(n) in the worst case; a backtracking regex is linear on normal input and exponential on a crafted one; quicksort is O(n log n) usually and O(n²) against an input chosen to hit its worst pivots. Benchmarks measure the average. Attackers engineer the worst, which is why “it is fast in practice” is not a security statement. These are algorithmic complexity attacks: a small, cheap input that forces a large, expensive computation, turning a performance footnote into a denial of service.
Where it shows up
- Hash tables: O(1) average, O(n) per operation when keys are chosen to collide. See hash tables and hash flooding.
- Regular expressions: backtracking engines go exponential on ambiguous patterns. See regex and ReDoS.
- Parsers: deeply nested JSON or XML exhausts the stack; XML entity expansion grows a tiny document into gigabytes (the billion laughs attack).
- Decompression: a small archive expands enormously (a zip bomb) without a decompressed-size cap.
- Sorting and searching attacker-supplied collections with no size limit.
- Serialization: quadratic blowups in building strings or merging objects from large inputs.
Integer overflow and bit-level surprises
Fixed-width integer arithmetic wraps at its boundary, and that wrap has caused a long history of security bugs. A length field that overflows to a small value leads to a buffer too short for the data that follows (a heap overflow). A quantity large enough to overflow a 32-bit total can wrap to a tiny or negative number, which is the arithmetic behind some business-logic abuses like negative-cost carts. Signedness confusion, where the same bits read as a large positive or a small negative depending on interpretation, bypasses naive bounds checks. The number base converter shows two’s-complement values side by side so the wrap is visible.
Graphs
Many security problems are graph problems. Networks, trust relationships, permissions, and attack paths are all nodes joined by edges. BloodHound’s core idea, the shortest path from an ordinary user to Domain Admins, is a textbook shortest-path search over a graph that was always there but never drawn. See graphs and attack paths.
Bits and bytes
Bitwise operations underpin Unix permissions (the chmod calculator is bit masks), protocol flags, subnet math (the subnet calculator), and XOR-based ciphers (the cipher workbench). Reading a value in binary and hex, rather than decimal, is often what makes a flag field or a mask suddenly legible.
The defensive takeaway
Bound everything an attacker controls: input size, nesting depth, item count, regex complexity, decompressed size, and processing time. Then choose data structures and algorithms whose worst case, not just average case, is acceptable, because the worst case is precisely what you will be sent on the day it matters.
Go deeper
- Hash Tables and Hash FloodingHow hash tables achieve fast lookups, how load factor and resizing work, why attacker-chosen collisions turn them into a denial-of-service vector, and how keyed hashing like SipHash closed the hole.
- Regular Expressions and ReDoSHow backtracking regex engines differ from finite-automaton engines, why nested quantifiers cause catastrophic backtracking, a trace of the blowup, the real outages it caused, and the engines and limits that prevent it.
- Graphs and Attack PathsHow graphs model networks, permissions, and trust, how breadth-first and weighted search find shortest attack paths, the Cypher queries behind BloodHound, and why graph thinking changed how both attackers and defenders see Active Directory and the cloud.