[Dovecot] Weird Authentication behaviour

[Joseph Tam]

Reindl Harald <h.reindl at thelounge.net> writes:

> frankly 8 chars is laughable, i recently wrote a PHP library to
> generate secure random passwords and for 100000 passwords get
> 13 collisions is way to much given that that means you have
> a collision every 8000 tries which means not you need 8000
> in a real world attack

(Off-topic)

Not that I disagree with the conclusion that 8 character passwords are
weak by todays standards, but there seems to be something wrong with
your generator (weak PRNG? limited character set?).  13 collisions in
10^5 passwords is terrible, even by 1980 Unix standards.

The keyspace for an 8-character alphanumeric password is 62^8, and
assuming a random selection of keys, you would need to generate 17,397,806
keys before expecting a 50% probability of finding one collision:

 	(Ref: http://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem)
 	p=0.5, d=62^8, n=sqrt(2*62^8*log(1/(1-0.5)) ~= 1.7E7

A hash collision (again, assuming crypt is a halfway decent hasher) is
even more unlikely, as the hash space is even larger (4096 salts * 64^11).

Jiri Bourek added

> Yes, AFAIK DES encryption is obsolete for very long time and if you know
> hash, it's quite easy to generate a secret which will match the hash ...

Quite easy?  Maybe if you could find a crypt rainbow tables for crypt().
Go ahead and invert "LXE5F6d8FPOa.".

Joseph Tam <jtam.home at gmail.com>