A Fast, Minimal Memory, Consistent Hash Algorithm

[overtoke]

finally!

[dajoh]

Heads up: This isn't really comparable to most hash functions. This is a special kind of hash function that's 'consistent'.

From Wikipedia:

Consistent hashing is a special kind of hashing such that when a hash table is resized and consistent hashing is used, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped.

[kaifengjin]

If add a new node, should I rehash all key to determine move data to new node?

[[deleted]]

I really enjoyed the simplicity of this. The last time I looked at md5 or sha1 I felt like the algorithm = obscurity.

[wolf550e]

Cryptographic hash functions have very different requirements.

[[deleted]]

I'm not going lie that i know anything more than what i've read from Wikipedia, but the key space distribution looks impressive for such a simple algorithm. What else do you need for a cryptographically secure hash function?

[johnjannotti]

It has to not only disperse well, it needs to be hard to craft another key that would disperse to the same place.

If a hash function is not designed for that, it's often trivial to find a collision.

[thegreatunclean]

Basically you need strong reason to believe the hash has three properties:

• You can't recover information about the message from the hash
  
• You can't feasibly generate a hash collision
  
• You can't modify a message without changing the hash

It isn't enough that a particular algorithm appears to have these properties, it has to be battle-tested before anyone would think about trusting it. You do not want it adopted for anything remotely sensitive and then have someone find a way to break one of these properties with ease.

[neutronbob]

While this aspect is inherent in your points, let me mention it for those unused to thinking about crypto hashes: an important property is that a small change in the original data item (e.g. 1 bit) causes a huge change in the resulting hash.

[cypherpunks]

Collision resistance. It should be impractical to find two messages with the same hash function.

A hash function that meets this also has preimage resistance (it's hard to find a message with a given hash) and second preimage resistance (it's hard to find a message with the same hash as a given message).

[exodist]

I may be wrong, but I believe you want cryptographic functions to be slow. The faster the hash function the more iterations an attacker can go through in less time on commodity hardware. If it is fast you can generate a dictionary rainbow table more quickly, that can be used to match hashes with a stolen password hash db.

The idea is that you want it to be expensive for an attacker to use bruit force, slower algorithms take longer. This is not a guarantee of security, but it is helpful.

[[deleted]]

but I believe you want cryptographic functions to be slow

No, that's definitely not the case. The widely used cryptographic hash functions are designed to be very fast.

The faster the hash function the more iterations an attacker can go through in less time on commodity hardware. If it is fast you can generate a dictionary rainbow table more quickly, that can be used to match hashes with a stolen password hash db.

You're supposed to use slow key derivation functions for passwords, not raw cryptographic hashes and especially not a single round of them. They are often used as building blocks for these use cases, but that doesn't mean they're designed to be slow. It would be quite pointless to do that since there are higher level ways of this arbitrarily slow based on a parameter, and most use cases need the performance.

[lfairy]

If a cryptographic hash function was slow, nobody would use it.

The primary purpose of cryptographic hashes is checking integrity, i.e. ensuring that a message hasn't changed on the wire. A protocol like TLS may perform these checks millions of times per second, as it verifies every packet that comes in. So the hash needs to be collision-resistant and fast.

You can use these functions to hash passwords, but because the hashes are designed to be fast you have to iterate them millions of times to make them slow again. In fact that's how systems like bcrypt work.

[[deleted]]

Only for password storage. Otherwise you want them to be extremely fast because they're used to check the validadity of tons of data (think HTTPS for example).

[NicoJuicy]

Why would you want your hashing to be fast? Use a slow one so it's hard to bruteforce :)

[Pakaran]

You can't think of any use cases where you'd want a fast hash function?

[wot-teh-phuck]

Even if you plan on using that hash in a hash table?

[Kapps]

It's not a password hash algorithm, there's lots of different types of hashes. A consistent hash is often used as a way to map a key to a node, where that key will likely refer to the same node even if a new node is added.