Key Refresh and Recovery

Recall that in a $t$-of-$n$ threshold-signature-scheme the secret key is split between $n$ participants, thereby assuring both security and availability.

• Security: An attacker has to gain access to at least $t$ shares in order to sign arbitrary messages.
• Availability: The loss of up to $n-t$ shares, for any reason, can be recovered. Note that once recovery is complete, additional share-losses can be once again recovered.

To get a better sense of this, let's start by considering two typical use cases.

Example

In a $2$-of-$3$ threshold signature scheme:

• An attacker needs to gain access to $2$ shares in order to sign arbitrary messages. Therefore, gaining access to a single device is not sufficient to successfully carry out an attack.
• In case one share is lost, it can be recovered.

Example

In a $2$-of-$2$ threshold signature scheme:

• An attacker needs to gain access to $2$ shares in order to sign arbitrary messages.
• A loss of a single share implies loss of the whole key.

Key Refresh and Proactive Security

You probably know the experience of websites asking you to change your password regularly. This is mainly because while centralized secrets (e.g. passwords) might remain hidden for a short period of time, after sufficiently long time, they could leak for a wide variety of reasons. The same claim holds when storing shares of a secret. As an attacker, gaining access to $t$ shares is definitely harder than gaining access to a single share, however given enough time an attacker might be able to slowly gain access to $t$ shares.

info

A common example is phishing or social engineering where a victim is being tricked into mistakenly sharing its password with an attacker. Such attacks have been proven to be highly effective if given enough time.

Proactive Security, Key Refresh or Proactive Secret Sharing is a security standard that ensures distributed keys are being updated on a regular basis so an attacker will have less time to gain access to a sufficient amount of shares in order to reconstruct the key. The shares are updated such that the old shares are deleted and new shares are created. The new shares match the same key as the old shares did. Note, old shares can't be used alongside new shares in order to reconstruct the key.

Example

In a $2$-of-$3$ setting, the participants, Alice, Bob and Charlie are holding key shares $s_A, s_B, s_C$ respectively. If an attacker gains access to a single share, say $s_A$, it cannot reconstruct the secret, since at least $2$ shares are required to do so. Assume, in the mean time, that a key refresh has taken place and now the parties hold new shares, $s'_A,s'_B,s'_C$ while disposing of their old shares. If the attacker now gains access to any share, say $s'_B$, the share can't be used with $s_A$ to reconstruct the secret key. Therefore, to pull off an attack successfully, the attacker must gain access to two shares within the time between key refershes. This improves the security of the secret being shared.

Key Refresh in Sodot MPC SDK

1. The Host App initiates a process, based on some regularly-occuring trigger, to initiate Key Refresh.
2. A connection is established between all devices to the Relay Server and the Key Refresh process is initiated.
3. Cryptographic material is exchanged between the devices, alongside proofs that the material is generated correctly.
4. A new share is constructed on each device based the information it received.
5. The share is validated to be a share of the same original key.
6. Once the new share is validated, it replaces the old share.

Key Recovery

In a $t$-of-$n$ threshold signature scheme, Key Recovery is a process where one of the $n$ participants has lost its key share and is trying to recover it using the information held by the rest of the $n-1$ participants.

tip

Keys do get lost sometimes - devices fall into a body of water, get left behind on a bus or simply malfunction. This is actually one the reasons to use TSS to distribute keys between devices. The good news are that Sodot MPC SDK supports Key Recovery.

In theory, since at least $t$ participants should collaborate in order to sign a message, then also at least $t$ participants should participate in the recovery. In Sodot MPC SDK, all participants take part in the recovery of a lost share. The recovering participant must identify itself to the other participants, so that the recovery process will begin. The participants then exchange cryptographic material so that a new share will be issued to the recovering participant. Note that the recovering participant does not hold any old cryptographic information which can be used to prove its identity, therefore, some other, non-cryptographic procedure has to be performed in order to identify it. We provide two examples of how this can be done below.

Key Recovery in Sodot MPC SDK

The following steps provide an overview of the key recovery process. For simplicity, we shall assume a $2$-of-$3$ setting between Alice,Bob and Charlie, where Charlie has lost his key share.

1. Charlie, who lost its key share, performs a fresh install of the Host App on a new device.
2. Charlie then uses the GUI to ask the Host App to start the recovery process.
3. The Host App then calls a specific method of the SDK that outputs an identifier, and then calls a recovery method that shall wait for Alice and Bob to join.
4. The identifier is then propagated to the devices of Alice and Bob (see tips below for examples).
5. On Alice's and Bob's devices, the Host App will call a recovery method of the SDK with the identifier of Charlie's new device.
6. Once all devices called the recovery method, they will use the Relay Server to communicate and output a new (2-of-3) share of the same secret for each device, including Charlie's new device.

Tip for a Client-Server Setting

In a Client-Server setting, where the Host App also hosts some server with which the client interacts to sign messages, the same mechanism (i.e TLS) that the Host App uses to interact with the server can be used during the recovery process to propogate the identifier between devices. This is done after authentication of the new device with the server.

Tip for a Peer-to-Peer signing Setting

In a peer-to-peer signing setting where a set of participants share a secret without the Host App server, the identifier can be propagated between devices using an off-band mechanism. For example, the new device can present a QR code of the identifier that can then be scanned by the other devices.