The Great Debates: Pass Phrases vs. Passwords. Part 2 of 3
Jesper M. Johansson, Ph.D., ISSAP, CISSP
This is the second article in our series on passwords versus pass phrases. The first installment covered the fundamentals of passwords and pass phrases, how they are stored, and so on. In this installment I will discuss the relative strength of each type of password, and use some mathematical approaches for illustration. In the third installment, I will offer some conclusions and guidance on how to choose passwords and configure a password policy.
The Arguments For and Against
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 actual number 7 is less important than the fact that information processing capability is limited. Some people assert the number is 5 plus or minus 2. I’ve met a few who insist it is 3, although I think they just have a very frustrating job. In any case, human information processing capability is severely limited.
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. This position has been validated by empirical testing. To assess the strength of passwords, I cracked 28,000 passwords from a large domain. Of those, I was able to crack 23,311, or 83%, fully, and an additional 13.16% partially. While this example is not entirely representative of all passwords, the statistics throughout the rest of this article are based on my analysis of these 23,311 cracked passwords. That analysis lends some credence to the 9-character limit: 64% of the cracked passwords on the domain, which required a minimum of 7 characters, were 9 characters or shorter. At least 90.37% of all the domain’s passwords were shorter than 15 characters. (It is impossible to tell exactly how many were shorter than 15 characters, unless the passwords are captured in clear-text. Therefore, those passwords without an LM hash were assumed to be 15 characters or longer even though some lacked an LM hash for other reasons.)
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. For instance, as we saw earlier, it would take 5 years and 11 months longer to crack an 8-character password than a 7-character one. Yet this is only accurate if the password is truly random and every symbol has equal probability of occurring in the password. If a password is not truly random, these calculations no longer hold.
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.
Let’s look at some examples. Testing reveals that more than 83% of the passwords in our sample were composed solely from the character set consisting of letters, numbers, and the symbols !@#$%^&*()-_+=. That character set has 26+26+10+14=76 symbols in English, and a few more in other languages. In addition, 80% of the symbols used in those passwords are chosen from only 32 of those 76 symbols. The 32 common symbols are, in order of occurrence: ea1oirn0st2lud!m3hcyg94kSbpM758B. Even more interesting, 10% of passwords were composed solely from these 32 symbols.
The natural entropy, or absolute rate, of a 76-symbol character set is R=Log2L = 6.25 bits per symbol. The absolute rate is typically considered an upper bound on entropy, and presumes that each character has equal probability of being chosen. C.E. Shannon, though, calculated the entropy per letter of an 8-letter chunk of English as 2.3 bits per letter (Shannon, C.E., “Predication and Entropy in Printed English,” Bell System Technical Journal, v. 30, n. 1, 1951, pp. 50-64). Keep in mind that Shannon’s work was based on English words using a 26-character set, not a 76-symbol character set as in our example. Still, we have seen that users choose the majority of symbols from only 32 symbols. In any case, the actual entropy per symbol in a password is probably larger than the 2.3 calculated by Shannon, but smaller than the absolute rate of 6.25. Log2 32 = 5, which, although a bit higher than I believe it is, should serve well as an upper bound estimate of the entropy per bit of a password. Since the average password is 9.16 characters long, which we round down to 9, it therefore has no more than 9*5=45 bits of entropy.
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 (I will refrain from any of the myriad cheap shots any righteous European would insert here) 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 (B. Schneier, “Applied Cryptography, 2nd Edition,” Wiley, 1996). Shannon advanced 1.3 bits per letter for 16-letter words, though, so it is probably not entirely applicable to our 5-character words. In any case, 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.
In this installment of the passwords article series, we took a first a step toward analyzing passwords and pass phrases. As you might have noticed, however, we do not know much about the pass phrases people use. In order to understand more about this, we would like to ask you a favor. If you would like to help us, think of a pass phrase you might use (preferably not the one you are currently using!) and e-mail it to email@example.com*. We hope to get enough samples to be able to perform some analysis on pass phrases and understand how they are actually formed.
As always, this column is for you. Let us know if there is something you want to discuss, or if there is a better way we can help you secure your systems. Just click the “Comments” button below, and send us a note.
*We will only retain the pass phrase you send us so we can perform our analysis. We will not store your email address or any other personal information you send along with the pass phrase. The pass phrase you send will be aggregated with the other pass phrases we receive and will not be associated with any of your personal data sent in your email.