Keysets

In Tink, a Keyset is a list of keys, with one designated primary key.

Tink uses Keysets to enable key rotation. Formally, a keyset is a non-empty list¹ of keys in which one key is designated primary (the key which is used for example to sign and encrypt new plaintexts). In addition, keys in a keyset get a unique ID² and a key status which allows to disable keys without removing them from a keyset.

Keysets are the main way in which users can access keys (via the class KeysetHandle). This ensures that every user has code to handle multiple keys at once. For most users of cryptography, handling multiple keys is a necessity: it needs to be possible to change keys (old keys can be leaked, for example), and there is almost never an atomic "switch to the next key" which can be applied to the machines the code runs and all ciphertexts, globally, and in an instant. Hence, the user needs to write code which works when one changes from one key to the next one.

Note: The full support of Keysets is one big advantage Tink has over other libraries: they facilitate key rotation, which otherwise every user would have to implement by themselves.

Example: AEAD

Consider an AEAD keyset, which contains multiple keys for the AEAD primitive. As explained before, each key uniquely specifies two functions: \(\mathrm{Enc}\) and \(\mathrm{Dec}\). The keyset now also specifies two new functions: \(\mathrm{Enc}\) and \(\mathrm{Dec}\) - \(\mathrm{Enc}\) simply equals the function \(\mathrm{Enc}\) of the primary key of the keyset, while the function \(\mathrm{Dec}\) tries to decrypt with all keys, going through them in some order (see below for how Tink improves the performance of this).

It is interesting to note that Keysets are full keys: they are a complete description of the functions \(\mathrm{Enc}\) and \(\mathrm{Dec}\) used. This means that users can write a class which takes as input a KeysetHandle, expressing the idea that the class needs a complete description of objects \(\mathrm{Enc}\) and \(\mathrm{Dec}\) to function properly. This enables user to write APIs which communicate that: to use this class you need to provide me the description of a cryptographic primitive.

Key rotation

Consider a Tink user, writing a program which first obtains a keyset from a KMS, then creates an AEAD object from this keyset, and finally uses this object to encrypt and decrypt ciphertexts.

Such a user is automatically prepared for key rotation; and switching algorithms in case their current choice does not meet the standard anymore.

One has to be somewhat careful though when implementing such key rotation: First, the KMS should add a new key to the keyset (but not yet set it as a primary). Then, the new keyset needs to be rolled out to all binaries, so that every binary using this keyset has the newest key in the keyset. Only then should the new key be made primary, and the resulting keyset is again distributed to all binaries using the keyset.

Key identifiers in ciphertexts

Consider again the example of an AEAD keyset. If done naively, decrypting a ciphertext requires Tink to try to decrypt with all the keys in the Keyset, as there is no way of knowing which key was used to encrypt the keyset. This can cause a large performance overhead.

Because of this, Tink allows to prefix ciphertexts with a 5-byte string derived from the ID. Following the philosophy of 'Full Keys' above, this prefix is part of the key, and all ciphertexts ever derived with this key should have this prefix. When users create keys, they can choose whether the key should use such a prefix, or if a ciphertext format without it should be used.

Note: Some primitives don't allow such tagging; for example in a PRF there is no obvious way how to embed such a prefix. For these keys, Tink does not offer such a facility.

When a key is in a keyset, Tink computes this tag from the ID the key has in the keyset. The fact that IDs are unique² within a keyset implies that the tags are unique. Hence, if only tagged keys are used, there is no performance loss compared to decrypting with a single key: Tink only needs to try one of the keys when decrypting.

However, since the tag is part of the key, this also implies that the key can only be in a keyset if it has one specific ID. This has some implications when describing the implementation of key objects in different languages.

---

1. Some parts of Tink still treat Keysets as a set. However, this should be changed. The reason is that the order is in general important: for example, consider the typical lifecycle of a key rotation with Aead. First, a new key is added to a keyset. This key is not made primary yet, but active. This new keyset is rolled out to all binaries. Once all binaries know the new key, the key is made primary (only at this point using this key is safe). In this second step, key rotation needs to know the last key added. ↩

2. For compatibility with a Google internal library, Tink allows to have keysets in which IDs are repeated. This support will be removed in the future. ↩