# Is this algorithm for a random string cryptographically secure?

I've pieced together this algorithm (if it can be called that) from various bits of code I've seen online, and I'm wondering how cryptographically secure it is. It's used to generate passwords:

``````function seed_random() {
\$seed = crc32(uniqid(sha1(microtime(true) . getmypid()), true));
mt_srand(\$seed);
\$n = mt_rand(1, 200);
for (\$i = 0; \$i < \$n; \$i++) {
mt_rand();
}
}

function mt_rand_custom(\$min, \$max) {
seed_random();
return mt_rand(\$min, \$max);
}

\$legal_characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'_!@#\$^*?<>[]{}~(),";
seed_random();
\$command = 'head -c 500 /dev/urandom | tr -dc %s | head -c %s; echo';
return shell_exec(sprintf(\$command, \$legal_characters, \$length));
}

}
``````

I know security, especially in a web environment, depends on numerous other things (e.g. is the password being sent over SSL) but I'm curious about this specific set of functions. Thank you for the feedback.

EDIT: Even though the sample is no longer using the mt_random_custom function, any feedback on that would be greatly appreciated as well, so I left it in.

-
Why do you use a random password length? This alone makes it difficult to estimate the entropy of your generated password (as it is very depending of this length). – Paŭlo Ebermann Aug 12 '11 at 21:18
Although this generator is meant for general use, it's primary goal was for a site with 15 characters as the minimum password length. You're right, I probably don't need the upper bound. I'll just set it at 10, for the sake of simplicity. – Ricardo Altamirano Aug 12 '11 at 21:22

In your code, you have to fill `\$legal_characters` with the list of characters that you accept as part of a password. E.g.:

``````\$legal_characters = "abcdefghijklmnopqrstuvwxyz";
``````

if you want passwords consisting of lowercase letters (all lowercase latin letters, but no other characters and no accents).

This code is a bit weird; it uses `mt_rand()` (an internal PRNG) seeded with the current time and the process ID to get the length of the password, between 15 and 60 characters. Then it uses `/dev/urandom` for the password itself, which is smart since `mt_rand()` is not cryptographically secure (especially since the process ID is not something which is very secret, and neither is the current time).

