-62

Generating Random Passwords in PHP

Generating unbiased random passwords is a surprisingly non-trivial problem. Most naive solutions, such as taking the remainder of a random integer or shuffling a string, lead to biases in the passwords. These biases make the passwords significantly easier to crack. We start by discussing a few common, but incorrect, ways of generating passwords, then provide a secure password generator class for PHP.

Common Mistakes

Weak Psudeo-Random Number Generator (PRNG)

Psudeo-random number generators such as mt_rand are not sufficient for generating passwords. They are designed so that their output looks statistically random, but they make no effort to be unpredictable. Given some of their output, it is easy to figure out their internal state, which can be used to predict their future output.

The passwords generated by a PRNG can only be as secure as the PRNG's initial state. Weak PRNGs usually have a small state (32 bits, for example), which allows an attacker to crack a password generated by the PRNG, quickly, by guessing the state of the PRNG rather than guessing the password itself. Worse, since PRNGs are not designed for security, they are often seeded with easy-to-guess values, such as the current time, making their states extremely easy to guess.

Cryptographically secure random number generators (CSPRNG) must be used to generate passwords. CSPRNGs are unpredictable and incorporate randomness from the physical world (mouse movements, key presses, network packets) into their large internal state. In PHP, the operating system's CSPRNG can be accessed with the mcrypt_create_iv function.

Modulo Character Set Size

The following seems to be the most common naive solution:

 1 <?php
 2 // WARNING: THIS CODE IS INSECURE. DO NOT USE THIS CODE.
 3 $password = "";
 4 $charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 5 
 6 for($i = 0; $i < 8; $i++)
 7 {
 8     $random_int = mt_rand();
 9     $password .= $charset[$random_int % strlen($charset)];
10 }
11 
12 echo $password, "\n";
13 
14 ?>

This code makes two mistakes. First, it uses a weak PRNG. Second, it uses a large random integer to select from a set of N elements by computing the remainder of the random integer divided by N. This is insecure. Unless the number of possible random integers is a multiple of N, some characters will have a higher chance of being picked than others.

For example, if number between 0 and 94 is generated by taking the remainder of a random byte divided by 95, the numbers 0 to 65 have a higher chance of being picked than the numbers 66 to 94. There are 3 possible byte values that will generate 0 to 65: N, N+95, and N+95+95. There are only two byte values that will generate 66 through 94: N and N+95 (not N+95+95 because 66 + 95 + 95 = 256, which is more than one byte). The same applies when a larger random integer is used, but there is less bias. Still, don't use this method.

Unbiased Random Selection Using Binary Data

The only known way to make an unbiased random selection from a set of N elements, using random bits, is to repeatedly generate a random number between 0 and 2k – 1, where 2k is the smallest power of two greater than N, until the random number is between 0 and N – 1 so it can be used to select an element from the set (numbers that aren't in that range are discarded). It may seem wasteful or inefficient to throw away some of the random numbers, but good CSPRNGs are fast, and only about half of the random numbers will be thrown away on average [1].

The following PHP code uses the method mentioned above to generate random ASCII, alpha-numeric, and HEX passwords. It can also generate passwords from a custom character set. The code is explicitly placed into the public domain, so feel free to use it for any purpose whatsoever.

Example Usage:

1 <?php
2 require_once('PasswordGenerator.php');
3 $ascii = PasswordGenerator::getASCIIPassword(64);
4 $hex = PasswordGenerator::getHexPassword(64);
5 $alpha = PasswordGenerator::getAlphaNumericPassword(64);
6 $custom = PasswordGenerator::getCustomPassword(array('a', 'b'), 64);
7 echo $ascii, "\n", $hex, "\n", $alpha, "\n", $custom, "\n";
8 ?>

Output

kbH'q\rO`F!trPC=E1v)~D7<g@`Ise0QkSlI93Ne/2/IIKgiIKZWnLrh^_oo^&b)
6D574CFF661E146C530729F8D44B545BC3192D1439B4113132B2FC221AFF56A7
ic4vQ2OXMsOzCmsMnhEHFRc6rp2oDBUDq9KZJnFXsHbKO8xh5Kcpp9T4ZHFPcVg7
abbababbabbaabaaaaabbabbbbababaabbabbaaabbabababbaaabbaaababbbbb

PHP Source Code

Source Code on GitHub

References

  1. Tadayoshi Kohno, Niels Ferguson, and Bruce Schneier. "9.7 Choosing Random Elements." Cryptography Engineering: Design Principles and Practical Applications. Indianapolis, IN: Wiley Pub., 2010. Print.