Use-Case Scenarios for Threshold Schemes

Introduction

Threshold schemes are useful for implementing multiple new features that are not possible through other means. However, when considering the suitability of sharding for a given set of circumstances that a user might encounter, different implementations are more or less appropriate to satisfy a given use-case’s differing needs.

The primary use of a threshold scheme is the ability it gives to a user to recover their key should they lose it, or lose access to it. However, loss of a key can occur under a variety of circumstances. If a key is lost but not compromised, recovery of the key is sufficient - to regain access to the data and continue using encryption. But if the key is lost and compromised, then it may be desirable to recover the key to regain access to data, but also necessary to issue a new key in such a way that (in the case of asymmetric encryption) it can be verified as genuine. If the key is compromised but not lost, the secret-owner can themselves revoke and reissue a new key.

While Dark Crystal has not yet been implemented for the purpose of affording such a feature, it is also possible to use threshold signature schemes in the case that the secret-owner is incapacitated, to afford the custodians of their shards the ability to revoke the secret-owner’s key in their absence, ensuring that no further data is compromised.

The purpose of this report is to offer app developers some idea of the features that threshold schemes can afford the users of encryption tools. The following example use-case scenarios demonstrate applications of threshold schemes focussed around key/identity management. Other use-cases scenarios exist, which we have as yet not fully explored. These are briefly described at the end of the report.

Usage Scenarios

Key Loss Scenario

Considerable user-research shows that fears relating to key-loss are the primary reason that people choose not to use encryption for their files and communications - as losing a key means losing access to their data. A user can lose (access to) their encryption key in a variety of ways. Perhaps their harddrive failed, and they had not been making regular manual backups. Or maybe they needed to delete an encrypted communications app that they use in an emergency, perhaps facing a likely imminent arrest. For our purposes here, this key loss scenario is one in which there is no known risk of key compromise. In this case, a lost phone or a phone captured during arrest do not count as lost but as compromised keys.

Anna, an internet freedom activist, needs to cross the border out of a country ruled by an authoritarian regime. She needs to cross with a clean phone, that does not reveal the communications app that she uses, nor data relating to the contacts she uses it to communicate with. However, she does not want to lose this data, and wishes to recover it easily once she arrives at her destination.

Luckily, Anna’s preferred communication app has a threshold scheme integrated for account backup. While preparing to leave, she sets it up.

Before she begins, she checks her app-specific contact list and considers which contacts are most suitable for this particular situation. As she knows approximately when she will arrive and need to recover her account, she sends a message to her preferred custodians to check that they will be available during that time, and that they are willing to be custodians for this purpose.
Having secured consent from her preferred custodians, she opens the app, goes to the settings menu, and selects the account backup option.
The app opens a new screen containing the list of the Anna’s contacts. Anna is asked to select a number of trusted contacts with whom to backup her account.
As the app she is using requires in-person return of shards, she has chosen trusted contacts who she can meet up with where she will arrive. Should the app allow for remote return of shards, she might still decide to choose custodians that she knows are currently located in a legal jurisdiction over which the repressive state she is leaving has no control.
As it is a very short-term back-up that she is making, she decides to choose a relatively small number of custodians and a relatively small quorum such that account recovery upon arrival will be swift. She choose 5 custodians.
The next screen asks her to choose the quorum of custodians from whom she will need to recover shards in order to recover her account. The user-interface offers her a visual representation of the security of her choice. Again, because it is a very short-term backup in this case, she chooses 3.
As this app has implemented Dark Crystal to provide a straightforward account backup feature, with the shards able to be recovered by the secret-owner only, there is in this case no need to add further information to the backup. The app therefore does not offer her the opportunity to add additional information in the form of a ‘label’ to be sharded together with the secret.
She clicks the ‘shard secret’ button. Behind the scenes, the app grabs her contact list data and combines it with her account key(s), running the secret sharing algorithm on them to shard.
The shards are automatically sent to the selected contacts.
Anna then deletes the app entirely from her phone.
She then embarks on her travels, crossing the border and arriving in her destination country.
Once settled, she follows the usual installation process to reinstall the app on her phone.
At the startup screen, she is offered the option to create a new account, or restore an old account from backup, which takes her into ‘recovery mode’.
She contacts her custodians out-of-band. Three of the five are available to meet on the same day.
At each meeting, the custodian opens their app-specific chat log with Anna. They go into the chat-options menu and open the ‘help recover account’ option. This gives them a QR code, which Anna can scan.
Once Anna has met with her quorum of custodians, the app recombines the shards to recover her account. At this point she is asked to enter her password, or enter a new password if preferred.
On opening her account, her original identity and contact list are restored.

