Schneier on Security

pdf23ds • October 25, 2009 12:52 AM

I’m starting to use TrueCrypt, and I want to use a good strong password. According to Wikipedia, the NIST recommends using a password with 80 bits of entropy for the strongest applications, so I’m going with that. Bruce, what’s your recommendation for entropy?

Now, a lot of people would just go with a password generated from random upper/lowercase letters, numbers, and symbols typeable on a regular keyboard. Assuming a uniform chance of each character being in a password, you would need 12.1 characters to reach 80 bits. (With 96 symbols, that’s 80 / log_2 96.) If that’s a little hard to type/remember for you, you could always use only lowercase letters, for 17 characters.

But I’ve looked into different ways to generate passwords. According to the wiki article on entropy, you can calculate the entropy of a random string where each symbol has a given probability of occurring. (This is the sum of [the probability of a symbol times the logarithm of its probability] for each symbol.) The article on letter frequency gives the probability of each letter in various languages. Using that data, I’ve calculated that a random string of lowercase letters drawn from a distribution matching English’s letter distribution will have 4.18 bits of entropy per character.

This gives a grand total of 19.1 characters to reach 80 bits of entropy. Surprisingly, using letter frequencies didn’t really change the required length much at all. These are probably a little easier to type (especially on the Dvorak layout), since they use common keys more often.

Here are a few examples.

mbbtfxbsbjdptjjfjct
tpueujueuoccbtqvbfp
mopsjsdsluudojzoeji

An even more advanced method is to use a table of common English trigram frequencies. This generates often-pronounceable, quite memorizable passwords. They have to be, on average, 37 characters long to be 80 bits strong (35 characters if you generate without spaces), so maybe not worth it to everyone. A few examples:

con lins not numbeen thernite yount
proulace of thouriesecals ris arth
rs the steraind and the mand new has wh
ble s justaintichand cerive of win

[Standard disclaimer about PRNGs.]

http://en.wikipedia.org/wiki/Entropy_(information_theory)
http://en.wikipedia.org/wiki/Letter_frequency
http://home.ccil.org/~cowan/trigrams

pdf23ds • October 25, 2009 1:41 AM

A sometimes recommended way of generating passwords is to pick a whole phrase and use the first letters of each word. By my calculations, you need between 12 and 26 characters to reach 80 bits by this method. Shannon’s estimates of the entropy in English are between .6 and 1.3 per letter, and the average English word is 5.1 letters long[1]. 80 / (5.1 * .6) is 26.

[1] http://blogamundo.net/lab/wordlengths/

And of course, all these estimates are rather conservative. The most obvious thing they don’t take into account is the uncertainty on the part of the attacker about which method you chose to choose your password. Since this is very difficult to estimate, it’s conservative to assume they know exactly how you picked, but it would be interesting to see estimates.

pdf23ds • October 25, 2009 1:55 AM

It’s interesting to compare Shannon’s estimate of around 1 bit/character to the current state of the art in English language compression, found at Marcus Hutter’s compression challenge site:

http://prize.hutter1.net/

The best compressor as of this writing compresses a 100 MB extract from Wikipedia at a rate of 1.3 bits per character. This implies 1.3/char as a maximum entropy of Wikipedia text. So it’s likely considerably lower. 1.0? .8? Who knows?