Local Key Security

How to encrypt and decrypt locally stored keys on your various devices.

The Basic Idea

Whenever a user stores a secret key on a device, it would be nice if she could encrypt that key with her passphrase, and if she changed her passphrase on any one of her machines, it would be reflected on the others.

We've developed a simple server-aided protocol to do so, in which a server-side mask is updated during a password change, so that encrypted device keys on offline clients will be decryptable with the new password. The server supplies this mask during decryption, but device keys are never exposed to the server, even in encrypted form.

There are four important steps to consider: key establishment, encrypting/decrypting, key update, and (not yet implemented) mask refreshing.

A Note About User Convenience

We would prefer not to constantly prompt the user for passwords. When we ship KBFS and configure the client to autostart on boot, this will be especially important. For users whose OS gives us a protected keyring (most of them), LKS encryption keys will be stored there by default, and process of computing them from the password and server-side mask during decryption will be skipped. (Currently implemented for OSX only.) We could provide some option for disabling this integration, but probably only advanced users will want it.

Key Establishment

On any device d that Alice needs to encrypt her device-specific keys, she does the following, given her passphrase pA.

  • Generates a new random secret key kAd[0,22561], and encrypts her device-specific keys with it.
  • Computes cA=Scrypt(pA)
  • Computes sAd=kAdcA
  • Sends sAd to the server, which it stores under device d.

Encrypting and Decrypting

Here's how Alice would encrypt or decrypt on device d. Of course the operation is symmetric, so they are handled equivalently:

  • Alice authenticates herself to the server.
  • Alice computes cA from pA via Scrypt.
  • Alice asks for sAd for device d.
  • Alice computes kAd=sAdcA.
  • Encrypts or decrypts device-specific keys using kAd and NaCl's SecretBox.

Password Changes

Alices now updates her password from pA to pA on one of her devices. She runs the password update protocol:

  • Compute cA=Scrypt(pA) and cA=Scrypt(pA)
  • Compute δ=cAcA.
  • Sends δ to the server.
  • For each device d:
    • Update sAsAdδ

Mask Resets (not yet implemented)

One vulnerability of the password change scheme above, is that it's possible to decrypt secret keys using an old password. If a user's password was compromised, and an attacker was also able to obtain the user's server-side mask sAd, then that attacker would be able to decrypt the user's local keys even after the user did a password change.

To prevent this, when decrypting keys, a device should notice that the current passphrase is newer than the one its keys were originally encrypted with. In that case it should generate an entirely new encryption key, repeating the steps from Key Establishment above. Note that this has to be done in a way that's resilient to the device crashing in the middle, so that there's never a risk that the user could end up in a state where their keys are impossible to decrypt. We can use the following procedure.

  1. Generate a new random encryption key.
  2. Encrypt the device-specific keys with the new encryption key, storing this ciphertext on disk in addition to the old ciphertext. Each ciphertext should be stored with the generation number of the passphrase that was originally used to encrypt it, to distinguish them.
  3. Compute the new server-side mask and send it to the server along with the passphrase generation it corresponds to.
  4. Only after the previous step succeeds, delete the old ciphertext from disk.

If the device happens to crash after (2) but before (4), it will have two ciphertexts on disk. When it goes to decrypt them, it will find that the server-side mask's passphrase generation corresponds to only one of them. After successfully decrypting that one, it should delete the other, and then if the passphrase generation of the key is still behind it should attempt another mask reset.

Note that a device that's persistently offline (as in, mothballed in your closet) won't have an opportunity to do a mask reset, and encrypted keys on such a device will still be decryptable using old passwords/masks until that device is used again. But it's unavoidable that a disk that hasn't changed in N years will still be readable with keys from N years ago -- we can't magically change the contents of the disk in the closet.

This scheme isn't implemented yet, but here are the changes we will need to make to support it in the future:

  • On the server, store the passphrase generation that each mask was originally created with. This makes it easier for the client to clean up after itself if it crashes in the middle of a mask refresh.
  • On the device, store the passphrase generation that each encrypted device key was originally encrypted with. This will get compared to the user account's current passphrase generation when masks are fetched, to decide whether a mask reset is needed.

Example

Here's a sketch of what a passphrase update and later mask refresh should look like on the server and client.

In the beginning there's one device key and one server-side mask. Note that we're only seeing the server masks for this specific device key. The same user will have more masks for other devices, and also for other device keys on the same device. (We could in theory use the same LKS encryption key for all device keys on one device, but we've implemented it with a unique LKS key for each device key.)

    SERVER
    key id | current | mask | passphrase gen | last reset gen
    -------|---------|------|----------------|---------------
    0x4    | *       | fabc | 1              | 1

    DEVICE
    key id | passphrase gen | device key ciphertext | [computed encryption key, not stored]
    -------|----------------|-----------------------|---------------------------------------
    0x4    | 1              | 7314ab...             | scrypt(pp1) X fabc

Using another device somewhere else, the user does a passphrase update. This adds a new mask to the server, but the device we're looking at here is unchanged. (There's now a new way to compute the encryption key, but this just a fact about the world, not actual data on disk.)

    SERVER
    key id | current | mask | passphrase gen | last reset gen
    -------|---------|------|----------------|---------------
    0x4    |         | fabc | 1              | 1
    0x4    | *       | d123 | 2              | 1

    DEVICE
    key id | passphrase gen | device key ciphertext |[computed encryption key, not stored]
    -------|----------------|-----------------------|-----------------------
    0x4    | 1              | 7314ab...             | scrypt(pp1) X fabc, scrypt(pp2) X d123

Later, our device wakes up, gets the latest passphrase from the user, and does a mask reset. It generates a new LKS key, uses that to encrypt another copy of the key locally, and then sends the new mask to the server.

    SERVER
    key id | current | mask | passphrase gen | last reset gen
    -------|---------|------|----------------|---------------
    0x4    |         | fabc | 1              | 1
    0x4    |         | d123 | 2              | 1
    0x4    | *       | e456 | 2              | 2

    DEVICE
    key id | passphrase gen | device key ciphertext |[computed encryption key, not stored]
    -------|----------------|-----------------------|-----------------------
    0x4    | 1              | 7314ab...             | scrypt(pp1) X fabc, scrypt(pp2) X d123
    0x4    | 2              | cc6142...             | scrypt(pp2) X e456

For security (and the whole point of the mask reset to begin with), the device should now delete the original device key ciphertext, and keep only the new one. It must guarantee that the server has the latest mask before it does that, to avoid accidentally losing access to the device key forever. The server could delete old device masks, but the security model here assumes that it can't reliably do that, so the masks could also be kept around for auditability, and just in case of client bugs.

Log Out

Even for users with a working OS keyring, LKS will be useful as part of the log out feature. Currently this command just invalidates your server session. It would be a good idea to also delete your LKS keys from the keyring. Since your password is already required to log back in, the added security for your device keys would have basically no downside, and the password update machinery also covers this case with no additional work.