Per-User Keys

Users on Keybase have one or more device keys, whose public halves are advertised in the user's signature chain, and whose private halves stay local to the device that generated them. Users can also have paper keys, which act as device keys for the purposes of recovery from lost devices.

With the rollout of teams, we introduce a new type of key: the Per-User Key or PUK. Conceptually, the secret half of the per-user key is encrypted for all of a user's active device and paper keys. The public half is advertised in the user's signature chain. When a user adds a new device, the secret-half of the PUK is simply encrypted for the new device. When the user revokes a device, a new PUK is generated, and all remaining devices get the new secret half.

Cryptographic Specifics

Users start at PUK generation 1. Every time they revoke a device, they increment their version number and roll their PUK. At generation _i_:

  • A user generates a 32-byte random seed _s_.
  • Computes _e_ = HMAC-SHA512(_s_, "Keybase-Derived-User-NaCl-EdDSA-1") and uses this value as the secret key for an EdDSA signing key. Then computes the public half, yielding keypair (E,e)
  • Computes _d_ = HMAC-SHA512(_s_, "Keybase-Dervived-User-NaCl-DH-1") and uses this value as a secret key for a Curve25519 DH encryption key. Then computes the public half, yielding keypair (D,d)
  • Computes _c_ = HMAC-SHA512(_s_, "Keybase-Derived-User-NaCl-SecretBox-1") and uses this value as symmetric secret key.

This process is repeated at every generation _i_. At any given generation, the public keys _E_ and _D_ are signed into the user's public sigchain. Whenever a new device is added, _B_ is encrypted for the new device's device key. This is an instantaneous operation and significantly improves keying performance over previous designs we've consdired and implemented. These NaCl boxes are written to the server and stored in the main DB. The current _s_ should have a box for every active device.

On device revoke, the revoking device makes a new PUK, encrypts for the private key for all remaining devices, and writes the new PUK to the sigchain along with the statement revoking the old device. Also, whenever the key rolls over, the previous seed _s_i is encrypted with _c__i_+1 via NaCl's SecretBox symmetric encryption, with a random 24-byte nonce. See newPerUserKeyPrev and openPerUsrKeyPrev for an implementation of encryption and decryption, respectively.

Sigchain Representation

The public side of PUKs are written to a user's public sigchain. To demonstrate this by example, here is the link in max's sigchain where his client added a PUK for him.

The relevant sections are:

{
  "body": {
    "per_user_key": {
      "encryption_kid": "0121f34ae7417cafa12d9d52bce5d6bdf4582f344f5aaa15022ea84d9ee54b6fe4070a",
      "generation": 1,
      "reverse_sig": "hKRib2R5hqhkZXRhY2hlZMOpaGFzaF90eXBlCqNrZXnEIwEgIFKhz54YC6M3WCKriGhYqjQrAEZMaeLZXebu5r8obpsKp3BheWxvYWTFA+R7ImJvZHkiOnsia2V5Ijp7ImVsZGVzdF9raWQiOiIwMTAxM2VmOTBiNGM0ZTYyMTIxZDEyYTUxZDE4NTY5YjU3OTk2MDAyYzhiZGNjYzliMjc0MDkzNWM5ZTRhMDdkMjBiNDBhIiwiaG9zdCI6ImtleWJhc2UuaW8iLCJraWQiOiIwMTIwNWQyZTM0YTcxM2UwMmE1ZWM1MGMzZjQxZGNkY2RhMGI5YTFkZTc0YmI1NTQ0NGNmNmI0ZGZiZjU0MTQ4N2QyNjBhIiwidWlkIjoiZGJiMTY1Yjc4NzlmZTdiMTE3NGRmNzNiZWQwYjk1MDAiLCJ1c2VybmFtZSI6Im1heCJ9LCJtZXJrbGVfcm9vdCI6eyJjdGltZSI6MTQ5ODY3NTE1MywiaGFzaCI6IjE1YTI0ZjA0MmVhODIzNjNmYjVmZmI3ZGZlYjUzM2JmYzE4YzdkNzQ3NDRkMDllYzQ2OTNjY2I3NmM2MDdjNzFkMWRmNmM1NThiMjNiNjZhNjFjMDNjMGQ5ZjBlOWM4YmE5NjExMTUyNzY1NDUzYjkyYmYyZjA4NjE0ZGVkNzI0IiwiaGFzaF9tZXRhIjoiMDdiZDU2NzZhMzgwYmU4ZDg2NWYwNmZkNDUzYzMwMTNhNTMwYTE2MzVlODk5YTg2NDRlMzUyZThiOGJiMTg2MCIsInNlcW5vIjoxMTk5MTE3fSwicGVyX3VzZXJfa2V5Ijp7ImVuY3J5cHRpb25fa2lkIjoiMDEyMWYzNGFlNzQxN2NhZmExMmQ5ZDUyYmNlNWQ2YmRmNDU4MmYzNDRmNWFhYTE1MDIyZWE4NGQ5ZWU1NGI2ZmU0MDcwYSIsImdlbmVyYXRpb24iOjEsInJldmVyc2Vfc2lnIjpudWxsLCJzaWduaW5nX2tpZCI6IjAxMjAyMDUyYTFjZjllMTgwYmEzMzc1ODIyYWI4ODY4NThhYTM0MmIwMDQ2NGM2OWUyZDk1ZGU2ZWVlNmJmMjg2ZTliMGEifSwidHlwZSI6InBlcl91c2VyX2tleSIsInZlcnNpb24iOjF9LCJjbGllbnQiOnsibmFtZSI6ImtleWJhc2UuaW8gZ28gY2xpZW50IiwidmVyc2lvbiI6IjEuMC4yNSJ9LCJjdGltZSI6MTQ5ODY3NTE4NSwiZXhwaXJlX2luIjo1MDQ1NzYwMDAsInByZXYiOiJiYWUwNWNjYWY0NzA3NDI4ZDUyNmJlYzY0MDQwMzFmYWQxZDcyMTMwYjI3NjNlMmEwYzU4MTBmOTNkZmUwNTQxIiwic2Vxbm8iOjMxMywidGFnIjoic2lnbmF0dXJlIn2jc2lnxEAekn745bQbOQLMdvurkVCQy6iKU3Tn2em8aTQlQtF5c4X0Upc+nNnQbR2KqSYNpSP2Ed83VoY0/dMKNfSZfWoNqHNpZ190eXBlIKRoYXNogqR0eXBlCKV2YWx1ZcQgDx5WL2Mwr2vEFphfaTGDtFS1jUa84efjIEmVKEXwb0qjdGFnzQICp3ZlcnNpb24B",
      "signing_kid": "01202052a1cf9e180ba3375822ab886858aa342b00464c69e2d95de6eee6bf286e9b0a"
    },
    "type": "per_user_key",
  },
}

As with any signing key, a reverse signature is computed with the new signing key over the entire JSON body, but with the reverse signature set to empty. This proves that the user knows the private key corresponding to the adverised signing_kid.

One of these links appears every PUK generation, or roughly, whenever a user revokes a device.

Teams

Teams the user is a member of will need to rotate their shared symmetric keys, but this can happen lazily (before the next write) and off the critical path (see CLKR).

Rollout

Users just joining Keybase get a PUK when then provision their first device. Some users were active before PUKs were rolled out, and their clients opportunistically upgrade to include a PUK upon software upgrade.

Note, this change introduces a new state a user can be in: they are signed up for keybase, they have device keys, but they don't have a PUK as described above. New CLI users won't get here, but legacy users and new Web users will. This makes some flows (like inviting users into teams) more complicated.