compare-by-hash (was Re: sharing /etc/passwd)

[Giorgos Keramidas]

On 2004-09-27 07:13, Colin Percival <cperciva at wadham.ox.ac.uk> wrote:
> Giorgos Keramidas wrote:
> >Increasing the number of bits the hash key uses will decrease the
> >possibility of a collision but never eliminate it entirely, AFAICT.
>
> How small does a chance of error need to be before you're willing to
> ignore it?

That's a good question.  I'm not sure I have a definitive answer, but
the possibility of a collision is indeed scary.  Especially since I
haven't seen a study of the real probability of a collition is, given
the fact that passwords aren't (normally) random binary data but a
much smaller subset of the universe being hashed.

> If an appropriately strong hash is used (eg, SHA1), then the probability
> of obtaining an incorrect /etc/*pwd.db with a correct hash is much
> smaller than the probability of a random incorrect password being
> accepted.  Remember, passwords are stored by their MD5 hashes, so a
> random password has a 2^(-128) chance of working.

I was probably being unreasonably paranoid about 'modified' passwords
that don't get detected as modified, but what you describe is also
true.