Merkle puzzles are the first publicly recorded example of asymmetric cryptography. It was devised by Ralph Merkle, he was trying to work out a way to remove the need for a shared secret key, to remove the need for people meeting first to exchange their key (or risk someone else seeing it by sending the key). 

His answer was Merkle Puzzles. Merkle puzzles are an approach to solving the difficult problem of key-distribution over an untrusted medium. 

How it works

Let’s say Bob wants to securely communicate with Alice (you’ll see these names a lot in my examples). We’ll swap combo locks on a bag for real encryption.

1. Alice creates 1000 unique pairs of an Identifier, and a key:  1000 x (identifier, key). She puts them in locked bags.
2. Alice locks each pair separately in their bags. This is easy enough to break, but it takes time – say an hour.
3. Alice then sends all 1000 bags to Bob
4. Bob chooses one bag at random and brute forces every combination until it is cracked
5. Bob gets his unique identifier and a key, say (sausage, A3D19F)
6. Bob encrypts his message with his key (A3D19F), and lets Alice know his identifier is ‘sausage’
7. Alice finds the key for sausage on her list
8. Alice decodes the message using the key A3D19F

How it’s hacked

If an attacker, Eve, wants to read these messages, she needs the matching key (A3D19F). Even though Eve can see the unique identifier ‘sausage’, she still doesn’t know the key that was used for encryption. 

So Eve has to brute force all of the bags until she finds one that contains ‘sausage’. This is 1000 x 1 hour, so 1000 hours work, compared to Bob’s 1 hour of work. Of course she might get lucky and pick the correct bag first, or she might be unlucky and it will take the full 1000 attempts. The average for a brute force is half the max, so it will take Eve, on average, 500 attempts to crack the encryption.

Reflection

Merkle puzzles aren’t secure enough for the real world, but his idea was revolutionary and did get people thinking about asymmetric cryptography. He was cited in the seminal RSA paper by Rivest, Shamir, and Adleman. 

I also realised that Merkle Puzzles also don’t scale to allow multiple channels with the same set of bags. What if the system was used by a group or organisation? With each pair of communicators using their own bag? As more people within an organisation communicate with each other, more bags are used, making it more likely that an attacker will crack a bag in use and obtain some information.

So let’s take a group of six people, each communicating with each other, using 1000 bags. My maths is a bit rusty, but here goes. Number of communication channels: 6C2 = 15

So 15 bags are required. All of a sudden, an attacker’s chances of choosing a bag in use go from: 1/(1000-n) to 15/(1000-n), where n = the attempt number. I can generalise this to:

p = c/(b-n)

where:

• p = probability of choosing a bag in use;
• c = communication channels (bags) in use
• b = total number of bags
• n = the attempt number

We all know from our previous activities that once part of a message is uncovered, the rest tends to follow (eg unshredding paper docs), so increasing the chances of an attacker getting a single bag is not in our interest.