[Next] [Up] [Previous] [Index]

Pass Phrases and Random Numbers

The 56-bit key length of DES was claimed to be inadequate in the late 1970s, when DES was originally proposed, and it is now considered to be inadequate because a relatively inexpensive machine was built that can exhaustively search the DES keyspace in weeks. The keyspace of a cipher with a 40-bit key is 65,536 times smaller.

But that keyspace still has over a trillion (a million million, or a British and Continental billion) possibilities in it. Isaac Asimov once wrote a book with the title Only a Trillion; that perhaps qualifies him as a prophet of cryptography.

The fact that 2^40 or 10^12 different keys is a hopelessly inadequate number in this part computer age at first hardly seems troubling. There are many ciphers around with 128-bit keys, and it is fairly trivial to design one with an even longer key. Of course, it isn't trivial to design a cipher well enough that there is no attack against it possible that is more effective than a brute-force search over all those keys.

But there is another problem: how to come up with a random key of the required length.

For many paper-and-pencil ciphers, the key is a single word from the dictionary, like "CONTINENTAL" or "INVIGORATING". There are thousands of words in the dictionary, but not millions, and certainly not trillions.

Some computer operating systems only allow passwords that are 8 characters long. Even if a password were composed of random letters, 26^8 is only 208,827,064,576 or just over a fifth of a trillion.

A pass phrase is much better. But it is important that the pass phrase not be a well-known phrase, a famous literary quotation, or the like, because that again limits the possibilities severely.

Some people find it useful to compose a pronounceable pass phrase from nonsense syllables chosen at random, or from random words in the dictionary, and there are tools available to assist in this, such as Diceware.

One way to protect a key is to memorize it, and give it only to whoever you are communicating with. However, public-key cryptography allows keys to be protected without having to be carried from place to place. So your computer just thinks of a random 128-bit key, enciphers it in RSA, and there is no problem?

Unfortunately, however, most computers today don't come equipped with special hardware to generate random numbers. A typical method for obtaining a genuinely random starting point for input to a pseudorandom number generator, so that, for example, a game contains elements that vary each time it is played, is to use the current date and time.

If one's computer provides the current time in thousandths of a second, and someone trying to break your enciphered messages can guess when you've enciphered them to within a week (often, messages are enciphered only minutes before they are sent, so this is an optimistic assumption), then, given that there are 86,400 seconds in a day, we are dealing with only 604.8 million possible keys; less than a billion.

In addition to the time, there are a few other sources of randomness in a computer, such as the position of the hard disk in its spin, and some register contents, but they are quite limited.

Counterpane Systems, the company of Bruce Schneier, author of the justly famed book Applied Cryptography, has made available the program Yarrow, which is a well-designed program for the purpose of obtaining randomness from a personal computer, to address these difficulties. (The name of the program is, no doubt, a reference to the traditional method of consulting the I Ching, or Book of Changes.)

At this point, it should not be hard to see why the earlier versions of PGP required the user, prior to the generation of keys for RSA encryption, to type characters on the keyboard for a time. The timing of those characters, not which characters were typed, were used as a source of randomness. A program for creating encrypted virtual disk drives obtains randomness by asking the user to move the mouse at random for a time.

The digits of pi look random, and for some purposes they are. But there is only one pi, and it is well known, and it is an easy thing to guess. Good cryptographic algorithms produce output that looks random. But a cipher is only as good as its key; a genuinely unpredictable and unguessable starting point, big enough to be a good key, is required for secure encryption. And obtaining such a key is harder than it may seem at first, and it is something that is often and easily forgotten.

[Next] [Up] [Previous] [Index]