3 ms·

Uh, wait a second... 64 bit hashing means only 2^64 . Understanding the birthday paradox ( https://en.wikipedia.org/wiki/Birthday_attack https://en.wikipedia.o

Uh, wait a second... 64 bit hashing means only 2^64 . Understanding the birthday paradox ( https://en.wikipedia.org/wiki/Birthday_attack https://en.wikipedia.org/wiki/Birthday_attack ) means that one needs only process 2^32 hashes to find a collision. Yuck. NO.

deleted 8y ago
[deleted]
teraflop 8y ago
Hash functions are used in a lot of situations where cryptographic collision-resistance is not particularly important.
MichaelBurge 8y ago
Not to mention a "fast hash" is inherently insecure, so the author must be mistaken: He should be trying to add arithmetic operations rather than remove them.
- bmm6o 8y ago
  This is a common misunderstanding (even with the caveat that you are talking about cryptography and the author is not). There is no reason that the hashes used for e.g. signing a document should be slow. If you have an application where you need the operation to be slow you can construct an iterative version; you'll want an adjustable work factor anyway.
- CodesInChaos 8y ago
  For most purposes fast hash functions are preferred. Expensive hash functions are only required for some specialized uses, such as password hashing or key-strengthening.
- olliej 8y ago
  Fast hashes are not inherently insecure - in fact you want hashing to be as fast as possible. You may be confusing the general case of hashing data, with the specific case of hashing passwords. The goal of the former is to provide a hash such that the likelihood of any arbitrary objects hashing to the same value is proportional to the square of the hash size (I think?), for cryptographic hashes their are additional goals like the hash output being uniform across all inputs, and that changing any single bit in the input should on average change half the bits in the output, etc. that’s because the use case is validation of a single input - eg verifying your download isn’t corrupt or whatever. For passwords the goal is different - you’re generally dealing with small objects, and so the cost of an “expensive” hash being measure in milliseconds is acceptable - the expectation being that people generally don’t get them wrong. But the attack scenario here is an attacker with a password hash wanting to brute force a large number of passwords to find the one that hashes to it. Given large is potentially very large, it doesn’t take a huge amount of time per hash to make the attack non viable. This particular version is hashing of the former type, without cryptographic concerns. It’s goal - to my reading - is to be a hash function that achieves something close to a single bit change flipping half the bits, while also guaranteeing that no two values hash to the same value.
CodesInChaos 8y ago
You are talking about unkeyed collision resistant cryptographic hashes. Which make collisions expensive to find. The article is about a different kind of hash, namely keyed universal hashes. The idea behind a universal hash is that for any two distinct messages, the hash will only collide for a negligible fraction of keys. This is an absolute mathematical property, so it holds even against computationally unbounded adversaries. Such a function can be used to construct MACs/PRFs, such as GHash or Poly1305.

deleted 8y ago

[deleted]

teraflop 8y ago

Hash functions are used in a lot of situations where cryptographic collision-resistance is not particularly important.

MichaelBurge 8y ago

Not to mention a "fast hash" is inherently insecure, so the author must be mistaken: He should be trying to add arithmetic operations rather than remove them.

bmm6o 8y ago
This is a common misunderstanding (even with the caveat that you are talking about cryptography and the author is not). There is no reason that the hashes used for e.g. signing a document should be slow. If you have an application where you need the operation to be slow you can construct an iterative version; you'll want an adjustable work factor anyway.
CodesInChaos 8y ago
For most purposes fast hash functions are preferred. Expensive hash functions are only required for some specialized uses, such as password hashing or key-strengthening.
olliej 8y ago
Fast hashes are not inherently insecure - in fact you want hashing to be as fast as possible. You may be confusing the general case of hashing data, with the specific case of hashing passwords. The goal of the former is to provide a hash such that the likelihood of any arbitrary objects hashing to the same value is proportional to the square of the hash size (I think?), for cryptographic hashes their are additional goals like the hash output being uniform across all inputs, and that changing any single bit in the input should on average change half the bits in the output, etc. that’s because the use case is validation of a single input - eg verifying your download isn’t corrupt or whatever. For passwords the goal is different - you’re generally dealing with small objects, and so the cost of an “expensive” hash being measure in milliseconds is acceptable - the expectation being that people generally don’t get them wrong. But the attack scenario here is an attacker with a password hash wanting to brute force a large number of passwords to find the one that hashes to it. Given large is potentially very large, it doesn’t take a huge amount of time per hash to make the attack non viable. This particular version is hashing of the former type, without cryptographic concerns. It’s goal - to my reading - is to be a hash function that achieves something close to a single bit change flipping half the bits, while also guaranteeing that no two values hash to the same value.

CodesInChaos 8y ago

You are talking about unkeyed collision resistant cryptographic hashes. Which make collisions expensive to find. The article is about a different kind of hash, namely keyed universal hashes. The idea behind a universal hash is that for any two distinct messages, the hash will only collide for a negligible fraction of keys. This is an absolute mathematical property, so it holds even against computationally unbounded adversaries. Such a function can be used to construct MACs/PRFs, such as GHash or Poly1305.