Passphrase Recommendations

PASSPHRASE RECOMMENDATIONS

Mark Swearingen
mark@ephesus.com

Created Wednesday 2000 January 26

When you create a new key pair with PGP, you will be asked to choose a key length and to enter a passphrase to protect your private key or secret key.

I recommend that you choose a key length for your private/public key pair which is the maximum that your software will allow. The current version of PGP can generate keys of up to 4,096 bits, which is what I would suggest using, unless you find that your processor is too slow to generate such a key. The key generation process, which you need to do only once, takes much longer than encrypting or decrypting a message. If you leave your computer running overnight, and it still has not produced a key pair by morning, then abort the procedure and try again with a shorter key length (2,048 bits, then 1,024 bits, then 768 bits).

I recommend a passphrase of at least 23 characters (25 or more is better), containing at least one character from each of the following categories:

upper case letters (ABC)
lower case letters (abc)
digits (123)
punctuation and other symbols (!@#)

English or foreign words may be included in your passphrase, but if they are, then I would recommend mixing upper and lower case within some or all of the words, and would also recommend including additional upper and lower case letters elsewhere within the passphrase that are not part of these words.

Here is an example of a passphrase that is relatively easy to memorize and which satisfies the above criteria:





%1943oRAnge\4sa7ya{Abe}

The above might be an effective and easy-to-remember passphrase for someone named Samuel Abraham, who was born (or married, or discharged from the military) in 1943, whose favorite color is orange, who has a wife named Yolanda, has four children, and whose favorite number is 7. The passphrase contains the initials "sa" and "ya" as well as an abbreviated form of Sam's last name. The word "orange" is embedded within the passphrase, but the mixed case makes it less vulnerable to a "dictionary attack" (described below).

Naturally, you would not want to create a passphrase that consists only of your birth year or your initials or favorite color or number, but if these are mixed in with other characters and words, they can increase the length of your passphrase without compromising its security, and while keeping it easy to remember.

The following sections explain in detail the reasoning behind my recommendations above.

How Passphrases Are Used by PGP

Your passphrase is a series of characters you type on your computer keyboard which protects your private key. It would be unwise to store your private key in unencrypted form on your computer's hard disk or on a diskette, where someone else might be able to copy it. For this reason, PGP always stores private keys in encrypted form. In fact, you could think of your passphrase itself as an encryption key which is used only for the purpose of encrypting your private key. Since your passphrase is never stored on disk, but only in your mind, it is not vulnerable to being stolen.

You might wonder why it is even necessary to have a separate private key at all -- why couldn't PGP simply use your passphrase as your private key? The reason for this is that a private key is generally longer than could be easily memorized and would be impractical to type in each time you wanted to use it. For example, a private key of 2,048 bits would require a string of 256 characters to represent, which would look like:





UQH/ZZ5IftcjI57mANIsiAMUV6PVW2rDcWl+hVVzsJ9s2q4ZQ6TbHXqfZvptVvR0

bmcgUHJpdmF0ZSBLZXkgPHRlc3RAZXBoZXN1cy5jb20+iQBRBBARAgARBQI4iZ2a

diSO5HnzmRVtqZa6ws26ZWOXBq5DgXH16iDGGiqPsPXfdvMbIHm1F4Lr5P3VRAHH

9q9TjpeZ9Hs9RgMC4O+HYurIoSNLq7WGSdObWQhIRmdKW1Og7rQqVGVzdCBTYXZp

As you can see, this would be much harder to memorize and to type than the 23-character sample passphrase suggested earlier.

Since it is not practical to memorize or type a private key, the private key must be stored in electronic form on your computer's hard disk. However, in order to protect it from being copied by someone else, it is protected by encrypting it with your chosen passphrase, so that even if someone else does gain access to your keyring on your hard disk, they will still not be able to unlock and use your private key.

What length, then, should your passphrase be in order to provide adequate protection for your private key? To answer this question, we must understand more about how PGP operates.

As explained in my article What Is Encryption?, PGP uses a combination of public key and symmetric key encryption in order to gain the security of public key encryption along with the speed and efficiency of symmetric key encryption.

Because encryption using long keys (of 1,000 bits or more) is a mathematically tedious operation, it would be too slow in many cases to encrypt an entire text message with your recipient's public key. Furthermore, if you wanted to send an encrypted message to multiple recipients, it would be necessary to do the encryption separately for each one.

Both of these problems are overcome by using a shorter "session" key of 128 bits, which is a unique key that is randomly generated for each encrypted message. The original plain-text message is encrypted with the session key, and the session key is encrypted using the public key of each of the recipients. An identical copy of this entire "package" can then be e-mailed to all of the recipients:





/------------------------------------------\

| Session key encrypted with Public Key #1 |

| Session key encrypted with Public Key #2 |

| Session key encrypted with Public Key #3 |

|
     
     
     
     
     
     
    
|

| Text message encrypted with session key  |

\------------------------------------------/

Thus, when sending an encrypted message to another person, we can see that there are actually 4 separate encryption keys involved: (1) A randomly generated session key is used to encrypt the original, plain-text message. (2) The recipient's public key is used to encrypt the session key. (3) When the recipient receives the message, his passphrase is used to decrypt his protected private key. (4) Finally, the recipient's private key is used to decrypt the session key, which is, in turn, used to decrypt the text message.

All of this complexity is handled automatically by PGP, so that all you have to do is select a public key when sending encrypted e-mail, or type the passphrase for your private key when receiving an encrypted message.

Cracking a Message

If a message you send contains valuable information (such as a credit card number or a personal secret), an unauthorized person may wish to decrypt your message and read it. This is called "cracking" a message.

A "brute force" attack is one in which all possible encryption keys of a certain length are attempted until one is found which successfully unlocks the message. Assuming you (and your recipients) have kept your private key and the original text of the message secure, there are two possible approaches to this type of attack:

(1) The attacker could attempt to crack your private key by trying all possible keys of the same length (perhaps 1,024 or 2,048 or 4,096 bits) until he found a match. If he did this, he would have access to all messages that were encrypted to the corresponding public key.

(2) The attacker could attempt to crack the session key of a specific message by trying all possible session keys of the same length (usually 128 bits) until he found a match. That would give him access only to that individual message, but not to any other messages encrypted to the same public key.

As you can see, a successful brute force attack on a private key would be much more rewarding -- granting access to all of your encrypted messages -- but also many trillions upon trillions of times more difficult than an attack on a single session key. (There are, in fact, more sophisticated methods of cracking a private key, based on large integer factorization; but these are beyond the scope of this article.)

However, if the attacker manages to get a copy of your keyring file, then there is a third possibility:

(3) The attacker could attempt to crack your passphrase in order to gain access to your private key.

Since your passphrase will generally be much shorter than your private key, then (3) would be a far easier attack than (1), but would have the same effect of gaining access to all of your encrypted data.

Dictionary Attacks

In general, a longer passphrase is better. One way of making a long passphrase is to use a phrase or sentence of English words. Such a phrase could easily be much longer, yet easier to remember, than a string of mixed characters such as the 23-character sample passphrase given at the beginning of this article. For example, here is a phrase taken from the middle of the first sentence of the U.S. Declaration of Independence:





for one people to dissolve the political bonds which

With practice, this phrase takes about as much time to type from memory as the sample string of 23 mixed characters given above; yet with 52 characters the word phrase is more than twice as long.

However, this type of passphrase is vulnerable to another method of cracking known as the "dictionary" attack. Rather than attempting random strings of characters, the dictionary attack generates passphrases by concatenating words taken from a large file of common English (or/and foreign) words. With a small dictionary of 10,000 words, the 9-word phrase from the Declaration of Independence could be cracked 3 billion times more easily than the 23-character mixed string.

Reasons for My Key Length and Passphrase Recommendations

Now that we understand in more detail how a message is encrypted and how a possible attack on an encrypted message might be mounted, we are in a better position to decide what is an adequate passphrase.

By making your private key long enough, you can discourage an attack of type (1), as described above, on your private key. This is the reason I recommend making your private key as long as your software will allow. Although it will take noticeably more time for the program to generate a longer key, the amount of time it takes to use your longer key for encryption and decryption will still be minimal on most processors.

There is nothing you can do to prevent someone from undertaking an attack of type (2) on the session key of an encrypted message. You can, however, make it more difficult to mount a successful attack of type (3) against your passphrase by choosing a good passphrase according to the recommendations contained herein.

Since you cannot choose the length of the session key, which is fixed at 128 bits, the next best thing you can do is to make an attack on your passphrase more difficult than an attack on a single session key. This is important, since your passphrase is protecting your private key, whereas a session key is protecting only an individual message. If you do this, then an attacker who had the time and resources to mount a successful attack against the session key of an individual message (not an easy task in itself) would in all likelihood still be unable to crack your passphrase and gain access to all your other messages.

This means that you must choose your passphrase in such a way that an attacker would have to attempt more passphrase combinations than the number of possible session key combinations.

The number of possible 128-bit session keys is:





2^128 = 3.403 * 10^38 =



34,028,236,692,093,800,000,000,000,000,000,000,000,000,000,000,000,000

Therefore, we would like to employ a set of rules that will produce at least 2^128 different possible passphrases (and preferably many more). If we make a passphrase of a given length using only lower-case letters, for example, there will be fewer possibilities than if we require ourselves to include both letters and digits.

The table below shows how long a string must be in order to have more than 2^128 possible combinations when formed from the following sets of characters:

Character set	Number of characters in set	String length required for at least 2^128 combinations
`Lower-case letters only (or UPPER-case only)`	`26`	`28`
`Lower-case + digits`	`36`	`25`
`Lower-case + UPPER-case`	`52`	`23`
`Lower + UPPER + digits`	`62`	`22`
`Lower-case + digits + symbols`	`69`	`21`
`Lower + UPPER + digits + symbols`	`95`	`20`

As the above table shows, the more characters that are included in the set from which a string is chosen, the shorter the string length must be in order to afford the same degree of protection.

Similarly, the following table shows how many English words are required to obtain the necessary number of combinations using a dictionary of a various sizes:

Dictionary size	Number of words required for at least 2^128 combinations
`10,000-word dictionary`	`10 words`
`50,000-word dictionary`	`9 words`
`70,000-word dictionary`	`8 words`

Comparing the two tables, we see that a 20-character string made up of digits, symbols and UPPER- and lower-case letters offers about the same level of passphrase security as does a 10-word phrase taken from a 10,000-word dictionary.

It is up to you to decide which type of passphrase you prefer (character strings or word phrases), which may vary from person to person depending on typing speed, memory, frequency of use, and other factors. You may find that a passphrase made up of a combination of English words and mixed characters is most optimal.

For someone who sends or receives about 5,000 encrypted messages per year (a little over 14/day average), then a multiple of at least 250,000 (times 2^128 combinations) will afford 50 years of protection.

Therefore, if you use a mixed character string, I recommend a string of at least 23 characters, which will give you a passphrase that is about 9 million times harder to crack than a single 128-bit session key. This means that -- unless you have over 9 million encrypted messages -- an attacker would prefer to mount an attack against each individual message than to obtain your private key by cracking your passphrase.

If you prefer to use English words, then I recommend a phrase of at least 11 words, which will make your passphrase almost 300,000 times harder to crack (using a dictionary of 10,000 words) than a 128-bit session key.