Shamir Secret Shares and Kryptology

Shamir Secret Shares and Kryptology

In 1979, Adi Shamir (the ‘S” in RSA) published a classic paper in the Communications of the ACM [1]:

While a fairly old method, it is now being used to split up encryption keys, so let’s have a look at a basic implementation.

Byzantine Fault Tolerance

We need to start building systems which are fault-tolerant, and where we assume that sometimes our systems give us errors, or can be faulty, or that they have been taken over by a malicious agent. This will give us Byzantine Fault Tolerance (BFT) in our processing and decision-making. For example, let’s say we are processing a transaction, and have four checkers for the validity of the transaction. If we had one checker, then it may have an error or could be compromised by a hacker. But if we have four, then if three of the checkers were good, we would have an election, and take the majority vote. A checker which loses these elections may then be faulty or is compromised.

A perfect way of keeping things secure and creating resilience is to use Shamir Secret Sharing (SSS), and where we can distribute a secret, and then allow any n-from-m to recover the secret. In this way, Bob, Alice, Carol and Dave can share a secret, and then any three of them can come together and recreate the share. This means we also have resilience in that one might not want to share — or have lost their secret — and we will still be able to recover it. But, what happens when Alice goes bad, can we recreate the shares between Bob, Carol and Dave, so that Alice cannot rebuild the secret? Well, yes! For this, we use Proactive Secret Shares (PSS), but first I’ll explain Shamir’s Secret Shares (SSS), and then outline PSS.

Shamir’s Secret Shares

With secret sharing, we take a secret value and then share it with others. For example, we might have a share for Bob, Alice, Carol and Dave and then for three of them to come together to bring their shares together. First, we generate a polynomial, and which has a secret value. In the following example, we have a quadratic equation of f(x)=2x² -2x + 5 [here]. The secret could be stored at f(0) (the red line), and where we give Bob their y value for x=1 (f(1) — the purple line), Carol the value at x=2 (f(2) — the blue line), Dave the value at x=3 (f(3) — the green line) and Alice the value at x=4 (f(4) — the outer blue line). With the values of their own, they cannot recover f(0), but if we have three of the values, we can recover it:

For an any-3-from-4, we can use a quadratic equation, such as f(x)=20x²−2x+10, and where the value of 10 is the secret. Bob then gets the value of f(x) when x=1. This can be defined as f(1). Carol gets f(2), Dave gets f(3) and Alice gets f(4). The secret value is thus f(0). They then each know a point on the quadratic equation, and three of them can bring temn back to recover the secret. In this case, we will generate a random polynomial of ax²+bx+secret, and then distribute the shares to Bob, Alice, Carol and Dave.

Shamir Secret Shares and Kryptography

We can use the Kryptography library developed by Coinbase to implement Shamir Secret Shares. In this case, we will define t for the threshold and n for the number of shares [here]:

package main

import (
	crand "crypto/rand"
	"fmt"
	"os"
	"strconv"

	"github.com/coinbase/kryptology/pkg/core/curves"
	"github.com/coinbase/kryptology/pkg/sharing"
)

func main() {

	msg := "Hello"
	var t uint32 = uint32(2)
	var n uint32 = uint32(3)
	argCount := len(os.Args[1:])

	if argCount > 0 {
		msg = os.Args[1]
	}
	if argCount > 1 {
		val, err := strconv.Atoi(os.Args[2])
		if err == nil {
			t = uint32(val)
		}
	}
	if argCount > 2 {
		val, err := strconv.Atoi(os.Args[3])
		if err == nil {
			n = uint32(val)
		}
	}

	curve := curves.ED25519()
	scheme, _ := sharing.NewShamir(t, n, curve)

	shares, _ := scheme.Split(curve.NewScalar().Hash([]byte(msg)), crand.Reader)

	fmt.Printf("== Secret shares == %d from %d ===\n", t, n)
	for _, s := range shares {
		fmt.Printf("%x ", s.Bytes())
	}
	fmt.Printf("\n=================\n")

	mysecret := curve.NewScalar().Hash([]byte(msg))

	fmt.Printf("Message: %s\n", msg)
	fmt.Printf("\nOriginal Hash: %x\n\n", mysecret.Bytes())

	secret, err := scheme.Combine(shares...)
	if err == nil {
		fmt.Printf("Recorded Hash with all the shares: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with all shares\n")
	}

	secret, err = scheme.Combine(shares[0])
	if err == nil {
		fmt.Printf("Recorded Hash with one share: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with one share\n")
	}

	secret, err = scheme.Combine(shares[0], shares[1])
	if err == nil {
		fmt.Printf("Recorded Hash with two shares: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with two shares\n")
	}

}

A sample run of a 2 from 3 is [here]:

== Secret shares == 2 from 3 ===
00000001cdd7b102063bd58b6d785823a686aab5fef297d0820d36d9ef3e2c51bd5ff604 00000002d2fc951ff25611d8d816dac4604e76f544970df5cac8c3d2234a4de4e71bc60a 00000003ea4d84dfc30f3bcc6d1864c33c1c63208b3b8319138451cc57556e7712d89500 
=================
Message: hello

Original Hash: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

Recorded Hash with all the shares: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f
Cannot recover with one share
Recorded Hash with two shares: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

Here is the running code:

https://asecuritysite.com/kryptology/sss01

References

[1] Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613.