An alternative implementation of the feature could allow for Anna to receive the shards from her custodians without having to meet them in person to do so. In this case:

Upon arrival at her destination, she follows the usual installation process to reinstall the app on her phone.
At the startup screen, she is offered the option to create a new account, or restore an old account from backup, which takes her into ‘recovery mode’.
The recovery mode screen offers her the option to recover shards in person or to receive them remotely. She selects to receive them remotely. The app then presents her with a new account identifier.
She contacts her custodians out-of-band and sends them her new account identifier.
It is recommended that a phone call or some exchange of information takes place that allows custodians to verify that the identity they have received is really from Anna (see our Threat Model Report for further exploration of this).
The custodians then open their app-specific chat log with Anna. They go into the chat-options menu and open the ‘help recover account’ option.
They select the option to ‘forward’ their shard to a new identity, and select Anna’s temporary identity to send it to.
Once Anna has received shards from a quorum of her custodians, the app recombines the shards to recover the account. At this point she is asked to enter her password, or enter a new password if preferred.
On opening her account, her original identity and contact list are restored. Her temporary identity is deleted and becomes obsolete.

In the account recovery scenario, it is recommended that in order to avoid confusion between the new ‘temporary’ identity, and the original one being restored, it may make sense at the user-interface level to restrict what a peer is able to do with the application whilst they are in the process of retrieving shards from custodians. For example, making clear that they are currently in ‘recovery mode’ and are not able to use the normal features of the app until either their original identity is restored, or they create a ‘normal’ new account.

Key Capture Scenario

In the case that a key or identity might have been compromised, it may be appropriate to abandon the old identity and create a new one. In this case, a recovered key can at least be used to recover the data encrypted to it.

Dark Crystal can be implemented to provide a way of establishing a new key, so that an identity can be seen to persist to it. It works by each peer selecting their custodians, constituting a ‘support group’ who are empowered to make assertions on their behalf. The support group can announce a new key when the old one is assumed to be compromised, and the client application can resolve these announcements to get the current key for a particular identity. This is done in such a way that the identities of the members of the support group are kept private, and that there is a degree of tolerance to particular group members being unavailable or uncooperative. This implementation would use group threshold signatures with a cryptographic scheme such as Boneh-Lynn-Shacham. Threshold signatures could be used for identifier or account re-issuance as follows:

A new peer-to-peer social networking app is gaining popularity in a repressive state. Users appreciate that there is no centralised server that can be censored, which means that they can continue to communicate, and would be able to do so even under conditions of internet blackout. Alice is a pro-democracy activist who uses the new app. She wants to ensure that her identity cannot be impersonated, so that her contacts can be sure that they are speaking to the real her, even if she needs to abandon her identity and install a new account.

Alice opens the Dark Crystal feature in the social networking app. She selects the ‘authenticate future identities’ item from the options provided.
She is asked to select a number of trusted contacts from her contact list. She chooses to select 7.
She is asked to select a quorum of these contacts who will be required to verify a new identity, should she need to establish one. The user-interface offers her a visual representation of how reasonable her choice is. Alice chooses 4.
The app creates an aggregated public key that will serve to verify the authority of the quorum, empowering the group to make assertions on her behalf. The app publishes a signed message announcing this key.
Once this key is published, the client application of any of her contacts, in seeking to validate messages from Alice, will resolve her current public key by looking for messages published by her trusted group.
In the event that Alice loses access to her identity or account, or should the account be compromised, she reinstalls the app, generating a new keypair.
She sends her trusted custodians a signed, timestamped message containing her new public key, and contacts them out of band to confirm it was her.
m of n group members each sign the message and their signatures are aggregated to produce and publish a single, signed message asserting Alice’s new public key. This also serves to revoke the old one.
The client applications of her contacts, in seeking to validate messages from Alice, will find the message signed with the aggregated key of her trusted group, and recognise that her old key has been revoked.
Alice publishes another signed message with her new key and confirming the public key of her trusted group. This allows her contacts to discover her new key and verify that any messages she sends from her new identity are legitimately from her.
In the case that group members change at any point during the process, the new group’s aggregate public key announcement must be signed by both Alice and a quorum of the old group.

A major advantage of this scheme is that it addresses the case that a key has been compromised. Furthermore, anonymity of group members is maintained. Nobody but Alice can see which group members created the signature or who the group members are. Which makes it difficult for them to be targeted by someone who wanted to impersonate Alice.

While this feature would be available to all users of such an app, it is most useful for higher-risk users who are likely to be targetted by impersonation attacks in an attempt to gather information from their social contacts.

Inheritance

The inheritance scenario is valuable for situations in which an individual is in possession of sensitive data and therefore at risk. If they disappear, their custodians can collaborate to access that data and execute instructions in relation to it in the absence of the owner.

Carol is a journalist investigating corruption in a near-east country under a repressive regime. She has recently received some sensitive documents from an anonymous source, and is concerned that this makes her a target. If she is captured, this information may never come to light. She is careful with her handling of the documents, avoiding that surveillance would reveal that they exist, or that others who discover them could reveal the information in an inappropriate or untimely manner, damaging the investigation. She therefore stores the files on a remote server, encrypted with her private key, which she accesses through Tor.

In this case, Carol chooses to shard her key using a secure communications app that has implemented Dark Crystal agnostically, allowing for any data of the user’s choice to be sharded.
Carol opens the app, opens the options menu and chooses the ‘share a secret’ option from the list.
The app asks Carol to enter the secret which she wishes to share. She does this by clicking on the ‘add from device’ option. This allows her to access her device’s file system, where she locates her private key and clicks ‘add’.
The next screen asks Carol if she would like to attach a note or label to her secret. She decides to provide brief instructions on where her custodians can find the sensitive files, and what they should do with them. She clicks ‘done’.
Carol is then asked to select her trusted custodians from her list of contacts. She chooses 6 trusted contacts. The custodians she chooses are all contacts from her professional network - a combination of lawyers, reporters and campaigners - and are all located abroad, outside of the jurisdiction she is residing within and reporting on. This further secures the data from compromise.
When asked to select a quorum of these who will be required to recombine the secret, she chooses 4. The user interface provides visual guidance relating to the security provided by the number she chooses for each.
The app appends the label to the secret and executes the sharding algorithm. It then offers Carol the option to add additional information to the shards before encrypting them with the custodian’s public keys.
In this specific case, as she needs the custodians to know who one another are so that they can recombine the secret in her absence, Carol chooses to append the custodian’s identities to the shards. This means that the identities are encrypted in transit and at rest on the custodians' devices, but that the custodians can discover one another once they decrypt their shards should the need arise.
Alternately, if she decides that despite their locations, she would prefer not to encrypt the shards together with this list, she can simply contact the custodians out of band to let them know who one another are, ensuring that this information is never stored together with the shards.
She then clicks ‘send shards’ and the app sends the shards to her custodians.
As she proceeds with her work, Carol continues to update the files encrypted with her key. Some months later, while still investigating the case, she disappears on her way to work one morning, never arriving at the office. Realising this, her colleague sends a message to their professional network and begins publicising her disappearance through media channels.
Eventually one of her shardholders decides that it is an appropriate time to recombine the shards, find out what Carol was working on and execute her instructions.
He contacts the other custodians to let them know. The other custodians independently confirm that she has in fact disappeared, and that the initiator is who he claims to be. Once they are confident that the situation is authentic, they collectively choose one of them to whom they will all forward their shards.
On receiving the shards, the recipient is able to recombine them, revealing both the encryption key and the instructions that Carol has provided. They are then able to execute her wishes in relation to the data she was protecting.

It should be noted that in this scenario, as indicated above, it may be desirable to technically implement a process to ensure that the custodian who initiates the recombining of the shards is not the one who gains possession of the secret. This provides an extra layer of protection in the case that one of the custodians is or becomes malicious. Further exploration of such threats and mitigations are explored in the Threat Model Report.

Application Architectures

Peer-to-peer application using a distributed ledger or append-only log

