Incident: Crafted keys slowed dictionaries to a crawl
Module 5 · Incident file · About 30 minutes
What happened
In December 2011, at the 28th Chaos Communication Congress (28C3) in Germany, Alexander Klink and Julian Wälde gave a talk on a cheap way to take web servers down. The same month, oCERT, a security response team for open-source projects, published advisory oCERT-2011-003 about it. Several of the most used web platforms were affected, Python among them.
The attack needed no stolen password and no bug in anyone's own code. It used a dictionary. When a web page receives a form, the platform usually puts the form's fields into a dictionary, field name as the key. An attacker sends one request holding many thousands of fields whose names were chosen in advance, so that all of them land in the same place inside the dictionary. Filling that one dictionary then took the server far longer than any normal request, and a handful of such requests could keep a server's processors busy.
colliding names worked out once
sent to any server
collisions cannot be planned
sets print in varying order
Python's answer was hash randomisation. From Python 3.3 (2012), the hash of every string is mixed with a random value chosen each time Python starts, so an attacker can no longer work out in advance which names will collide. Python 3.4 went further and changed the string hash to a stronger design called SipHash (PEP 456, 2013). This is the change Lessons 2 and 3 pointed to when a set printed in a different order on each run.