[cryptography] Password non-similarity?

Jonathan Katz jkatz at cs.umd.edu
Tue Jan 3 08:24:16 EST 2012

On Tue, 3 Jan 2012, Solar Designer wrote:

> 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.

At the risk of belaboring this point, there is no contradiction: You are 
calculating the probability of compromise after N attempts, and I was 
referring to the expected number of attempts before a compromise occurs.

More information about the cryptography mailing list