sss-rs

An implementation of a secret sharing scheme in Rust.

Given N required shares to reconstruct, and M shares generated, any X number of shares where N <= X <= M can be used, without the need of specifying how many were required (using more shares however will increase reconstruction time).

There are two primary modules, [wrapped_sharing] and [basic_sharing]. [basic_sharing] holds the core secret sharing implementation, and [wrapped_sharing] provides convenience wrappers around those implementations as well as the option to verify reconstruction of the secret.

This implementation uses arithmetic over GF(256) for the core secret sharing algorithm.

Examples

Abstractions

Functional wrapped API

Useful for working with relatively small secrets.

use sss_rs::prelude::*;
let shares_required = 3;
let shares_to_create = 3;
let verify = true;
let secret: Vec<u8> = vec![5, 4, 9, 1, 2, 128, 43];
let shares = share(&secret, shares_required, shares_to_create, verify).unwrap();
let recon = reconstruct(&shares, verify).unwrap();
assert_eq!(secret, recon);

Streaming wrapped API

Useful for working with very large secrets and shares that you don't want all loaded into memory at once.

use sss_rs::prelude::*;
use std::io::Cursor;

let mut dest1 = Cursor::new(Vec::new());
let mut dest2 = Cursor::new(Vec::new());
let full_secret = b"This is a very long secret read in from a buffered file reader";
let secret_chunks = full_secret.chunks(8).collect::<Vec<&[u8]>>();
let mut recon_dest = Cursor::new(Vec::new());

let mut sharer = Sharer::builder()
    .with_shares_required(2)
    .with_output(&mut dest1)
    .with_output(&mut dest2)
    .with_verify(true)
    .build()
    .unwrap();

for secret in secret_chunks.iter() {
    sharer.update(secret).unwrap();
}
sharer.finalize().unwrap();

// The outputs dest1 and dest2 have had their shares written to them.

let mut reconstructor = Reconstructor::new(&mut recon_dest, true);

for (chunk1, chunk2) in dest1.get_ref().chunks(4).zip(dest2.get_ref().chunks(4)) {
    reconstructor.update(&[chunk1, chunk2]).unwrap();
}
reconstructor.finalize().unwrap();
assert_eq!(&full_secret, &recon_dest.into_inner().as_slice());

Core

Single-byte

If you need more control over sharing and reconstruction or write your own abstractions, the [basic_sharing] functions can be used.

use sss_rs::basic_sharing::{from_secret, reconstruct_secret};
let secret: u8 = 23; // The secret to be split into shares
let shares_required = 3; // The number of shares required to reconstruct the secret
let shares_to_create = 3; // The number of shares to create, can be greater than the required

let shares: Vec<(u8, u8)> = from_secret(
		secret,
		shares_required,
		shares_to_create,
        None,
	).unwrap();
let secret_recon = reconstruct_secret(shares);

assert_eq!(secret, secret_recon);

Slice of bytes

Very similar to the above example but works on slices of bytes.

use sss_rs::basic_sharing::{from_secrets, reconstruct_secrets};
let secret = b"Hello world"; // The secret to be split into shares
let shares_required = 3; // The number of shares required to reconstruct the secret
let shares_to_create = 3; // The number of shares to create, can be greater than the required

let shares: Vec<Vec<(u8, u8)>> = from_secrets(
		secret,
		shares_required,
		shares_to_create,
        None,
	).unwrap();
let secret_recon = reconstruct_secrets(shares).unwrap();

assert_eq!(secret, secret_recon.as_slice());

Slice of bytes deduped x values

Also very similar to the above example but will dedup the x-value of each share and place it at the beginning of each list of shares. All functionality in [wrapped_sharing] utilizes this. There is an explanation below that describes how and why this works in more detail.

use sss_rs::basic_sharing::{from_secrets_compressed, reconstruct_secrets_compressed};
let secret = b"Hello world"; // The secret to be split into shares
let shares_required = 3; // The number of shares required to reconstruct the secret
let shares_to_create = 3; // The number of shares to create, can be greater than the required

let shares: Vec<Vec<u8>> = from_secrets_compressed(
		secret,
		shares_required,
		shares_to_create,
        None,
	).unwrap();
let secret_recon = reconstruct_secrets_compressed(shares).unwrap();

assert_eq!(secret, secret_recon.as_slice());

Sharing and share 'compression' explanation

N = Number of shares required for reconstruction
M = Number of shares that were created
S = Length of the secret being shared.

Usually, a list of points is needed for the reconstruction of a byte. (x1, y1), (x2, y2), (x3, y3), ... (xM, yM) where at least N number of points from the M created points are needed to reconstruct the byte. Each share is twice as large as the original secret.

When we share a slice of bytes, we get lists of shares like this:

(x1a, y1a), (x2a, y2a), (x3a, y3a), ... (xMa, yMa)
(x1b, y1b), (x2b, y2b), (x3b, y3b), ... (xMb, yMb)
(x1c, y1c), (x2c, y2c), (x3c, y3c), ... (xMc, yMc)
...
(x1S, y1S), (x2S, y2S), (x3S, y3S), ... (xMS, yMS)

Each of the above list of points corresponds to just 1 byte of the secret. For example, any N points from the first list will reconstruct the first byte of the secret. These cannot be distrubted this way, since each share corresponds to one byte, rather than one piece of the whole secret. So, we transpose this, so every list has one piece of every byte of the secret.

(x1a, y1a), (x1b, y1b), (x1c, y1c), ... (x1S, y1S)
(x2a, y2a), (x2b, y2b), (x2c, y2c), ... (x2S, y2S)
(x3a, y3a), (x2b, y2b), (x3c, y3c), ... (x3S, y3S)
...
(xMa, yMa), (xMb, yMb), (xMc, yMc), ... (xMS, yMS)

Now with a given index, the byte of the secret at that index can be reconstructed from at least N shares. For example, to reconstruct the 3rd byte of the secret, you need the third point from at least N shares to reconstruct. Now everyone has a list of points where each point corresponds to just 1 byte of the original secret. These can now be distributed.

Moving onto the compression, the x values can be predictable without a significant impact to the security of the shares. This is what the list of shares prior to transposition look like with predictable x-values.

(1, y1a), (2, y2a), (3, y3a), ... (M, yMa)
(1, y1b), (2, y2b), (3, y3b), ... (M, yMb)
(1, y1c), (2, y2c), (3, y3c), ... (M, yMc)
...
(1, y1S), (2, y2S), (3, y3S), ... (M, yMS)

And when we transposed for the reasons stated prior to make these shares distributable:

```notrust
(1, y1a), (1, y1b), (1, y1c), ... (1, y1S)
(2, y2a), (2, y2b), (2, y2c), ... (2, y2S)
(3, y3a), (3, y3b), (3, y3c), ... (3, y3S)
...
(M, yMa), (M, yMb), (M, yMc), ... (M, yMS)

We can see the x values for every point in a given share is identical. So we can dedup that x-value and have one copy of it at the beginning of each share.

1, y1a, y1b, y1c, ... y1S
2, y2a, y2b, y2c, ... y2S
3, y3a, y3b, y3c, ... y3S
...
M, yMa, yMb, yMc, ... yMS

Which brings the size of each share to just S + 1 compared to S * 2 previously.