Worked Example of integrating social recovery into an application

As an example, we will imagine making a social backup mechanism for an encrypted email client.

The objective is to secure the cryptographic keypair (or multiple keypairs) used to sign and encrypt email messages. This brings a great usability benefit, as it means that if the peer’s device is lost or broken, they have a means of recovering the key and do not loose access to their encrypted messages.

The idea is that rather than relying on a trusted service provider, the peer chooses a small group of trusted contacts who collectively store a backup of the key.

Following key loss because of a lost device, forgotten password, or corrupted disk, the secret-owner would reinstall the email client, associate a new, temporary keypair with their email address, and request the custodians to ‘forward’ their shards using their new public key. Once sufficient shards are received and the original key is recovered, the secret-owner can switch back to their restored keypair.

The key backup mechanism would be integrated into the email client, and mean that an option to backup keys would be present in the user interface. Keys would never need to be manually copied and pasted, or displayed to the user, since the email client knows where to find them.

Dark Crystal is ‘transport agnostic’, so the messages it uses to manage these backups can be sent by the application’s existing transport mechanism. So in the case of an email client, lets say the transport mechanism is email messages. This is good for application developers as it minimises the amount of extra dependencies needed.

However this also has disadvantages. Although email messages can be sent using client-side encryption, this does not provide forward-secrecy out of the box. Email providers routinely log data, and if a custodians key is later compromised these logs could be used to retrieve the shard. Extra steps will need to be taken to ensure forward secrecy, by introducing ephemeral keys for shard transmission. This is possible with email, but it should be noted that this key-backup technique is best suited to peer-to-peer protocols which have some sort of handshaking built in.

The good news is, the steps in the examples below are already implemented in the dark-crystal-key-backup-java package. This packages gives a high level API, which is easy to use but somewhat opinionated. It might anyway be useful to look at these examples to see what is going on, and in many cases you might want to do things a bit differently because of the particular needs of your application.

Here is the simplest possible example of how we might use the secret-sharing-wrapper module to share and combine a GPG key:

emailClient is an instance of our theoretical email client.

import org.magmacollective.darkcrystal.secretsharingwrapper.SecretSharingWrapper;
import java.util.List;

public class GpgKeyBackup {

  public static void main () {
    // The secret is our private key
    byte[] secret = emailClient.getPrivateGPGKey();
    
    // A label describing the type of key, and with which email address it is associated
    String label = "GPG ed25519 key for " + emailClient.getEmailAddress();
    
    // Encode this into a single message
    byte[] secretWithLabel = new SecretSharingWrapper.SecretWithLabel(secret, label).encode()
    
    // Create shares - these are then sent to our trusted contacts
    // Here the chosen number of shares is 5 and the threshold is 3
    List<byte[]> shares = SecretSharingWrapper.share(secretWithLabel, 5, 3);

    // Remove two shares to demonstrate that we only need the threshold amount (3 shares):
    shares.remove(0);
    shares.remove(0);

    // Recombine the shares:
    SecretSharingWrapper.SecretWithLabel reconstructedSecretWithLabel = SecretSharingWrapper.decodeSecretWithLabel(SecretSharingWrapper.combine(shares));

    System.out.println("Label: " + reconstructedSecretWithLabel.getLabel());
    System.out.println("Secret: " + new String(reconstructedSecretWithLabel.getSecret()));
  }
}

• SecretSharingWrapper.share in API documentation
• SecretSharingWrapper.combine in API documentation
• SecretSharingWrapper.share in source code
• SecretSharingWrapper.combine in source code

Choosing a threshold value

For the threshold value, we can take a value from the peer. In the UI example above, a slider is used and a pie chart to visually represent the proportion of shards needed to recover the secret. Colours or warnings can be used to indicate how appropriate the chosen value is.

Alternatively, a set proportion can be used, to choose an appropriate value automatically and not overwhelm the peer with choices. Sometimes it is better to sacrifice control in favour of usability.

If doing this, we recommend using a threshold of 75% of the number of shards, truncating integers (rounding down):

int threshold = (int)(numberShards * 0.75f);

So here we would have a threshold 2 of 3, 3 of 4, 3 of 5, 4 of 6, etc.

It is important to be able to validate the integrity of the shares later. There are various methods of doing this, but we recommend using cryptographic signatures. This works particularly well with applications where there is already established key for signing other kinds of messages in the application. So in this case we would use our GPG keys to sign shards. This is helpful because the public key is probably already available elsewhere - either published publicly to a key-server or held by contacts other than the custodians. This is good as it means we are not reliant on the custodians themselves to find out what the original public key was, meaning a malicious custodian cannot fool us by presenting a different public key and signature to the one they were given originally.

‘Secret sharing wrapper’ has methods signAndShare and VerifiyAndCombine, which allow adding signatures using EdDSA:

import org.magmacollective.darkcrystal.secretsharingwrapper.SecretSharingWrapper;
import java.util.List;

public class GpgKeyBackup {

  public static void main () {
    // The secret is our private key
    byte[] secret = emailClient.getPrivateGPGKey();
    
    // A label describing the type of key, and with which email address it is associated
    String label = "GPG ed25519 key for " + emailClient.getEmailAddress();
    
    // Encode this into a single message
    byte[] secretWithLabel = new SecretSharingWrapper.SecretWithLabel(secret, label).encode()
    
    // Create and sign shares - these are then sent to our trusted contacts
    // Here the chosen number of shares is 5 and the threshold is 3
    List<byte[]> shares = SecretSharingWrapper.signAndShare(secretWithLabel, 5, 3, emailClient.getEdDSAKeyPair.getPrivateKey());

    // Remove two shares to demonstrate that we only need the threshold amount (3 shares):
    shares.remove(0);
    shares.remove(0);

    // Recombine the shares:
    byte[] recombinedSecret;
    try {
      recombinedSecret = SecretSharingWrapper.VerifyAndCombine(shares, emailClient.getEdDSAKeyPair.getPublicKey());
    } catch (Exception e) {
      // Prints 'unable to verify share' if one or more shares could not be validated
      System.out.println(e.getMessage());
      System.exit(1);
    }
    
    // Unpack secret and label
    SecretSharingWrapper.SecretWithLabel reconstructedSecretWithLabel = SecretSharingWrapper.decodeSecretWithLabel(SecretSharingWrapper.combine(shares));

    System.out.println("Label: " + reconstructedSecretWithLabel.getLabel());
    System.out.println("Secret: " + new String(reconstructedSecretWithLabel.getSecret()));
  }
}

• SecretSharingWrapper.shareAndSign in API documentation
• SecretSharingWrapper.shareAndSign in source code
• SecretSharingWrapper.verifyAndCombine in API documentation
• SecretSharingWrapper.verifyAndCombine in source code

Depending on how sensitive the data your application handles is, or what kinds of information your target user group might use, it may or may not make sense to include a mandatory consent process for being a custodian. That is, we explicitly ask them if they want to hold a shard.

Of course, even if you decide not to implement an explicit consent process, the secret-owner is anyway able to send a message before making a backup to ask if it is ok. Furthermore, custodians should always be given the option to ‘opt out’ by deleting their share. The secret owner should always be notified that the share has been deleted.

There are two possible ways consent can be implemented:

‘Weak’ consent

The custodian is sent the shard right away, and asked it they would like to opt-out. Inaction on the part of the custodian assumes consent is given. This is much simpler, both in terms or building a user-interface, and it only requires a single pass should they accept.

‘Strong’ consent

The custodian must actively respond with acceptance before they receive a shard. Inaction on the part of the custodian assumes no consent is given. This better respects the wishes of the custodian, but it requires three passes should they accept.

We want to have a local record that a backup has taken place, in order to be able to display this information in the user-interface. We call this message the ‘root’ message, and it also serves as a unique identifier for the secret we have backed up. These is needed so that if we have backed up more that one secret, we know which shards belong together.

   final int thresholdShards = 3;
   final int numberShards = 5;
   // If the application backs up different kinds of secret, the name can be used in the UI
   final String name = "GPG Key backup";

   // Generate a random tag which is included in the root message
   final byte[] tag = KeyBackupCrypto.generateSymmetricKey();

   // Create the root message 
   final byte[] rootMessage = new BuildMessage().buildRoot(thresholdShards, numberShards, name, tag);
   // This message can then be stored locally in a database or file   

   // Get its id, used to identify the secret (included in each shard message)
   final byte[] rootId = KeyBackupCrypto.blake2b(rootMessage);

