And remember, computing power doubles every 18 months. If you expect your keys to stand up against brute-force attacks for 10 years, you’d better plan accordingly.

Poor Key Choices

When people choose their own keys, they generally choose poor ones. They’re far more likely to choose “Barney” than “*9 (hH/A.” This is not always due to poor security practices; “Barney” is easier to remember than “*9 (hH/A.” The world’s most secure algorithm won’t help much if the users habitually choose their spouse’s names for keys or write their keys on little pieces of paper in their wallets. A smart brute-force attack doesn’t try all possible keys in numerical order; it tries the obvious keys first.

This is called a dictionary attack, because the attacker uses a dictionary of common keys. Daniel Klein was able to crack 40 percent of the passwords on the average computer using this system [847,848]. No, he didn’t try one password after another, trying to login. He copied the encrypted password file and mounted the attack offline. Here’s what he tried:

1.  The user’s name, initials, account name, and other relevant personal information as a possible password. All in all, up to 130 different passwords were tried based on this information. For an account name klone with a user named “Daniel V. Klein,” some of the passwords that would be tried were: klone, klone0, klone1, klone123, dvk, dvkdvk, dklein, DKlein leinad, nielk, dvklein, danielk, DvkkvD, DANIEL-KLEIN, (klone), KleinD, and so on.

2.  Words from various databases. These included lists of men’s and women’s names (some 16,000 in all); places (including variations so that “spain,” “spanish,” and “spaniard” would all be considered); names of famous people; cartoons and cartoon characters; titles, characters, and locations from films and science fiction stories; mythical creatures (garnered from Bullfinch’s Mythology and dictionaries of mythical beasts); sports (including team names, nicknames, and specialized terms); numbers (both as numerals—“2001,” and written out—“twelve”); strings of letters and numbers (“a,” “aa,” “aaa,” “aaaa,” etc.); Chinese syllables (from the Pinyin Romanization of Chinese, an international standard system of writing Chinese on an English keyboard); the King James Bible; biological terms; colloquial and vulgar phrases (such as “fuckyou,” “ibmsux,” and “deadhead”); keyboard patterns (such as “qwerty,” “asdf,” and “zxcvbn”); abbreviations (such as “roygbiv”—the colors in the rainbow, and “ooottafagvah”—a mnemonic for remembering the 12 cranial nerves); machine names (acquired from /etc/hosts); characters, plays, and locations from Shakespeare; common Yiddish words; the names of asteroids; and a collection of words from various technical papers Klein previously published. All told, more than 60,000 separate words were considered per user (with any inter- and intra-dictionary duplicates being discarded).

3.  Variations on the words from step 2. This included making the first letter uppercase or a control character, making the entire word uppercase, reversing the word (with and without the aforementioned capitalization), changing the letter ‘o’ to the digit ‘0’ (so that the word “scholar” would also be checked as “sch0lar”), changing the letter ‘l’ to the digit ‘1’ (so that the word “scholar” would also be checked as “scho1ar”), and performing similar manipulation to change the letter ‘z’ into the digit ‘2’, and the letter ‘s’ into the digit ‘5’. Another test was to make the word into a plural (irrespective of whether the word was actually a noun), with enough intelligence built in so that “dress” became “dresses,” “house” became “houses,” and “daisy” became “daisies.” Klein did not consider pluralization rules exclusively, though, so that “datum” forgivably became “datums” (not “data”), while “sphynx” became “sphynxs” (and not “sphynges”). Similarly, the suffixes “-ed,” “-er,” and “-ing” were added to transform words like “phase” into “phased,” “phaser,” and “phasing.” These additional tests added another 1,000,000 words to the list of possible passwords that were tested for each user.

4.  Various capitalization variations on the words from step 2 that were not considered in step 3. This included all single-letter capitalization variations (so that “michael” would also be checked as “mIchael,” “miChael,” “micHael,” “michAel,” etc.), double-letter capitalization variations (“MIchael,” “MiChael,” “MicHael,”..., “mIChael,” “mIcHael,” etc.), triple-letter variations, etc. The single-letter variations added roughly another 400,000 words to be checked per user, while the double-letter variations added another 1,500,000 words. Three-letter variations would have added at least another 3,000,000 words per user had there been enough time to complete the tests. Tests of four-, five-, and six-letter variations were deemed to be impracticable without much more computational horsepower to carry them out.

5.  Foreign language words on foreign users. The specific test that was performed was to try Chinese language passwords on users with Chinese names. The Pinyin Romanization of Chinese syllables was used, combining syllables together into one-, two-, and three-syllable words. Because no tests were done to determine whether the words actually made sense, an exhaustive search was initiated. Since there are 298 Chinese syllables in the Pinyin system, there are 158,404 two-syllable words, and slightly more than 16,000,000 three-syllable words. A similar mode of attack could as easily be used with English, using rules for building pronounceable nonsense words.

6.  Word pairs. The magnitude of an exhaustive test of this nature is staggering. To simplify the test, only words of three or four characters in length from /usr/dict/words were used. Even so, the number of word pairs is about ten million.

A dictionary attack is much more powerful when it is used against a file of keys and not a single key. A single user may be smart enough to choose good keys. If a thousand people each choose their own key as a password to a computer system, the odds are excellent that at least one person will choose a key in the attacker’s dictionary.

Random Keys

Good keys are random-bit strings generated by some automatic process. If the key is 64 bits long, every possible 64-bit key must be equally likely. Generate the key bits from either a reliably random source (see Section 17.14) or a cryptographically secure pseudo-random-bit generator (see Chapters 16 and 17.) If these automatic processes are unavailable, flip a coin or roll a die.

This is important, but don’t get too caught up in arguing about whether random noise from audio sources is more random than random noise from radioactive decay. None of these random-noise sources will be perfect, but they will probably be good enough. It is important to use a good random-number generator for key generation, but it is far more important to use good encryption algorithms and key management procedures. If you are worried about the randomness of your keys, use the key-crunching technique described below.

Some encryption algorithms have weak keys: specific keys that are less secure than the other keys. I advise testing for these weak keys and generating a new one if you discover one. DES has only 16 weak keys out of 2⁵⁶, so the odds of generating any of these keys are incredibly small. It has been argued that a cryptanalyst would have no idea that a weak key is being used and therefore gains no advantage from their accidental use. It has also been argued that not using weak keys gives a cryptanalyst information. However, testing for the few weak keys is so easy that it seems imprudent not to do so.

Generating keys for public-key cryptography systems is harder, because often the keys must have certain mathematical properties (they may have to be prime, be a quadratic residue, etc.). Techniques for generating large random prime numbers are discussed in Section 11.5. The important thing to remember from a key management point of view is that the random seeds for those generators must be just that: random.

Generating a random key isn’t always possible. Sometimes you need to remember your key. (See how long it takes you to remember 25e8 56f2 e8ba c820). If you have to generate an easy-to-remember key, make it obscure. The ideal would be something easy to remember, but difficult to guess. Here are some suggestions:

— Word pairs separated by a punctuation character, for example “turtle*moose” or “zorch!splat”

— Strings of letters that are an acronym of a longer phrase; for example, “Mein Luftkissenfahrzeug ist voller Aale!” generates the key “MLivA!”