• This repository has been archived on 25/Jul/2019
  • Stars
    star
    208
  • Rank 189,015 (Top 4 %)
  • Language
    Java
  • License
    Apache License 2.0
  • Created over 7 years ago
  • Updated 12 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

A Java implementation of Shamir's Secret Sharing algorithm over GF(256).

Shamir's Secret Sharing

CircleCI

A Java implementation of Shamir's Secret Sharing algorithm over GF(256).

Add to your project

<dependency>
  <groupId>com.codahale</groupId>
  <artifactId>shamir</artifactId>
  <version>0.7.0</version>
</dependency>

Note: module name for Java 9+ is com.codahale.shamir.

Use the thing

import com.codahale.shamir.Scheme;
import java.nio.charset.StandardCharsets;
import java.security.SecureRandom;
import java.util.Map;

class Example {
  void doIt() {
    final Scheme scheme = new Scheme(new SecureRandom(), 5, 3);
    final byte[] secret = "hello there".getBytes(StandardCharsets.UTF_8);
    final Map<Integer, byte[]> parts = scheme.split(secret);
    final byte[] recovered = scheme.join(parts);
    System.out.println(new String(recovered, StandardCharsets.UTF_8));
  } 
}

How it works

Shamir's Secret Sharing algorithm is a way to split an arbitrary secret S into N parts, of which at least K are required to reconstruct S. For example, a root password can be split among five people, and if three or more of them combine their parts, they can recover the root password.

Splitting secrets

Splitting a secret works by encoding the secret as the constant in a random polynomial of K degree. For example, if we're splitting the secret number 42 among five people with a threshold of three (N=5,K=3), we might end up with the polynomial:

f(x) = 71x^3 - 87x^2 + 18x + 42

To generate parts, we evaluate this polynomial for values of x greater than zero:

f(1) =   44
f(2) =  298
f(3) = 1230
f(4) = 3266
f(5) = 6822

These (x,y) pairs are then handed out to the five people.

Joining parts

When three or more of them decide to recover the original secret, they pool their parts together:

f(1) =   44
f(3) = 1230
f(4) = 3266

Using these points, they construct a Lagrange polynomial, g, and calculate g(0). If the number of parts is equal to or greater than the degree of the original polynomial (i.e. K), then f and g will be exactly the same, and f(0) = g(0) = 42, the encoded secret. If the number of parts is less than the threshold K, the polynomial will be different and g(0) will not be 42.

Implementation details

Shamir's Secret Sharing algorithm only works for finite fields, and this library performs all operations in GF(256). Each byte of a secret is encoded as a separate GF(256) polynomial, and the resulting parts are the aggregated values of those polynomials.

Using GF(256) allows for secrets of arbitrary length and does not require additional parameters, unlike GF(Q), which requires a safe modulus. It's also much faster than GF(Q): splitting and combining a 1KiB secret into 8 parts with a threshold of 3 takes single-digit milliseconds, whereas performing the same operation over GF(Q) takes several seconds, even using per-byte polynomials. Treating the secret as a single y coordinate over GF(Q) is even slower, and requires a modulus larger than the secret.

Performance

It's fast. Plenty fast.

For a 1KiB secret split with a n=4,k=3 scheme:

Benchmark         (n)  (secretSize)  Mode  Cnt     Score    Error  Units
Benchmarks.join     4          1024  avgt  200   196.787 ±  0.974  us/op
Benchmarks.split    4          1024  avgt  200   396.708 ±  1.520  us/op

N.B.: split is quadratic with respect to the number of shares being combined.

Tiered sharing

Some usages of secret sharing involve levels of access: e.g. recovering a secret requires two admin shares and three user shares. As @ba1ciu discovered, these can be implemented by building a tree of shares:

class BuildTree {
  public static void shareTree(String... args) {
    final byte[] secret = "this is a secret".getBytes(StandardCharsets.UTF_8);
    
    // tier 1 of the tree
    final Scheme adminScheme = new Scheme(new SecureRandom(), 5, 2);
    final Map<Integer, byte[]> admins = adminScheme.split(secret);

    // tier 2 of the tree
    final Scheme userScheme = Scheme.of(4, 3);
    final Map<Integer, Map<Integer, byte[]>> admins =
        users.entrySet()
            .stream()
            .collect(Collectors.toMap(Map.Entry::getKey, e -> userScheme.split(e.getValue())));
    
    System.out.println("Admin shares:");
    System.out.printf("%d = %s\n", 1, Arrays.toString(admins.get(1)));
    System.out.printf("%d = %s\n", 2, Arrays.toString(admins.get(2)));

    System.out.println("User shares:");
    System.out.printf("%d = %s\n", 1, Arrays.toString(users.get(3).get(1)));
    System.out.printf("%d = %s\n", 2, Arrays.toString(users.get(3).get(2)));
    System.out.printf("%d = %s\n", 3, Arrays.toString(users.get(3).get(3)));
    System.out.printf("%d = %s\n", 4, Arrays.toString(users.get(3).get(4)));
  }
}

By discarding the third admin share and the first two sets of user shares, we have a set of shares which can be used to recover the original secret as long as either two admins or one admin and three users agree.

License

Copyright © 2017 Coda Hale

Distributed under the Apache License 2.0.

More Repositories

1

sneaker

A tool for securely storing secrets on S3 using Amazon KMS.
Go
801
star
2

metrics

This is not the Java library.
Go
451
star
3

jerkson

[ABANDONED] The Scala applewood bacon to Jackson's chicken breast: JSON cordon bleu.
Scala
279
star
4

usl4j

A reasonably complete implementation of the Universal Scalability Law model.
Java
201
star
5

lunk

lunk provides a set of tools for structured logging in the style of Google's Dapper or Twitter's Zipkin
Go
127
star
6

sss

A pure Go implementation of Shamir's Secret Sharing algorithm over GF(256)
Go
103
star
7

http-handlers

Some handy HTTP handlers for Go.
Go
85
star
8

ministat

A small tool to do the statistics legwork on benchmarks etc.
Shell
75
star
9

tinystat

A Go library and CLI tool for evaluating whether two or more sets of measurements are statistically different.
Go
69
star
10

sketchy

A small set of useful probabilistic data structures.
Rust
69
star
11

logula

[ABANDONED] A Scala library which provides a sane log output format and an easy-to-use mixin for adding logging to your code.
Scala
51
star
12

chacha20

A pure Go implementation of the ChaCha20 stream cipher.
Go
46
star
13

charlie

charlie provides a fast, safe, stateless mechanism for adding CSRF protection to web applications.
Go
45
star
14

buster

A Go library which provides a re-usable framework for load-testing things.
Go
43
star
15

fast-uuid

A fast random UUID generator.
Java
41
star
16

rfc6979

A Go implementation of RFC 6979's deterministic DSA/ECDSA signature scheme.
Go
39
star
17

blake2

A BLAKE2 wrapper for Go.
Go
37
star
18

xsalsa20poly1305

A pure Java implementation of XSalsa20Poly1305 authenticated encryption.
Java
34
star
19

aes-gcm-siv

A Java implementation of AES-GCM-SIV (RFC 8452).
Java
33
star
20

jersey-scala

[ABANDONED] A Scala library which adds support to native Scala types in Jersey applications.
Scala
32
star
21

guava-cache-clj

A Clojure wrapper for Guava caches.
Clojure
30
star
22

usl

A Go library and CLI tool which simplifies calculation of Universal Scalability Law parameters given system measurements.
Go
30
star
23

horcrux

A pure Go implementation of security question style password recovery that preserves end-to-end cryptographic security.
Go
28
star
24

soy-clj

An idiomatic Clojure wrapper for Google Closure templates.
Clojure
28
star
25

fig

[ABANDONED] A small Scala library for using JSON-based configuration files.
Scala
27
star
26

time-id

Generates 27-character, time-ordered, k-sortable, URL-safe, globally unique identifiers.
Java
26
star
27

grpc-proxy

A gRPC service which proxies requests to an HTTP server.
Java
25
star
28

chacha20poly1305

An implementation of the chacha20poly1305 AEAD construction.
Go
25
star
29

passpol

A Java library for validating passwords against NIST SP-800-63B requirements.
Java
25
star
30

sskg

A Go implementation of a fast, tree-based Seekable Sequential Key Generator.
Go
24
star
31

pcg.rs

A Rust implementation of the PCG PRNG.
Rust
23
star
32

veil

Veil is an incredibly experimental hybrid cryptosystem for sending and receiving confidential, authentic multi-recipient messages which are indistinguishable from random noise by an attacker.
Rust
21
star
33

ruby-gsl

[ABANDONED] New development on the Ruby bindings for the GNU Scientific Library
C
20
star
34

guild

[ABANDONED] Simple, fast actors for Scala.
Scala
20
star
35

xoroshiro.rs

A Rust implementation of the Xoroshiro128+ PRNG.
Rust
19
star
36

colorbot

A Go library which determines the dominant colors in an image.
Go
19
star
37

yellhole

Where else you gonna scream?
Rust
18
star
38

docker-rebase

A tool to rebase Docker images.
Go
18
star
39

og

Java
18
star
40

veil-go

Stupid crypto tricks
Go
18
star
41

nanostat

A Rust library and CLI tool for evaluating whether two or more sets of measurements are statistically different.
Rust
16
star
42

shore

[ABANDONED] What makes Jersey fun.
Java
16
star
43

yoink

[ABANDONED] A Scala library which wraps Clojure's immutable, persistent collections.
Scala
16
star
44

healthchecks

A Go package which exposes health check results as expvars.
Go
15
star
45

faster-builder

[ABANDONED] A drop-in replacement for Builder::XmlMarkup which uses libxml for speed and security.
Ruby
15
star
46

cassie

See https://github.com/twitter/cassie for an actual, maintained version.
Scala
15
star
47

emacs.d

My Emacs configuration.
Emacs Lisp
14
star
48

safecookie

A Go library which provides simple, strong protection for cookies.
Go
14
star
49

