3 ms·

In any situation where a hashcode is cacheable (which seems to me to cover all situations where a hashcode even makes sense) a cryptographic hash function might

by yarg 7y ago

In any situation where a hashcode is cacheable (which seems to me to cover all situations where a hashcode even makes sense) a cryptographic hash function might not be such a bad idea (especially if you're IO bound in any way). With a bad hash function you can end up with a high level of bucket utilisation, significantly reducing the efficiency of the structure. With user defined data there's even the possibility of maliciously crafted input attempting to force collisions as part of a DOS attack. You can salt your input, and pretty much eliminate the issue - but as far as I can tell, you'll just end up rolling your own crypto.

yarg 7y ago
Actually, a counter-point: there might be situations where you want an anti-cryptographic hash function - where similar inputs produce generally similar hashes. It could have some application as a preprocessing step in clustering (if it could be done efficiently).
- earenndil 7y ago
  Easy: for n-byte output, separate input into n equally-sized chunks (pad with zeroes if not enough). For each chunk, XOR all the bytes together.
- nneonneo 7y ago
  Those are called fuzzy or locality-sensitive hashes; they’re used a lot in image processing for similarity testing, for example. I don’t consider them to be in the same category as normal hashes, though, because fuzzy hashes have vastly different properties.
- dgacmu 7y ago
  The term for this is locality sensitive hashing, and it's very useful in some contexts.
nneonneo 7y ago
Cryptographic hash functions can be orders of magnitude slower than functions tuned for hashtables and dictionaries. If you’re using them as hash table indexes, then you have to take the big cryptographically secure number and mod it by a small bucket count - and then you’re going to have collisions. If you don’t salt, then an attacker is going to predict the bucket indexes no matter how strong your hash function is, and since you can’t have that many buckets, they can just brute force to find collisions. Salting is the way to deal with these issues, and for hash tables it works well even if your hash function isn’t cryptographically secure. Hence, for hash tables, salt+fast hash function should be sufficient.
- yarg 7y ago
  Thanks.

by yarg 7y ago

yarg 7y ago

Actually, a counter-point: there might be situations where you want an anti-cryptographic hash function - where similar inputs produce generally similar hashes. It could have some application as a preprocessing step in clustering (if it could be done efficiently).

earenndil 7y ago
Easy: for n-byte output, separate input into n equally-sized chunks (pad with zeroes if not enough). For each chunk, XOR all the bytes together.
nneonneo 7y ago
Those are called fuzzy or locality-sensitive hashes; they’re used a lot in image processing for similarity testing, for example. I don’t consider them to be in the same category as normal hashes, though, because fuzzy hashes have vastly different properties.
dgacmu 7y ago
The term for this is locality sensitive hashing, and it's very useful in some contexts.

nneonneo 7y ago

Cryptographic hash functions can be orders of magnitude slower than functions tuned for hashtables and dictionaries. If you’re using them as hash table indexes, then you have to take the big cryptographically secure number and mod it by a small bucket count - and then you’re going to have collisions. If you don’t salt, then an attacker is going to predict the bucket indexes no matter how strong your hash function is, and since you can’t have that many buckets, they can just brute force to find collisions. Salting is the way to deal with these issues, and for hash tables it works well even if your hash function isn’t cryptographically secure. Hence, for hash tables, salt+fast hash function should be sufficient.

yarg 7y ago
Thanks.