Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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!
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).
Another way to look at this is to assume nothing is known about the method of constructing the passwords (i.e. from the point of view of a hacker). Then, one could put a prior on the space of possible passwords. A smart prior would probably make passwords that contain english words more likely than strings of random characters, as people tend to make their passwords something meaningful to them since this makes it easier to remember. The 'measure' or 'randomness' would then be the probability assigned to the given password under your prior. If you had access to a number of passwords created by the generator, you could use this data to update your prior to a more accurate distribution.
However, if you are only shown one password, there is very little information to go on. It would be difficult to make a judgement of its 'randomness' unless more data on the generator could be collected.
