Roadmap: Credential key unlinkability

[emlun]

As the wallet is currently implemented, each user has a single public-private key pair which is used for all of the user's credentials. At some point we will need to satisfy stricter privacy requirements that credentials and credential presentations are unlinkable; this is a roadmap of the steps toward those goals.

Phase 0: More flexible encryption architecture

• Extract stateless keystore core functions and add unit tests wallet-frontend#242
• Migrate to asymmetric encryption wallet-frontend#262
• Support asymmetric encryption in frontend wallet-backend-server#56
• Update encryption architecture docs to v3 wallet-docs#8

Currently, the wallet creates a DID and a credential key pair once when the account is created, and encrypts these data to the user's PRF key(s). These encrypted data are never modified after this point, so we currently have not implemented a way to re-encrypt new contents and upload the new encryption ciphertext to the server. To support unique keys per credential, we will need the ability to edit the encrypted data and upload the new ciphertext. This is a good opportunity to revise the encryption architecture.

The current encryption architecture is a bit inflexible: in particular, we cannot easily rotate the main encryption key because it is symmetrically encrypted to each of the user's PRF keys (and password key, if applicable), and each PRF key is only available after performing a WebAuthn ceremony to obtain the PRF output for that key. A consequence of this is that the main encryption key persists for the entire lifetime of the wallet - so a compromise of this main key becomes a significant threat, since it gives access to both past and future versions of the encrypted data. Therefore, we should revise the encryption architecture to use asymmetric encryption instead. This will enable us to rotate the main key at any time:

• To register a new WebAuthn credential:

  1. Generate a new ECDH key pair.
  2. Use the PRF output as a wrapping key to encrypt the ECDH private key.
  3. Store the wrapped ECDH private key alongside the PRF data.

• To encrypt a new version of wallet contents:

  1. Generate a new mainKey for the encryption.
  2. Encrypt the wallet contents to this mainKey.
  3. Generate a new, ephemeral ECDH key pair.
  4. For each of the user's PRF keys:
     1. Perform an ECDH exchange between the ephemeral ECDH private key and the PRF key's ECDH public key.
     2. Use the ECDH output as a wrapping key to encrypt the mainKey.
     3. Store the wrapped mainKey alongside the PRF key data.
  5. Store the encrypted wallet contents and the updated PRF key data on the server.

This way each mainKey is used only for a single version of the encrypted data, which significantly mitigates the threat of a compromised key. Also, using asymmetric encryption means we can re-encrypt new versions of the wallet contents any number of times without having to re-authenticate the user to obtain an encryption key. Therefore, perhaps we could eliminate the sessionKey encryption from the copy of the wallet contents stored in session storage, and just store the wallet contents in plain text for the duration of the session. Especially sensitive secrets such as credential private keys should remain encrypted at rest, however - preferably under a key not stored alongside the ciphertext.

Phase 1: Unique key pair per credential

• Protect UserEntity.privateData update with ETag/If-Match headers wallet-backend-server#57
• Protect private data update with ETag/If-Match headers wallet-frontend#263
• Rename UserEntity.webauthnUserHandle to uuid and use it instead of DID where possible wallet-backend-server#65
• Support unique, per-credential key pairs wallet-backend-server#66
• Use unique keypair per credential wallet-frontend#307
• Update encryption architecture docs to v4 wallet-docs#9

The first step towards credential key unlinkability is to generate a new key pair for each credential issued. This should be fairly straightforward:

• To create a new verifiable credential:

  1. Generate a new key pair for the credential.
  2. Request a new credential issuance tied to the new key pair.
  3. Store the new credential in the wallet account and store the new private key in the encrypted wallet contents.

• To create a credential presentation:

  1. Decrypt the wallet contents and retrieve the private key of the credential to be presented.
  2. Sign the credential presentation with this private key.

Phase 2: Unique key pair per credential presentation

For improved privacy, even presentations of the same credential should be unlinkable (assuming the presented claims are not personally identifying, of course). For this, we will likely need to re-issue the credential with a new key pair for each each presentation, and present each credential only once.

This phase will be more convoluted than the previous ones, since re-issuing credentials will require cooperation from the credential issuer. We may need to extend our data model so that a "credential" can consist of many unique instances of that credential, each tied to a unique key pair, and track which credential instances have had presentations generated. We may need to periodically "refresh" credentials in advance for offline use, and garbage-collect expired but unused credential instances.

Note that other approaches have also been proposed for how to achieve unlinkable presentations.

Phase 3: Hardware-bound credential keys

The current wallet implementation supports using the WebAuthn PRF extension to derive encryption keys, and using those keys to encrypt the user's credential private key on the client side. This is a good first step, allowing wallet contents to be end-to-end encrypted under a key that is never exposed to the server side, and this can probably satisfy the requirement for "Type 2" credentials. But PRF-derived keys are ultimately software keys - they are exposed to the client OS, the browser and the wallet-frontend JavaScript. To satisfy "Type 1" credentials, we most likely need hardware-bound keys that can guarantee "sole control". We are working on a pair of new WebAuthn extensions: the sign and kem extensions, to enable this.

This phase will be to use these extensions both to generate hardware-bound credential key pairs (see phase 1) and to encrypt the wallet contents for storage. The development, standardization and implementation of the extensions will take a while - likely on the order of years - but once in place their implementation in the wallet should be fairly straightforward since this only has to do with the wallet-frontend's internal operation.

Some caveats:

• The credential issuance and presentation flows as currently implemented require 3 signatures to complete the flow. With hardware-bound keys, a distinct WebAuthn authentication ceremony is needed for each signature. This should ideally be reduced to 1 or at most 2 to not weigh down the user experience too much. We may need to review external specs for which signatures are required.

Phase 4: ARKG credential keys

As noted above, for phase 2 we may need to generate large numbers of key pairs to be used only once, and we may need to "refresh" credentials in batches and tie them to newly generated key pairs. For phase 3 we want to make these credentials hardware-bound, which means a distinct WebAuthn authentication ceremony will be required whenever we need to generate a new key pair, so the user might need to perform of tens of authentication ceremonies in a row in order to refresh a batch of keys. That is not an acceptable user experience.

To solve this, we might use the ARKG key generation algorithm to enable the wallet-frontend to generate public keys deterministically without getting access to the corresponding private keys. The sign and kem extensions are intended to support this algorithm, so the wallet could create an ARKG seed for each new WebAuthn credential and use that ARKG seed to derive public keys whenever one is needed for credential issuance.

This might require some changes to the credential issuance flow. In particular, the wallet-frontend cannot autonomously generate a signature for the newly generated public key without invoking a WebAuthn authentication ceremony. Wallet interoperability spec may need to be revised in order to allow a credential issuance flow that does not require a proof of possession of the private key.

Like phase 3, standardization of the features needed for this may take a while. In the meantime, we can emulate these features in wallet-frontend software using the PRF extension as the source of key material.

[emlun]

Phase 0 is addressed by these PRs:

• Migrate to asymmetric encryption wallet-frontend#262
• Support asymmetric encryption in frontend wallet-backend-server#56
• Update encryption architecture docs to v3 wallet-docs#8

[emlun]

Phase 1 is addressed by these PRs:

• Support unique, per-credential key pairs wallet-backend-server#66
• Use unique keypair per credential wallet-frontend#307
• Update encryption architecture docs to v4 wallet-docs#9