Good pre-image resistance value for hash visualization

Question

I want to do "hash visualization", i.e. derive a human-meaningful information from a hash, like a phrase or an avatar. But the current techniques usually don't use many bits, for example tripphrases by Bret Victor only use roughly 43 bits. This is a problem because all the hash isn't used, so using a "big" hash function with many bits wouldn't help.

What is the minimum number of bits in the output of an "ideal" hash function that would guarantee preimage resistance by modern standards (i.e. with the biggest computing power that we can gather today)? This doesn't need collision resistance.

Answer 1

I disregard the perfect hash requirement.

In the application asking for preimage-resistance with a narrow hash, one should use a purposely-slow memory-hard hash (as used for passwords, also known as key-streching or password-based hash). This greatly reduces the number of bits needed for preimage resistance.

More precisely, we want to build a hash that starts with a fast hash of the payload (e.g. with SHA-512), then performs a slow hash of the result and (if the application allows) salt¹ and/or pepper² (e.g. per Argon2id), with the largest parametrization (iterations, threads, memory size) that the application allows.

If in the application one spends 1 second slow-hashing, and the adversary can spend $2^{25}$ more time (over a year) with $2^{20}$ (over a million) more×better computing resources, and we want residual probability $2^{-10}$ (less that one in a thousand) that the adversary succeeds, we need $25+20+10=55$ bits of hash.

This hash size is date-independent, but does not account for how much time the system must remain secure without adjustment of parametrization of the slow hash. Add like 1 or 2 bits per year to account for progress in technologies.

Caution: the need for collision-resistance is easily overlooked³, and much more bits of hash are needed for that. With the same hypothesis, we'd need $2\times(25+20)+10-1=99$ bits of hash (see this), and twice more extra bit per year for progress in technologies.

---

¹ Salt could be an email or/and a random number. The idea is to make it impossible for an adversary to amortize the cost of the slow hash across multiple targets with different salt, and make it impossible to start a meaningful attack before knowing the salt.

² Pepper could be a server-unique string, tentatively kept secret, but considered public in a conservative security analysis.

³ For example, collision resistance is required for integrity if an adversary can influence the hashed content after the last unpredictable step in its generation. With preimage-resistance only, a maintainer of a Unix distribution that uses an automated nightly build is vulnerable to a contributor maliciously changing a text in release note and becoming capable of producing something unrelated to the original but with the same hash.