In this segment we're going to look at our first key exchange protocol without a trusted third party. So the settings are, we have our friends Alice and Bob as usual. And these friends have never met before but somehow they want to generate a shared key. So what they're going to do is they're going to send messages to one another, back and forth. And this time there is no trusted third party that they can communicate with. And at the end of this protocol, somehow they should have a shared key that they both know. So there's a secret key k that they both know. But an eavesdropper who listens in on this traffic has absolutely no idea what this secret key k is. For now we're just going to worry about attackers that only eavesdrop on the conversation. In other words, we don't allow any tampering with traffic. All we allow is just eavesdropping, and yet eavesdroppers should have no idea what the secret key k is. So we're going to look at a number of key exchange protocols in these settings. Namely, when the attacker is only eavesdropping on the conversation but cannot change traffic. And we're going to see three protocols that achieve this goal. And the first question, though, for this segment, is "Can this be done only using symmetric crypto?" So can this only be done using block ciphers or hash functions, or any of the tools that we've seen in the last four weeks. And so very surprisingly, the answer is "Yes", in fact we can do key exchange just using block ciphers or hash functions without a trusted third party but unfortunately the resulting protocols are very inefficient and are actually never used in practice. Nevertheless, these are very simple protocols and so I want to show you how they work, and then we'll move on to the more efficient protocols that we'll discuss this week and the next. So the simple protocol I want to show you what's called a Merkle Puzzles protocol. This protocol was invented by Ralph Merkle back in 1974 when he was just an undergraduate. Interestingly, he invented this protocol as part of a seminar that he took, but apparently the professor didn't quite understand the significance of the contribution and as a result Ralph Merkle actually graduated and then moved to Stanford where he became Marty Hellman's student and they've done a lot of good things in public-key cryptography since then. So let me show you how Merkle Puzzles work. The main tool for this protocol is what's called a "puzzle" and let me explain what I mean by a puzzle. A puzzle is a problem that's difficult to solve, but can be solved with some effort. In other words, if you really put your mind to it you can solve it. So let me give an example. Suppose we have a symmetric cipher that uses keys that are 128 bits long So just think of AES for example. And suppose what I do is a choose an AES key such that the first 96 bits are all 0 and only the remaining 32 bits are non-zero and just chosen at random. Ok, so only 32 bits of this 128-bit key are random. The rest are all 0. And now what I do is I encrypt a fixed plaintext, for example, simply the plaintext "message" using this 128-bit key that happens to be mostly 0. The result is what I would call a "puzzle". The reason I call it a puzzle is because it's actually not that hard to find the secret key P simply by trying all 2-to-the-32 possibilities. Remember the first 96 bits are all 0, there are only 2-to-the-32 possible keys to try. And for each key we'll try to decrypt this puzzle and see if we get the plaintext "message". If so, we know that we've recovered the right solution, P. So within 2-to-the-32 work, we can actually solve this puzzle. Namely, we can find P just given puzzle(P). So the way this is going to work is as follows: Alice is going to start by generating a large number of puzzles. In particular, she's going to generate 2-to-the-32 different puzzles. Now each of these puzzles, the way she generates it is as follows: What' she'll do is she'll choose a 32-bit random puzzle P-i, (she does this for i = 1 to 2-to-the-32) and then she's going to choose two more values, x-i and k-i that happen to be 128-bits each. Now what she'll do is she'll use the puzzle P-i as an AES secret key. So she'll create 128-bit key where 96 of the bits are set to 0. And only the 32 least significant bits happen to be random. So this is a key that only has 32bits of entropy, if you like, and there are only 2-to-the-32 such keys. Now the plaintext that she'll encrypt using this key is this message that I wrote over here. Basically it's starts off with the word "Puzzle". That puzzle is identified by the identifier x-i, which happens to be 128 bits. And to that we concatenate a value k-i which also happens to be 128 bits. So she does this for all 2-to-the-32 puzzles, and as a result she gets 2-to-the-32 different puzzles. She then goes ahead and sends these 2-to-the-32 puzzles to Bob. So what does Bob do? Well Bob receives this flood of 2-to-the-32 different puzzles. He's just going to choose one of them. He doesn't even have to remember any of them. He just randomly lets most of them go by. And he happens to choose one of them. Let's say he chose puzzle number "j". Then he spends time 2-to-the-32 and solves this puzzle. Well what does it mean to solve this puzzle? He's going to try all possible values of P-i. He's going to decrypt the puzzle that he chose, and he's going to check whether the first part of the plaintext starts with the word puzzle. And if it does, he knows that he's correctly solved that puzzle, and he basically obtains the data embedded in the puzzle namely, x-j and k-j. Remember x-j is this value that identifies the puzzle and k-j is going to be a secret that they use. So now he's solved the puzzle -- he knows that he's solved the puzzle correctly and he obtained this x-j and k-j. What he'll do is he'll send x-j back to Alice -- just the value of x-j. k-j he keeps for himself, and keeps it a secret. And then Alice is simply going to lookup in her database of puzzles, she's going to lookup puzzle number x-j, and then she knows Bob chose the key k-j. And now they have this shared key. So k-j is going to be the shared key they that use to communicate securely with one another. So in a diagram the way this protocol works is as follows: Alice starts off by sending 2-to-the-32 puzzles to Bob. So we can generalize this. Let's say that she says n puzzles to Bob. And lets say that each puzzle takes work proportional to n to solve. Bob solves one of these puzzles, and then he sends back x-j to Alice. So far each one of them has spent work n. And then Alice basically looks up puzzle x-j and recovers the key that corresponds to this puzzle. And as a result both of them now have a shared key that they can use to communicate with one another. Ok so lets look at the work they did. So the work that Alice did is that she had to prepare n puzzles. Well, preparing the puzzle takes constant time. She had to prepare n puzzles, so her work is roughly order n. Bob chose one puzzle and solved it, so his work is also proportional to order n. So linear in n. Let's see what the eavesdropper has to do. Well the poor eavesdropper sees these n puzzles go by and then he sees this x-j come back. And he doesn't really know which puzzle Bob actually solved. All he sees is this random value inside of the puzzle. And so to break this protocol, the eavesdropper would actually have to solve all puzzles until he finds the right puzzle that has the value x-j in it, and then he will recover k-j. So my question to you is, "What is the attacker's work?" How much work did the eavesdropper have to spend in order to break this protocol. So the answer is, of course, order n-squared. You know, quadratic time in n. He had to solve n puzzles. Each puzzle takes time n to solve. And as a result he had to spend time order n-squared. In our example we said that there were 2-to-the-32 puzzles and each one took 2-to-the-32 time to solve, so overall the attacker's work is roughly 2-to-the-64 steps. So you can see the problem with this protocol. First of all, the participants Alice and Bob had to do quite a bit of work themselves. If you think about it, Alice basically had to send 2-to-the-32 puzzles to Bob. That's many. many gigabytes that she had to send to Bob. Like 16 or 32 gigabytes, depending on how big each puzzle is. Bob had to spend time 2-to-the-32 to solve one of these puzzles. That would take a few seconds, too. But then, all the security they got is that the attacker can break this protocol in time 2-to-the-64. So 2-to-the-64 is still not considered particularly secure. As a result, the attacker, really, if he really wanted to break this protocol, he could. So to make this secure, the participants would have to increase the parameter n. And they would have to send, say, 2-to-the-64 puzzles to one another, and then spend time 2-to-the-64 to solve each puzzle, and then the attacker's work would be 2-to-the-128, which is considered secure. But having the participants spend time 2-to-the-64 to set up a secure session is a little bit too much to ask each of these participants. So this is why this protocol is not particularly used in practice. But nevertheless there's a really nice idea here in that the participants had to spend linear time, whereas the attacker had to spend quadratic time. So there's a "quadratic gap" between the amount of work that the participants had to do, versus what the attacker had to do to break the protocol. So a natural question is, "Can we actually do better than a quadratic gap, just using symmetric ciphers?" In other words, just using tools that we developed in the first four weeks of the class. And the answer really is that this is unknown. We don't know whether a quadratic gap is the best that we can do. You might even try to think about this a bit. How would you use AES or SHA-256 to do key exchange that achieves better than a quadratic gap. But I can tell you that we believe that quadratic is the best we can do. And there are even some negative results along those lines. So roughly speaking, there is a result that says that, in fact, if we treat the block cipher or the hash function that we use as a black box oracle -- in other words all the participants can do is just query the block cipher or query the hash function at certain points and receive the results -- if that's all they're allowed to do, in other words, they're not allowed to actually use the implementation of the cipher, or the hash function, then in fact there is a result that says that if the participants only query the block cipher at n points, there will always be an attack that runs in time n-squared. So again this suggests that if all you do is use the block cipher as a black box that you query, then whatever key exchange you come up with, there will always be a quadratic attack on this key exchange. And, in fact, at the end of this module, I point to this paper -- it's a fairly recent paper from 2009 -- that shows that quadratic is best we can do. If you want to read more about this impossibility result you know, go ahead and take a look at this paper. It's actually a very readable paper, and you should be able to understand it. And so the question is what to do next. So now we're kind of stuck. We said that with block ciphers, we really can't do better than a quadratic gap. And so what do we do? So this was kind of the starting point of public-key cryptography. And the realization is that we need more than just generic block ciphers and generic hash functions. We actually need functions that have very, very special properties. And to build these functions, we actually have to rely on some algebra. So in the next few segments we're going to look at some algebraic constructions and then we'll see how to use those for key exchange and for many other things in public-key cryptography.
