Shamir's Secret Sharing

Understanding Shamir's Secret Sharing (SSS) and how BAP uses it to implement threshold-based access control for digital wills.

Shamir's Secret Sharing (SSS) is a cryptographic algorithm that splits a secret into multiple shares, where a minimum number of shares are required to reconstruct the original secret.

BAP uses SSS to ensure that no single survivor can access the will alone — multiple survivors must collaborate.

How SSS Works

The Concept

Imagine you have a secret (the DEK) and you want to split it among 5 people, but any 3 of them together should be able to reconstruct it.

SSS works using polynomial interpolation:

Choose a threshold K and total shares N
Generate a random polynomial of degree K-1
Evaluate the polynomial at N different points
Each share is a point (x, y) on the curve

To reconstruct the secret, you only need K points — the polynomial's coefficients (including the secret at x=0) can be recovered through Lagrange interpolation.

Mathematical Example

For a 2-of-3 scheme (threshold = 2, shares = 3):

Secret: 42
Choose random coefficient: 15
Polynomial: f(x) = 42 + 15x
Generate shares:
- Share 1: f(1) = 42 + 15(1) = 57
- Share 2: f(2) = 42 + 15(2) = 72
- Share 3: f(3) = 42 + 15(3) = 87

To reconstruct:

Use any 2 shares: e.g., 57 and 72
Lagrange interpolation gives f(0) = 42 (the secret)

Security Properties

Information-theoretic security — With fewer than K shares, you learn nothing about the secret
No single point of failure — Losing one share doesn't prevent reconstruction
Flexible thresholds — Any K-of-N combination works

SSS in BAP

Key Distribution Flow

┌─────────────────────────────────────────────────────────────────┐
│                  Data Encryption Key (DEK)                      │
│                       256-bit secret                            │
└─────────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────┐
│              Split via Shamir's Secret Sharing                  │
│                     K-of-N threshold                             │
└─────────────────────────────────────────────────────────────────┘
                              │
          ┌───────────┬───────────┬───────────┐
          ▼           ▼           ▼           ▼
      ┌───────┐   ┌───────┐   ┌───────┐   ┌───────┐
      │Share 1│   │Share 2│   │Share 3│   │Share 4│
      │(Jane) │   │(John) │   │(Mary) │   │(Bob)  │
      └───────┘   └───────┘   └───────┘   └───────┘
          │           │           │           │
          ▼           ▼           ▼           ▼
    ┌─────────────────────────────────────────────────────────┐
    │    Each share encrypted with Survivor's derived key    │
    │         (HKDF: survivor_secret + survivor_id)           │
    └─────────────────────────────────────────────────────────┘

Threshold Configuration

When setting up a will, the host chooses:

Setting	Description	Valid Range
N	Total survivors	2-10
K	Threshold (shares needed)	2 to N

Examples:

Configuration	Meaning
2-of-3	Any 2 of 3 survivors can access
3-of-5	Any 3 of 5 survivors can access
2-of-2	Both survivors must authenticate
5-of-5	All survivors must authenticate

Recommended Configurations

Scenario	Recommended	Rationale
2 close family members	2-of-2	Maximum security
3 family members	2-of-3	One can act as backup
4+ family members	2-of-4 or 3-of-5	Balance of security and practicality
Distributed family	2-of-3	Allows for travel/availability issues

Reconstruction Process

When enough survivors authenticate:

┌─────────────────────────────────────────────────────────────────┐
│              Authenticated Survivor Shares                       │
│     Survivor 1: x=1, encrypted_y=enc(57, key1)                 │
│     Survivor 2: x=2, encrypted_y=enc(72, key2)                 │
│                              │                                  │
│                              ▼                                  │
│     ┌─────────────────────────────────────────────────────────┐ │
│     │   1. Decrypt each share with survivor's key           │ │
│     │   2. Collect decrypted (x, y) points                   │ │
│     │   3. Apply Lagrange interpolation                      │ │
│     │   4. Recover DEK                                        │ │
│     └─────────────────────────────────────────────────────────┘ │
│                              │                                  │
│                              ▼                                  │
└─────────────────────────────────────────────────────────────────┘
                             │
                             ▼
┌─────────────────────────────────────────────────────────────────┐
│           DEK → Decrypt Documents → Serve to Survivors          │
└─────────────────────────────────────────────────────────────────┘

Server-Side Reconstruction

Authentication — Each survivor verifies via OTP
Share retrieval — Server retrieves their encrypted SSS share
Decryption — Share is decrypted with survivor's key
In-memory combination — Once K shares are collected, DEK is reconstructed
Document access — DEK decrypts documents for authenticated survivors
Memory wipe — Shares and DEK are wiped from server memory after access

Important: The server never stores unencrypted shares. They're held only in server memory during the transfer window.

Backup Codes

Each survivor receives 5 single-use backup codes as a fallback if they can't receive OTPs.

How Backup Codes Work

Each code is an alternative authentication method
When used, the backup code decrypts the survivor's SSS share
Each code can only be used once
Codes are hashed with Argon2 before storage (irreversible)

Distribution

Backup codes are displayed only once when a survivor is added. The host must:

Print the codes
Give them to survivors in sealed envelopes
Store copies securely

Warning: If a survivor loses their backup codes and can't receive OTPs, they cannot authenticate!

Security Considerations

What SSS Protects Against

Threat	SSS Protection
Single survivor betrayal	Need multiple survivors
Accidental activation	Unlikely multiple survivors accidentally trigger
Survivor unavailable	Multiple options for authentication

What SSS Doesn't Protect Against

Threat	Mitigation
Colluding survivors	Can't prevent; choose trusted survivors
Server compromise during transfer	Shares held briefly in memory
Social engineering	User education

Threshold Trade-offs

Threshold	Pros	Cons
Low (K=2)	Easy to achieve	Less security
High (K=N)	Maximum security	Difficult to achieve
Middle	Balanced	Requires planning

Implementation Details

BAP uses the hashicorp/vault/shamir library:

import "github.com/hashicorp/vault/shamir"

// Split secret into N shares with threshold K
shares, err := shamir.Split(secret, numShares, threshold)

// Reconstruct secret from K shares
secret, err := shamir.Combine(shares)

Parameters

Prime: 256-bit prime (matches AES-256)
Threshold: Minimum shares for reconstruction
Shares: Individual share data

Encryption — AES-256-GCM encryption details
Will Transfer Protocol — What happens when a will is triggered
Creating a Will — Setting up survivors and threshold