0:01

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.

Â