dotfiles

Shell
13
star
50

redact

A Go package which allows you to easily redact sensitive flag values to prevent them from being exposed as expvars or via debugging endpoints.
Go
12
star
51

etm

A Go implementation of AES/CBC/HMAC-based AEAD constructions.
Go
11
star
52

common-pom

A common Maven POM for my various bits of Java software.
11
star
53

aesnicheck

A Go library for checking AES-NI support.
Go
10
star
54

kmssig

A Go utility and library to sign and verify files using AWS’s Key Management Service.
Go
10
star
55

usl-rs

A Rust crate and CLI tool which simplifies calculation of Universal Scalability Law parameters given system measurements.
Rust
9
star
56

reynolds

[ABANDONED] Your serialization format sucks.
Scala
9
star
57

jumphash

A Rust implementation of the Jump Consistent Hash algorithm.
Rust
9
star
58

trove-scala

[ABANDONED] Scala wrappers for the Trove primitive collections.
Scala
9
star
59

hadoop-streaming

[ABANDONED] Support libraries for writing Hadoop Streaming-compatible map/reduce tasks.
Python
8
star
60

balloonhash

A Java implementation of the Balloon Hash algorithm.
Java
8
star
61

ropen

[ABANDONED] A process execution library which doesn't suck.
Ruby
8
star
62

veil-java

Stupid crypto tricks
Java
7
star
63

baconhand

[ABANDONED] A useful slap in the face with baconhand.
Ruby
7
star
64

vlock

[ABANDONED] Vector clocks in Scala
Scala
7
star
65

lockstitch

Lockstitch is an incremental, stateful cryptographic primitive for symmetric-key cryptographic operations (e.g. hashing, encryption, message authentication codes, and authenticated encryption) in complex protocols.
Rust
7
star
66

mocko

A simple mocking library for Clojure.
Clojure
6
star
67

wasp

[ABANDONED] An append-only transaction log for Scala
Scala
6
star
68

kht

A Go implementation of a keyed hash tree.
Go
6
star
69

hrw

A Go implementation of Highest Random Weight hashing.
Go
6
star
70

spritz

A pure Go implementation of the Spritz stream cipher.
Go
5
star
71

u2f-clj

A library for implementing FIDO U2F multi-factor authentication.
Clojure
5
star
72

totp-clj

A Clojure library for TOTP multi-factor authentication.
Clojure
5
star
73

geoip

A simple Go wrapper for libGeoIP.
Go
5
star
74

gimli

A Java implementation of the Gimli cryptographic permutation and hash algorithm.
Java
4
star
75

sss.rs

Shamir’s Secret Sharing for Rust
Rust
4
star
76

longmapper

A bijective mapping for 64-bit integers.
Java
4
star
77

simple_do

[ABANDONED] A simple wrapper around DataObjects.
Ruby
4
star
78

makwa-go

A Go implementation of the Makwa password hashing algorithm.
Go
4
star
79

deyaml

Life’s too short to be a YAML farmer.
Go
4
star
80

hs-shamir

A Haskell implementation of Shamir’s Secret Sharing Scheme over GF(256).
Haskell
4
star
81

jdbc-perf-wrapper

[ABANDONED] A JDBC performance tracking wrapper.
Java
4
star
82

zk-cds

Hypothetical design of a zero-knowledge contact discovery system
Rust
4
star
83

tmpmysqld

tmpmysqld allows you to spin up temporary instances of mysqld in Go for testing purposes.
Go
4
star
84

path_mapper

[ABANDONED] TOTALLY NOT EVEN CLOSE TO WORKING YET. An efficient URL-to-options mapper.
Python
3
star
85

areion

A Rust implementation of the Areion256 and Areion512 permutations.
Rust
3
star
86

testdb

Go
3
star
87

grump

do not use this
Go
3
star
88

sfearthquakes

@sfqearthquakes
Java
3
star
89

voldemort-sets

[ABANDONED] A collection of view classes for the Voldemort key/value store which allow for the storage of sets of numbers.
Java
3
star
90

cpseg

Go
3
star
91

merb_simple_do

[ABANDONED] A Merb plugin for using DataObjects::Simple (simple_do).
Ruby
3
star
92

yrgourd

yrgourd uses Lockstitch to establish mutually-authenticated, forward-secure, confidential, high-performance connections. Like a toy Wireguard.
Rust
3
star
93

aead-stream

Java
3
star
94

xoodoo-p

High-performance, pure-Rust implementation of the Xoodoo-p permutation.
Rust
2
star
95

hudson_deployer

[ABANDONED] A Capistrano-based solution for deploying Java projects from Hudson.
Ruby
2
star
96

gubbins

Go
2
star
97

esi-blog

[ABANDONED] A sample application for playing around with some ESI ideas I had.
Ruby
2
star
98

rsa_pprf

A puncturable PRF based on the RSA accumulator.
Rust
2
star
99

eventflow

A high-throughput, low-latency, GCP-native, analytical event pipeline.
Java
2
star
100

kms-pass

Java
2
star