← All posts
Engineering CloakAPI · 2026-04-03 · 14 min read

Shamir 3-of-3 key custody: why we built our own

CloakAPI's desktop app protects your persona-cipher key — the local key that de-tokenises your data — by splitting it with Shamir's Secret Sharing into three shares held in three different places: your OS keychain, an encrypted recovery vault, and a passphrase-locked share. No single location can reconstruct it, and CloakAPI never holds a share. This post explains why we wrote the implementation from scratch instead of reaching for an existing library — and how the underlying arithmetic works.

Why 3-of-3 instead of 2-of-3 or HSM-only

Shamir's Secret Sharing (SSS) — introduced by Adi Shamir in "How to Share a Secret" (Communications of the ACM, 1979) — splits a secret into n shares such that any k shares suffice to reconstruct it, and any k-1 shares reveal nothing about the secret. The pair (k, n) is the threshold scheme.

The desktop app defaults to (3, 3): threshold 3, total shares 3 — all three shares are required to reconstruct the key. The three shares live in three different places: s1 in your operating-system keychain, s2 in an encrypted recovery vault, and s3 behind a passphrase you set. The alternatives, and where they land:

The honest limitation of (3, 3): if all three share locations are compromised simultaneously, the key is exposed — and, conversely, if you lose both your device and your vault, 3-of-3 is unrecoverable (which is exactly why the 2-of-3 toggle exists). The point of the split is that no single place — and specifically not CloakAPI, which holds none of the shares — can reconstruct your key alone.

The library landscape and where it falls short

Before writing anything, we evaluated the ecosystem:

The problem is not that these libraries are wrong — most are correct implementations of SSS. The problem is that "Shamir's Secret Sharing" underspecifies the encoding. Two correct implementations can produce shares that are incompatible with each other's reconstruction if they differ in: the choice of irreducible polynomial, byte ordering, how multi-byte secrets are chunked, how the x-coordinate of each share is encoded, and whether share indices start at 0 or 1.

We needed the share-splitting path and the share-reassembly path to produce byte-for-byte compatible output — every time, on every platform, entirely on the user's device. The safest path was to write both to the same explicit specification.

GF(2^8) arithmetic: a walkthrough

Shamir's Secret Sharing requires arithmetic in a finite field. The standard choice for byte-level SSS is GF(2^8) — the field of 256 elements, where each element is one byte.

In GF(2^8), addition is XOR (carry-free addition modulo 2, applied bitwise). Multiplication is polynomial multiplication modulo an irreducible polynomial of degree 8 over GF(2). We use the same polynomial as AES:

p(x) = x^8 + x^4 + x^3 + x + 1  — binary: 0x11b (decimal: 283)

Why this polynomial? It is well-studied, widely implemented, and choosing it means our test vectors can be cross-checked against AES GF(2^8) implementations.

Multiplication in GF(2^8)

Multiplying two elements a and b in GF(2^8) using the "Russian peasant" algorithm:

def gf_mul(a: int, b: int) -> int:
    """Multiply a and b in GF(2^8) with polynomial 0x11b."""
    result = 0
    while b:
        if b & 1:
            result ^= a       # add current a to result (XOR = addition in GF(2))
        a <<= 1               # multiply a by x
        if a & 0x100:
            a ^= 0x11b        # reduce modulo p(x)
        b >>= 1
    return result & 0xff

Division is multiplication by the multiplicative inverse. We precompute a 256-element log/antilog table using a generator element (0x03 is a generator of the multiplicative group of GF(2^8) under the AES polynomial) so that division becomes two table lookups and a subtraction modulo 255.

Secret splitting

To split a single-byte secret s into 3 shares with threshold 3:

  1. Choose two random coefficients a1, a2 from GF(2^8) uniformly at random (using a CSPRNG).
  2. Define the polynomial f(x) = s + a1*x + a2*x^2 over GF(2^8).
  3. Evaluate at x = 1, 2, 3: the shares are (1, f(1)), (2, f(2)), (3, f(3)).

For a multi-byte secret (like a 32-byte AES-256 key), repeat independently for each byte. The x-coordinates are the same for all bytes; each byte gets its own independent polynomial. The result is three shares, each 32 bytes, plus their x-coordinates.

Polynomial degree 2 means exactly 3 coefficients (degree-0 = secret, degree-1 = a1, degree-2 = a2). A polynomial of degree k-1 over GF(2^8) requires k evaluation points to reconstruct — consistent with a threshold of k=3.

Reconstruction via Lagrange interpolation

Given any 3 shares (x1,y1), (x2,y2), (x3,y3), the secret f(0) is recovered by Lagrange interpolation:

f(0) = Σ yi * Π (0 - xj)/(xi - xj)  for j ≠ i

All arithmetic is in GF(2^8). Subtraction equals addition equals XOR. Division is via the precomputed inverse table. The interpolation is O(k^2) per byte, which is negligible for any practical secret size.

Test vectors and cross-validation

We validated our implementation against:

The share-splitting and reassembly paths produce identical byte sequences on all of these test vectors. Byte-for-byte compatibility was the primary design constraint, and it is checked in our test suite on every change.

How recovery actually works

Recovery is something you do, on your own device — there is no ceremony to schedule and no third party to call:

  1. Collect the shares. On a working device, share s1 is read from your OS keychain automatically. If you are moving to a new device, you restore s2 from your encrypted recovery vault.
  2. Unlock the passphrase share. You enter the passphrase you set during onboarding, which unlocks share s3.
  3. Reconstruct locally. Once the threshold number of shares is present (3 in the default scheme, 2 if you chose 2-of-3), the app reconstructs the key in memory via the Lagrange interpolation described above. The reconstruction happens entirely on-device.
  4. Nothing leaves the machine. No share and no reconstructed key is ever transmitted to CloakAPI — the gateway is a pure relay and holds none of your key material. There is nothing on our side to subpoena, breach, or lose.

Honest limitations

Shamir's Secret Sharing is information-theoretically secure — knowing k-1 shares reveals exactly zero bits about the secret. But the threat model has practical constraints our scheme does not fully address: