Denial of Service Attack through Forced Hash Collisions #663

Closed
antirez opened this Issue Sep 6, 2012 · 3 comments

Comments

Projects
None yet
3 participants
Owner

antirez commented Sep 6, 2012

The hash collision seed we use in the hash function is completely useless as the following email I received shows how it is trivial to find seed-independent collisions. The original email follows:

From: Martin Schönert

On the "Redis Security" Topic page you write:

For instance an attacker could supply, via a web form, a set of strings that is known to hash to the same bucket into an hash table in order to turn the O(1) expected time (the average time) to the O(N) worst case, consuming more CPU than expected, and ultimately causing a Denial of Service. To prevent this specific attack, Redis uses a per-execution pseudo-random seed to the hash function. Unfortunately the structure of the hash functions and the way the seed is used still leaves it open to attacks (if the
keys are all of the same length). This is demonstrated by the attached file.

https://gist.github.com/3076234

Contributor

pietern commented Sep 8, 2012

We can check if another hashing function like Murmur is any better (it supposedly is).

http://en.wikipedia.org/wiki/MurmurHash

@antirez antirez added a commit that referenced this issue Oct 3, 2012

@antirez antirez Hash function switched to murmurhash2.
The previously used hash function, djbhash, is not secure against
collision attacks even when the seed is randomized as there are simple
ways to find seed-independent collisions.

The new hash function appears to be safe (or much harder to exploit at
least) in this case, and has better distribution.

Better distribution does not always means that's better. For instance in
a fast benchmark with "DEBUG POPULATE 1000000" I obtained the following
results:

    1.6 seconds with djbhash
    2.0 seconds with murmurhash2

This is due to the fact that djbhash will hash objects that follow the
pattern `prefix:<id>` and where the id is numerically near, to near
buckets. This improves the locality.

In many common access patterns this also means better locality, so this
speed hint is not limited to synthetic benchmarks, but also to real
world access patterns.

However in other access patterns with keys that have no relation
murmurhash2 has some (apparently minimal) speed advantage.

On the other hand a better distribution will probably significantly
improve the quality of the distribution of elements returned with
dictGetRandomKey() that is used in SPOP, SRANDMEMBER, RANDOMKEY, and
other commands.

This commit fixes issue #663.

At this time it is not clear when this commit will be merged into a
release branch.
2dde073

@antirez antirez added a commit that referenced this issue Oct 5, 2012

@antirez antirez Hash function switched to murmurhash2.
The previously used hash function, djbhash, is not secure against
collision attacks even when the seed is randomized as there are simple
ways to find seed-independent collisions.

The new hash function appears to be safe (or much harder to exploit at
least) in this case, and has better distribution.

Better distribution does not always means that's better. For instance in
a fast benchmark with "DEBUG POPULATE 1000000" I obtained the following
results:

    1.6 seconds with djbhash
    2.0 seconds with murmurhash2

This is due to the fact that djbhash will hash objects that follow the
pattern `prefix:<id>` and where the id is numerically near, to near
buckets. This improves the locality.

However in other access patterns with keys that have no relation
murmurhash2 has some (apparently minimal) speed advantage.

On the other hand a better distribution should significantly
improve the quality of the distribution of elements returned with
dictGetRandomKey() that is used in SPOP, SRANDMEMBER, RANDOMKEY, and
other commands.

Everything considered, and under the suspect that this commit fixes a
security issue in Redis, we are switching to the new hash function.
If some serious speed regression will be found in the future we'll be able
to step back easiliy.

This commit fixes issue #663.
99c3338
Owner

antirez commented Oct 5, 2012

Switched to murmurhash2, please check the latest commit that references this issue for detailed information. Closing.

antirez closed this Oct 5, 2012

@antirez antirez added a commit that referenced this issue Oct 5, 2012

@antirez antirez Hash function switched to murmurhash2.
The previously used hash function, djbhash, is not secure against
collision attacks even when the seed is randomized as there are simple
ways to find seed-independent collisions.

The new hash function appears to be safe (or much harder to exploit at
least) in this case, and has better distribution.

Better distribution does not always means that's better. For instance in
a fast benchmark with "DEBUG POPULATE 1000000" I obtained the following
results:

    1.6 seconds with djbhash
    2.0 seconds with murmurhash2

This is due to the fact that djbhash will hash objects that follow the
pattern `prefix:<id>` and where the id is numerically near, to near
buckets. This improves the locality.

However in other access patterns with keys that have no relation
murmurhash2 has some (apparently minimal) speed advantage.

On the other hand a better distribution should significantly
improve the quality of the distribution of elements returned with
dictGetRandomKey() that is used in SPOP, SRANDMEMBER, RANDOMKEY, and
other commands.

Everything considered, and under the suspect that this commit fixes a
security issue in Redis, we are switching to the new hash function.
If some serious speed regression will be found in the future we'll be able
to step back easiliy.

This commit fixes issue #663.
da920e7

Bad news: murmurhash2 is vulnerable to the same attack. Here's a program to very quickly generate seed-independent collisions for murmurhash2:

https://www.131002.net/siphash/murmur2collisions-20120821.tar.gz

SipHash is a cryptographic MAC designed for this purpose; its speed is competitive with murmurhash and djbhash, and it's strongly resistant to collision attacks:

https://www.131002.net/siphash/

C code for SipHash is here:

https://www.131002.net/siphash/siphash24.c

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment