2
$\begingroup$

How do I pick passwords uniformly at random when given a min and max length?

It seems that if I first pick a random length, then choose random characters, this procedure will choose shorter length strings preferentially when you consider the number of different strings of a fixed length that are possible.

$\endgroup$
  • $\begingroup$ define your own number system (with the size of your character set as base), pick a number from the appropriate range and map-back? $\endgroup$ – SEJPM May 26 '16 at 12:24
  • 3
    $\begingroup$ Why bother? Simply using the maximum length is easier and only results in a small decrease of the password space. $\endgroup$ – CodesInChaos May 26 '16 at 17:48
4
$\begingroup$

In practice, it is sufficient to pick a random password with the maximum allowed length.

Assuming that your alphabet has $n$ different usable characters, the total number of passwords of length up to $k$ is $$t(k) = n + n^2 + n^3 + \dotsb + n^k = \sum_{j=1}^k n^j = \frac{n^{k+1}-1}{n-1},$$ and thus the fraction of all passwords that have length less than $k$ is $$\frac{t(k-1)}{t(k)} = \frac{n^k-1}{n^{k+1}-1} \approx \frac 1n.$$

For example, assuming that your passwords are composed of printable ASCII characters ($n = 95$), all the passwords shorter than the maximum length make up only about $1/95 \approx 1.05\%$ of the total password space.

(In any case, if these "passwords" are meant to be memorized by a human, it's generally much more effective to use a passphrase selected by picking random common words from a suitable dictionary. See diceware for a popular example implementation. Depending on the size of the dictionary used, each such word can encode about 10 to 13 bits of randomness, whereas two random printable ASCII characters encode a little over 13 bits, but a single meaningful word is much easier for a human to remember than a pair of random characters. Of course, such passphrases do end up being a couple of times longer than a random character sequence of equivalent entropy, but this is only a serious problem if you're running against some kind of a hard maximum length limit, in which case the existence of such a limit is the real problem.)

$\endgroup$
  • $\begingroup$ Can you confirm then that the algorithm I described would pick passwords in this 1.05% of the keyspace 9 times out of 10, if min=1, max=10, and that my concerns were valid? Can you also comment on rmalayters procedure? $\endgroup$ – user9070 May 26 '16 at 18:41
  • 1
    $\begingroup$ Yes, your algorithm (first pick random length, then generate random password of that length) would have only a 10% chance of generating a 10-character password, even though (assuming all printable ASCII characters are allowed) those 10-character passwords make up almost 99% of the entire password space. $\endgroup$ – Ilmari Karonen May 26 '16 at 21:57
1
$\begingroup$

Consider null as a valid character to be randomly selected. Remove null characters from the final string. If it is too short, try again.

$\endgroup$
  • 1
    $\begingroup$ This would also tend to favor short passwords over long ones. For a simple example, consider the case where the minimum length is 1, maximum is 2, and the alphabet only has two characters A and B. Letting _ represent the null character, your algorithm would first generate one of the following nine strings: AA, AB, A_, BA, BB, B_, _A, _B, __ (of which the last one would be rejected). After removal of _ characters, the single-character strings A and B would be generated twice as often as any of the two-character strings. $\endgroup$ – Ilmari Karonen May 26 '16 at 21:54
  • 1
    $\begingroup$ Your contrived example is completely irrelevant. With a sane length and alphabet, a null would have say only 1/95 probability in each position. Longer passwords would be favored by the fact that a null would be chosen infrequently at any single position. $\endgroup$ – rmalayter May 27 '16 at 0:10
  • 1
    $\begingroup$ I agree it's not quite that drastic in practice, but if the max length is N then there are still N permutations that construct the same password of length N-1 compared to 1 way for any password of length N. $\endgroup$ – Rup May 27 '16 at 8:23
  • $\begingroup$ @Rup that is true, so my answer isn'tso great. The only alternative I can see is to calculate the probability of each password length from the total number of combinations of all passwords between min and max. Generate a max-length password, then generate a random number and truncate the password to a shorter length based on the probability of the length. $\endgroup$ – rmalayter May 28 '16 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy