# Hash-Collision Denial-of-Service Vulnerability in Markdown Parser

Snudown's markdown reference hash table uses weak SDBM hash and allows duplicates, enabling algorithmic-complexity DoS via crafted colliding reference names.

- Payout: hidden
- Severity: medium
- Program: Reddit
- Found by: nicolaas
- Disclosed: 2021-10-21
- Write-up quality: 8/10
- Original: https://hackerone.com/reports/1341957
- Library page: https://bugbountylibrary.com/r/h1%3A1341957
- Tags: area:web domain:web impact:dos kind:bounty platform:hackerone sev:medium tech:python technique:chained technique:source-review vuln:dos

**Target:** Markdown parser (snudown) reference hash table
**Root cause:** Reference hash table uses weak case-insensitive SDBM hash, permits duplicate keys, and compares entries by hash value only, so many references map to one linked list making lookup O(N).
**Steps:**
1. Identify hash_link_ref as case-insensitive SDBM and table index = hash % T.
2. Bug 1: generate s1..sN with distinct hash values but identical hash % T so all land in same bucket.
3. Bug 2: find s' and s'' with hash(s')!=hash(s'') but hash(s')%T==hash(s'')%T, then repeat s'' N times.
4. Build markdown of `[si]: /url` followed by `[s1]` for each i.
5. Parse and measure time; grows linearly with N for malicious input vs random.
6. Confirm live Reddit via Bug 3: define colliding refs `37qpypz` and `uvhisfu` with different URLs; both resolve to the last-defined URL.
**How found:** Read snudown source, noticed reference table uses SDBM hash with chaining; reasoned that weak hash plus duplicate-allowing insert plus hash-only equality yields O(N) lookups, then crafted inputs satisfying hash%T collisions rather than full hash collisions because Bug 3 short-circuits full collisions.
**Exploitation:** Attacker submits markdown containing many reference definitions crafted to collide into one bucket, each followed by a use of the first reference, forcing O(N) linked-list traversal per lookup and consuming server CPU until availability degrades.
**Insight:** When a hash table compares keys by hash value only, full-collision payloads get short-circuited in O(1); instead generate distinct hashes that share the same modulus (bucket index) to still build a long chain. Also, duplicate-key insertion lets you grow a chain with a single repeated string.