@noy-db/on-shamir

k-of-n Shamir Secret Sharing of the vault KEK for multi-party unlock. Any K of N enrolled shares recombines the KEK; fewer than K leaks zero bits.

The defining feature is composability — each share can itself be protected by any other @noy-db/on-* method. Share 1 behind a WebAuthn passkey, share 2 behind an OIDC login, share 3 printed on paper in a corporate safe. Fractional trust across different authentication modes.

Part of the @noy-db/on-* authentication family.

Install

pnpm add @noy-db/on-shamir

Use cases

• "Any 2 of 3 admins must authorise unlocking the audit vault."
• "CFO + COO consent required to unlock the CEO vault during vacation."
• "3-of-5 board escrow — the vault survives any 2 resignations."
• "Executive key is split across a passkey + OIDC + paper backup — any 2 of 3 unlock."

Threat model

Protects against:

• Up to K-1 colluding share holders (mathematically — fewer than K shares reveals zero bits of the KEK)
• Loss of up to N-K shares (remaining K shares still reconstruct)

Does NOT protect against:

• K colluding share holders (by design — that's the threshold contract)
• Device compromise of the combining machine during reconstruction (the KEK is briefly in memory; if that machine is malicious, no library-level hedge helps)
• Side-channel attacks on the Lagrange interpolation (not constant-time by design — the threat model assumes a trusted combine-device)

Math

Shamir Secret Sharing over GF(2^8), byte-wise. For each byte of the KEK:

1. Construct a random polynomial of degree k-1 whose constant term is the KEK byte.
2. Each share is the polynomial evaluated at a distinct x-coordinate (1..255; x=0 reserved because it would reveal the byte).
3. Lagrange interpolation at x=0 given any K points recovers the byte.

Implemented in ~120 LoC of pure TypeScript (gf256.ts + shamir.ts). Zero cryptographic dependencies — just Web Crypto's getRandomValues for randomness and subtle.importKey to rehydrate the reconstructed KEK.

Reduction polynomial: x^8 + x^4 + x^3 + x + 1 (0x11b, same as AES).

Usage

Enroll — after primary unlock

import { splitKEK, encodeShareBase32 } from '@noy-db/on-shamir'

const shares = await splitKEK(currentKEK, { k: 2, n: 3 })

// Each share is now a RawShare structure. Serialise for distribution:
const shareStrings = shares.map(encodeShareBase32)
// Example: 'SHAMIR_S1_K2N3__AKHT-P4L7-...'

// Distribute via any on-* method:
//   shareStrings[0] → store under a WebAuthn-protected keyring entry
//   shareStrings[1] → store under an OIDC-protected keyring entry
//   shareStrings[2] → print on paper, put in the corporate safe

Unlock — collect K shares and combine

import { combineKEK, decodeShareBase32 } from '@noy-db/on-shamir'

// Unlock each share via its own on-* method (not shown — uses whichever
// on-webauthn / on-oidc / on-recovery / on-magic-link the holder chose).
const shareA = decodeShareBase32(shareStringFromCFO)
const shareB = decodeShareBase32(shareStringFromCOO)

// Combine — returns a non-extractable KEK ready to use
const kek = await combineKEK([shareA, shareB])

Low-level — for custom integrations

import { splitSecret, combineSecret } from '@noy-db/on-shamir'

const shares = splitSecret(new Uint8Array(secretBytes), 2, 3)
const recovered = combineSecret([shares[0], shares[1]])
// recovered is a Uint8Array — you handle its lifecycle

JSON form — store shares inside other on-* keyring entries:

import { encodeShareJSON, decodeShareJSON } from '@noy-db/on-shamir'

const json = encodeShareJSON(shares[0])
// { v: 1, x: 1, k: 2, n: 3, y: '<base64>' }
await keyring.put('_recovery_share_1', json)

API

// High-level — wraps a CryptoKey
async function splitKEK(kek: CryptoKey, options: { k: number; n: number }): Promise<RawShare[]>
async function combineKEK(shares: readonly RawShare[]): Promise<CryptoKey>

// Low-level — operates on raw bytes
function splitSecret(
  secret: Uint8Array,
  k: number,
  n: number,
  randomBytes?: (count: number) => Uint8Array,  // Injectable for tests
): RawShare[]
function combineSecret(shares: readonly RawShare[]): Uint8Array

// Serialisation
function encodeShareBytes(share: RawShare): Uint8Array
function decodeShareBytes(bytes: Uint8Array): RawShare

function encodeShareBase32(share: RawShare): string
function decodeShareBase32(input: string): RawShare

function encodeShareJSON(share: RawShare): ShareJSON
function decodeShareJSON(json: ShareJSON): RawShare

interface RawShare {
  x: number          // 1..255
  y: Uint8Array      // One byte per secret byte
  k: number          // Threshold
  n: number          // Total
}

// GF(2^8) arithmetic — exported for composition / auditing
function gfAdd(a: number, b: number): number
function gfMul(a: number, b: number): number
function gfInv(a: number): number
function gfDiv(a: number, b: number): number
function gfPolyEval(coeffs: readonly number[], x: number): number
function lagrangeInterpolateAtZero(points: readonly [number, number][]): number

Share format

Binary (6-byte header + y-bytes):

offset  size  field
0       1     version (= 1)
1       1     x-coordinate (1..255)
2       1     k (threshold)
3       1     n (total)
4       2     byteLength (big-endian uint16)
6+      L     y-bytes (L = byteLength)

For a 32-byte KEK: 38 bytes total per share.

Base32 form includes a human-readable prefix (SHAMIR_S{x}_K{k}N{n}__) followed by the payload in groups of 4:

SHAMIR_S2_K2N3__AKHT-P4L7-KDFG-H3JX-M8E...

The prefix is stripped by the decoder — metadata is recovered from the binary header. Consumer tools can show the prefix to the user for at-a-glance share identification without trusting it.

Composability recipe — Shamir + any on-* method

import { splitKEK, encodeShareJSON } from '@noy-db/on-shamir'
import { createMagicLinkToken } from '@noy-db/on-magic-link'
// Plus whichever other on-* packages you use

const shares = await splitKEK(currentKEK, { k: 2, n: 3 })

// Share 1 — passkey
await webAuthn.enrollWithPayload(ceoPasskey, encodeShareJSON(shares[0]))

// Share 2 — magic link to an auditor's email
const link = createMagicLinkToken('escrow-vault', { ttlMs: 30 * 24 * 60 * 60 * 1000 })
await emailAuditor(link, encodeShareJSON(shares[1]))

// Share 3 — paper backup
console.log('Corporate-safe backup:', encodeShareBase32(shares[2]))

Performance

GF(2^8) operations are table-lookup O(1) — all micro-operations run in nanoseconds. Splitting a 32-byte KEK into 3 shares takes sub-millisecond. Combining likewise. Web Crypto's importKey on the reconstructed KEK is the dominant cost (~1ms).

License

MIT