LinuxQuestions.org
LinuxAnswers - the LQ Linux tutorial section.
Go Back   LinuxQuestions.org > Blogs > Musings on technology, philosophy, and life in the corporate world
User Name
Password

Notices

Hi. I'm a Unix Administrator, mathematics enthusiast, and amateur philosopher. This is where I rant about that which upsets me, laugh about that which amuses me, and jabber about that which holds my interest most: Unix.
Rate this Entry

icanhazmathz?

Posted 06-29-2014 at 08:23 PM by rocket357
Updated 07-02-2014 at 09:21 AM by rocket357 (clarification)

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.
Posted in Uncategorized
Views 258 Comments 2
« Prev     Main     Next »
Total Comments 2

Comments

  1. Old Comment
    Interesting.
    For my WPA2 passphrase, I grabbed one of my books, opened a random page, looked for a unique/memorable sentence, changed some letters to upper-case, wrote it on a cigarette paper, memorized it and then burnt the paper. So you'd have to know the book, the page, and the sentence. I've got quite a lot of books: fiction and non-fiction, several genres and subjects. How, excluding torture, would you crack that?
    P.S.
    It's not something I've ever quoted on LQ.
    Posted 07-01-2014 at 06:16 AM by brianL brianL is offline
    Updated 07-01-2014 at 06:28 AM by brianL
  2. Old Comment
    2^10 is a much bigger keyspace than 10^2, or more generally, X^Y > Y^X for X < Y.

    In short, passphrase length gives more keyspace than passphrase complexity, so if given a choice between a long passphrase of [a-z] or a short passphrase of [a-zA-Z0-9], it's best to choose the longer, simpler passphrase...so I'd have to agree with your choice of "book indexing" of passphrases (a technique I've used before, too...it's a great one!).
    Posted 07-01-2014 at 10:01 AM by rocket357 rocket357 is offline
 

  



All times are GMT -5. The time now is 11:25 AM.

Main Menu
Advertisement

My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration