How much is the entropy of a randomly generated password reduced if I regenerate until I get a password I like? [duplicate]

Question

In many of the answers and comments on the well-known XKCD #936: Short complex password, or long dictionary passphrase? question, the importance was stressed of generating the password randomly, and not just making one up. In particular, the current second highest voted answer on that question says:

Random choices are random and uniform. This is hard to achieve with human users. You must convince them to use a device for good randomness (a coin, not a brain), and to accept the result. This is the gist of my original answer (reproduced below). If the users alter the choices, if only by generating another password if the one they got "does not please them", then they depart from random uniformity, and the entropy can only be lowered (maximum entropy is achieved with uniform randomness; you cannot get better, but you can get much worse).

This got me wondering: what if I don't accept the result and instead generate a new random password? How big of an impact would that have on the entropy of the final generated password?

Presumably the more times I allow myself to reject a password, the more the entropy of the final password could potentially be reduced, so let's say for example that I generate 8 passwords and pick the one I like best. How much could that potentially reduce the effective entropy of the password I select? (Maybe log_2(8) = 3 bits as a worst-case scenario?)

Answer 1

Your assumption is reasonable. If we repeatedly generate truely random passwords and pick the one we like most then a good assumption is that it is the simplest among the generated list. For simplicity of the argument, let us assume that the passwords are numbers between 1 and N, inclusive, with small numbers being "simpler", that is: the attacker will attempt the numbers in order 1, 2, 3, ... and your pick of "most liked" password is also the lowest number among the ones generated. (You may imagine that 1 corresponds to "1234", 2 corresponds to "password", 3 corresponds to "summ3r", ..., 1000000 corresponds to "zg_uP%bwG", ...)

The expected value of a single random number is N/2, so the attacker will need N/2 attempts on average. But the expected value of the minimum of k random numbers is N/(k+1), so now the attacker will need only N/(k+1) attempts on average. Thus if k is not very small compared to N, the attacker will get a significant advantage.

Answer 2

Your rejection/acceptance of a truly randomly generated password, and how many times you reject until you accept, will not affect the entropy as the entropy is determined in isolation from generation to generation (just like each toss of a coin doesn't affect the entropy of the next toss). All strings have the same entropy, it's only the context of evaluation that determines the 'subjective entropy' (which isn't relevant).

But, the strength of a password isn't directly linked to its randomness - as you suggest - if you ask for a random sequence of 11 characters from letters and numbers then you could get password123 as your first random sequence. It would be completely random, just not very strong. It would have the same entropy as the next generation.

Similarly, although the entropy isn't less or more, if you keep generating random strings until you 'like' one you are more likely to select a weaker random string of characters (well, if your 'liking' is based on typical human considerations such as memorableness or lyrical quality or pronounceability etc.)

So entropy and human liking aren't connected, but liking and password strength most certainly are.

Answer 3

In order for user rejection of specific random word selections to have an meaningful impact on passphrase security those rejections would need to be predictable. Otherwise there's no way for an attacker to eliminate certain words or word pairings and save time in their attempts to guess the passphrase, which is the primary way this practice would benefit them. As David Scholefield points out, one particular random word selection doesn't have any less entropy than another.

If we had data that 90% of people will not choose a randomly generated passphrase that contains the word "asymptote" (either because it is meaningless to them or they worry about misspelling it), then an attacker could either eliminate all potential passphrases containing that word or deprioritize them so they are tried last in the guessing process. Excluding that one word eliminates hundreds of millions or billions of guesses (depending on the size of word dictionary being used to generate the passphrases, and passphrase length).

So as you can imagine being able to gather data on typical user word rejections for an entire dictionary of words would be very valuable to an attacker since it would probably allow them to eliminate significant portions of the work normally needed to brute force a passphrase. I'm not aware of any public research regarding the predictability of user acceptance of specific random words for passphrase use.

But there is data out there on words that people know and commonly use, which might correlate with their preference to then use those words in passphrases. Similar research exists on words that commonly appear in passwords. I also wouldn't be surprised to hear that there is unpublished research on passphrase word preferences that one or more intelligence agencies are keeping to themselves.

So to be most secure you should resist the temptation to reject a particular passphrase since you may be falling into a predictable pattern that is known to attackers. However, it is hard to quantify whether rejecting the occasional random passphrase in preference for another will impact your security enough to outweigh the potential usability benefits.

Answer 4

I believe the randomness would be reduced to lean to the human intuition that makes the password you chose "better".

Linguistic, phonetic, logical, and other patterns can be used to seed such an attack dictionary.

If a dictionary can be created, then it's not "perfect entropy", so choosing a password will reduce it somewhat.. but given the constraint of 8 passwords, I don't think the security reduction is significant.

Answer 5

It depends on the parameters of what you like. Say you prefer a password that you can type on your mobile device without switching keyboards. You can compute the entropy of passwords composed of only the characters on your main keyboard. If what you like is more subjective, the question becomes much harder to answer.