icanhazmathz?

A "quick and dirty" random password generator that I see a lot of people use is a construct similar to the following:

dd if=/dev/urandom of=/dev/stdout bs=6 count=1 2>/dev/null | base64

This produces output such as the following:

0zdQE0WC

Or perhaps even:

Pg7Ub+Rx

base64 is an encoding scheme that "converts" binary data into text data using 64 characters. The 64 characters chosen vary from implementation to implementation, but typically are based on A-Z (26 characters), a-z (26 additional characters), 0-9 (10 more characters), and 2 final characters (typically chosen by the implementation, but on Linux appear to be + and /). The way it works is by taking the stream of binary data and breaking it into 6 bit chunks, then mapping that 6 bits into the 64 characters set chosen for the base64 implementation. Looks like a great way to create a passphrase, right?

Let's crunch the numbers, shall we? 64 characters possible for, say, an 8 character passphrase like the above (did you note that the 6 bytes of input lead to an 8 character passphrase? 6 bytes is 48 bits, divided by six gives 8 values...base64 "extends" the input a bit), gives (2^6)^8 possible values. That is:

281,474,976,710,656

possible combinations. If you weren't using base64 and used the randomly generated 6 bytes, you would have (2^8)^6, which is:

281,474,976,710,656

So base64 effectively reduces the "pure" random input (by extending the number of characters required to keep the same difficulty). In other words, a base64 encoded passphrase that is only 6 characters long, by comparison, only has:

68,719,476,736

combinations. If an attacker could brute force ten thousand passphrases per second, it would take 892+ years to crack the 8 character passphrase, but only ~79.5 days to crack the 6 character base64 encoded passphrase. I'm making two very big assumptions here: 1) that's the time the attacker would use if he hit every single value in the possible key space, and 2) the attacker can't attempt more than 10,000 keys per second (which on today's computers is relatively trivial to do, especially if the attacker has an unsalted hash of the passphrase to brute force on his own machine or the attacker distributes the load among several machines (also trivial to do given today's cloud compute capabilities), or the attacker has hardware asics, which are growing in popularity for tasks like this).

Note that I'm not saying "don't use dd if=/dev/urandom blah | base64" to generate passphrases, rather I'm saying "please ensure you make your passphrases long enough and you understand the implications of using base64". Let's look at the keyspace for two other configurations for comparison:

1) Purely binary data (1's and 0's only), 256 bits (32 1-byte "characters") of data. This would contain 2^256 possible combinations, or ~1.158 x 10^77 values.
2) All characters (A-Z,a-z,0-9,and !-) (traditional PC keyboard)). This would contain 72^<keylength> possible combinations. In order to match (roughly) the difficulty of cracking the 256 bit key, you would need a 41 character passphrase (1.415 x 10^76, approximately).

Most passphrases are far fewer than 40 characters (I confess, my wireless APs have 63 character randomly generated WPA2 PSKs, but very few of my other passphrases contain that much entropy). This is why SSH keys (purely binary data) are so much tougher to crack: the keyspace is much larger than your traditional passphrase's keyspace would be.

Now, I see suggestions to replace the above base64 with md5 or sha* conversions, but I must advise NEVER to do that. md5 and sha output a fixed-length string with the character sets a-z and 0-9. This is only 36 possible characters, so the above calculations would be:

dd if=/dev/urandom of=/dev/stdout bs=6 count=1 | md5 -> 36^32 (32 characters, assuming you use the entire md5 hash as your passphrase)

6.334 x 10^49

combinations. Please note, in addition to easier keyspace, unsalted md5 rainbow tables exist online that would make looking up a hash incredibly easy and likely considerably faster than brute forcing (again, I'm making the assumption we're traversing the entire keyspace).

Bottom line is, my advice is that if you're going to generate random passphrases on the command line, you need to ensure you:

1) understand the binary-to-text transform you are using, and ensure it doesn't severely restrict the possible character set.
2) use a long enough passphrase
3) use keys, where possible
4) use random data (i.e. do not 'date | md5' for a "random" passphrase).

I recall a story years ago of a company that had an online gambling website. They were so sure of their code they posted it online. Within hours, attackers had written scripts that would calculate what the next card would be and were winning left and right. The issue? The website used the current second of the day (84600 possible values) as the seed to "shuffle the deck", meaning a deck shuffled a 8:02:34 AM two days back to back would generate the same card distribution. In addition to that weakness, 84600 values are easy to brute force, meaning the attackers didn't need to wait 24+ hours to start raking in the cash.