# Test randomness of a generated password?

As you know, there are many password generators out there to increase computer security.

Suppose I am given such a password (say, a string of letters, numbers, symbols, etc.), is there a way for me to test how random it is? Is there some sort of index for this measurement?

Thanks!

• Thank you so much for your answers! I wish I could mark all as part of the the final answer. :)
– hpy
Apr 4, 2012 at 23:12

On top of Daniel's great suggestion to use the information measures, you can consider breaking down the characters into groups to overcome the limitation of having to deal with way too many combinations. A natural breakdown is to capital letters (26), lower case letters (26), numbers (10), and other symbols (5-15 depending on implementation). So instead of having 70 independent symbols, you can deal with groups that have probabilities 26/70, 26/70, 10/70 and 8/70.

Alternatively, you can consider the transition probabilities from one character to the next. The password "blah273blah" would imply the transition probabilities "lower case -> lower case" of 6/10, "number -> number" 2/10, "lower case -> number" of 1/10, and "number -> lower case" of 1/10. All other probabilities are zeroes. These should be compared to the uniform transition probabilities (given above), although arguably Pearson $\chi^2$ will hardly work well with so many zero cells. I guess this is an extension of the run test for binary events. I am sure a multinomial extension exists and is applicable to this situation.

In any case, you need to have a reference distribution of whatever "test statistic" you will end up with, which can be obtained by simulation from your own reliable source of random passwords. It is arguably better to use the true random numbers for this purpose, e.g., from http://www.random.org.

When considering random generators and random number generators for security purposes you have to be extremely careful. To answer your question, there are many tests that you can carry out on RNGs, for example see the links offered here: http://csrc.nist.gov/groups/ST/toolkit/rng/batteries_stats_test.html

Please note that I am assuming that you are actually asking about "how to test random number generators for password generators" as opposed to the question "how can I measure the randomness (or entropy) of a given random array of bits" - which has been answered above.

Note that a random number generated can be easily used to generate passwords: generate several bytes of data and transform this data into the password using some transformation of your choice.

I wish to draw your attention to the notion of cryptographically secure RNGs. While the Mersenne Twister is generally considered as one of the better RNGs you can use because it is efficient and has very large periods before repetition, etc..., it is NOT considered to be cryptographically secure.

A cryptographically secure RNG algorithm is important for security sensitive applications (such as password generators). Without this property, an attacker can infer the current state of your RNG and be able to predict your next password.

Now, RNG algorithms are all pseudorandom (unless you use a truly random source such as http://www.random.org or a Quantum Random Number generator card). Given knowledge about the current state of the algorithm, we can predict perfectly the next "random" number. An attacker that infers this state would therefore be able to predict your next "random" password.

Besides the myriad of tests for a good Pseudo-Random Number Generator, also make sure that you check that it actually is cryptographically secure. Otherwise go for a true random number generator source.

Information theoretic entropy is often viewed as a 'measure' of how 'random' a random variable is. This would not tell you how random a specific password is, but would tell you how random the method for creating the password is. In general, the uniform distribution gives the highest entropy. In the context of the password constructor (for a fixed password length), this corresponds to picking each character independently and uniformly. Note that the longer the password length allowed, the more random it will be (and thus will have higher entropy).