Saturday, July 8, 2017

Most Random Password Generators are Bad

Good for you!  You're taking the advice of experts and clicking "Generate Password", resulting in 10 characters of gibberish.  There!  Now your password will take thousands of years to crack.

Um ... not necessarily.  Try a few days.


RAND() LIMITS ENTROPY TO 32 BITS

When using the pseudo-random number generator supplied by most language libraries, the entropy of the resulting password is limited to 32 bits!

Let's take XKCD's algorithm: ~2000 word dictionary, randomly select 4 words, produces 2000**4 different possible passwords, which is 16 trillion.  Log base 2 gives 43.9 bits of entropy.

But using a pseudo-random number generator with a 32-bit initial seed means that it will only generate 2**32 different sequences, or 4 billion.  That's .027% of the total!  In other words, 99.97% of the possible XKCD-style passwords CANNOT BE GENERATED by that program!

Normally, you can add more bits of entropy by either expanding the dictionary size (the number of words to choose from), or increasing the number of words in the password.  But because of the pseudo-random number generator, you are STUCK at 32 bits of entropy.  An attacker could even pre-generate the 4 billion possible XKCD-style passwords that a standard Linux rand() produces.

My point is not that 32 bits bits of entropy aren't enough, it's that you aren't necessarily going to get what you think you're getting if you use the stock pseudo-random number generator.

So if you're running somebody's application and you click "generate random password" and you see a string of gibberish that claims to have a crack time of thousands of years, it is probably wrong.  32 bits of entropy at 1000 guesses per second has a brute force crack time of under 50 days.  (And modern crackers go MUCH faster than 1000/sec.)


TRULY RANDOM NUMBERS ELIMINATE THE LIMIT

For my program, I offer the "-r" option, which reaches out to https://random.org to get random numbers.  It doesn't need very many -- you only need 4 random numbers to generate an XKCD-style password -- but the important feature is that random.org is truly random.  There is no seed.  Each number is uniformly random and independent from the previous number.  (Or at least, so claims the owner of random.org.)  I'm pretty sure this removes any artificial limit on entropy, so you can get as much entropy as you want by increasing the dictionary size and/or the number of words in the password.

Using random.org is not the only way to solve this problem.  Have you ever generated an SSL certificate?  It can take several seconds while the software "generates" enough entropy for long key lengths.  I'm not personally familiar with how that is done, but I've heard the the OS uses external physical events, like keystrokes, network interrupts, etc.  I think I've heard that it also uses disk interrupts, which makes me wonder if SSD drives make it harder for kernels to generate entropy.

If you're going to be demanding a lot of entropy for your application, you should not abuse random.org.  Instead learn how to use locally-generated entropy.

The vast majority of on-line password generators are written in Javascript.  I'm not sure how to get truly random numbers (i.e. entropy) in Javascript, but this might be a good starting point.

(By the way, a bit of reading on my part shows me that I have a lot to learn.  But my reading to date does reinforce my primary point: simply using rand() or a similar/derived function does not produce passwords that take thousands of years to crack.  At best they rely on "security through obscurity".)


PASSWORD MANAGERS' RANDOMIZER???

I'm a little worried about the "random password generators" included in password managers.  The idea is that you should have a different password for every on-line account, and you let the password manager deal with the hundreds of passwords you end up with.  Since you don't need to remember, or even type those passwords, you might as well make them be random character gibberish.  Only the password manager's master password needs to be memorized.

However, if your password manager just uses the normal pseudo-random number generator in the system, that sequence of random characters will not have as much entropy as you think.  I can tell you that LastPass's online password generator just uses Javascript's get_random() function, which only has 32-bits of entropy.  Now maybe their laptop application uses /dev/random, but also maybe the fact that their on-line generator uses built-in random indicates they didn't give the issue much thought.

I haven't done an exhaustive search, but I would wager that 90% of "generate password" functions just use the language's default random number generator, which has a 32-bit seed (or less!).

My suggestion is to use https://www.random.org/passwords/ to generate your gibberish passwords, or my program to generate XKCD-style passwords.


SEED V.S. PERIOD

The rand() man page says that Linux rand() uses the same algorithm as random().  And srandom()'s man page says that the seed is an unsigned int, which is 32 bits.  It also says:
The period of this random number generator is very large,
approximately 16 * ((2^31) - 1).
I.e. the period is approximately 34 billion, which is about 35 bits.  But the seed is 32 bits.  This means that you cannot start the random number generator at any arbitrary point in its period.  Even if you figure out a way to fully-leverage all 35 bits of random()'s period, that still gives you a crack time of 397 days, at 1000 guesses/sec.  And by the way, modern password crackers go much faster than 1000/sec.

No comments: