dsprenkels/sss

Library for the Shamir secret sharing scheme

Shamir secret sharing library

sss is a library that exposes an API to split secret data buffers into a number of different shares. With the possession of some or all of these shares, the original secret can be restored. It is the schoolbook example of a cryptographic threshold scheme. This library has a command line interface. (web demo)

Table of contents

1. Introduction
2. Download
3. Usage
   1. Example
   2. How to Run Program (above)
4. Bindings
5. Technical details
6. Comparison of secret sharing libraries
7. Questions

Introduction

An example use case is a beer brewery which has a vault which contains their precious super secret recipe. The 5 board members of this brewery do not trust all the others well enough that they won't secretly break into the vault and sell the recipe to a competitor. So they split the code into 5 shares, and allow 4 shares to restore the original code. Now they are sure that the majority of the staff will know when the vault is opened, but they can still open the vault when one of the staff members is abroad or sick at home.

As often with crypto libraries, there is a lot of Shamir secret sharing code around that does not meet cryptographic standards (a.k.a. is insecure). Some details—like integrity checks and side-channel resistance—are often forgotten. But these slip-ups can often fully compromise the security of the scheme. With this in mind, I have made this library to:

• Be side channel resistant (timing, branch, cache)
• Secure the shared secret with a MAC
• Use the platform (OS) randomness source

It should be safe to use this library in "the real world". I currently regard the API as being stable. Should there be any breaking changes, then I will update the version number conforming to the semantic versioning spec.

Download

I have released version 0.1.0 of this library, which can be downloaded from the releases page. However, I actually recommend cloning the library with git, to also get the necesarry submodules:

git clone --recursive https://github.com/dsprenkels/sss.git

The current version is version 0.1.0, which should be stable enough for now. The functionality may still change before version 1.0.0, although I will still fix any security issues before that.

Usage

Secrets are provided as arrays of 64 bytes long. This should be big enough to store generally small secrets. If you wish to split larger chunks of data, you can use symmetric encryption and split the key instead. Shares are generated from secret data using sss_create_shares and shares can be combined again using the sss_combine_shares functions. The shares are octet strings of 113 bytes each.

This library is implemented in such a way that the maximum number of shares is 255.

Moreover, every share includes an ID, which is implemented as a counter. This ID is not considered a secret by the library, and an participants may be able to infer the amount of shares from these ids (for example, if I have a share with ID=3, I expect that ID∈{1,2} will also exist. If you require random share IDs, then you should generate 255 different shares, and randomly throw away the excess shares.

Example

#include "sss.h"
#include "randombytes.h"
#include <assert.h>
#include <string.h>

int main()
{
	uint8_t data[sss_MLEN], restored[sss_MLEN];
	sss_Share shares[5];
	size_t idx;
	int tmp;

	// Read a message to be shared
	strncpy(data, "Tyler Durden isn't real.", sizeof(data));

	// Split the secret into 5 shares (with a recombination theshold of 4)
	sss_create_shares(shares, data, 5, 4);

	// Combine some of the shares to restore the original secret
	tmp = sss_combine_shares(restored, shares, 4);
	assert(tmp == 0);
	assert(memcmp(restored, data, sss_MLEN) == 0);
}

How to Run program (above)

1. clone from git by bellow command. (As It is recommended. If you clone make sure that file under subdirectory also came with it)

git clone --recursive https://github.com/dsprenkels/sss.git

2. go inside sss directory and run make command

make

3. copy the example provided in readme as above and save it as demo.c

4. compile demo.c by running bellow commnad

gcc demo.c -o demo randombytes.o sss.o hazmat.o tweetnacl.o

5. execute program by bellow command

./demo

Bindings

I have currently written bindings for the following languages:

• Node.js
• Go
• Rust
• WASM
• Android¹
• Haskell¹
• Swift¹

¹ No releases yet.

There are also contributed bindings:

• Nim
• Erlang

Technical details

Shamir secret sharing works by generating a polynomial (e.g. 33x³ + 8x² + 29x + 42). The lowest term is the secret and is just filled in. All the other terms are generated randomly. Then we can pick points on the polynomial by filling in values for x. Each point is put in a share. Afterwards, with k points we can use interpolation to restore a k-degree polynomial.

In practice there is a wrapper around the secret-sharing part (this is done because of crypto-technical reasons). This wrapper uses the XSalsa20/Poly1305 authenticated encryption scheme. Because of this, the shares are always a little bit larger than the original data.

This library uses a custom randombytes function to generate a random encapsulation key, which talks directly to the operating system. When using the high level API, you are not allowed to choose your own key. It must be uniformly random, because regularities in shared secrets can be exploited.

With the low level API (hazmat.h) you can choose to secret-share a piece of data of exactly 32 bytes. This produces a set of shares that are much shorter than the high-level shares (namely 33 bytes each). However, keep in mind that this module is called hazmat.h (for "hazardous materials") for a reason. Please only use this if you really know what you are doing. Raw "textbook" Shamir secret sharing is only safe when using a uniformly random secret (with 128 bits of entropy). Note also that it is entirely insecure for integrity. Please do not use the low-level API unless you really have no other choice.

Comparison of secret-sharing libraries

If you would like your library to be added here, please open a pull request. :)

Library	Side-channels	Tamper-resistant	Secret length
B. Poettering	Insecure¹	Insecure	128 bytes
libgfshare	Insecure²	Insecure	∞
blockstack	??³	Insecure	160 bytes
sssa-golang	Secure	Secure⁴	∞
sssa-ruby	??³	Secure⁴	∞
snipsco	Secure	Insecure	Note⁶
c-sss	Insecure⁷	Insecure	∞
timtiemens	Insecure⁸	Note⁹	512 bytes
dsprenkels	Secure	Secure⁵	64 bytes

Notes

It is important to note that a limited secret length does not mean that it is impossible to share longer secrets. The way this is done is by secret sharing a random key and using this key to encrypt the real secret. This is a lot faster and the security is not reduced. (This is actually how sss-cli produces variable-length shares.)

1. Uses the GNU gmp library.
2. Uses lookup tables for GF(256) multiplication.
3. This library is implemented in a high level scripting library which does not guarantee that its basic operators execute in constant-time.
4. Uses randomized x-coordinates.
5. Uses randomized y-coordinates.
6. When using the snipsco library you will have to specify your own prime. Computation time is O(p²), so on a normal computer you will be limited to a secret size of ~1024 bytes.
7. As mentioned by the documentation.
8. Uses Java BigInteger class.
9. Basic usage of this tool does not protect the integrity of the secrets. However, the project's readme file advises the user to use a hybrid encryption scheme and secret share the key. Through destroying the ephemeral key, the example that is listed in the readme file protects prevents an attacker from arbitrarily inserting a secret. However, inserting a garbled secret is still possible. To prevent this the user should use a AEAD scheme (like AES-GCM or ChaCha20-Poly1305) instead of AES-CBC.

Questions

I do not know a lot about secret sharing. Is Shamir secret sharing useful for me?

It depends. In the case of threshold schemes (that's what this is) there are two types:

1. The share-holders cannot verify that their shares are valid.
2. The share-holders can verify that their shares are valid.

Shamir's scheme is of the first type. This immediately implies that the dealer could cheat. Indeed, they can distribute a number of shares which are just random strings. The only way the participants could know is by banding together and trying to restore the secret. This would show the secret, which would make the scheme totally pointless.

Use Shamir secret sharing only if the dealer and the participants have no reason to corrupt any shares.

Examples where this is not the case:

• When the secret hides something that is embarrasing for one of the participants.
• When the shared secret is something like a testament, and the participants are the heirs. If one of the heirs inherits more wealth when the secret is not disclosed, they can corrupt their share (and it would be impossible to check this from the share alone).

In these cases, you will need a scheme of the second type. See the next question.

Wait, I need verifiable shares! What should I use instead?

There are two straightforward options:

1. When the secret is fully random—for example, a cryptographic key—use Feldman verifiable secret sharing.
2. When the secret is not fully random—it could be a message, a number, etc.—use Pedersen verifiable secret sharing.

Other

For other questions, feel free to open an issue or send me an email on my Github associated e-mail address.

sss's Issues

Question: does this library support feldman verifiable sss ?

hi,
could not see how else to address this question. hence filing an issue. How can i use the library to use verifiable sss using feldman approach of homomorphic encryption ?
thanks,
regards,
Nilay

Publish a 1.0 release

I seems the library has been stable for quite a while. It may be time to move to a 1.x-release channel.

List Tim Tiemens' implementation in readme

Hi there,

You are missing Tim Tiemens implementation in Java https://github.com/timtiemens/secretshare

Also maybe relevant this end-user application I've made https://secrets.dyne.org which can split any plain-text material into secret shares using FastPFOR128 integer compression. I would love to find a C implementation compatible with the output of my software, which is written in Clojure and runs on Tim's Java library.

Error while executing makefile

I've been trying to run your makefile, and as soon as I've cloned your git, I have then tried running the make command, but I keep on getting the error that there's no file or directory named sys/syscall.h (included in the randombytes.c and randombytes.h files).

Notes on blockstack/secret-sharing

It does not use GF(256) or other GF(2^n) unlike sss and others.
Something worth while to note.
Also

• https://github.com/SSSaaS
• https://github.com/ronreiter/multicrypt (Python)
• https://github.com/klingebj/shamir_bip39_2039 (Python)
• https://github.com/seancomeau/ShamirSecretSharing (Python)
• https://github.com/szymekk/shamirs_secret_sharing (Python)
• https://github.com/pcrain/pyshamir (Python)
• https://github.com/myd1/Shamir-s-Secret-Sharing (Python)
• https://github.com/nijynot/shamir (JS)
• https://github.com/mdciotti/polypass (JS)
• https://github.com/agl/shamirsplit (Go)
• https://github.com/itslab-kyushu/sss (Go)
• https://github.com/iowaguy/shamir-secret-sharing (Go)
• https://github.com/republicprotocol/shamir-go (Go)
• https://github.com/amousa11/sss (Go)

has this feature. (have not checked C or C++)

Implement a "detached" version of `sss_create_shares`

For performance reasons you may want to generate a lot of sss_Shares, but write the ciphertext that is being generated only once. This is currently not supported by the API. Perhaps we should write a "detached" version of sss_create_shares (and sss_combine_shares) to make this possible.

undefined behavior in shamir unbitslice()

During security research for SatoshiLabs on the Trezor firmware, I recently discovered an undefined behaviour edge case via (1 << 31) in the following line for unbitslice():

sss/hazmat.c

Line 59 in b3ac4e7

r[arr_idx] |= ((cur & (1 << arr_idx)) >> arr_idx) << bit_idx;

UndefinedBehaviorSanitizer:
runtime error: left shift of 1 by 31 places cannot be represented in type 'int'

Please see the main bug report for details of the issue and two proposed patches. Note that our unbitslice() variant has a dynamic length parameter, but is called with len = 32 in this context and should be functionally identical.

@dsprenkels : we're interested if you can confirm the issue. Which patch do you prefer? Thanks!

Language bindings

Ordered by priority:

• C++ (natively supported)
• Go
• Rust
• Python
• Node.js
• Swift
• Java (not yet mature)
• Haskell (not yet mature)

Command line interface

We should build a command line interface that so that users can split/combine secrets from the command line. This also allows for demos.

Change `sss_Keyshare` type to uint8_t[33]

Repeating shares on embedded device

I'd like to use your great library on an embedded device (Arduino), but unfortunately the randombytes library doesn't work because there is no OS running on the microcontroller.

So I'm running a modified sss.c that doesn't rely on randombytes. I'm just trying to get a basic working example, and worry about secure implementation later.

#include <stdlib.h>
#include <time.h>

void sss_create_shares(sss_Share *out, const unsigned char *data, uint8_t n, uint8_t k)
{
        srand(time(NULL));
	unsigned char key[32];
        int val;
	unsigned char m[crypto_secretbox_ZEROBYTES + sss_MLEN] = { 0 };
	unsigned long long mlen = sizeof(m); /* length includes zero-bytes */
	unsigned char c[mlen];
	int tmp;
	sss_Keyshare keyshares[n];
	size_t idx;

	/* Generate a random encryption key */
	//randombytes(key, sizeof(key));
       
       //generate a key with a different method
       for(int i = 0; i < 32; i++){
             val = rand();  
              key[i] = val;
        }

And I'm calling sss_create_shares like so:

sss_Share shares[2];
uint8_t data[sss_MLEN]
strncpy(data, "hello", sizeof(data));
sss_create_shares(shares, data, 2, 2);

for(int i = 0; i < sizeof(shares[0]); i++){
    Serial.println(shares[0][i]);
    Serial.println(shares[1][i]);
    Serial.println("");
}

The output shows that the shares are exactly the same, except the beginning few characters. The output of the above code looks like (all values at the same idx are the same, except first bits):

93
93

236
236

153
153
... 

I'm stuck at this point and was hoping for some hint about how it's possible the shares come out pretty much exactly the same. I've a feeling it's because of how I'm making the key in sss_create_shares

EDIT: I ended up using this library and it works great

Explicitly warn that `x` is *not* considered secret

This issue was (kind of) reported by @wolfmcnally.

An implementor has assumed that the x coordinate is secret. They expect that you are not able to read---from a share---how many shares exist in total. Right now, you can deduce from the existence of (for example) share 8, that shares 7..1 exist.

Support variable-length secrets

Note: the idea is not to change the key length, only the XSalsa20 encrypted message. We should estimate whether we want to make this the default functionality, and if so, whether it's acceptable to break backwards-compatibility with the current API.

make error syscall

I am using Window's subsystem Ubuntu 18.04, when I call make, it gives an error

randombytes.c:77:10: warning: implicit declaration of function ‘syscall’; did you mean ‘sysconf’? [-Wimplicit-function-declaration]
    ret = syscall(SYS_getrandom, (char *)buf + offset, chunk, 0);

should I comment #include <sys/syscall.h> from random.h file? Or what is the solution? Please help.
I am trying to use this library in EOS smart contract.

How to add this library as a dependency in an Android project

I wish to use the Java binding of the library for an Android project, but I cannot find a maven dependency for it. Can you please provide the maven dependency for it?

Also, I'm unable to compile the Android code I cloned from the library. So, can you also provide the steps, to integrate and use the library for an android project.

How to integrate the library in a Swift project.

> 255 shares

Because you are using byte-wise (GF256) shamir/reedsolomon the limit on codewords is 255.

This means you can't have more than 255 unique shares.

How difficult would it be to extend this work to GF(2^16) where the limit would be 65535 shares?

Python and JS wrapper

Might be useful for people who wants to play around with SSSS

Tamper-resistant criterion

From the comparing table on the README.md, another two libraries (sssa-{golang,ruby}) are secure on the Tamper-resistant. As the notes say, the current library use AEAD to check the integrity of the raw result, so mark as Tamper-resistant. The other two libraries, which share the same implementation, do not perform aead, but split the raw input into 256-bit slices and generate polynomial for each slice independently. Why the independent polynomials can pass Tamper-resistant review?

Do not expose `sss_share` struct

For the high-level API, users will not need to be able to access values inside the structs. So we should hide the struct from the user and expose only static-sized byte arrays.

Is it possible to create this project as portable?

First, I am ignorant on development, so maybe I am just saying something that does not makes sense.

I am trying to find a solution to use SSS with my personal password manager so, in case something happens to me, my wife or my family will be able to open it and get the passwords.

Because of this, I was hoping I would be able to find a solution that includes a portable system to "recreate" the main key, and store that on a USB and shared that with the parts.

This way, if they need to create the key, they will know how to do it.

Is there any way to use this library like that?
If not, do you know any other solution that could work for me?

Thanks

Getting Start section needed in Readme

I feel there is need for getting start section in Readme which provide instruction about how to run this program. It describe this process step by step.
suppose I want to run the example provided in readme then how I am going to run this ?
I started this and got some errors some of them are as bellow.

1. rondombytes.h and randombytes.c are not actual file they are symbolic link and my Ubuntu 18.04 os not able to find it.

 demo.c:2:10: fatal error: randombytes.h: No such file or directory
 #include "randombytes.h"
          ^~~~~~~~~~~~~~~
compilation terminated.

2. when I try to make using file getting from github from bellow link and then run the example then i get bellow error.

make -C randombytes librandombytes.a
make[1]: Entering directory '/home/vishvajeet/Desktop/Election/helping_script/shamir/sss-master/randombytes'
make[1]: *** No rule to make target 'librandombytes.a'.  Stop.
make[1]: Leaving directory '/home/vishvajeet/Desktop/Election/helping_script/shamir/sss-master/randombytes'
Makefile:20: recipe for target 'randombytes/librandombytes.a' failed
make: *** [randombytes/librandombytes.a] Error 2

3. when i try to make I got bellow error

make -C randombytes librandombytes.a
make[1]: Entering directory '/home/vishvajeet/Desktop/Election/helping_script/shamir/sss-master/randombytes'
make[1]: *** No rule to make target 'librandombytes.a'.  Stop.
make[1]: Leaving directory '/home/vishvajeet/Desktop/Election/helping_script/shamir/sss-master/randombytes'
Makefile:20: recipe for target 'randombytes/librandombytes.a' failed
make: *** [randombytes/librandombytes.a] Error 2

If there will be guide then it will helpful for people who are new like me.
Thank you