Pass Phrases vs. Passwords

Pass phrases are coming into vogue for a number of reasons, one being the development of tools that can crack many passwords in minutes. These tools are not new. Quakenbush Password Appraiser could do this in 1998. What is new is the theory and practice behind the space-time tradeoff, advanced by Dr. Phillippe Oechslin. The time-space tradeoff means that you do not store all possible hashes, which would require more storage than exists in the universe (if you try to store NT hashes). Storing all the NT hashes up to 14 characters for the 76-character character set would require 5,652,897,009 exabytes of storage, which exceeds the capacity of any file system today. Storing all the LM hashes, which only requires 310 terabytes, is still infeasible.

To solve this dilemma, Dr. Oechslin came up with a time-space tradeoff where you only store a portion of the hash and its associated passwords. This drastically cuts storage requirements, and with only 17 gigabytes of storage, you can store the LM hashes for the same character set. As we shall see, one of the primary arguments for pass phrases is that they make the storage requirements prohibitive and break the pre-computed hash attacks.

Claim 1: Users Can Remember Pass Phrases
The first argument of proponents of pass phrases is that users are more apt to remember a pass phrase than a long (10+ character) password. That may be true, but since few users use 10+ character passwords, it is hard to tell. To answer that question, I performed a totally unscientific study of whether users can remember 10-character passwords. I asked administrators for their opinions; 99% said users will not only forget 10-character passwords, they will mutiny if forced to use them.

Could users remember a phrase with 10 characters in it? Probably, since there are only a few tokens (words, in this case) in it. A famous paper that I love to quote is Miller's 1956 classic "The Magical Number Seven, Plus or Minus Two: Some Limits On Our Capacity For Processing Information." The premise of the paper, which is one of those great papers where it is enough to just read the title, is that humans have limited information processing capability. We can remember 7 plus or minus 2 chunks of information at a time.

The definition of a "chunk" also varies according to what we are trying to do. In a random 10-character password, a chunk is a symbol, and Miller would state that most people cannot remember 10 random symbols. A user is much more likely to remember a 10-character pass phrase composed of 2 or 3 words or chunks.

If we assume users can remember 7 chunks, words, or symbols, then the longest password they could use would be limited to 9 characters. In a pass phrase, each word is a chunk. The average length of an English word is five characters. In English, five characters per word is also the standard used to measure typing speed in words per minute. Likewise, in a 1995 survey of 45 PGP users, Arnold Reinhold discovered that the average PGP pass phrase contained words of 5.3 characters. Interestingly, Reinhold also reported that 5/8 of all the words in his study were English dictionary words. That sample is so small as to render it virtually scientifically invalid, but it is the best we have in very sparse literature.

Returning to Miller, a user remembering a 7-word sentence can have a 41-character password. There are several caveats with this reasoning. First, it is unlikely that a real pass phrase is that long. For instance, my current pass phrase (yes, I do use them) is only 35 characters long, and I already think it is cumbersome. Also, Reinhold found that the median pass phrase contained only 4 words.

Claim 2: Longer is Stronger
The other argument for pass phrases is that they are longer, and therefore stronger. Still, the length of a pass phrase is not directly comparable to the length of a password. Longer passwords are considered to be better because of the typical way to measure password strength — the time it takes to crack them.

As an additional argument for longer passwords, it is often cited that passwords longer than 14 characters do not generate LM hashes. Considering that we can remove LM hashes in other ways, the mere removal of LM hashes is not an advantage of pass phrases. So is there a length advantage? Well, not really. Current password crackers are designed to crack symbols, but there is no reason that future ones will not use words as the symbols. Indeed, some of us find that likely. So longer passwords do not provide a lasting advantage; they merely help deter the cracking tools available today.

Claim 3: Pass Phrases Can Have More Randomness
There is one distinct advantage to pass phrases: higher entropy. Entropy is the common measure of randomness. There are three components to entropy: the number of items chosen, the size of the set from which they are chosen, and the probability that each individual item is chosen. Since pass phrases are longer than passwords, they may have the potential for higher entropy than passwords, even if they are picked from the same character set. This is noteworthy because password crackers can be designed to operate probabilistically. Instead of simply trying every possible combination of letters in a password, password crackers typically start with common combinations from a dictionary, then move on to permutations of those based on letter frequencies. Thus, our 28-day calculation to crack a 7-character password may not be accurate. Actually, it is frequently possible to crack many passwords in mere seconds, depending on how they are composed. Therefore, entropy is a better measurement of password strength than simple length and character set.

The argument for pass phrases is that most people have more than 76 words in their vocabulary. A pass phrase can also be considered as composed from a language - from words available in the language used to construct the pass phrase. The Oxford English Dictionary contains 616,500 words, although only spelling bee contestants and students sitting for college entrance exams bother with 614,000 of those words. In reality, the average vocabulary of an American is estimated from 10,000-20,000 by linguist Richard Lederer to 50,000-70,000 by linguist James L. Fidelholtz. Both authorities agree that the vast majority is recall vocabulary - i.e., you recognize a word if you hear it, but you would not use it. The average person would only use a fraction of that vocabulary.

Let's assume pass phrases are based on a set of only 300 words. That is probably a very conservative estimation, but on the other hand, most of those words only make sense when strung together in a particular way, significantly decreasing the randomness of the pass phrase. To calculate the actual entropy of a pass phrase, we need to know how many words are used. The median number of words in the PGP study referenced above was 4, but the average was higher. To appease Miller's memory, let us use a 5-word pass phrase average.

If there are 5 characters per word, we have 25+4=29 characters, where 4 are spaces, in the pass phrase. How much entropy that pass phrase contains depends on whose estimates you use. Using Shannon's estimates of 2.3 bits per letter in an 8-letter word nets a total entropy of 29*2.3=66.7 bits. The 66.7 bits calculation is probably a reasonable upper bound on the entropy of a pass phrase, and it compares favorably with a 9-character password with only 45 bits of entropy. For a lower bound, we can use Bruce Schneier's estimate of 1.3 bits per letter, based on a study by Thomas Cover. Using 1.3 as the entropy estimate computes to 29*1.3= 37.7, which is actually worse than the 9-character password. Based on that number, you would need a 6-word pass phrase to attain roughly the same entropy as a 9-character password.

Then again, our calculation of pass phrase entropy does not take into account the vocabulary we estimated for these examples. We can presume that if pass phrases become commonplace, attackers will start using "pass phrase crackers" that employ the word, instead of the symbol, as the unit. This situation would significantly change how we calculate the randomness of the passwords. Using words as the units might be more appropriate than employing letters composing the words as symbols. If we use 300 words in our vocabulary for pass phrases and assume that they can be randomly combined, we get an absolute rate per word of Log2300 = 8.23 bits per word. Using a 5-word pass phrase nets 8.23*5= 41.2 bits of entropy, and employing a 6-word pass phrase totals 49.4 bits of entropy.

Using words as units makes pass phrases look a lot less attractive than passwords. In fact, a 5- to 6-word pass phrase is roughly as strong as a 9-character password. I would like to state that this is not a scientifically proven result. Further study is necessary to validate these entropy calculations.