mozilla/rust — Issue #1616: String hashes vulnerable to algorithmic complexity attacks
Author: kosta
Created: 2012-01-23 09:46:23+00:00
State: open

Hello!

The string hash function from here is vulnerable to an algorithmic complexity attack (from src/libcore/str.rs):

fn hash(&&s: str) -> uint {
// djb hash.
// FIXME: replace with murmur.

let u: uint = 5381u;
for c: u8 in s { u *= 33u; u += c as uint; }
ret u;
}

Consider a web service that accepts e.g. a POST request in urlencoded form or JSON and constructs a map from the POST data (extremely common case). For this hash function, it is extremely easy for an attacker to create input where all map keys will have the same hash. This allows for e.g. 1MB of POST data to get one CPU core busy for *hours*.

This is an issue that affects a lot of languages, see http://www.ocert.org/advisories/ocert-2011-003.html

Here a talk by the ppl creating the advisory: http://www.youtube.com/watch?v=R2Cq3CLI6H8

One solution is to use a random seed and to use XOR instead of adding. If this is to be replaced with murmur, make sure that the seed is random (I'm not an expert on murmur).