WEBVTT 00:00:00.000 --> 00:00:02.000 The next thing I'm going to talk about is an idea that Ralph Merkle 00:00:02.000 --> 00:00:05.000 came up with in 1974. 00:00:05.000 --> 00:00:08.000 It's not a practical idea at all, but it's a really clever idea, 00:00:08.000 --> 00:00:11.000 and I think it's a fun thing to talk about before we get into 00:00:11.000 --> 00:00:14.000 the more realistic solutions that are used today. 00:00:14.000 --> 00:00:17.000 The idea behind Merkle's puzzles is that you have the 2 parties 00:00:17.000 --> 00:00:21.000 that want to share a key, and we'll call them Alice and Bob, as usual. 00:00:21.000 --> 00:00:24.000 First they have to agree on some parameters. 00:00:24.000 --> 00:00:26.000 They agree on an encryption function. 00:00:26.000 --> 00:00:31.000 They agree on security parameters s, n, N. 00:00:31.000 --> 00:00:35.000 The basic idea is Alice is going to create many puzzles, 00:00:35.000 --> 00:00:39.000 and then Bob will randomly pick one of the puzzles to solve, 00:00:39.000 --> 00:00:44.000 and part of solving that puzzle will give Bob the number of the puzzle and a secret. 00:00:44.000 --> 00:00:47.000 And what he'll send back to Alice is the number of the puzzle, 00:00:47.000 --> 00:00:49.000 and Alice will know the corresponding secret, 00:00:49.000 --> 00:00:51.000 and they'll use that as the key. 00:00:51.000 --> 00:00:54.000 Let me go through this in a little more detail, 00:00:54.000 --> 00:00:57.000 but that's the high level idea, and the reason that this gives you 00:00:57.000 --> 00:01:01.000 a way to establish a key is because Bob is randomly picking one puzzle to solve, 00:01:01.000 --> 00:01:05.000 whereas an attacker would have to solve many puzzles 00:01:05.000 --> 00:01:08.000 before they could get the one that Bob actually solved. 00:01:08.000 --> 00:01:10.000 Here's how the steps work in a little more detail. 00:01:10.000 --> 00:01:15.000 In order to create puzzles--so Alice creates a list of N secrets. 00:01:15.000 --> 00:01:18.000 Each one of these is a random number s bytes long. 00:01:18.000 --> 00:01:21.000 Then she creates a set of messages, also N messages, 00:01:21.000 --> 00:01:27.000 and each message will be encrypted using the encryption function that they agreed on 00:01:27.000 --> 00:01:30.000 using a key that's the corresponding secret concatenated 00:01:30.000 --> 00:01:34.000 with enough zeros to make the appropriate key length. 00:01:34.000 --> 00:01:40.000 If this was a 128-byte AES key, the secret size might be, say, 40 bytes, 00:01:40.000 --> 00:01:43.000 and then we would add zeros to fill out the rest of the key. 00:01:43.000 --> 00:01:46.000 And then what we'll encrypt using that key 00:01:46.000 --> 00:01:50.000 is a message that gives the identity of the puzzle, 00:01:50.000 --> 00:01:55.000 which will be that index, and the message will give the identity of the puzzle, 00:01:55.000 --> 00:01:59.000 and we'll include a string before it so it's clear that that's the right message. 00:01:59.000 --> 00:02:02.000 If we just included a number, if there were enough numbers 00:02:02.000 --> 00:02:05.000 we might accidentally decrypt one to that. 00:02:05.000 --> 00:02:08.000 That's what we encode for each message here. 00:02:08.000 --> 00:02:11.000 After this, Alice shuffles the messages, 00:02:11.000 --> 00:02:15.000 and then she sends all N messages to Bob. 00:02:15.000 --> 00:02:19.000 Bob randomly picks one of those, then does a brute-force key search 00:02:19.000 --> 00:02:22.000 where Bob is trying to decrypt using a guess key 00:02:22.000 --> 00:02:25.000 concatenated with N - s zeros, 00:02:25.000 --> 00:02:29.000 the message that Bob randomly selected from those puzzles. 00:02:29.000 --> 00:02:32.000 Eventually he's going to find one of these decrypts 00:02:32.000 --> 00:02:34.000 to puzzle followed by a number. 00:02:34.000 --> 00:02:37.000 At this point, Bob knows the guess, so he knows the secret 00:02:37.000 --> 00:02:40.000 that was used for that, and he knows the puzzle number. 00:02:40.000 --> 00:02:42.000 If we wanted a larger key, which we probably do, 00:02:42.000 --> 00:02:46.000 what we should include in the puzzle instead of just the i 00:02:46.000 --> 00:02:50.000 we should include a key, and this means the key can be of any length. 00:02:50.000 --> 00:02:54.000 This would be some new random key associated with that puzzle. 00:02:54.000 --> 00:02:58.000 Alice would keep track of those keys, and so for each puzzle, 00:02:58.000 --> 00:03:02.000 when Bob decrypts it, he acquires both the puzzle number and the key number, 00:03:02.000 --> 00:03:04.000 sends the number of the puzzle back to Alice. 00:03:04.000 --> 00:03:08.000 Alice can look up in her keys and figure out which key 00:03:08.000 --> 00:03:10.000 was the one in the puzzle Bob decrypted. 00:03:10.000 --> 00:03:14.000 Assuming encryption and the random number generation work perfectly, 00:03:14.000 --> 00:03:19.000 the question is how much more work does an eavesdropper have to do than Bob has to do? 00:03:19.000 --> 00:03:22.000 And an eavesdropper hears all the messages between Alice and Bob, 00:03:22.000 --> 00:03:25.000 wants to determine the key that they'll use to communicate. 00:03:25.000 --> 00:03:27.000 Here are the choices. 00:03:27.000 --> 00:03:29.000 It's impossible for the attacker to find the key. 00:03:29.000 --> 00:03:34.000 The attacker would need to use N times as much work as Bob to determine the key. 00:03:34.000 --> 00:03:38.000 The attacker would expect to need N/2 times as much work as Bob, 00:03:38.000 --> 00:03:43.000 or the attacker would be expected to need twice as much work as Bob. 00:03:43.000 --> 00:03:49.000 And the value of N is the number of puzzles that Alice creates and sends to Bob.