Sharded Key Storage

sharded-key-storage.md

Sharded Secret Key Storage

• Store secret keys on the internet
• Authenticate with arbitrary authentication methods to retrieve secret
• Trustless: None of the key storage server providers can read the secret
• Recoverable funds: Even if authentication credentials are lost, the secret can be recovered
• Secure: If a key storage server gets compromised, the attacker will not even know a fragment of the secret
• Fault-tolerant: Redundancy fragment allows retrieving the secret even if a server is down
• Versatile: Allows storage of arbitrary secrets

How it works

Components / Prerequisits

• S is the set of all available independent key storage servers, run by different people
• Pick set of N key storage servers to use out of all the S

In the following we will assume:

• We are saving 256-bit ED25519 secret key seeds
• We are using AES to encrypt the secret key seed
• |S| > 4
• |N| = 4

Authentication

Any read or write access to any key storage server must be authenticated. The key storage servers can all use different authentication methods, but they don't have to. It might be desirable for the user experience to have them all offer a common way to authenticate. In that case two-factor authentication should be considered mandatory.

Save a key

1. Take an arbitrary secret key K
2. Create an AES key A and use it to encrypt K: K' = AES_ENC(A, K)
3. Split K' into 3 (|N| - 1) fragments F'1, F'2 & F'3 and calculate F'4 = XOR(F'1, F'2, F'3)
4. Let F = { F'1, F'2, F'3, F'4 }
5. On each server in S, authenticate, then store one fragment of F' and the complete AES key A

Retrieve a key

1. Contact each server in S, authenticate, then read the fragment F'x and the AES key A stored on the server
2. Check that all servers returned the same AES key A. If one is different, dismiss the fragment.
3. Combine fragments: K' = CONCAT(F'1, F'2, F'3). If one of the fragments is missing, recover it by XOR-ing the three known fragments.
4. Decrypt secret key: K = AES_DEC(A, K')

Rotate the encrypted key after a partial security breach

1. Take the secret key K, retrieve it as usual (see Retrieve a key above) if not already present
2. Create a new AES key A and use it to encrypt K: K' = AES_ENC(A, K)
3. Split the new K' into fragments and store the updated fragments and new A on the servers (see Save a key above)

Secret recovery if credentials are lost

Potential flow: Contact customer service of each key storage server involved (or at least all but one of them, thanks to redundancy fragment), request reset of authentication credentials. The customer service will request further proof of identity and only then reset the authentication credentials.

Security considerations

General

• Any security breach on a key storage server must be made public as soon as possible to trigger data rotation
• Key storage servers should take great efforts to
  • Securely store the data
  • Rate limit authentication endpoints
  • Ensure sufficiently strong passwords are used
  • ...
• Resetting the user password and other recovery actions are especially sensitive and should only be done alongside a proper identity verification
• The concept is not completely trustless as
  • The key storage servers must not share data with each other (and I as a user have to trust them with that)
  • If more than one server denies authentication for whatever reason or loses the stored data, the secret cannot be retrieved

OAuth / Social login

Social logins would be easily feasible, but impose a high risk if the same authentication provider is used for all key storage servers. The authentication provider would become the single point of failure.

A scenario where multiple social logins are used and different ones are used for different key storage servers might be safe enough. Requires further investigation.

Future

• Come up with an automatic encrypted secret rotation triggered by a breach notification
  • Requires the client to be online, though
  • Might want to rotate regularly, anyway