[cryptography] Password non-similarity?

Solar Designer solar at openwall.com
Mon Jan 2 22:12:14 EST 2012


On Mon, Jan 02, 2012 at 09:40:36PM -0500, Jonathan Katz wrote:
> Say passwords are chosen uniformly from a space of size N. If you never 
> change your password, then an adversary is guaranteed to guess your 
> password in N attempts, and in expectation guesses your password in N/2 
> attempts.
> 
> If you change passwords constantly, and an adversary guesses a random 
> password (with replacement) each password-guessing attempt, then in 
> expectation the adversary guesses your password in N attempts.

Not exactly.  In N attempts, assuming that N is very large, their chance
will be more like 1-1/e, which is around 63%.  For a 50% chance, I think
they need to try merely N*ln(2) passwords, or about 69% of N.

> Not much of an advantage.

Right.  About 39% of extra effort for the attacker (50% to 69% of the
keyspace to test) for a 50% chance.

Alexander



More information about the cryptography mailing list