Shamir's secret sharing

Unlike more commonly used cryptographic primitives, there is little standardisation for threshold-based secret sharing algorithms. Although there does exist a standardised scheme 'SLIP39', this protocol does not completely adhere to it. Rather, we use a C implementation 'sss' authored by Daan Sprenkles.

The reasoning behind this choice is explained in Choosing a threshold-based secret sharing algorithm.

'sss' has bindings for NodeJS, Go, Rust, and Webassembly, and includes a 'submodule' containing a secure random number generator.

Like many other secret sharing implementations, it uses a Lagrange interpolation on a 256 bit Galois field.

Authenticated encryption of secret

To ensure a uniformly random secret, as well as to enable integrity checking on recovery, the secret is not used directly in the secret sharing algorithm. Rather, a random key is generated, the secret is encrypted with this key using the authenticated symmetric encryption technique described above, and this key is taken to be the secret in the secret sharing algorithm. The ciphertext is concatonated to each share.

Secrets flow diagram

Share format: share-index||share||ciphertext

Although Daan Sprenkles' implementation includes this functionality, it restricts us to a 64 byte fixed length secret. In some cases, this might make the share size unnecessarily long (which could be an issue, for example if the shares are to be encoded as QR codes). In order to give more flexibility, to allow longer secrets such as RSA keys, as well as compact secrets, our standard allows a variable length secret, with optional padding for cases where it is important to obfuscate the secrets length.

Bit slicing

'sss' uses several techniques to protect against side channel attacks, including 'bit slicing'. These types of attacks rely on factors such as timing or even physical properties such as CPU temperature, to derive knowledge otherwise unavailable to an attacker. For example a custodian might be able to derive something about the secret by repeatedly trying a combination of their own share and several random shares, and observing the time the algorithm takes to run.

Bit slicing, involves taking the two dimensional array of shares and 'turning it on its side' when doing the interpolation computations, and then re-orienting the result appropriately afterwards. This makes it near impossible to determine knowledge about individual shares by observing physical factors relating to the computation.

Zero-padding of secret

Zero padding of secret

The technique of using authenticated encryption and using the key in the secret sharing algorithm allows us to have a variable length secret. So any kind of key or data can be 'sharded' regardless of its size. However, it must be noted that the length of the secret can be determined by the length of a given share, so it is revealed to the custodian. In some situations this may be undesirable, for example when the secret is a password, or a particular kind of key with a characteristic length. A solution to this is to add padding, in order to make the secret have a constant length. For example a secret of length 32 could be padded with an additional 32 bytes, all of which are zero, to pad to a standard length of 64 bytes.

Obfuscation of the x-coordinate

Random subset of shares

Shares are a collection of points on an array of parabolic curves, and contain both a 'share index', the x coordinate, which remains constant throughout the array, and the 'share value', an array of y coordinates. The share indexes are given a consecutive numbers for each share, so if we have 4 shares, they would have share indexes 1, 2, 3, and 4. This means that having a share gives some indication of the total number of shares. For example, if we have share number 3, we can infer that at least two other shares exist. To obfuscate this additional information, we generate a set of 255 shares and randomly select the desired amount of shares from this set. This means nothing can be inferred from knowing your own share value, other than that the number of shares is less than 255.

This is achieved using a 'Durstenfeld schuffle' algorithm, to shuffle the array of shares, but instead of completely shuffling the array, we take only the desired number of elements.

Including a label with the secret

This is an optional feature to indicate the intended purpose of the secret, meaning that it is still useful if recovered 'out of context'. This will generally include a 'label' property which will be a human readable description, including, for example, the name of the application it was created with or the purpose. The label may also include application-specific data.

This feature is important because, as Pamela Morgan makes clear in her book 'Crypto-asset inheritance planning', recovering a key is only half the story. For it be useful, we need to know what to do with it. In some situations it makes less sense to include a descriptive label with the secret because the context in which the shares are stored gives us information about their intended use. For example, if they are shares of an email encryption key used in an email client, the fact that they are stored with the other files relating to this application is probably enough context to determine what they are for. However, if the shares are to be printed on paper as mnemonics or QR codes, it is less obvious.

The amount of information included in a label depends on how critical it is that share size is kept small, which varies with different applications.

If this feature is adopted, the secret should be encoded as a protocol buffer with two properties, the secret itself, stored in binary form, and the label stored as a string. Protocol buffers were chosen as the serialisation standard because it is widely adopted and implemented in many languages.

The protocol buffer schema for this message looks like this:

syntax = "proto2";

message Secret {
  required bytes secret = 1;
  optional string label = 2;
}