• Message builders and decoders in source code
• Message builders in API documentation
• Message decoders in API documentation
• Protocol buffers schema for a ‘root’ message

Example user interface showing local record of backup

Dark Crystal has five types of messages. We just saw how to create a ‘root’ message which serves as our local record of a backup being made.

When we send shards to the custodians, they are sent in shard messages which contain the ‘rootId’.

  final byte[] shardMessage new BuildMessage().buildShard(rootId, custodiansPublicKey, shardData)

As well as the properties given in the builder method, all dark crystal messages are given a version number (to allow backward compatibility when the protocol is revised) and a timestamp (useful for the user interface).

• Protocol buffers schema for a ‘shard’ message

Lets put together the previous steps to make a share method, which takes a list of custodian IDs (public keys) and a threshold value, and returns a list of shard messages.

import org.magmacollective.darkcrystal.secretsharingwrapper.SecretSharingWrapper;
import org.magmacollective.darkcrystal.keybackup.messageschemas.Publish.BuildMessage;
import org.magmacollective.darkcrystal.keybackup.crypto.KeyBackupCrypto;
import java.util.List;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class GpgKeyBackup {

  public static List<byte[]> share (int thresholdShards, List<byte[]> custodians) {
    int numberShards = custodians.size()    

    // The secret is our private key
    byte[] secret = emailClient.getPrivateGPGKey();
    
    // A label describing the type of key, and with which email address it is associated
    String label = "GPG ed25519 key for " + emailClient.getEmailAddress();
    
    // Encode this into a single message
    byte[] secretWithLabel = new SecretSharingWrapper.SecretWithLabel(secret, label).encode();
    
    // Create and sign shares - these are then sent to our trusted contacts
    // Here the chosen number of shares is 5 and the threshold is 3
    List<byte[]> shares = SecretSharingWrapper.signAndShare(secretWithLabel, thresholdShard, numberShards,  emailClient.getEdDSAKeyPair.getPrivateKey());

    // If the application backs up different kinds of secret, the name can be used in the UI
    final String name = "GPG Key backup";

    // Generate a random tag which is included in the root message
    final byte[] tag = KeyBackupCrypto.generateSymmetricKey();

    // Create the root message 
    final byte[] rootMessage = new BuildMessage().buildRoot(thresholdShards, numberShards, name, tag);
    // This message should then be stored locally in a database or file   

    // Get its id, used to identify the secret (included in each shard message)
    final byte[] rootId = KeyBackupCrypto.blake2b(rootMessage);

    // Create a set of shards (sets are good for shards as duplicates are never stored)
    Set<byte[]> shards = new HashSet<>(SecretSharingWrapper.shareAndSign(secret, numberShards, thresholdShards, keyBackup.signingKeyPair.getPrivate()));

    // Build one shard message for each custodian
    List<byte[]> shardMessages = new ArrayList<>();
    Iterator<byte[]> shardIterator = shards.iterator();
    for (int i = 0; i < numberShards; i++) {
      shardMessages.add(new BuildMessage().buildShard(rootId, custodians.get(i), shardIterator.next()));
    }
    return shardMessages;
  }
}

Supposing the peer has now lost their key, perhaps they forgot the password, or perhaps they formatted their computer to install a new operating system and forgot to back it up.

They install a fresh copy of our encrypted email client, and choose an option to recover their key. In order to regain access to their email account itself, should they have difficulties, they would contact their email provider. So here we are in the fortunate position that the custodians have some evidence as to the identity of the secret-owner, since they would be making the request from their normal email address. However, this is far from secure and it is a good idea for the user interface to encourage some kind of out of band verification of the identity of the secret owner.

Our email client will generate a temporary keypair used for the recovery process, and publish a request message to each custodian.

    byte[] request = new BuildMessage().buildRequestBySecretOwner(recipient, secretOwnerPk);

• Protocol buffers schema for a ‘request’ message

