Crypto Home

Key Exchange using Merkle Puzzles


The term Merkle's Puzzles doesn't refer to any particular type of puzzle, but rather the use of puzzles in general to implement a reasonably secure means of exchanging a secret key over an insecure communications channel.

Consider the following scenario where Alice wants to send Bob a secret message but they haven't established a secret key ahead of time. They are, however, able to establish an insecure communications channel that they can use to exchange a secret key provided they can do so without Eve being able to also figure it out.

At first glance this might seem an impossible task - indeed, for much of the history of cryptography, the impossibility of such a task was simply accepted without question. If Eve knows everything Alice has ever communicated to Bob as well as everything Bob has ever communicated to Alice, then how can anything arise out of those communications that Alice and Bob both know but of which Eve is ignorant?

Let's first, at least temporarily, relax the requirements faced by Alice and Bob. Instead of needing to keep Eve from ever figuring out their shared secret, they only have to keep her from figuring it out for a while. How long is "a while"? Long enough so that, even after figuring it out, the knowledge does her no good. For instance, if the secret being exchanged is the radio frequency that Alice and Bob are going to immediately use to have a conversation lasting ten minutes, then as long as it takes Eve more than ten minutes to figure out the secret Alice and Bob win (unless, of course, Eve has the ability - and foresight - to be recording the traffic on every possible radio frequency that Alice and Bob might use).

Given this relaxation, we can now exploit that fact Alice and Bob are active participants in the conversation while Eve is a passive listener. Alice and Bob have the initiative - they can act while Eve can only react. Alice, who is going to initiate the exchange with Bob, knows exactly what she is going to send him and can take as long as necessary to plan in advance for however Bob might respond, whereas Eve can't start that process until Alice actual transmits her message. Similarly, Bob has the ability to make a quick decision based on what Alice sends, while Eve must take the time to figure out what that decision was.

So what if Alice generates a list of many keys and sends them to Bob (Eve is able to copy the list) and then asks Bob to pick one and let her know which one he picked (Eve will be able to copy down Bob's response to Alice). It might sound like we haven't accomplished anything, but what if Bob refers to the key he chose in a very indirect way - a way that would require Eve to examine every key in order to figure out which one Bob selected?

The simplest way to do this might be for Alice to pick a codephrase and tell Bob to use the key he picks to encrypt that phrase (using a particular symmetric cipher - which Eve knows as well) and send it back to her. Eve will have to take what Bob sent and work her way through the entire list of keys until she finds one that produced the same result. Essentially Alice must do the same thing, but she had the option of performing the encryption ahead of time (at the same time that she generated the list of keys) and so all she has to do is look up the encrypted message that Bob replied with and retrieve the associated key.

Will Eve eventually be able to break the key? Yes, but if the list of keys that she must search through is long enough (say, millions of keys) then it might be good enough for the purpose that Alice has in mind. Essentially Bob sent Alice and Eve a puzzle (figure out which key I used to encrypt the codephrase) and is relying on the fact that Alice has a very strong advantage that will permit her to solve it much quicker than Eve.

Another way to do it is for Alice to send Bob a puzzle - or actually a list of many puzzles. Each one takes a short but quite measurable amount of time to solve (perhaps one second on a state of the art computer). Bob then picks one puzzle at random and solves it. The puzzle is such that the answer is a number and Bob then uses that number as the key to encrypt that same number and send the result back to Alice. Once again, Alice knows the answers to all of the puzzles and has already generated a list of all the possible responses Bob might make - she only has to look up the key corresponding to the one that was actually sent. Notice that, unlike Eve, she didn't have to solve all of the puzzles provided she chose puzzles that let her to start with the answers and generate the puzzles from them very quickly).


Alice decides to send Bob the following instructions:

Pick a number from the attached list and find the largest factor. Square the result repeatedly until you get a result that, reduced modulo 10000, is greater than 5000. Use that as the key and encrypt the key using Fred's General Purpose Cipher and send me the result.

Let's say that Bob picked the number 19,177 from the list and proceeded to factor it. He would discover that it factors into 127 and 151. He then takes 151 and squares the result reducing it modulo 10,000 to get 2,801. Since this is not greater than 5,000, he squares 2,801 and reduces it modulo 10,000 to get 5,601 which is acceptable to use as the encryption key. He then looks up Fred's General Purpose cipher and encrypts 5601 using 5601 as the key and gets B7$kpR#6qT and sends that to Alice. She looks up B7$kpR#6qT in the table she prepared ahead of time as sees that the corresponding key is 5601. Her and Bob have now agreed on a secret key.

But how secure is it? Let's say that Alice prepared a list containing ten million numbers and they were large enough that it takes, on average, ten seconds to factor one of them. Alice and Bob should be able to come to agreement on a key in about ten seconds. If Eve has the same computing power as Bob, then it would take her one hundred million seconds to work through the entire list, which is greater than three years. You would expect her to get the answer, on average, in about half that time (right about 19 months).

But Eve might enlist help from Ed, Evelyn, Ernest, and a enough other people whose first initial is 'E' to let her throw a hundred computers at the problem. Now you would expect her to break the key in a bit under six days.

Is that secure? That's not the right question. The question should be: Is that secure enough? If the message that Alice needs to send Bob is, "I've buried the treasure in the northwest corner of the vacant lot at 6th and Main," then, presumably, even if Eve breaks the key after only a few hours she will still get to the vacant lot only to find an empty hole.

But, don't forget that she might get lucky and break it on the very first attempt. As in many fields of endeavor, no matter how carefully you prepare, no matter hard you try, no matter how heavily you stack the odds in your favor - sometimes the dragon wins.