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.