The UI would then prompt the custodian to confirm the identity of the secret owner by means of out-of-band contact. We recommended doing this by means of a voice call, where 3 or 4 dictionary words which are derived from the temporary public key, are read out by the secret owner and entered by the custodian.

The confirm-key package provides a way of doing this:

import org.magmacollective.darkcrystal.confirmkey.English;
import org.magmacollective.darkcrystal.confirmkey.getWords;

...

// Derive 3 words from a key:
System.out.println ConfirmKey.getWords(English.INSTANCE, 3, "This is the key".getBytes());
// output: blossom addict eye

The idea is that 'blossom addict eye' is much easier to confirm with someone verbally than something like "Ntlx01+YGX9qDdJIayhYWheGG5wegnDTXj7yJCZKG80=". Of course, not all data is confirmed with only three words, but its enough to make a collision unlikely without being a tedious task for the peers.

Confirmation words - User interface mockup example

Confirming the identity of the secret owner - from the secret owner’s point of view.

Confirming the identity of the secret owner - from the custodian’s point of view.

Once the custodian has confirmed the identity of the secret owner, the shard is ‘forwarded’ to them.

Dark Crystal has two message types for returning shards, ‘reply’ and ‘forward’. The difference is that ‘reply’ is used when the shard is sent back to the same identity that authored it. Which is only useful in cases where the secret was not the thing securing that identity itself. A reply message must always follow a ‘request’ message from the secret-owner. ‘Forward’ is used when sending the shard to another identity, so in this case to the temporary keypair set up by the secret owner.

The Publish.BuildMessage class in org.magmacollective.darkcrystal.keybackup.messageschemas provides a method to encode a ‘forward’ message together with a timestamp and version number:

import org.magmacollective.darkcrystal.keybackup.messageschemas.Publish.BuildMessage;

...

// If this is in response to a 'request' message, the 'branch' reference is included:
final byte[] forwardMessage = new BuildMessage().buildForward(recipientPublicKey, rootId, shardData, branch);

// Otherwise no branch reference is included: 
final byte[] forwardMessage = new BuildMessage().buildForward(recipientPublicKey, rootId, shardData);

The ‘branch’ property is optional and is generally the hash of the ‘request’ message being responded to, if there was one, for example:

import org.magmacollective.darkcrystal.keybackup.crypto.KeyBackupCrypto;

...

final byte[] branch = KeyBackupCrypto.blake2b(requestMessage);

• Message builders and decoders in source code
• Protocol buffers schema for a ‘forward’ message
• Protocol buffers schema for a ‘reply’ message

On receiving ‘forward’ messages we extract the shard data and add it to our set of shards associated with that particular ‘root id’. We recommend using a set to avoid storing duplicate shards.

The secret owner is able to verify that the shards are identical to what they originally sent out using their original public key. This protects against a malicious custodian or ‘person in the middle’ modifying a share. But it requires us to know our original public key.

  private boolean receiveForward(Forward forward) throws Exception {
    if (!forward.isInitialized()) throw new Exception("Forward message badly formed");

    // Check which secret this forward is for
    byte[] rootId = forward.getRoot().toByteArray();
    OwnSecret ownSecret = getSecretByRootId(rootId);
    
    // Get the shard data
    byte[] shard = forward.getShard().toByteArray();

    // Check branch reference to 'close' request
    byte[] branch = forward.getBranch().toByteArray();
    ownSecret.closeRequest(branch);

    // Verify shard:
    if (!edDSA.verifyMessage(signedShare, originalPublicKey))
        throw new GeneralSecurityException("Unable to verify shard");
        
    // Add to our set of shards
    return ownSecret.addShard(shard);
  }

Upon adding a shard with the method OwnSecret.addShard, we check if we are able to recombine, and return true if we can.

  public boolean addShard(byte[] shard) {

    // Add the shard to our set of shards
    shards.add(shard);

    if ((thresholdShards != null) && (shards.size() < thresholdShards)) return false;
    try {
      this.combine();
    } catch (Exception err) {
      return false;
    }
    return true;
  }

If we can, the original account is restored, and the temporary keypair for ‘recovery mode’ is discarded.