The architecture of peer-to-peer applications that are based on append-only logs is such that many peers in a given network will have copies of other peers' data on their local harddrives. This means that the data itself, belonging to any given peer, is at almost no risk of getting ‘lost’. However, because of this architectural decision, an individual peer’s data is encrypted - and loss of their key means losing access to their entire identity, history and contact list. Without any central storage location it is impossible to automatically backup or re-issue encryption keys in the case that, for example, a peer forgets their password or otherwise loses their key.

Dark Crystal can be integrated into such an app to allow users to back-up their identity by sharding their key and distributing it among a number of their peers.

When a peer loses their identity, they can freshly install the app in ‘recovery mode’, giving them a new (temporary) identity. With this they can find their peers in the usual way in which discovery occurs within the app, and contact their custodians to recombine their shards and recover their secret. Successful recombination of the secret in recovery mode can reinstall the original identity and allow the secret-owner to regain access to their account.

One important point to bear in mind when integrating a Dark Crystal feature into applications based on append-only logs is that distributed shards cannot be deleted from the log, so it may be wise in some cases to consider using ephemeral keys for the initial distribution of shards, to ensure that should a custodian’s identity become compromised in the future, the shards that they hold will remain secure.

Peer-to-peer application without a distributed ledger or append-only log

When a peer-to-peer application does not use an append-only log, automating backups becomes a serious issue. There is no central server, and no distributed log, on which to store a user’s data. In this case, sharding can bring a vital feature to users of such protocols that they would otherwise be denied.

In this case, a selected amount of app data could be appended to the account key, and distributed with the shards. This allows users to back-up their account, for example including their contact list and a certain quantity (in bytes) of messages, allowing these to be recovered should they lose their device or need to delete the app temporarily. Of course, the same question of loss vs compromise applies to this as with any other feature, and implementations may want to account for this in the UI workflow.

It is this feature scenario that Dark Crystal have collaborated on with Briar, to implement into the Briar secure communications app. More information about the workflow and UI decisions that were made are available in the series of blog posts charting the development process, available here: https://darkcrystal.pw/post/

Another feature which threshold signatures offer to peer-to-peer applications that do not use append-only logs is that of remote deletion. Some applications that use a centralised architecture have begun to implement remote-deletion as a feature in recent years, but for peer-to-peer applications this is much more tricky.

In this case, the app could be set up to recognise a unique ‘deletion trigger’ message that can only be sent once a threshold (quorum) of custodians combine their shards to recover a trigger key. This allows for data to be deleted in the event that the owner is not able to execute the action on their own device, offering a measure of organisational security without the need to rely on centralised systems.

Centralised server application

In the case of a centralised service, there is no need to shard selected data. It is important, however, that the data stored on the server is encrypted, and that the key is stored client-side and never revealed to the server itself.

With email, as the storage provided is centralised per provider, but federated between providers, as long as the secret-owner deletes their copies of the ‘sent’ shard messages from their account, this also alleviates the single point of failure scenario that entirely centralised services are vulnerable to.

In the case of email, key-management is critical because poor key management will lead to loss of access to message data, with the potential for significant frustration or damage. It is for this reason that many of those interviewed for the needfinding reports, which informed the ideation phase of this project, chose not to use encryption at all, considering the risk of losing their data too high. Therefore, even when using centralised services, where access is unique to a given individual and cannot be re-issued by a third-party, automated key sharding and recovery become valuable mechanisms for enabling users to securely and confidently use encryption.

Other features that Dark Crystal enables on centralised services include that data stored in a single location and belonging to a single individual can be decrypted and re-encrypted with a different key in the absence of the secret-owner, should the need arise. Such data could also be remotely deleted by trusted contacts if necessary. We have not yet explored the workflow for such use-cases but are excited at the prospect of doing so in the future.

Multi-use sharding feature

In all of these use-cases, the Dark Crystal feature, once implemented within an existing application, can be used either as a fully integrated tool that allows a user to back-up only the data and keys associated with the app itself, or potentially also as a general sharding tool that allows users to enter multiple different secrets to be sharded. Such an implementation would obviously require more thought relating to the user-interface workflow, and the option to back-up unrelated secrets is perhaps most relevant for relatively small amounts of data. In the case that the data should be a key, then for users who understand at least the basics of encryption - enough to know where to find a given key on their filesystem, or to be guided in doing so, in order to upload it into the sharding feature of the unrelated app - such a tool could prove invaluable.