skip to content W3C SVG

Choosing a threshold-based secret sharing implementation

This article explains how we decided which secret sharing implementation to use for Dark Crystal.

Introduction

The difficulty with threshold-based secret sharing, compared to other cryptographic operations is that there is no widely accepted, rigorously defined standard.

Shamir’s paper describing the technique was published 1979 (with a similiar technique proposed by Blakley the same year), and since then there has been a great amount of academic work building and improving on it. Much of this work focusses on introducing verification of shares, such as the schemes proposed by Feldman and Pederson. However, turning a proven mathematical scheme into a secure implementation in code is rarely straightforward. Often design decisions need to be made which might deviate from the specification or introduce flaws or complications.

We aim to create a protocol which can be adopted by a wide variety of projects, but reliably gives consistent behaviour. So it is important to be agnostic to the choice of programming language. This means either proposing a rigorously defined standard, citing a clearly documented ‘reference implementation’ which can be re-implemented in other languages, or choosing an implementation in a low-level language which can be called by popular high-level languages through ‘bindings’.

Requirements of the implementation

  • Compact share size. In some cases it is important that shares are not too long, for example when they are going to be encoded as QR codes, or when many shares are to be stored on a mobile device. So using efficient encoding and only including the necessary metadata is important.

  • Using a secure random number generator with a good source of entropy, or allowing either a custom random number generator or an additional source of entropy to be passed in (in some cases it can be useful to take additional entropy from the secret itself, assuming the secret is uniformly random).

  • Flexible. We are looking for a low-level library, giving only basic functionality and allowing extra security features to be added depending on the use-case. In practice, many projects will need a message authentication code (MAC), padding to obfuscate secret length, and obfuscation of the ‘share id’ (x coordinate). Many implementations come with some of these features, but we want developers to be able to choose what best suits their project.

  • Actively maintained. While there are unlikely to be many fixes, it is important that the library is maintained and the maintainers are contactable should security issues arise.

  • Mature, reviewed, and adopted. Being adopted by other projects, and having had time for problems to emerge and be resolved, are good signs. Independent reviews are also important.

A standard for Shamir’s secret sharing

The only standardised protocol for implementing such secret sharing schemes that we are aware of is ‘Satoshi Labs Improvement Proposal 39’ (SLIP39), entitled ‘Shamir’s Secret-Sharing for Mnemonic Codes’. Although this is an open-source standard, it is written and maintained by blockchain company ‘Satoshi Labs’, who also produce the hardware cryptocurrency wallet, ‘Trezor’.

The scheme is not said to be specifically for use with keys for cryptocurrency, but simply ‘describes a standard and interoperable implementation of Shamir’s secret-sharing’. However, the proposal does refer several times to Bitcoin wallets and it is clear that addressing this use-case is a priority, which we feel is very different from the use-case we are proposing for Dark Crystal.

However, the specification does include several noteworthy security features, and there are some promising implementations based on it.

For example, most implementations we looked at take the secret to be the y-value of point x=0 on the polynomial. SLIP39 suggests constructing the polynomial such that x=254 is the secret and x=255 is the hash of the secret. This gives authentication - we have a way of knowing that the secret was successfully recovered. Another approach to this is to use an encrypted secret with a MAC.

SLIP39 also introduces a ‘two tier’ scheme whereby there are different kinds of custodians with different levels of trust assigned to them, as is described in the article ‘A New Approach to Social Key Recovery’. For example, there might be a ‘high trust’ group of family members and a ‘lower trust’ group of colleagues. As well as assigning different levels of trust, this also has the advantage that requiring a combination of shares from different groups, might reduce the likelihood of custodians colluding against the secret owner.

Although the ‘two tier’ system has clear advantages, our concern is that it further complicates what is already a new and complex concept for users, and also that it could optionally be implemented at a higher level. We are looking for a standard which is simple and unopinionated, allowing extra functionality to be added depending on the use-case.

For this reason, as well as the orientation towards cryptocurrency use-cases, we decided not to adopt and comply with SLIP39, but to take inspiration from the security features it offers when considering higher-level features of our protocol.

Implementations considered

Pure Java implementations considered:

As the others parts of the reference implementation of the Dark Crystal distributed key backup system will be written in Java, we considered some pure java implementations. We were unable to find one which met our requirements, mostly due to them not being actively maintained.

C implementations:

This would be our ideal choice, since it is possible to have ‘bindings’ written in popular high level languages, giving totally consistent behaviour across implementations, making the shares interoperable, and eliminating the need to monitor multiple libraries for security flaws or updates.

  • Daan Sprenkles' ‘sss’ is a C library with bindings already written for NodeJS, Go, Rust, and Webassembly. The documentation includes a table comparing the security features of the library with 8 other popular implementations. In particular, protection against attacks using side-channel analysis (such as timing) is included. Although in some cases protection against such attacks might not be necessary, this indicates the author’s rigorous approach to security. A ‘submodule’ containing a secure random number generator is also included. Members of our team have met the author personally and discussed security, and his talk at the Chaos Communications Congress (see references) about his library outlines the security considerations he has made. The library has been reviewed by other cryptographic engineers at Radboud University, Nijmegen. Project started in 2017, latest commit September 2019. https://github.com/dsprenkels/sss

  • B. Poettering’s ‘ssss’ is much older (created in 2005), and is widely adopted, packaged as a command line interface which is available in many linux distributions including debian. However it is (as far as we know) no longer maintained, and does not give an authentication method to make shares ‘tamper resistant’.

SLIP39 based:

  • ‘BlockchainCommons/sss’ is a fork of the C library ‘dsprenkles/sss’ (described below), modified to be SLIP39 compliant. It is no longer maintained due to being ‘superceded’ by the library below. https://github.com/BlockchainCommons/sss
  • ‘BlockchainCommons/BC-SLIP39’ is another C implementation of SLIP39. It is a complete re-write of Sprenkles' library. It is actively developed but we feel it is not mature enough - the initial commit was made in March 2020. https://github.com/BlockchainCommons/bc-slip39

Bindings to Java

There are two popular systems for writing bindings to native code in Java. Java Native Access (JNA) (https://github.com/java-native-access/jna) and Java Native Interface (JNI) (https://docs.oracle.com/javase/8/docs/technotes/guides/jni/).

Both systems work on android. But JNA bindings require less work, and are easier to maintain.

Conclusion

Daan Sprenkles ‘sss’ C library was chosen, for its security features, active maintenance, adoption, existing bindings to high level languages, and the author’s academic background in cryptographic engineering.

Although there exists an unfinished ‘work-in-progress’ project to create Java bindings to ‘sss’ for Android, it uses JNI. We have chosen to create our own using JNA as the procedure is much simpler.

References