The actual password generation work thus: it produces 500 random bytes (from `/dev/urandom`), then removes all those which are not in the set of accepted characters (that's the "`tr`"), and finally truncates again the remaining sequence of characters to the desired length. This process generates uniformly random sequences, so that's good, and `/dev/urandom` is the appropriate PRNG for that. Note, though, a few caveats:

• If the set of "legal characters" is small, you could end with a shorter password. E.g. if you want passwords with only digits from 1 to 6, there will be, on average, only 12 or so matching bytes in the 500 random bytes. The code has no failsafe for "too short". If you set `\$legal_characters` to all 26 lowercase letters, then about 1 byte in 10 will be legal (byte values range from 0 to 255, and 26/256 is close to 1/10) and, on average, the "`tr`" part will yield about 50 characters, and it is extremely improbable that it will yield less than 20. Still, this is worth noting and there should be a failsafe.

• It makes little sense to have a variable length for the password. If a password of minimal length is acceptable security-wise, then all passwords could have that length. And if it is not acceptable, then why do you use that minimal length ? You'd better use a single, fixed length, rather than a range. This would allow you to remove `seed_random()` and `mt_rand_custom()`, substantially simplifying the code.

• A "password" is something that a human being will be able to type an memorize -- hence "word". Will he memorize a 60-character sequence ? I am sure there is a medical name for such a condition.

• You should set the length of the passwords to an "appropriate" value such that the entropy will be high enough. If there are x legal characters and the password length is n, then the entropy will be xn. What entropy is needed depends on the intended usage. For authenticating users on a Web site, through an appropriate SSL tunnel, 240 ("40 bits" of entropy) is more than enough, which translates to 9 lowercase letters (269 is greater than 240).

• The code uses unixisms (`/dev/urandom`, `head`, `tr`...) and will have a hard time running on, say, a Windows server (and PHP runs on Windows, too).

Summary: the passwords will be strong, but the code is weird. You should drop the variable length, and if your users can swallow 60-character passwords, then please congratulate them for me. Or sell them to a zoo. Here is a simplified code which should be OK (warning: I do not use PHP so I am improvising here):

``````function generate_password() {
return shell_exec('head -c 500 /dev/urandom | tr -dc abcdefghijklmnopqrstuvwxyz | head -c 9; echo');
}
``````
-
Thanks for all the input; I snipped the declared value of `\$legal_characters` because it was a long value, so I put a comment in place of the actual value. I added the true value back in for the sake of readability. It is always at least the set of characters stated, if not more. - I'm confused why `tr` would yield on average 100 characters when using 26 lowercase letters. 6/256*500 ~= 12, as you said, but 26/256*500 ~= 500*1/10 ~= 50. I ran that same calculation initially with the 81 characters in `\$legal_characters` (500*81/256 ~= 160) and figured that would be enough. – Ricardo Altamirano Aug 12 '11 at 22:13
Also, I figured I could always increase the number of bytes drawn from /dev/urandom if need be, and I could do that within the problem itself through a simple string substitution. mt_rand_custom() wasn't really related to the function itself; variable length was something to mix up the output, nothing more. It's not really related to the strength of the algorithm. I'm not worried about supporting Windows servers, either, because my client has no intention (or the funds, for that matter) to run a Windows servers, and that single command is easy enough to swap out. – Ricardo Altamirano Aug 12 '11 at 22:17
And to spam with one more comment, whether or not the users will remember a 60 character password is beyond me. Maybe they'll surprise me. From a learning standpoint I'm more interested in the strength or weakness of the algorithm. Thanks for the feedback! – Ricardo Altamirano Aug 12 '11 at 22:19
Sorry about the "one hundred", it was a mistake on my part. You understood it well enough. I edited the offending part. – Thomas Pornin Aug 12 '11 at 22:53
Not a problem; I just wanted to make sure at least that part of my math was correct. I really appreciate your answer, though (and so thorough!) Thank you again. I'd vote it up if I had enough reputation. – Ricardo Altamirano Aug 12 '11 at 23:03

Analysis. Your code has some shortcomings:

1. Buggy use of system(). I suspect your shell command isn't going to do what you want it to, because you haven't quoted various shell metacharacters. Instead of `tr -dc %s`, you need `tr -dc '%s'`, and then you need to escape the single-quote in \$legal_characters.

2. Too-broad set of characters. This isn't going to generate passwords that can be reliably used on all sites. Many sites impose restrictions on which characters are allowed in passwords (e.g., they may prohibit single-quote). As a result, if you use your script in practice, you'll find it often generates passwords that some sites will reject. I'd suggest limiting the range of characters to a-zA-Z0-9, for maximum portability. This is not going to significantly reduce entropy or password security, but it'll make your script more useful.

3. Dead code. You have useless dead code (`mt_rand_custom()`). That code is also crummy stuff and not secure for cryptographic purposes, but that's a tangent: if you want to ask about that code, put it in a separate question. Don't stuff two questions into one post.

Solution. @Thomas Pornin's one-line shell command is much better. Personally, I'd improve it slightly by allowing capital letters and numbers:

``````head -c 500 /dev/urandom | tr -dc a-zA-Z0-9 | head -c 12; echo
``````

This is enough to get you 71 bits of entropy, which should be more than enough for a website password, and the resulting passwords should be accepted by pretty much every web site out there.

(If you want a shorter password, replacing the `12` by `10` gets you a 10-character password with 59 bits of entropy, which is probably still enough for all reasonable purposes. A 8-character password would have 47 bits of entropy, which is also probably enough, as long as the web site's password hash database is not compromised -- and for most users, that's not the main thing they need to worry about. A 8-character site-specific password is good enough to prevent online password guessing attacks, which is probably the most important threat that most users face.)

-
1. The shell command is working perfectly now, without escaping, but I'll keep that in mind. 2. The set of characters is easy enough to change dynamically; I'll probably change it to include fewer symbols, though. 3. mt_rand_custom was used in the original question to generate a random length for the password, but was removed to focus on the other code (see comments above). Thanks for the help! – Ricardo Altamirano Aug 13 '11 at 13:28
8 character lower, upper case letters and numbers password stored as NTLM is crackable in about 15 hours on 3GHz C2D using brute-force, or in about 5 minutes using 500GB rainbow tables... – Hubert Kario Aug 14 '11 at 14:04
@Hubert, the primary risk most website users need to defend against is online password guessing. Any decent website should ensure that password hashes don't fall into the hands of an adversary; only in exceptional cases do attackers have access to password hashes that let them mount offline attacks. (BTW we're talking about website passwords, so they're not going to be hashed with NTLM.) If you want to defend against offline attacks, you can increase the password length to 10 characters (that's 59 bits of entropy) or 12 characters (71 bits). – D.W. Aug 14 '11 at 17:26
@D.W.: "Any decent website" Oh, you mean, ones run by the likes of Sony or US federal agencies? No website is "decent", you have to assume the worst. Rainbow tables for SHA1 and MD5 hashes are not much larger... – Hubert Kario Aug 14 '11 at 17:53
@pythonscript, you might want to read a little more about best practices for password hashing. (1) Best practice is to use bcrypt or PBKDF2, to slow down offline password search, if the password dictionary is leaked. (2) "salt is encrypted with 256-bit AES" - huh? That doesn't sound like you're using the salt properly. The proper use of salt is to generate a new random salt for each user, and store two items associated with that user's account: the salt, and Hash(password, salt). – D.W. Aug 15 '11 at 2:17