The Secret of Tipsy Cola is …

The Secret of Tipsy Cola is …

And so the eight directors of Tipsy Cola sit round the table. Neither of them trust each other, but they need a way to store their secret formula without anyone else finding out. “Why don’t we put it in a safe, and we can all have the key for it?”, “Well, that won’t work, as one of us could sneak in and steal it!”, “Well, why don’t we create a combination lock, and each of us can have one of the numbers?”, “Well, we will need all of the directors, but just say one of us falls under a bus, we will never be able to open the safe!”, “Ah, why don’t we accept any six numbers from eight, and we’ll be able to open the safe?”, “Yes. That’s it!”.

The method we have derived is a threshold secret sharing method, and where we have s shares and where t shares are required to built the secret. In the case of Tipsy Cola, we have eight shares and have a threshold of six. The method of threshold encryption was created by Adi Shamir, and he outlined a method where we take a mathematical function, and then derive points on this function. For example, if we have a function of:

y = mx +c

Then we can make m the secret, and then share two points on the line. Only with the knowledge of both points is it possible to derive the gradient of the line. If one point is (5,5) and the other is (6,9), the gradient is (9–5)/(6–1)=3. For most complex shares we can use higher order polynomials.

We can use Python to create our shares [here]:

import tss
from tss import share_secret, reconstruct_secret, Hash, TSSError
import base64
import sys

secret="hello"
t=3
s=8

if (len(sys.argv)>1):
        secret=str(sys.argv[1])
if (len(sys.argv)>2):
        t=int(sys.argv[2])
if (len(sys.argv)>3):
        s=int(sys.argv[3])

shares = tss.share_secret(t, s, secret, 'my-id', Hash.NONE)

print "Using t shares"
reconstructed_secret = tss.reconstruct_secret(shares[0:t])

print "Secret:\t",secret

print "===Shares==="
for x in range (0,s):   
    print base64.b64encode(shares[x])

print "Reconstructed:\t",reconstructed_secret

and a sample run is [here]:

Secret: The secret of Tipsy-cola is ...
Using  8 shares and a threshold of 6
===Shares===
bXktaWQAAAAAAAAAAAAAAAAGACABSbG5SsYUO+3yDQiocw7IK9XrZPn342lmJHvIsi3AoQ==
bXktaWQAAAAAAAAAAAAAAAAGACACG3DYxuxi80ZHtS92LMjJdXKZXK0qUyQPPN75QTDWWQ==
bXktaWQAAAAAAAAAAAAAAAAGACADymMqG4Jcj3DzsEj5vrR3H4dSC1zBz4o+hOT3cRedcA==
bXktaWQAAAAAAAAAAAAAAAAGACAE4799QERpCUmkFcbcM8tr9iPZC2s9OYNZeGjOV33lcg==
bXktaWQAAAAAAAAAAAAAAAAGACAFqpKK7RKjFdWQ06Jrzk8DR1mOOnGx0TmduuU1Ahhk9g==
bXktaWQAAAAAAAAAAAAAAAAGACAGGVEu2UckgelXWnYemD+Nt9/hRfijjTRyNVomHT9hvQ==
bXktaWQAAAAAAAAAAAAAAAAGACAHnLb3w8qhudxA4F3h4unHLvXlPsdQdSWAS/9o6n5Fnw==
bXktaWQAAAAAAAAAAAAAAAAGACAIGu3qTwMRWkBACZiNArdFh5XFs3dmUFfqeSj3TR3p2g==
Reconstructed: The secret of Tipsy-cola is ...

And so we could give each director one of the shares, and then the recipe would only be revealed when six of them got together.

While this works well with small amounts of data, it does not scale well with large data elements. And so we normally take an encryption key and split it into a number of shares. These shares are then stored on different cloud systems, and when we require the key back we request the shares from the cloud systems. Anyone looking at these systems could not derive the key, unless they are able to get access to all the systems. We could also make a system where we could make data inaccessible if we delete the number of key shares to less than the threshold.

Here is a more advanced method and uses elliptic curve key shares: