Solving the Lost YubiKey problem with WebAuthn PRF & Shamir’s Secret Sharing

Standard account recovery relies on centralized servers or passwords. While the FIDO Alliance recommends registering multiple authenticators as backups, this approach proves impractical and costly for average users. Consequently, many services implement fallback authentication methods (passwords, SMS codes), creating a critical vulnerability: downgrade attacks. Attackers exploit these weaker recovery mechanisms through social engineering, with research showing 55% of users falling for real-time phishing and 35% remaining susceptible to these attacks. This effectively reduces account security to its weakest link.

Shamir’s Secret Sharing (SSS) offers a decentralized alternative. Unlike standard backups that simply copy data, SSS splits a key into multiple unique parts called shares. This method allows for secure recovery without a single point of failure or reliance on weaker authentication methods.

Practical Implementation Architecture

Since no WebAuthn SSS extension currently exists in the standard, I propose a browser extension-based approach that achieves the same security goals. This system functions as a modern, passwordless identity manager with decentralized account recovery capabilities in the event of hardware key loss.

System Components

• Master Key: A random key generated within the extension. This root secret encrypts all user data (website passwords, notes, etc.).

• Authenticator (e.g., YubiKey): Used to unlock the Master Key during normal operation via the WebAuthn PRF extension.

• Shamir’s Secret Sharing: Enables Master Key recovery during catastrophic failure (YubiKey loss).

• Browser Extension: The orchestration layer that performs encryption, communicates with the authenticator, and isolates the process from web pages.

Registration

The registration phase securely creates the Master Key, encrypts it, and establishes backup mechanisms:

1. Generation: The extension generates a cryptographically strong random Master Key in memory.

2. WebAuthn PRF: The extension prompts the user to insert their YubiKey and calls navigator.credentials.create with the PRF extension enabled. A random salt is transmitted to the authenticator to serve as the input for the PRF extension. The YubiKey returns a PRF output (deterministic key bound to the hardware).

3. Encryption: The extension uses the PRF output as a Key Encryption Key (KEK) to encrypt the Master Key. The salt and the encrypted Master Key are then stored on a server.

4. Backup: The extension takes the unencrypted Master Key and mathematically splits it into $n$ shares using SSS with threshold $k$ (e.g., 2-of-3). The shares are distributed across independent storage locations to prevent single points of failure. This distribution strategy balances availability (easy recovery) with security (preventing unauthorized reconstruction).

5. Cleanup: The extension securely erases both Master Key and PRF output from RAM using e.g. zeroing.

type Share = [bigint, bigint];

const toBigInt = (buffer: Uint8Array): bigint => {
  let bigInt = 0n;
  for (const byte of buffer) {
    bigInt = (bigInt << 8n) + BigInt(byte);
  }

  return bigInt;
};

const split = (
  masterKey: Uint8Array,
  threshold: number,
  total: number,
): Share[] => {
  // Convert masterKey bytes to BigInt
  const masterKeyBigInt = toBigInt(masterKey);

  // Generate random coefficients [a1, a2, ..., a(threshold-1)]
  const coefficients = Array.from({ length: threshold - 1 }, () => {
    const bytes = crypto.getRandomValues(new Uint8Array(32));
    const randomBigInt = toBigInt(bytes);
    return mod(randomBigInt);
  });

  // Polynomial: q(x) = masterKey + a1*x + a2*x^2 + ... + a(k-1)*x^(k-1)
  const q = (x: bigint) => {
    return coefficients.reduce(
      (acc, coeff, i) => mod(acc + mod(coeff * x ** BigInt(i + 1))),
      masterKeyBigInt,
    );
  };

  // Generate shares: [(1, q(1)), (2, q(2)), ..., (total, q(total))]
  return Array.from({ length: total }, (_, i) => {
    const x = BigInt(i + 1);
    return [x, q(x)];
  });
};

Authentication

Standard authentication quickly unlocks the vault using the hardware authenticator:

1. Initiation: The user arrives at their device with the extension locked.

2. Data Retrieval: The extension downloads the encrypted Master Key and the salt from the server.

3. Key Derivation: The extension calls navigator.credentials.get with the stored salt. The user touches their YubiKey, which internally computes and returns the same PRF output as during registration.

4. Decryption: The extension uses the PRF output to decrypt the encrypted Master Key.

5. Result: The extension has the Master Key in memory. The user is authenticated and the extension can autofill passwords or generate passkeys.

const credential = await navigator.credentials.get({
  publicKey: {
    ...,
    extensions: {
      prf: {
        eval: {
          first: salt
        }
      }
    },
  }
});

Recovery

Recovery enables account access when the user loses their YubiKey:

Critical constraint: Without the YubiKey, obtaining the PRF output is impossible. The encrypted Master Key stored on the server is cryptographically useless.

1. Initiation: The user on a new device (or with a new authenticator) clicks “Recover Account” in the extension.

2. Share Collection: The extension collects at least $k$ shares from their distributed storage locations. Remote shares may require authentication (e.g., email verification, OAuth). Physical shares require user input (scanning QR codes, entering text). The specific retrieval mechanism depends on the storage medium chosen during registration.

3. Reconstruction: The extension mathematically combines the shares. If the shares are valid, the polynomial evaluation yields the original Master Key.

4. Key Rotation: Once the user reconstructs the master key via the recovery process, the extension prompts them to insert a new YubiKey. The registration process repeats. A new salt is generated, new PRF output is obtained from the new authenticator, and the master key is re-encrypted. Finally, the old encrypted master key and salt on the server are replaced with the new versions.

const toBytes = (num: bigint, buffer: Uint8Array): void => {
  let temp = num;

  for (let i = buffer.length - 1; i >= 0; i--) {
    buffer[i] = Number(temp & 0xffn);
    temp >>= 8n;
  }
};

const recover = (shares: Share[], masterKey: Uint8Array): void => {
  // Lagrange interpolation: evaluate polynomial at x = 0 to recover secret
  const masterKeyBigInt = shares.reduce((sum, [x_i, y_i], i) => {
    // Calculate Lagrange basis polynomial L_i(0)
    const basis = shares.reduce((product, [x_j], j) => {
      if (i === j) return product;
      // L_i(0) = product of (-x_j) / (x_i - x_j) for all j != i
      const numerator = mod(-x_j);
      const denominator = mod(x_i - x_j);
      return mod(product * numerator * modInverse(denominator));
    }, 1n);

    // Sum all y_i * L_i(0)
    return mod(sum + mod(y_i * basis));
  }, 0n);

  // Convert BigInt back to Uint8Array
  toBytes(masterKeyBigInt, masterKey);
};

// Usage example:
const secret = crypto.getRandomValues(new Uint8Array(32));
const shares = split(secret, 3, 5);

const recoveredSecret = new Uint8Array(32);
recover(sample(shares, 3), recoveredSecret);

Security Properties

Zero-Knowledge Server: The server observes only an encrypted blob, the salt, and optionally one SSS share. None of these components provides useful information without the remaining elements.

Phishing Protection: Standard authentication requires physical possession of the hardware authenticator.

Loss Protection: The loss of the hardware authenticator does not result in permanent account lockout. Instead, the system utilizes a decentralized recovery mechanism.

Isolation: Browser extensions execute in an isolated context, separate from the web page’s main-world scripts. This architectural boundary prevents malicious JavaScript on compromised websites from accessing the extension’s memory or the Master Key, even if the visited page contains Cross-Site Scripting (XSS) vulnerabilities.

Mathematical Foundation

Shamir’s Secret Sharing relies on polynomial interpolation. The fundamental idea is that it takes $k$ points to uniquely define a polynomial of degree $k-1$.

To protect a secret $S$, we construct a random polynomial $q(x) \in \mathbb{Z}_p[x]$ of degree $k-1$ where $q(0) = S$. The polynomial is defined as:

$$q(x) = S + a_1 x + a_2 x^2 + \dots + a_{k-1} x^{k-1} \pmod{p}$$

In this equation:

• $S$ represents the secret key material
• $p$ is a cryptographically large prime satisfying $p > \max(S, n)$
• Coefficients $a_1, \dots, a_{k-1} \in \mathbb{Z}_p$ are chosen randomly from a uniform distribution
• All arithmetic operations are performed in the finite field $\mathbb{Z}_p$

The share generation evaluates $q(x)$ at $n$ distinct non-zero points to produce shares $(i, q(i))$ for $i \in \{1, \dots, n\}$.

Secret reconstruction requires collecting at least $k$ shares. Given these points, we apply Lagrange interpolation to calculate $q(0)$ and retrieve the private key.

Figure 1: Lagrange interpolation reconstructing a polynomial from threshold shares. The animation demonstrates how $k$ points uniquely determine a polynomial of degree $k-1$, enabling secret recovery.

The visualization depicts four data points $(0, 3), (1, 5), (3.5, 1), (5, 3)$ represented as black dots. The animation sequentially reveals four colored curves—each a Lagrange basis function $L_i(x)$ weighted by its corresponding $y_i$ value, where the basis polynomial is generally defined as:

$$L_i(x) = \prod_{\substack{j=0 \\ j \neq i}}^{k-1} \frac{x - x_j}{x_i - x_j}$$

For these specific points, the four basis functions are:

$$L_0(x) = \frac{(x-1)(x-3.5)(x-5)}{(0-1)(0-3.5)(0-5)}, \quad L_1(x) = \frac{(x-0)(x-3.5)(x-5)}{(1-0)(1-3.5)(1-5)}$$ $$L_2(x) = \frac{(x-0)(x-1)(x-5)}{(3.5-0)(3.5-1)(3.5-5)}, \quad L_3(x) = \frac{(x-0)(x-1)(x-3.5)}{(5-0)(5-1)(5-3.5)}$$

The blue curve represents $y_0 \cdot L_0(x) = 3 \cdot L_0(x)$, orange shows $y_1 \cdot L_1(x) = 5 \cdot L_1(x)$, green displays $y_2 \cdot L_2(x) = 1 \cdot L_2(x)$, and red illustrates $y_3 \cdot L_3(x) = 3 \cdot L_3(x)$. In the final frame, the thick black line represents the reconstructed polynomial $q(x) = 3 \cdot L_0(x) + 5 \cdot L_1(x) + 1 \cdot L_2(x) + 3 \cdot L_3(x)$—the sum of all four weighted basis functions—which passes exactly through each of the four data points.

Conclusion

Decentralized recovery offers a promising path away from the fragility of centralized backups, weak recovery methods and the complexity of managing multiple hardware keys. By combining the cryptographic strength of WebAuthn PRF with the resilience of Shamir’s Secret Sharing, we can build identity systems that are both secure and user-friendly.