Security implications of slow-by-design hashes on relative security vs. hash size

Question

Would it be true to say that that one can get away with much smaller cryptographic hashes if the hashing algorithm is slow and expensive by design?

Example: let's say you want 128-bit hashes. This is considered insecure today since this is small enough to be able to be attacked via things like rainbow tables (if you have a ton of storage) and any partial break of the algorithm is more likely to be devastating. But what if your hash function is designed to be slow and expensive? An example would be balloon hashing or franken-hash algorithms like CryptoNight.

Slowing down the hash function makes each iteration expensive to compute, so theoretically it seems that one can get away with smaller security margins. For example let's say you use a partial break or a rainbow table to reduce the hash's strength to 2^64 bits. You still have to evaluate it 2^64 times. If each evaluation takes an average of 100ms even on very fast hardware, this still leaves millions of years to search for a collision even if you have a million CPU cores to work with. The same line of reasoning seems to apply to birthday and multi-collision attacks.

Obviously the wildcard here is ASICs, but techniques like memory hardness or intentional algorithmic complexity can reduce the advantage presented by an ASIC vs. a general purpose CPU (and greatly increase the design and production cost of an ASIC). An ASIC that speeds this up 1000X still takes many millions of years per ASIC for a brute force search. You'd need hundreds of millions of ASICs to search 2^64 hashes in reasonable time, which of course assumes you have some way of halving the security of a 2^128 hash.

Is this reasoning basically correct?

This builds on a previous question I asked about Grover's algorithm. Grover's algorithm can (only in theory so far) roughly halve the security of a hash, but it still requires one classical evaluation per quantum search iteration. This extends the question to include classical security.

Answer 1

You CAN get away with using less memory if the hash is expensive. However, that does not mean you should, and it would rarely make any sense.

So why would you try to "get away with" using smaller hash functions? You could save some storage space, which is definitely appealing. However memory is cheap, and using larger hash functions adds more security, it also has the benefit of being more future proof than a smaller hash.

But in the end, it depends entirely on your data. There are many uses for hash functions, and using a slow hash with ASIC preventative measures for a checksum would be silly. However, if you are storing passwords in a secure database, you would want to add a salt and/or pepper and use an ASIC-safe slow hash.

I also want to address a couple misconceptions:

1. Your example does not make much sense. A rainbow table is a set of pre-computed hash chains for some expected plaintexts. This means that you could compute a rainbow table for a 1024 bit function for a small factor more memory than a 128 bit function. And if you add a salt to all of your data, it becomes infeasible to use a rainbow table at all.

2. You say "any partial break of the algorithm is more likely to be devastating" Why is this? A flaw in a hash algorithm is a flaw. Assuming the search space is reduced, the more bits you have the safer you are; however this does not necessarily mean any flaw is "devastating", a flaw is nearly as likely to be devastating as in a larger hash function.