Do these numbers between 1 and 3 trillion seem random to you?
1414213562373 1732050807569 2236067977499
A good cryptographic system uses randomization with as little detectable pattern as possible. The lack of pattern is crucial for many reasons. Here's one. Say BlackHat records Alice's challenges to Bob. On Monday, Alice sends Bob the challenge 1,414,213,562,373; on Tuesday, 1,732,050,807,569; and on Wednesday, 2,236,067,977,499. Bob correctly responds and is authenticated by Alice. The challenges may, at first glance, look like random numbers; but they actually follow a simple sequence. As shown in Figure 7-6, they are the square roots of 2, 3, and 5, respectively (with decimal points removed). Although they look random, they're not because it's easy to figure out the next number in the sequence.3
|BlackHat successfully masquerades as Bob to Alice|
If BlackHat figures out Alice's sequence, he can impersonate Bob. BlackHat guesses that Alice's next challenge will be the square root of 6 (2.449489742783) with the decimal point removed. BlackHat knows he can't correctly respond to Alice's challenge of 2,449,489,742,783 because he doesn't have the correct secret key. But he may be able to trick Bob into doing the work for him. BlackHat intercepts Bob's next call to Alice's computer. Bob thinks he's connected to Alice. BlackHat challenges Bob with 2,449,489,742,783. Bob encrypts the challenge and responds to BlackHat. BlackHat now knows how to respond to Alice's challenge of 2,449,489,742,783. He puts Bob on hold while he calls Alice's computer. BlackHat logs on to Alice's computer and drops Bob's connection. When Bob tries Alice's computer again, he gets a busy signal.
Figure 7-6 The square roots of 2, 3, and 5.
Computer cryptography crucially relies on random numbers. But almost the most
difficult task you can give a computer is to make something random. Even though
computers are made to behave in the same identical way over and over again,
many, if not most, people think computer work is already frustrating enough.
Imagine if a computer behaved differently on different days (ugh).
The one-time pad got its name from Germany's use of this system around the 1920s. The Germans typed a sequence of supposedly random numbers on two separate pads-one for the receiver and one for the sender-to be used only once. The German system had a mechanical precursor, called the one-time system, that was developed independently. It was created by AT&T engineer Gilbert Vernam, who was studying security problems with the teletypewriter. It was improved on by U.S. Army Major Joseph Mauborgne, who proposed modifying Vernam's system by using a nonrepeating random key.
Making Good Use of Randomization
One cryptographic system that absolutely cannot be cryptanalyzed wasn't conceived of until the twentieth century. In this system-termed the one-time pad-a randomly generated, nonrepeating key (the length of the key is at least as great as the length of the message) is used only once. The one-time use ensures that ciphertext can't be cryptanalyzed through an examination of patterns in different messages. Perfect secrecy is ensured only by a truly random number. Quantum events, such as those measured by a Geiger counter, are believed to be the only source of truly random information.
In fact, computer programs can't make random numbers. They may come close, but not close enough to be called random. Instead, "random" numbers made by computer programs are actually pseudo-random. To you and me, a pseudo-random number may look like a random number, and we can use it as though it were a random number. Economists, statisticians, scientists, and others use pseudo-random numbers all the time. Nevertheless, if a cryptographer isn't very careful in using pseudo-randomness, a hound-dog cryptanalyst might spot it and use it to launch a successful attack.
3. See Appendix A for more on pseudo-random numbers.