- The Search for an Innovative Key Delivery Solution
- Developing an Innovative Secret Key Delivery Solution
- A New Solution: Diffie-Hellman-Merkle Key Agreement
- Separate Encryption and Decryption Keys
- Review
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Developing an Innovative Secret Key Delivery Solution
While a graduate student at Berkeley in the early 1970s, Ralph Merkle devised a system that enabled people like Alice and Bob to exchange secret keys over a public line, marking the beginning of public key cryptography. Even though BlackHat is assumed to be listening to Alice and Bob's communications, Merkle envisioned a way to create a difficult, time-consuming problem for BlackHat. At the same time, Merkle's approach makes it easier for Alice and Bob to establish their shared secret key.
The goal was to create a problem that would take BlackHat a long time to solve even with the aid of a computer. Here's what Merkle devised.
First Attempt: A Database of Key/Serial Number Pairs
Suppose that Alice makes 1,000,000 new secret keys and stamps a unique serial number on each one (see Figure 9-1). Note that there's no reason to order the serial numbers. Alice keeps a database of each secret key and serial number.
){kind=link}
If Alice then sends Bob a plaintext electronic copy of that database, he can easily pick a serial number (say, serial number 500,121) and its paired secret key (1yt8a42x35); then he calls Alice to tell her to use the secret key associated with serial number 500,121. But as Figure 9-2 shows, what's easy for Alice is also easy for the eavesdropping BlackHat. BlackHat has copied the database Alice sent to Bob-remember that it was sent over public lines-and quickly figures out the secret key. So this secret key exchange doesn't work for Alice and Bob.
){kind=link}
Figure 9-1 Alice makes 1,000,000 secret keys.
Figure 9-2 Alice sends Bob a file of secret keys and serial numbers, but BlackHat copies it and learns their secrets.
Second Attempt: An Encrypted Database of Key/Serial Number Pairs
| Alice encrypts the entire database of serial number/secret key pairs. |
Now suppose that Alice encrypts her serial number/secret key database and then ships the encrypted database to Bob. Alice tells Bob the encryption method she used but not the encryption key. Because Bob doesn't know Alice's encryption key, he must try all possible keys. Say it takes Bob about one hour, using his desktop computer, to find Alice's encryption key.1 After decrypting the entire database, Bob selects a secret key and tells Alice the matching serial number-say, serial number 500,121. As before, Alice knows to use secret key 1yt8a42x35 (see Figure 9-3). But, like Bob, BlackHat can also spend about an hour decrypting Alice's database, so BlackHat can also figure out that serial number 500,121 matches secret key 1yt8a42x35. We still need a method that will make BlackHat's job much tougher than Alice and Bob's job.
){kind=link}
Figure 9-3 Alice sends an encrypted database of secret key and key pairs, but BlackHat isn't intimidated.
Merkle's Insight: Individually Encrypted Key/Serial Number Pairs
This brings us to Merkle's creative insight. As the result of this innovation, Bob's work doesn't change, but BlackHat's work increases dramatically. Let's see how.
| Third approach. Encrypt each individual serial number/secret key pair. |
Previously, Alice encrypted the entire database with one secret key. But that didn't make BlackHat work longer than Bob. Now Alice sends 1,000,000 encrypted secret key/serial number pairs (see Figure 9-4).
){kind=link}
Figure 9-4 Alice sends Bob 1,000,000 encrypted secret key/serial number pairs. BlackHat eavesdrops and copies the key pairs sent to Bob.
| Each secret key/serial number pair is encrypted with a different secret key. |
Each secret key/serial number pair (second column, Table 9-1) is encrypted with a unique secret key (third column, Table 9-1) to make the encrypted pair (final column, Table 9-1). Alice uses a million different secret keys to encrypt the 1,000,000 individual secret key/serial number pairs. Table 9-1 shows each secret key/serial number pair encrypted with a separate key.
Bob gets 1,000,000 encrypted secret key/serial number pairs and picks one encrypted pair-say, Pair3. He spends an hour deciphering it and learns that Pair3 means secret key 1yt8a42x35 and serial number 500,121 (see Figure 9-5). As before, he tells Alice that he will encrypt with the secret key matching the serial number 500,121. Alice quickly matches the serial number to the corresponding secret key in her database.
){kind=link}
As before, Alice and Bob assume that BlackHat is listening, has copied all 1,000,000 encrypted pairs Alice sent to Bob, and has heard Bob tell Alice to use the secret key associated with serial number 500,121.
Black Hat's Frustrating Problem
| BlackHat must decrypt many more serial number/secret key pairs than does Bob. |
How does BlackHat figure out the secret key Alice and Bob agreed to share? BlackHat doesn't know that Bob selected Pair 3; he knows only that one of the encrypted pairs Alice sent to Bob contains serial number 500,121. But here's the rub: BlackHat doesn't know which pair. It must be one of the million pairs, but he has no clue which one (see Figure 9-6).
){kind=link}
Table 9-1 Alice's database of secret keys and serial numbers, encryption key, and encryption message sent to Bob (and snooped by BlackHat).
Figure 9-5 Bob picks one encrypted pair and decrypts it to learn the secret key and serial number.
Recall that Bob tells Alice only the serial number he learned. BlackHat has a much bigger problem than Bob: He must decrypt about half the encrypted pairs Alice sent to Bob until he stumbles onto the one pair that decrypts to 1yt8a42x35 / 500,121.
With this twist, Merkle turned a relatively simple problem for Bob into a time-consuming problem for BlackHat. If deciphering one encrypted pair takes about one hour and if BlackHat must try, on average, about 500,000 of them, BlackHat has a 500,000-hour problem. Bob has only a one-hour problem.
As a result, Alice and Bob can communicate confidentially with their shared secret key while BlackHat is busy trying to figure out which secret key they are using.
The Key to Public Key Technology
| Easy and difficult puzzles. |
All public key cryptography works in the same way. You and your confidant share a quickly solved problem. Let's call it an easy puzzle. But if you withhold a critical puzzle piece from your adversary, the easy puzzle is transformed into a difficult, time-consuming puzzle. In Merkle's innovative implementation, Bob solves one encrypted pair and finds a secret key to share with Alice. BlackHat doesn't know and isn't told which encrypted pair Bob solved. That critically withheld puzzle information forces BlackHat to solve, on average, 500,000 encrypted pairs-a much more time-consuming puzzle.
Figure 9-6 BlackHat has a big problem. He knows that one of the 1,000,000 pairs he copied contains the pair Alice and Bob are using; but because he doesn't know which one, he must try them one by one. According to probability theory, he'll have to try about half of them before he stumbles onto Bob's choice.
| Technology reduces the perceived advantage. |
A ratio of 500,000 to 1 may seem impressive, and certainly after 500,000 hours (or about 50 years) Alice and Bob's secrets have much less value. A delay of 50 years may seem sufficient to protect secrets, but more powerful computer hardware and more efficient software can dramatically reduce that number.
Bob may use a $1,000 computer to solve a puzzle sent to him by Alice, but an adversary-wanting to learn about, let's say, the next major West Coast land deal, might use a $10,000,000 computer. A computer 10,000 times more expensive and 10,000 times faster than Bob's desktop might solve the 50-year problem in 50 hours. With better software, it might take even less time.
Cryptographic history is replete with stories of technological advances eliminating cryptographic advantages. As a result, cryptographers prefer a much larger advantage: at least 500,000,000 to 1, which is about 1,000 years compared with 1 minute. One way to accomplish that is to give BlackHat a much bigger search space. For example, Alice could send a greater number of encrypted pairs, but that's an inefficient use of bandwidth. Only one of the 1,000,000 encrypted pairs is used; the other encrypted 999,999 pairs just cloak the selected one and are thrown away.
Hiding in Plain Sight
Just as Merkle designed a way to keep an electronic adversary busy looking through a maze of possibilities, so, too, did spies design real-world mazes to hide the locations of dead drops: prearranged hidden places for leaving and retrieving messages and money. A good location was one that let you hide your message in plain sight, a hiding place that was hard to recognize unless you had secret information.
One of the more elaborate hiding places in the history of espionage helped the U.S. Central Intelligence Agency (CIA) retrieve valuable information about the Cuban missile crisis of the 1960s from an insider in Soviet military intelligence. The informant gave the CIA specific instructions about how to find the information hidden in a Moscow building-a task that would be hard for someone without the instructions or who had never directly observed the exact location.
His instructions were to go to a particular foyer near the number 28 telephone. Across the hallway was a dark green radiator held to the wall by a single metal hook. Between the wall and the radiator was a space 2 to 3 centimeters wide that was to be used as the drop. The selected hiding place made it easy for both parties to deposit and retrieve materials while in a standing position. In this way, someone observing the scene would be less likely to notice the drop.
Merkle envisioned his public distribution of secret keys in a similar way: Make it hard for BlackHat to find your secret key by giving him a much bigger search space than Bob's.
1. Obviously, Alice does not choose a "strong" cryptographic method to encrypt her database. Recall from Chapter 4 that a strong encryption method is one in which the most practical attack is to try each possible key and there are so many possible keys that it's infeasible to try even half of them.