Ralph Merkle is best known today for his research and development in
nanotechnology; one must only scan his list of published papers to see his enthusiasm for what has long been a mainstay of modern science fiction, but is every day coming closer to realization. Perhaps with more scientists like Merkle, we can see this astounding technology reach fruition in our lifetimes; but this is not about
molecular manufacturing, this is about, of all things,
cryptography.
Ralph's webpage mentions that one of his main interests outside of nanotech is cryptography, including digital signatures and one-way hash functions. Considering that his invention of the self-titled "Merkle's Puzzles" in 1974 laid the groundwork for public key cryptography and, thus, infinitely more secure forms of digitally signing documents and secure communication, it seems at least a little bit ironic that he would only label his interest as a "hobby." If cryptography is just something he does in his spare time, we should be seeing nanites in active use any minute now.
The importance of Merkle's Puzzles lies in the fact that it gave birth to one of modern crypto's most astounding and important breakthroughs: public key cryptography. It was the subject of his term paper, titled "Secure Communication Over Insecure Channels," for a course in computer security that he took at UC Berkeley in his senior year for an undergraduate degree in computer science. His professor could not make heads or tails of it, and Merkle ended up dropping the class. So much for his genius, but what I find funnier is that the Puzzle system is so inefficient and, surprisingly, insecure that it would have been considered almost unusable even then, before the advent of DES.
The system works like this: Assume that Alice and Bob are the two participants in the protocol and Eve is the eavesdropper, an outside party initiating a passive attack1.
- Alice and Bob agree on a symmetric algorithm2.
- Alice generates a large number (over a million, at least) number of messages of the form, "This is my index, X, and my puzzle is Y." Each of the messages is encrypted with a 20-bit key.
- Alice sends all the encrypted messages to Bob.
- Bob picks a random message and brute forces it to get the key.
- Bob sends the plaintext X and Y to Alice.
- Bob and Alice happily communicate using the 20-bit key.
It is not impossible for Eve to recover the key that Alice and Bob are now using, it will just take much longer for her to find. (Actually, except for
one time pads, there are no impossible
ciphers, there are only ones that require ludicrous amounts of time and computing power to break.) Whereas Bob only has to
brute force one message, Eve has to
brute force all of them. The plaintext X and Y that Bob sends back does Eve no good, and she presumably does not know the exact layout of the message; even if she did, it would still be a
chosen-ciphertext attack3 to over a million messages because she'd only have
one message in
cleartext. Considering the fact that the key has to be short to make this protocol even vaguely efficient, cracking a million messages does not take too much time. Let's look at some examples:
- Assume there are 220 (about a million) messages, it takes 220 operations to get the key, and a computer can perform 220 operations per second. Bob takes 1 second to recover the key to a message. Eve takes 12 days.
- Now make that 230 (about a billion) messages. Bob still only takes a second to get the key, and it will take Eve 34 years.
The problem with the Puzzles is that increasing the complexity also vastly increases the inefficiency. 2
20 messages is probably the most realistic amount that would be generated, as even that much encrypted data would take a long time to transmit over a fast connection. That would mean Eve could have the key within 12 days (Remember, she is trying random keys and could easily accidentally stumble upon the right key for the right message on the first try.), which is extremely insecure by most standards. Increasing the length of the key would make Bob's life harder, too. Merkle's Puzzles is
ingenious, but just not worth implementing.
The professor never understood Merkle's paper, but it obviously made its way around and most likely ended up in the hands of Whitfield Diffie and Martin Hellman, the two people credited with creating public key cryptography. This kind of cryptography is usually used to encrypt a session key4 to use with a symmetric algorithm; this idea of encrypting a session key was first introduced in the Puzzles.
Some of the terms I use are, surprisingly, not noded yet; at least, I can't find them. To make this more understandable, I will be defining some of the terms here.
1In cryptography, when someone listens in on the exchanges between two or more parties to gather information, but does not actively disrupt the protocol. Eavesdropping.
2An algorithm that uses the same key to encrypt and decrypt a message. Think of it as a locked box: You have one key, and you use it to put things in the box and take them out. Compare to public key cryptography.
3Using a large number of encrypted messages and trying to obtain the key (and possible the algorithm) used to encrypt them.
4A key for a symmetric algorithm that is only used for one conversation. This is like using the locked box described above, but every time you put something in and take something out, you throw away the key and recore the lock.
Sources:
Applied Cryptography by Bruce Schneier: ISBN 0-471-11709-9
http://www.merkle.com