Shamir secret sharing, explained with a lost phone

Shamir secret sharing splits a secret, such as a recovery key, into several shares so that any chosen number of them (the threshold) can rebuild it, while fewer reveal nothing about it. It is a good fit for the problem of a lost phone: the key that rebuilds your data can be held by the people and devices you trust, without any single one of them being able to open it alone.

This post explains the idea with a lost phone, how Havenfold's design uses it, and the honest limits. One thing first: Havenfold's vault code exists and is tested, but it will not be released before an independent security audit. Havenfold is pre-alpha; do not use it for real data.

The problem: the phone was the only key

When end-to-end encryption is done properly, the keys live on your devices, not on a company's server. That's the point. It also means that if your only phone is lost, the keys that open your history may be lost with it. There's no "forgot password" button, because nobody else holds the key.

The usual workarounds each have a weakness:

• Write the key on paper. Whoever finds the paper has the key.
• Give a copy to one trusted person. That person, or anyone who steals from them, has the key.
• Keep a copy on a home server. Whoever steals the server has the key.

What you want is something in between: the key can be rebuilt, but only when enough trusted parties agree.

The idea in one paragraph

In 1979 Adi Shamir published "How to share a secret". The idea rests on a simple fact: a line needs two points to be fixed, a parabola three, and in general a polynomial of degree t − 1 needs t points. Put the secret in the polynomial, hand each holder one point on it, and any t holders can rebuild the polynomial, and with it the secret, while t − 1 holders learn nothing about it. In practice the arithmetic is done in a finite field, often GF(256), byte by byte.

A lost phone, step by step

Imagine a family where a parent's backup key is split so that any two of three holders can rebuild it: the other parent's phone, an adult child's phone, and a paper share kept outside the home with someone trusted.

• The parent's phone is lost. The new phone joins the family through the in-person ceremony.
• The new phone asks the holders for shares. Each person sees a request on their phone and approves it with biometrics.
• With two shares, the new phone rebuilds the backup key, opens the backup, and restores what was lost.
• Right after, the secret is rotated: a new key is generated and new shares are handed out, so old shares become useless.

Nobody else could have done this alone: one holder with one share learns nothing.

How Havenfold's design uses it

Havenfold's vault is specified in RFC-0004. A few of its choices are worth noting:

• Two secrets. A backup key per member, which encrypts that member's backup index, and a vault recovery key per vault collection, which encrypts that vault's keys.
• People and devices. Shares can be held by parents' and adults' phones, by paper shares kept outside the home, and by the home box or TPM-equipped workers. Children's phones and guests don't hold shares.
• Devices are counted as one person. A device share is sealed to the TPM, but someone with root access to the box could open it. So the RFC counts device shares as if one person could reach them all: for the backup key, one person's share plus every device share can never reach the threshold. A parent can't open another member's backup alone by getting at the box.
• The owner chooses holders. The interface suggests a default; for a child, the default means both parents together could open the child's backup, and the RFC says the interface states this openly. The child can switch to paper shares only.
• Paper at home doesn't count. Paper shares are always printed with the instruction to keep them outside the home with someone trusted.
• A waiting period for suspicious rotations. If the requesting phone came from a device replacement that the old phone didn't sign, share holders wait before giving shares, and the old phone is notified.
• A tested library. The arithmetic uses an existing, independently audited open-source library rather than new code; changing it requires an RFC.

Honest limits

• Not released. The vault is not released before an independent audit, and there has been no independent audit of Havenfold yet.
• Default trade-offs. In the default setting, two parents together can open a child's backup. That is a design choice written down, not hidden.
• Holders must be reachable. Shamir doesn't help if not enough holders are alive, reachable and willing. Choosing holders is a family decision, not a technical one.
• Pre-alpha. Do not use Havenfold for real data.

Summary

• Shamir secret sharing splits a key so any threshold of holders can rebuild it, and fewer learn nothing.
• It fits the lost-phone problem: recovery without a company holding your key, and without any one person holding it either.
• Havenfold's vault design spreads shares across trusted people, paper outside the home and TPM-equipped devices, counts devices as one person, and rotates the secret after recovery.
• The vault code exists and is tested, but it won't be released before an independent audit; Havenfold is pre-alpha.