1
00:00:00,000 --> 00:00:02,000
The next thing I'm going to talk about is an idea that Ralph Merkle

2
00:00:02,000 --> 00:00:05,000
came up with in 1974.

3
00:00:05,000 --> 00:00:08,000
It's not a practical idea at all, but it's a really clever idea,

4
00:00:08,000 --> 00:00:11,000
and I think it's a fun thing to talk about before we get into

5
00:00:11,000 --> 00:00:14,000
the more realistic solutions that are used today.

6
00:00:14,000 --> 00:00:17,000
The idea behind Merkle's puzzles is that you have the 2 parties

7
00:00:17,000 --> 00:00:21,000
that want to share a key, and we'll call them Alice and Bob, as usual.

8
00:00:21,000 --> 00:00:24,000
First they have to agree on some parameters.

9
00:00:24,000 --> 00:00:26,000
They agree on an encryption function.

10
00:00:26,000 --> 00:00:31,000
They agree on security parameters s, n, N.

11
00:00:31,000 --> 00:00:35,000
The basic idea is Alice is going to create many puzzles,

12
00:00:35,000 --> 00:00:39,000
and then Bob will randomly pick one of the puzzles to solve,

13
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.

14
00:00:44,000 --> 00:00:47,000
And what he'll send back to Alice is the number of the puzzle,

15
00:00:47,000 --> 00:00:49,000
and Alice will know the corresponding secret,

16
00:00:49,000 --> 00:00:51,000
and they'll use that as the key.

17
00:00:51,000 --> 00:00:54,000
Let me go through this in a little more detail,

18
00:00:54,000 --> 00:00:57,000
but that's the high level idea, and the reason that this gives you

19
00:00:57,000 --> 00:01:01,000
a way to establish a key is because Bob is randomly picking one puzzle to solve,

20
00:01:01,000 --> 00:01:05,000
whereas an attacker would have to solve many puzzles

21
00:01:05,000 --> 00:01:08,000
before they could get the one that Bob actually solved.

22
00:01:08,000 --> 00:01:10,000
Here's how the steps work in a little more detail.

23
00:01:10,000 --> 00:01:15,000
In order to create puzzles--so Alice creates a list of N secrets.

24
00:01:15,000 --> 00:01:18,000
Each one of these is a random number s bytes long.

25
00:01:18,000 --> 00:01:21,000
Then she creates a set of messages, also N messages,

26
00:01:21,000 --> 00:01:27,000
and each message will be encrypted using the encryption function that they agreed on

27
00:01:27,000 --> 00:01:30,000
using a key that's the corresponding secret concatenated

28
00:01:30,000 --> 00:01:34,000
with enough zeros to make the appropriate key length.

29
00:01:34,000 --> 00:01:40,000
If this was a 128-byte AES key, the secret size might be, say, 40 bytes,

30
00:01:40,000 --> 00:01:43,000
and then we would add zeros to fill out the rest of the key.

31
00:01:43,000 --> 00:01:46,000
And then what we'll encrypt using that key

32
00:01:46,000 --> 00:01:50,000
is a message that gives the identity of the puzzle,

33
00:01:50,000 --> 00:01:55,000
which will be that index, and the message will give the identity of the puzzle,

34
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.

35
00:01:59,000 --> 00:02:02,000
If we just included a number, if there were enough numbers

36
00:02:02,000 --> 00:02:05,000
we might accidentally decrypt one to that.

37
00:02:05,000 --> 00:02:08,000
That's what we encode for each message here.

38
00:02:08,000 --> 00:02:11,000
After this, Alice shuffles the messages,

39
00:02:11,000 --> 00:02:15,000
and then she sends all N messages to Bob.

40
00:02:15,000 --> 00:02:19,000
Bob randomly picks one of those, then does a brute-force key search

41
00:02:19,000 --> 00:02:22,000
where Bob is trying to decrypt using a guess key

42
00:02:22,000 --> 00:02:25,000
concatenated with N - s zeros,

43
00:02:25,000 --> 00:02:29,000
the message that Bob randomly selected from those puzzles.

44
00:02:29,000 --> 00:02:32,000
Eventually he's going to find one of these decrypts

45
00:02:32,000 --> 00:02:34,000
to puzzle followed by a number.

46
00:02:34,000 --> 00:02:37,000
At this point, Bob knows the guess, so he knows the secret

47
00:02:37,000 --> 00:02:40,000
that was used for that, and he knows the puzzle number.

48
00:02:40,000 --> 00:02:42,000
If we wanted a larger key, which we probably do,

49
00:02:42,000 --> 00:02:46,000
what we should include in the puzzle instead of just the i

50
00:02:46,000 --> 00:02:50,000
we should include a key, and this means the key can be of any length.

51
00:02:50,000 --> 00:02:54,000
This would be some new random key associated with that puzzle.

52
00:02:54,000 --> 00:02:58,000
Alice would keep track of those keys, and so for each puzzle,

53
00:02:58,000 --> 00:03:02,000
when Bob decrypts it, he acquires both the puzzle number and the key number,

54
00:03:02,000 --> 00:03:04,000
sends the number of the puzzle back to Alice.

55
00:03:04,000 --> 00:03:08,000
Alice can look up in her keys and figure out which key

56
00:03:08,000 --> 00:03:10,000
was the one in the puzzle Bob decrypted.

57
00:03:10,000 --> 00:03:14,000
Assuming encryption and the random number generation work perfectly,

58
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?

59
00:03:19,000 --> 00:03:22,000
And an eavesdropper hears all the messages between Alice and Bob,

60
00:03:22,000 --> 00:03:25,000
wants to determine the key that they'll use to communicate.

61
00:03:25,000 --> 00:03:27,000
Here are the choices.

62
00:03:27,000 --> 00:03:29,000
It's impossible for the attacker to find the key.

63
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.

64
00:03:34,000 --> 00:03:38,000
The attacker would expect to need N/2 times as much work as Bob,

65
00:03:38,000 --> 00:03:43,000
or the attacker would be expected to need twice as much work as Bob.

66
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.