4 ms·

SHA-3 shows secure hash functions are possible. But can we build fast ones?

9 points by vgnet 15y ago

gte910h 15y ago
Don't you want hash functions to be slow to prolong their lifespan?
- mtinkerhess 15y ago
  I'm not an expert on this but my understanding is that it's not the speed of a hash function that determines its security, because once an adversary is trying to brute-force a hash function you can just increase the length of the hash. The speed of the hash function is polynomial in the length of the output, but the cost of brute forcing is exponential in the length of the output, so if you have a faster hash function (or a faster processor) you can increase the size of the output by a constant multiple, and increase the cost of brute-forcing by an exponential amount, keeping the hash function secure. But I could be totally off-base here.
- jacques_chester 15y ago
  You've misunderstood the two key requirements of a hashing function. The first is to be secure. It should produce irreversible, unpredictable changes to at least half of the bits in the output string if one bit of input is changed. The second is to be fast. Hash functions are typically used to produce authentication of various pieces of original data. Each such unit of data might be small; hashes should not add an unacceptable overhead to communications, for example. By contrast, key-derivation functions should be slow, because they have a different threat profile. Using a hash function for key-derivation purposes is a mistake.
  - saurik 15y ago
    The problem I have with this simplification is that if I can brute force your hash (which is a feasible attack vector as computers get faster: people even sit around brute forcing MD5 nowadays, thanks to some mathematical attacks that reduce some of its strength), then I can spoof your "authentication". If you have two 128-bit hash algorithms, and one is fundamentally twice as slow as the other, it is effectively a 129-bit hash in comparison.
    - jacques_chester 15y ago
      You don't see hashes with, say, thousands of rounds because it's just too slow. Hash algorithms always exist in tension between security and speed. Because authentication is their purpose, not secrecy.

9 points by vgnet 15y ago

gte910h 15y ago

Don't you want hash functions to be slow to prolong their lifespan?

mtinkerhess 15y ago
I'm not an expert on this but my understanding is that it's not the speed of a hash function that determines its security, because once an adversary is trying to brute-force a hash function you can just increase the length of the hash. The speed of the hash function is polynomial in the length of the output, but the cost of brute forcing is exponential in the length of the output, so if you have a faster hash function (or a faster processor) you can increase the size of the output by a constant multiple, and increase the cost of brute-forcing by an exponential amount, keeping the hash function secure. But I could be totally off-base here.
jacques_chester 15y ago
You've misunderstood the two key requirements of a hashing function. The first is to be secure. It should produce irreversible, unpredictable changes to at least half of the bits in the output string if one bit of input is changed. The second is to be fast. Hash functions are typically used to produce authentication of various pieces of original data. Each such unit of data might be small; hashes should not add an unacceptable overhead to communications, for example. By contrast, key-derivation functions should be slow, because they have a different threat profile. Using a hash function for key-derivation purposes is a mistake.
- saurik 15y ago
  The problem I have with this simplification is that if I can brute force your hash (which is a feasible attack vector as computers get faster: people even sit around brute forcing MD5 nowadays, thanks to some mathematical attacks that reduce some of its strength), then I can spoof your "authentication". If you have two 128-bit hash algorithms, and one is fundamentally twice as slow as the other, it is effectively a 129-bit hash in comparison.
  - jacques_chester 15y ago
    You don't see hashes with, say, thousands of rounds because it's just too slow. Hash algorithms always exist in tension between security and speed. Because authentication is their purpose, not secrecy.