Keysets

Tink uses Keysets to enable key rotation. Formally, a keyset is a non-empty list1 of keys in which one key is designated primary (the key which is used to e.g. sign and encrypt new plaintexts). In addition, keys in a keyset get a unique ID2 and a key status which allows to disable keys without removing them from a keyset. We will discuss these things in detail later.

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. We claim that 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.

The full support of Keysets is one big advantage Tink has over other libraries: they facilitate key rotation, which otherwise every user should reimplement.

Example: AEAD

Consider first 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 specifies two new functions \(\mathrm{Enc}\) and \(\mathrm{Dec}\): \(\mathrm{Enc}\) simply equals the function \(\mathrm{Enc}\) of the primary key of the keyset. The function \(\mathrm{Dec}\) tries to decrypt with all keys, going through them in some order (but see below for how Tink improves the performance of this).

It is interesting to note that Keysets are full keys in the above sense: 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. In other words, this enables user to write APIs which communicates '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.

Tagging 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 be 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 format without it should be chosen.

Some primitives do not 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 we describe the implementation of key objects in different languages later. Note that keys which are not in a keyset do not have such a requirement.


  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 were repeated. This support will be removed in the future.