Lion Cipher Lab
Build a hash table, and measure how hash flooding turns it quadratic
- Foundations
- Advanced
- ~75 min (plus an optional 10-minute wait for the 50,000-key flood)
- Free · no account required
Why it matters
Almost every program you will ever defend stores data in hash tables: Python dicts, JSON objects, HTTP headers, form fields, caches, session stores. They are fast because of an average-case promise. Spread the keys out, and finding one takes about the same time no matter how many there are. That promise breaks if an attacker can choose keys that all land in the same place. Then every insert has to walk past every earlier key, and the work grows with the SQUARE of the input. In 2003 Crosby and Wallach showed this against Perl, the Squid proxy and the Bro intrusion detection system. In December…
What you'll learn
- building a separate-chaining hash table from scratch with a pluggable hash function, power-of-two buckets, a 0.75 load factor and resize that reuses stored hashes
- implementing SipHash-2-4 from the paper in pure Python and proving it against the official reference vectors before trusting it
- constructing 65,536 keys with one DJBX33A hash from the Ez/FY equivalent-substrings trick (69x33+122 = 70x33+89 = 2399), the structure behind oCERT-2011-003
- measuring linear vs quadratic with exact probe counts and a log-log slope: random keys 0.5 probes/key and slope 1.03; colliding keys N(N-1)/2 probes and slope 1.97 (50,000 keys: 309 CPU-s vs 1.03 s)
- showing a secret random key defeats a precomputed collision set: the same 50,000 keys under SipHash took 4.6 s, 0.5 probes/key, longest chain 5
- demonstrating PYTHONHASHSEED and sys.hash_info across fresh processes, and why a fixed seed in production turns the defence off
- measuring what keyed hashing misses: a custom __hash__ (12.5 million __eq__ calls for 5,000 keys) and unsalted ints flooding a real dict, and a 200,000-field body costing 0.7 CPU-s and 45 MB until max_num_fields rejects it in 2 ms
- pricing the fix: SipHash costs 8.8x DJBX33A per key in pure Python, and judging when that trade is worth it
Steps in this lab
- What you are building, and why a data structure can be a denial-of-service bug
- Set up: a terminal, Python, and a lab folder
- Build the table and two hash functions: hashtable.py
- Construct 65,536 keys with one hash: collide.py
- Measure BEFORE: random keys vs colliding keys in the unkeyed table
- Why storing the hash did not save you, and why a bigger table would not either
- The fix: SipHash with a secret random key, measured AFTER
- Watch Python do the same thing: sys.hash_info and PYTHONHASHSEED
- Honest negative 1: a key the attacker knows or can learn is no key, and Python only salts str and bytes
- Honest negative 2: no collisions at all, and a huge request still costs you
- Honest negative 3: the keyed hash costs real speed
- Do it better: the judgment, in one page