[cryptography] Number of hash function preimages

Eitan Adler lists at eitanadler.com
Sat Mar 10 20:24:04 EST 2012


On Sat, Mar 10, 2012 at 7:28 PM, Jon Callas <jon at callas.org> wrote:
>>
>> 2) Is it known if every (valid) digest has always more than one
>> preimage? To state it otherwise: Does a collision exist for every
>> message? (i.e., is the set h^{-1}(x) larger than 1 for every x in the
>> image of h?).
>>
>
> Sure, by the pigeonhole principle. Consider a hash with 256-bit (32-byte) output. For messages larger than 32 bytes, by the pigeonhole principle, there must be collisions. For messages smaller than 32 bytes, they might collide on themselves but don't have to, but there will be some large message that collides with it.

I think you are misunderstanding the question (or at the very least I
am). The pigeonhole principle only shows that there exist collisions
not that collisions exist for every element in the codomain.
Think about the function over the natural numbers:
f(x) = {
1, if x = 0
2, if x > 0
3, if x < 0
}

While there exist collisions within N it isn't true that every element
in the co-domain has a collision.

-- 
Eitan Adler



More information about the cryptography mailing list