How long should a hash be to be absolutely secure?

Question

Is there some sort of rule to determine how large a hash should be to ensure the security (meaning exactly one message maps to a given hash) of a message? Something that can be applied to any message, such as a 32-bit number or an 8-letter ASCII password.

Answer 1

exactly one message maps to a given hash

This is not possible due to the pigeonhole principle. As long as the input message to the hash function can be larger than the hash itself, it is guaranteed that some messages collide with each other and map to the same hash. This is normal and is not a problem for the security of hashes by itself.

You only need to ensure that the hash function is so large that intentionally finding such collisions (a collision attack) is computationally infeasible. A hash digest of n bits has a collision resistance of n / 2 bits. To achieve 128-bit security against a collision attack, it's thus necessary to have a hash digest of 256 bits. This is, of course, assuming the hash is cryptographically secure (like SHA-256) in order to avoid there being attacks that take a shortcut and can find collisions more easily than by brute force.

Answer 2

It depends very much on what you want to achieve. First, as already pointed out by forest, what you actually want in terms of only one input maps one hash is -- in the gerneral case -- not possible. It is possible in special cases if the hash is as long as the input, or longer. Since you mentioned 32-bit integers, there exist indeed 32-bit integer-to-integer hashes.
Note however that the possible number of inputs is so small at 32 bits that building a lookup table is actually quite feasible (takes up a mere 32GB, so on the computer that I'm using right now, the lookup table would fit completely into RAM!). Needless to say that this is not, and cannot possibly be secure, regardless of what actual algorithm you use.

If you plan to identify something (such as a file or a string) with the hash, and malicious tampering is not a consideration or at least not your first priority, then you can pretty much consider 64 bits "good enough" and 128 bits "absolutely secure".
CRC32 which doesn't even provide the guarantees given by cryptographically secure hashes has been accepted as "quite good" for telling things apart and reliably identifying accidential modifications for many years (and 64 bits is a wholly different order of magnitude compared to 32!!!). UUIDs are 128 bits, and they are considered "unique" when they clearly aren't. But for all practical matters, they are.
_{I was going to add that GIT, which is used among other things to host the Linux kernel and other security-relevant software used in billions of devices (thus making it a very interesting target for an attack) uses 128 bit hashes to keep stuff apart and secure, but it's actually 160 bits...}

Now, if malicious tampering is a concern, you most likely want a secure hash algorithm (so CRC won't do the trick), but you do not necessarily need more bits. It just depends on what you want to protect, and for how long, and against what kind of attack.
Siphash or Cityhash (by default, in the original/common configuration, there's 32 and 128 bit variants, too) are just 64 bits. Which is mighty fine, and absolutely secure if you use it e.g. to ensure the integrity of some reasonably sized message that you send over the internet. Could a sufficiently powerful attacker possibly find a collision within 15-20 minutes? Sure. But who cares, after 15 minutes it's 14 minutes and 59 seconds too late for him to do something with it.
It is, on the other hand, not at all fine if you plan to use it for something that is stored for a longer time.

In that case, you want at least 128, better 160 bits, and in order to say with reasonable certitude "absolutely secure", you will need 256 bits or upwards, again it depends what exactly you want. AES-CGM, which is considered "good enough for pretty much everybody" has at most 128 bits (down to 96).

Is your attacker getting to choose two inputs, so a birthday attack is applicable? In that case, 128 bits is only worth 64 bits (or, if projections hold, 42 bits on quantum computers). That's definitely a bit meager and not enough for saying "good enough", let alone "absolutely secure".

Are you only worrying about second preimage attacks, i.e. you are getting to choose one of the inputs? In that case, 128 bits will be "mighty fine", 160 bits will be "unbreakable", and 256 bits will be "ridiculously unbreakable". Unless the algorithm itself is broken, that is.

tl;dr
All in all, if you prefer an unconditional answer that doesn't require you to take preconditions into consideration, you should consider that answer being 256 or more.
256 bits is within the realm of "ridiculously impossible", but one should consider that algorithms do get broken over time, so a 256 bit algorithm might only be worth a workload of 2^140 or 2^150 in 10-20 years, there is no way of knowing. If you are a bit paranoid, that may not be enough for you to say "absolutely secure" (though for most people I guess it's still way enough).

Hence, without knowing your paranoia level, I say "256 or more". A few extra bits don't really cost much, but they have a huge impact. Make it 384 or even 512, why not. If a 512-bit algorithm is very, very significantly broken and weakened to a workload of, say 2^300, and hyper-quantum-super-magic computers invented by para-dimensional aliens can, by applying mathematically and physically impossible magic, further reduce that to a workload of 2^150 bits, then you're still pretty much good to go.

Answer 3

The output size of a hash function puts an upper bound on its security level. The three main properties any cryptographic hash function is expected to have is resistance to collision, first-preimage, and second-preimage attacks.

If an algorithm has n-bit security, it means that there is no attack that breaks the relevant security properties which would require much fewer than 2ⁿ steps (approximately and on average) to succeed. If n is large enough, then we can be practically certain that no one has enough computing power to attack a system.

From a hash function with n-bit output, we can expect up to n-bit security when it comes to preimage attacks, but no higher. One could hypothetically search for a preimage by brute force and succeed after, on average, 2ⁿ tries.)

For collision resistance, however, the birthday problem means you would need 2*n bits instead of n bits.

We often aim for 128-bit security, so that means the smallest acceptable digest size is 256 bits. 128-bit security leaves you with a big enough security margin that you would probably still be safe using a few less output bits, but using too few bits is risky.

Note: This is an upper bound. Even though algorithms like Murmur3, CityHash, xxHash, and others may claim to be high quality and have long outputs, they don't provide meaningful security.

Definitely do not choose an algorithm based only on its output size. Output size only determines a hash's maximum theoretical strength. Not its actual strength.

Instead choose a collision resistant hash function that people agree are safe, eg. Blake-2, SHA-3, Skein, or SHA-2.

Note 2: If you're using something like SHA-512, then you can treat the algorithm as if distinct inputs will always result in unique outputs. With probability almost equal to one, you will not get duplicates digests for any real-world set of inputs.

The actual probability of seeing colliding digests depends both on how many messages you try to hash and how many possible outputs there can be. The number of distinct messages you could try to hash is naturally limited because your power to compute hashes is limited.

Hash functions are not truly injective, but software developers can use a large collision resistant hash function and treat it as if that were true. The chance of inadvertently producing one or more collisions is technically non-zero, but a person's brain cannot comprehend how incredibly improbable it is.

Answer 4

If we must have it so that each message digest corresponds to exactly one message, then our digest must be as large as the longest possible message.

We take the message as a giant N-bit integer and calculate another N-bit integer from it using an invertible function. One way to do this would be to encrypt the message with a symmetric cipher (whose key then specifies the hashing function).

Of course, hashes which are as long as the longest message are impractical, because a key requirement for message digests is that they are of a fixed, small size, which is often much smaller than the digested messages themselves.

However, if for whatever reason you ever need to convert a small message into a code which is free of collisions, and from which the message is difficult to recover, the above would be a way to do it.