Thursday, August 16, 2012

Serious (secret/seed-independent) collision attacks on MurmurHash3 and CityHash

Remember Denial of Service via Hash Table Collisions attack?

BREAKING NEWS!  Paul Khuong pointed these tweets out to me:

JP Aumasson ‏@aumasson
MurmurHash3 (now used in #Java etc.) fails to protect against #hashdos: many collisions for any key here http://131002.net/siphash/murmur3collisions-20120731.tar.gz … /cc @nahi
Retweeted by Daniel J. Bernstein

30 JulJP Aumasson ‏@aumasson
universal multicollisions for Google’s CityHash64 hash function with 128-bit secret http://131002.net/siphash/citycollisions-20120730.tar.gz … (details in citycollisions.cc)
Retweeted by Daniel J. Bernstein

There are basically (and I’m really simplifying things, but I think the gist holds true) two types of hash function: cryptographic hash functions are slow to compute and impossible to break and are used when we need security e.g. signing documents and HTTPS connections.  Normal hash functions are fast to compute but not secure from attacks, and they are super useful and we use them all the time in the basic building blocks of modern applications in the hash table data-structure and so on.

The thing is, we’ve been putting tainted data into these hash tables of ours.  Data that an attacker can pick.  So an attacker can generate collisions for our non-secure hash function and fill up our hash tables with collisions and bring our servers down…

The focus swung to hash DOSing the other month and the quick fix has been to allow web-server owners and such to configure various mitigations… most servers are still vulnerable, and it seems that just randomising a key for the hash function is not always enough any which way…

I’m no expert, I’m just a very interested bystander.

My previous opinions and fears.


 ↓ click the "share" button below!