
Title:
Merkles Puzzles  Applied Cryptography

Description:

The next thing I'm going to talk about is an idea that Ralph Merkle

came up with in 1974.

It's not a practical idea at all, but it's a really clever idea,

and I think it's a fun thing to talk about before we get into

the more realistic solutions that are used today.

The idea behind Merkle's puzzles is that you have the 2 parties

that want to share a key, and we'll call them Alice and Bob, as usual.

First they have to agree on some parameters.

They agree on an encryption function.

They agree on security parameters s, n, N.

The basic idea is Alice is going to create many puzzles,

and then Bob will randomly pick one of the puzzles to solve,

and part of solving that puzzle will give Bob the number of the puzzle and a secret.

And what he'll send back to Alice is the number of the puzzle,

and Alice will know the corresponding secret,

and they'll use that as the key.

Let me go through this in a little more detail,

but that's the high level idea, and the reason that this gives you

a way to establish a key is because Bob is randomly picking one puzzle to solve,

whereas an attacker would have to solve many puzzles

before they could get the one that Bob actually solved.

Here's how the steps work in a little more detail.

In order to create puzzlesso Alice creates a list of N secrets.

Each one of these is a random number s bytes long.

Then she creates a set of messages, also N messages,

and each message will be encrypted using the encryption function that they agreed on

using a key that's the corresponding secret concatenated

with enough zeros to make the appropriate key length.

If this was a 128byte AES key, the secret size might be, say, 40 bytes,

and then we would add zeros to fill out the rest of the key.

And then what we'll encrypt using that key

is a message that gives the identity of the puzzle,

which will be that index, and the message will give the identity of the puzzle,

and we'll include a string before it so it's clear that that's the right message.

If we just included a number, if there were enough numbers

we might accidentally decrypt one to that.

That's what we encode for each message here.

After this, Alice shuffles the messages,

and then she sends all N messages to Bob.

Bob randomly picks one of those, then does a bruteforce key search

where Bob is trying to decrypt using a guess key

concatenated with N  s zeros,

the message that Bob randomly selected from those puzzles.

Eventually he's going to find one of these decrypts

to puzzle followed by a number.

At this point, Bob knows the guess, so he knows the secret

that was used for that, and he knows the puzzle number.

If we wanted a larger key, which we probably do,

what we should include in the puzzle instead of just the i

we should include a key, and this means the key can be of any length.

This would be some new random key associated with that puzzle.

Alice would keep track of those keys, and so for each puzzle,

when Bob decrypts it, he acquires both the puzzle number and the key number,

sends the number of the puzzle back to Alice.

Alice can look up in her keys and figure out which key

was the one in the puzzle Bob decrypted.

Assuming encryption and the random number generation work perfectly,

the question is how much more work does an eavesdropper have to do than Bob has to do?

And an eavesdropper hears all the messages between Alice and Bob,

wants to determine the key that they'll use to communicate.

Here are the choices.

It's impossible for the attacker to find the key.

The attacker would need to use N times as much work as Bob to determine the key.

The attacker would expect to need N/2 times as much work as Bob,

or the attacker would be expected to need twice as much work as Bob.

And the value of N is the number of puzzles that Alice creates and sends to Bob.