You are here

Generating long random passwords

I decided to try to use as my SSL cert provider before giving up. They really wanted me to give them a truly random 32-character password string. Here's what I did to get them one…

On my GitHub is a program called randpass. Up until tonight, it was a slightly-hacked version of a C program I wrote in the 1980s. It used a simplistic heuristic to generate a random password from bytes pulled from /dev/random. Frankly, I no longer understand that heuristic, and am not sure it was random. Besides, it didn't appear to use /dev/random efficiently, which is bad: I don't have a hardware random number generator, so I'm blocked until the entropy pool fills enough that I can get a password out. More wasted bits = slower passwords. (This is exactly where /dev/urandom would be the wrong answer: I want my password to have as many bits of true entropy as its length implies.)

A better plan is to figure out the number of possible passwords of the given length and drawn from the given character set, and pick one at random. This is "obviously" correct, and requires generating the smallest-possible uniform random number. The only convenient way to do this, though, is with large integer arithmetic. I started to get out GMP, and realized I don't have the energy to do that. I considered Nickle and Haskell, and finally decided Python 3 was the right answer.

So now randpass is written in Python 3. It pulls enough bytes out of the random number generator to sample the possible passwords. If the index it gets is too big (very very rare) it must restart, and pull all new bytes out of the generator. Otherwise, it effectively just constructs the password from the index. This algorithm is guaranteed to use the minimum number of possible random bytes, on average. If it doesn't restart, it's obviously minimal. Because it restarts vanishingly often, it turns out that the restarts make no difference to the average performance.

Whee. Fob