How Do Pirates Share a Treasure Map, If They Don’t Trust Each Other?

How Do Pirates Share a Treasure Map, If They Don’t Trust Each Other?

Pirates don’t trust each other

Ah-har! Jim lad! Shiver me timbers! Where be the treasure? Ah just don’t trust me fellow pirates!

If there’s one thing that pirates learn at Pirate School is that they should never trust other pirates, so the problem they often have is how to share a secret treasure map.

So let’s say we have we have two pirates and they need to define the route to get to the buried treasure. Now they think back to Pirate School and remember that they should each put down a marker, along the route, so that both markers are in a line from the start point to the treasure. They can then get together and put their marker down in each place, and then they follow the route and find the treasure. This works with more pirates, but now only two pirates are needed to get together to reveal the treasure.

As we know being a pirate is a risky business, and they might not make it back to the treasure island. So let’s say we now set up a Pirate’s Co-op, where the pirates share their booty. In the first meeting we now have three pirates and we need to define a route to the treasure. If we want any 2 from 3 pirates, we basically just add another point on the straight line, so that two pirates can get together. That works fine, but not very scaleable.

So, if they don’t trust each other, and are willing to take a risk of one pirate not returning to the island, they must now define a 2nd order equation to show the way. Let’s say it is 4x²+6x+1, and each pirate takes a point on the route: (9,331), (6,151) and (3,43). So only when the three pirates get together, they put their markers down, and then can find the route to the treasure: This is the basics of an amazing little method which allows shares to be distributed, without revealing the original data. It provides us with a way to create keyless encryption.

This is the basics of an amazing little method which allows shares to be distributed, without revealing the original data. It provides us with a way to create keyless encryption.

Outline

In 1979, Adi Shamir (who represents the “S” in RSA) created a secret sharing algorithm which allows a secret to be split into parts, and only when a number of them are added together will the original message be created (paper). In these times when we need to integrate trust, his algorithm has many application areas.

So let’s take an example … let’s say that there are six generals who have control over firing a missile, and there are three bases, with two generals on each base. Unfortunately we are worried that one of the generals might make a rash decision, so we agree that the generals will not get the secret password to fire the missile. We are also worried that a base could be taken over by a malicious force, so we agree that no two generals will be able to gain the password. So to overcome these problems we decide that a least three generals must agree together to generate the correct password to fire the missile.

Obviously, if this was a real scenario, we would create a password which would change over time, where we generate a one-time password, which cannot be used again (just in case!). For this we can use either a time-based mechanism, where the password is only relevant for a certain time window, such as with Time-based One Time Password (TOTP). Otherwise we can use an original seed password, which then changes each time we access it, where only those who know the original seed will be able to generate the next password. For this we can use a counter-based system such as for the Hash-based One Time Password (HOTP). With these schemes the same password would not be generated for each consecutive access, so that even when they had generated their password, they could only use it for a certain amount of time (with TOTP) or would differ for the next access (with HOTP).

Shamir’s Secret Sharing

In Shamir’s scheme, the number of generals can be represented by the number of shares, and the number generals who are required to generate the secret is represented by the threshold. Thus, in this example, we have a share value of six, and a threshold value of three. So we give out one of the shares to each of the generals, so that none of them have the same one. We will then require three generals to put together their shares in order for them to generate the password for the missile. To solve this problem and generate the shares (and also check the answer), I’ve created this Web page [Link]:

So for a password of “Fire The Missile”, with a share of six, and threshold of three we get:

000if30kGfSjyDNilwU0Tyz5awf2uk=

001PoYDi8eMEoMI6Zkbkn2n1GABoas=

002HxjSfFEEakXLqUnfGolr27XG3Ws=

003qGMlZ/Fa9+YOyozQWch/6nnYpik=

004RHyZDtPQP9/yXgv4cojC6Zg6Ets=

0058wduFXOOonw3Pc73McnW2FQkaZk=

for which each of these can be distributed to each of the generals. When three of them combine their codes, the result will be:

Trying a share of 1: ‰ýôgҏ ÍŠ\Ñ<³å¬Úé

Trying a share of 2: ?D·CümQFH¤Ú¼A7™r¹Ì

Trying a share of 3: Fire The Missile

Basic theory

The basic theory relates to the number of points within a mathematical equation, that are required to reveal what the equation is (and thus determine the secret). For example if we have a secret of 15, and can only be revealed when two people combine their information. For this we thus need a linear equation, such as:

y=2x + 15

The two pieces of information that could be generated to reveal the equation would thus be two points on this line, such as:

(0,15) and (1,17)

If we only know one point, such as (1,17), we cannot determine the equation of the line, but knowing two points we can determine the gradient:

m = (17–15)/(1–0) =2

and from here we can determine the point it cuts the y-axis ©:

c = y -mx = 17- 2×0 = 15

and thus we have the equation (y = 2x + 15), where the secret is 15. In this example we have only two shares, but if we require three shares we need a parabola, such as:

y = 2x² + 5x + 15

and share three points on the equation to generate the secret. If we require four shares then a cubic curve is required, and so on.

In most situations, it would be too processor intense to encrypt data with the secret share method, especially if we had a complete equation (such as using an any 8 from 10 share), so we often use symmetric encryption (such as for AES or ChaCha) to encrypt the data, and then create a share of the key. For example, if we had an 8 from 10 secret share policy, we would generate a 256-bit encryption key and then encrypt the data. Next we would then take the 256-bit AES key and create a secret share where 8 of the 10 shares can come together to recreate the key.

http://asecuritysite.com/encryption/shamir

ECC secret shares

In this modern world we often turn to ECC (Elliptic Curve Cryptography) to perform complex cryptography operations in creating signatures. With ECC we can also create secret:

Conclusion

So as the threats increase around losing encryption keys, you can see that keyless cryptography is one method of sharing information securely, especially if you are a pirate.

So can you find out where the treasure is and how many pirates can come together to find the secret:

000EIZur4REus/wAwer2yOddXl68QHaMH647tqjF+xQPok=

001XW3uscRnKYG523YmkcEfAEUOPV/RYHQwqYQAvMvCb4Q=

002i1FukwQDnFNjs+SxTuaZnwGTab3MkGuoYGfkQaN0nJM=

http://asecuritysite.com/encryption/shamir_decode

Here is some of our research in the area:

• The Future Internet: A World of Shares? Here.
• Secret shares to store health records. Here.
• Performance Evaluation of a Fragmented Secret Share System. Here.