6 ms·

Ok, thank you. I understand that it is for implementing things like dictionaries/hash tables.

lucb1e 7y ago
Or integrity checking for non-authenticated encryption modes (wouldn't want file encryption or https to be slow).
nneonneo 7y ago
No, Blake3 is a cryptographic hash algorithm, not for dictionaries or hash tables. It is intended for cryptographic signatures, file/data integrity, message authentication codes, etc. For dictionaries/hash tables you'd typically use a very fast hash algorithm like xxHash, murmurHash, etc. Those are tuned for speed but can have collisions (typically they have very short outputs - 32 or 64 bits - so that they're easy to compare and compute with). For cryptographic purposes (authenticity, integrity) you'd use a medium speed algorithm like SHA2/3, Blake2/3, etc. which are reasonably fast and essentially guarantee there won't be collisions (i.e. it's computationally hard to come up with collisions). These are meant to be computed quickly and potentially in parallel because you want to be able to verify data fast. For password hashing you'd use a slow algorithm like bcrypt/scrypt or Argon2. These are designed specifically to be slow; some also use lots of memory specifically to slow down parallel attackers. You want password hashing to be relatively slow because you need to protect low-entropy data (a typical password only has a few dozen bits of security). By making the algorithm deliberately slow you would ensure that an attacker can't quickly guess the password, even if they have the hash. These are the three major categories of hash; knowing which one to use in which application is pretty important. Don't mix them up!
- 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.

Or integrity checking for non-authenticated encryption modes (wouldn't want file encryption or https to be slow).

No, Blake3 is a cryptographic hash algorithm, not for dictionaries or hash tables. It is intended for cryptographic signatures, file/data integrity, message authentication codes, etc. For dictionaries/hash tables you'd typically use a very fast hash algorithm like xxHash, murmurHash, etc. Those are tuned for speed but can have collisions (typically they have very short outputs - 32 or 64 bits - so that they're easy to compare and compute with). For cryptographic purposes (authenticity, integrity) you'd use a medium speed algorithm like SHA2/3, Blake2/3, etc. which are reasonably fast and essentially guarantee there won't be collisions (i.e. it's computationally hard to come up with collisions). These are meant to be computed quickly and potentially in parallel because you want to be able to verify data fast. For password hashing you'd use a slow algorithm like bcrypt/scrypt or Argon2. These are designed specifically to be slow; some also use lots of memory specifically to slow down parallel attackers. You want password hashing to be relatively slow because you need to protect low-entropy data (a typical password only has a few dozen bits of security). By making the algorithm deliberately slow you would ensure that an attacker can't quickly guess the password, even if they have the hash. These are the three major categories of hash; knowing which one to use in which application is pretty important. Don't mix them up!

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.