Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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).
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$.
