# What is the probability of the first half of a hash output being identical to the first half of another hash output?

Let's say for example that I encrypt a password with some hash function and receive a 256-bit hash value in return. What are the chances that the first 128-bits (half) of this value are identical to the first 128-bits of another hash output?

If you're feeling generous, what are the chances that the first 64-bits (1/4) of the output are identical to the first 64-bits of another output?

• Is that 'identical to the first 128-bits of one specific (distinct) hash output', or is it 'identical to the first 128-bits of one of these large number of hash outputs'? If the second, the probability would depend on how large of a list you got. – poncho Dec 20 '16 at 16:47
• Actually, I was thinking more of the first - what the probability is that the first half of one unique hash value would be identical to the first half of one other unique hash value. But, thank you for your input! – Liv Dec 20 '16 at 16:51

Let's say for example that I encrypt a password with some hash function and receive a 256-bit hash in return.

You cannot encrypt a password using a hash function, you can only create a hash value as the name implies.

What are the chances that the first 128-bits (half) of this key are identical to the first 128-bits of another key?

The hash value can be used as a key, but usually you'd use a KDF for that. Hash functions can be used as KDF, but you're better off using a real KDF such as HKDF.

Obviously if the amount of possible "key" or "password" input is (next to) infinite then the amount of "keys" that map to a certain hash value is infinite as well. The same goes of course for the first 128 bits of the output.

The trick is that finding this particular input is hard as hashes are one-way. Basically you'd have to iterate over all possible inputs to find the hash, and iterating over that large an amount is (completely) infeasible.

Once you've chosen a key / password then you would have to perform a pre-image attack. In that case the hash is secure then you'd simply have a chance of $1 \over 2^n$ that another key / password hashes to the same value, where $n$ is the output size. So that's $1 \over 2^{128}$ for 128 bits of output and $1 \over 2^{64}$ for 64 bit of output.

If you just generate a large number of passwords then the chances of collisions between the set of hashes grows as well. In that case you have to assume that the birthday attack applies. The security then depends on the amount of hashes. For very large lists you should use 128 bits of output (giving about $2^{64}$ bits security for $2^{64}$ outputs).

• I.e. brute forcing 128 bits of output would be about as hard as finding a key used for AES-128, something nobody will try to achieve. The chance of stumbling on it by chance is next to zero, even for 64 bit output. – Maarten Bodewes Dec 20 '16 at 16:43
• Awesome, thank you so much for walking me through that. And as well thank you for correcting my jargon. I'm relatively knew to working with hashes, and I'm trying to learn as much as I can - so I greatly appreciate your help! – Liv Dec 20 '16 at 16:52

Short answer: one in $2^{128}$.

Slightly longer answer: Assuming that the hash function you're using is indistinguishable from a random oracle, its output for each distinct input will effectively behave like a uniformly distributed random bitstring of the specified output length. Thus, the probability that the $k$ bit prefixes of the hash outputs for two distinct inputs are the same is $1/2^k$.

• Thank you for your help! Just out of curiosity, if one is to use a random oracle is it possible to revert the random value back into a password? I'm assuming that it is possible, but I can't really understand how that would be so if the value is totally random. I guess unless the random values and passwords combinations are stored somewhere? But then how would that be secure? – Liv Dec 20 '16 at 17:04
• No, it's generally not possible to revert a hash output back into the input (or any input) that generates it, except by brute force search. In fact, this is an explicit design criterion for cryptographic hash functions. – Ilmari Karonen Dec 20 '16 at 17:07
• Okay, I understand. Thank you for the clarification. – Liv Dec 20 '16 at 17:19