- COMP.SEC.100
- 19. Applied Cryptography
- 19.3 Key management
Key management¶
Keys are needed both for physical locks and for cryptographic algorithms. In the latter case, there are both symmetric and asymmetric keys. For all types of keys, it is important that the right individuals have the keys they need and others do not. Key requirements vary, and many things can happen to keys, from loss to unauthorised copying. All of this imposes administrative requirements on those whose interest is to protect data or physical locations using these keys. It is essential to note that most of these management tasks do not fall within the responsibilities of a locksmith or a cryptographer.
The challenge of key management can be understood by considering one’s own password management—assuming the same password is not used everywhere. A modern person needs passwords for so many purposes that it is impossible to remember them all. Nor should all passwords be stored on the same device, as this would create a problem if it were lost.
Behind passwords lie devices, processes, services, communication, and data. The relationships between these entities require cryptographic keys. In many cases, some other entity must also know the same key—or its counterpart, if the cryptosystem is asymmetric. This other entity is often outside one’s own sphere of control and is trusted to varying degrees.
Key management may involve many different stages, as keys also have a lifecycle. This leads to the development of their own information systems.
An important example of the need for key management is storing data outside devices under one’s own control, especially in the now popular “cloud”. The data stored ranges from traditional concrete files to traces generated by one’s activity on the internet. Protecting this data—at a minimum by encrypting and decrypting it—requires keys. Thus, keys themselves also become data that must be stored, and their storage can likewise be outsourced. Fortunately, the volume of keys is much smaller than that of other data, allowing protection efforts to be focused on them. Other measures are also required, but at the core of information management lies key management.
Key lifecycle¶
One way to “create” a cryptographic key is generation. To ensure sufficient entropy, this requires a cryptographically strong pseudorandom source or even a source of true randomness. Keys can also be derived from existing keys using appropriate cryptographic algorithms, referred to as KDFs (key derivation functions). Once created, a key must be stored securely.
Keys must typically be distributed securely to where they are used. An obvious example is a public key, but this is also possible with symmetric keys. For instance, a key required by a smart card or an IoT device may have been generated outside the device. Another example is a session key, that is, a key protecting a single communication session (or message), which is generated by one party and transmitted to another using asymmetric encryption.
The use of a key means protecting data in some manner. It may be necessary to set limits on how much data can be protected using the same key before the key must be replaced or updated. Such limits may arise from the cryptographic method in use. For example, the latest version of the TLS specification, TLS 1.3, includes recommendations on how much data can be protected with each AEAD key of the protocol, depending on the security bounds of the underlying construction. TLS includes a subprotocol for key updating, allowing new keys to be established within a protected connection.
In addition to the amount of data protected by a key, key management must track the key’s age and trigger renewal accordingly. It is also good practice to associate a usage purpose with a key, possibly including additional restrictions. In public-key certificates, this information is encoded within the key. This practice is not limited to public keys but follows the general—and frequently violated—principle of key separation, which states that a given key should be used for only one purpose or within a single algorithm.
A key may need to be revoked if it is found to be compromised. This must, of course, be communicated to those who relied on the key.
Keys may also need to be archived, so that data they protect can be accessed when necessary. Archiving involves long-term secure storage and may include encrypting the key with other keys, which themselves require management. Finally, keys must be deleted securely at the end of their lifecycle. This may involve physically destroying storage media or carefully overwriting the keys.
It is evident that the lifecycle of a key and the associated processes must be carefully considered and documented as part of the design process in all systems using cryptography.
Keys can be compromised in many ways. Causes may include poor randomness, insecure transport to the point of use, insecure storage, side-channel attacks during use, and inadequate deletion. It is often more effective to target keys and their management rather than the algorithms that use them.
Key derivation¶
Key derivation refers to the creation of new keys from a single key, the root key. This is done using specially constructed cryptographic hash functions, which typically take as input, in addition to the key, so-called salt bits, ensuring that different derivations produce different keys. The input may also include an iteration count, specifying how many times the function is applied internally. This can be used to make computation sufficiently slow that, even if the result is revealed, it is not practical to try to determine the original input. Such slow functions are needed when the root key is a password (see the next section)—including for password storage. When the root key has sufficient entropy, the slowness of the KDF is neither necessary nor desirable.
The specialised construction mentioned above may refer to a function specifically designed for KDF use, but often it involves applying a standard hash function. This is particularly the case for the general-purpose HMAC-based KDF, HKDF. General-purpose here means that the specification of HKDF accounts for inputs of varying lengths and different required output lengths. The salt may be provided or omitted.
In broad terms, HKDF operates as follows: let H be an HMAC construction based on a hash function such as SHA-256, where H takes a key and data as input. If J is the root key and s is the salt (or a zero string), we first compute the initial key K = H(s, J). Additional keys are then extracted from the sequence K1 | K2 | K3 …:
k0 = empty
k1 = H(K, k0 | 1)
k2 = H(K, k1 | 2)
k3 = H(K, k2 | 3)
….
It is useful to compare the idea of HKDF with how a block cipher is used to generate a keystream. It can be seen as a combination of CTR mode and OFB mode. Feeding each ki into the next H computation corresponds to OFB mode, while supplying the counter values 1, 2, 3, … corresponds to CTR mode.
Above, the first step of HKDF was H(s, J), where the salt acts as the HMAC key and the root key J serves as the data. Even if s is a zero string, it has the length of an HMAC key, while J may be of arbitrary length. For example, it may be a large integer resulting from a Diffie–Hellman key exchange.
KDF usage facilitates adherence to the key separation principle. For example, it suffices to use a single symmetric key and derive from it two keys, so that the encryption key and the MAC key for a message are different. Of course, AE schemes perform a similar separation internally and more efficiently. Another example is using a KDF to derive a new key for each application of an encryption algorithm, for example for each transaction. In this case, it is advisable to include as input some identifier derived from the transaction. HKDF also accounts for this, as a place is defined for such data between ki and the counter.
Another possibility is to derive new keys from already derived keys, resulting in a key hierarchy (or key tree). For example, a bank may have a master secret for an entire payment system, from which the secret of each card is derived. Transaction-specific keys are then derived from the card’s secret. A similar hierarchy also appears in certificates. In both cases, storage and use of the master key are typically handled using specialised hardware.
Password-based key derivation¶
A very common practice is to derive keys from passwords. An important property of password-based KDFs, PBKDFs, is slowness. This prevents attackers from performing exhaustive searches. The slowness can be adjusted using an input parameter that determines the number of internal iterations. This may correspond to tens of thousands of hash computations. Another important parameter is the salt (see Key derivation). It is a plaintext random string of tens of bits. When included in the computation, the same password will produce different keys in different contexts with very high probability. As a result, an attacker cannot use a precomputed table of password guesses and their corresponding PBKDF values. Without a salt, such a table can be used to find the password corresponding to a given PBKDF value much faster than computing the function each time. Precomputation would have to be multiplied to cover all possible salt values, which is not practical.
An alternative to deriving a key directly from a password is to use password authentication within a key exchange protocol. The result is password-authenticated key exchange, or PAKE. Even the PIN of a smart card may be sufficient as a starting point for key derivation. A PAKE protocol developed for that purpose is called PACE, password authenticated connection establishment.
Key generation¶
When a key must be created for a cryptosystem and cannot be derived from any previous key, one needs as genuine random bits as possible. These could be obtained from electronic noise, cosmic noise, or quantum effects. In practice, one is likely to rely on pseudorandom bits provided by the operating system, which are collected from environmental sources (cf. section Random…). Tossing a coin would be a good method but too slow.
One option is to use a PUF device, where given inputs produce unique responses: it is not possible to copy the device such that the copy would produce the same outputs for the same inputs. The name PUF comes from Physical Unclonable Function. In manufacturing a PUF device, randomness is introduced, for example by scattering particles into an optical component. Ordinary microchips also exhibit PUF characteristics, from which actual PUF devices can be developed. By measuring signal delays and their differences, even identical chips can be distinguished. When designing a PUF device, it is necessary to ensure that the measured differences are suitably distributed and cannot be modelled computationally. Nevertheless, considerable post-processing may be required to correct errors and achieve good randomness properties. A simpler PUF application than key generation is device identification in trusted computing. PUFs are also suitable for challenge–response authentication.
When a generated key is to be used in an asymmetric algorithm, algebraic properties are often required. It may be necessary to generate several candidates or perform further computations to find, for example, a random prime among random numbers. Cryptosystem specifications and implementations typically include a procedure for this. Thus, externally, a cryptosystem generally requires only a standard source of random bits.
Key generation can be challenging to implement in constrained environments, such as smart cards. Especially in identity card applications, the key should not be generated outside the card and then loaded into it. Although processors have become more powerful, there may be a temptation to optimise the generation process too aggressively within them, at the expense of security.
Key storage (advanced)¶
Once keys have been created, they usually need to be stored. Exceptions include cases where keys can be regenerated from a password provided by the user. It may also be that a key is immediately encapsulated into a message to be transmitted and is no longer needed locally.
Typically, the storage location must be protected so that keys do not fall into the hands of an attacker. Often, the only protection is the operating system’s access control combined with hardware-based memory partitioning, which keeps processes separate from one another. Local attackers may bypass such protection mechanisms using low-level techniques that exploit shared resources between processes, such as caches, as discussed in the section on cryptographic challenges. This is a significant issue in multi-user environments, such as cloud systems, where a customer has little control over what other processes are running alongside their own. The problem also arises in single-user environments when the risk of malware is taken into account.
A particular challenge arises when a web browser must implement operating system–like protections between code running in its different tabs. The browser process includes cryptographic operations that are also connected to processes on web servers. The Heartbleed incident in 2014 was a case where a private key stored on a server could be exposed to an attacker. The underlying cause was a simple software vulnerability that allowed reading beyond the bounds of a buffer in the TLS/DTLS Heartbeat protocol implementation in OpenSSL. Strong cryptography was powerless in this case.
When cryptographic keys must be stored in memory or program code, obfuscation techniques are often used to make keys harder to identify and extract. There are also tools designed to reverse such obfuscation. This is another area of ongoing arms races. The use of obfuscation is not limited to cryptographic programming (it may be used for protecting intellectual property or hiding malware, but as a privacy technique, obfuscation is lossy blurring).
Specialised hardware offers an alternative to storing keys in the same memory as ordinary data. Such devices are available in all sizes and price categories. For example, a smart card may cost only a few cents to manufacture but can be well protected against both passive and invasive attacks targeting the keys stored within it. A well-designed smart card interface strictly limits the interaction between the card and the card reader communicating with it. In particular, no command should cause the card to output its keys directly. Instead, the reader can only send data to the card for processing and receive the results of cryptographic computations performed by the card. In other words, the reader can interact with the card’s secrets only via a crypto API. Smart cards are typically limited in bandwidth and computational capacity.
At the other end of the spectrum are HSM modules (Hardware Security Modules), which may cost several thousand euros. In addition to providing better capabilities, they are often certified according to high-level security standards (e.g. the NIST FIPS 140 series). HSMs are commonly used in the financial sector and are now also offered in cloud environments. Like smart cards, HSMs provide key storage and usage functions through a strictly controlled API. Through this interface, the protection of the HSM can be extended to keys stored elsewhere. The idea is simply to encrypt them using a key-encryption key that remains inside the HSM. The HSM can then be asked to decrypt them when needed. Naturally, re-encryption is required for transporting the key if the HSM is located across an untrusted link.
Technologies for trusted execution environments, such as TPMs, also provide hardware-supported storage for keys. Examples include Intel SGX and ARM TrustZone. These also offer more general capabilities. In mobile devices, operating systems such as Android and iOS provide similar key storage: Android Keystore and the iOS Secure Enclave are essentially mini-HSMs.
Key transport (advanced)¶
Depending on the system architecture, keys may be created in a different location from where they are used. Couriers and courier services have been used, even in the digital era, to transport keys physically—initially on paper tapes and later on magnetic media. A similar approach, still used in consumer applications such as wireless home routers, is simply to print the key on the back of the device. In this case, security relies on the physical security of the device.
Another approach is widely used in mobile communications and banking. Symmetric keys are embedded in inexpensive security modules distributed to customers, such as SIM cards and bank cards. Copies of these keys are stored by the service provider. In mobile communication, this is done in the logical network component AuC (authentication centre), and the key is used to authenticate the SIM card to the network and to derive session keys. In banking applications, the symmetric keys of cards are typically derived from master keys stored in the bank’s HSM.
If a key is already in place, it can be used to transport new keys. With the invention of public-key encryption, the problem of key transport has been reduced to the problem of delivering an authentic copy of the recipient’s public key to the sender. Since the key does not need to be secret, this is easier than transporting a secret key. It is nevertheless still a significant challenge (cf. PKI). Earlier versions of the TLS protocol used key transport mechanisms where the key was encrypted with the recipient’s public key. Other required keys were then derived from it using a KDF at both ends. More recently, the root key for KDF is established using key exchange protocols.
Key update and forward security (advanced)¶
If a symmetric key protecting communication between two parties is compromised, the security of all data encrypted with that key is lost. This motivates regular key updates. Another reason is that the formal security analysis of some systems, such as AEAD, guarantees security only up to a certain amount of encrypted data.
There are several mechanisms for updating symmetric keys. A simple technique is to derive a new key from an existing one using a KDF. This forms a key chain. The idea is that if a key is compromised at some point, earlier keys cannot be recovered. Of course, it is possible to compute all subsequent keys using the KDF, as the legitimate parties must be able to do. The protection of previous keys even if the current key is compromised is known as forward secrecy (sometimes forward security or perfect forward secrecy). The term is easier to understand when considering it from the perspective of each earlier key (and message): they remain secure in the future even though new keys are only derived (and not freshly generated).
Another method for updating a symmetric key is to transport new keys from one party to another encrypted with the recipient’s public key. If the threat model includes the attacker’s ability to break the recipient’s private key, this method does not achieve forward secrecy. Achieving forward secrecy assumes that the attacker may be able to compromise session keys. The ability to break a private key does not meaningfully differ from this—and not at all if keys must be disclosed, for example due to legal requirements.
Forward secrecy can be achieved by using ephemeral Diffie–Hellman key exchange, authenticated for example with the parties’ signatures. Here ephemeral means that the Diffie–Hellman values are generated separately for each key update of a session. The result of the key exchange leaves only the session key, with no link to other keys. Even in this case, an attacker may have compromised the parties’ authentication keys and cannot be prevented from conducting a man-in-the-middle attack. This would lead the parties to agree on new session keys with the attacker instead of with each other. Future keys would then also be compromised, but previously established session keys would still remain secure. They cannot be recomputed by either honest party, nor even jointly. This is distinct from whether either party has stored an earlier message in plaintext or archived it poorly encrypted.
As noted above, achieving protection in the opposite direction (i.e. after compromise) is more difficult. The attacker is already “inside” and controls future communication. Ephemeral Diffie–Hellman could help restore security, provided that at least one key exchange can occur without the attacker being able to intervene.
Public key management and public key infrastructure¶
Binding public keys to identities using certificates¶
The central challenge of public-key cryptosystems is how a public key can be linked to the entity (a person or a machine) that possesses the corresponding private key. The owner of the private key can, of course, demonstrate that a given public key is theirs by using it. This linkage is mathematical and is used, for example, in authenticating the entity. The problem, however, is that nothing about the identity of that entity can be assured in this way. An additional mechanism is needed to associate the public key with trustworthy information about who holds the corresponding private key.
In a passport or other conventional identity document, a person’s identity is traditionally linked, through an authority’s assurance, to a photograph and signature representing them, and nowadays also to other biometric data. When such a document is used for authentication, one’s physical appearance and ability to sign effectively act as a private key, verified against the public key (the photograph and specimen signature).
Binding a public cryptographic key to a person’s identity could in principle be done in the same way that a photograph is linked to a name in a passport. However, this would not be very useful in networked environments. Instead, the binding is performed by cryptographic means—simply by digitally signing a short document that contains both pieces of information to be bound. This signed document is called a public key certificate, or simply a certificate. Its contents and structure are defined by the X.509 standard.
The certificate’s signature is almost the only aspect of binding public keys to identities that falls within the domain of cryptography. The rest is largely administrative, although additional cryptography is used to secure various stages. The overall system is referred to as a public key infrastructure, or PKI. Its purpose is to manage public keys and their certificates within an organisation, a society, or a part of one. A central role in such systems is played by the trustworthiness of certificate issuers and the extent to which others trust their signatures. These issuers are generally called certificate authorities.
All parties should be able to trust the CA, particularly that it verifies the identity of each of its clients. Certification is a large business, and the more common targets are servers and websites rather than individuals.
Website certificates are a central and visible example of PKI, referred to as the web PKI. Web browser vendors embed in their software a list of the public keys of a few hundred root certification authorities and update this list periodically via their software update mechanisms, which themselves may rely on separate certificate structures. Website operators obtain certificates that bind their URLs to their public keys. These certificates are often not issued directly by root authorities but by intermediate authorities, which in turn have certificates signed by root authorities. When TLS is used to secure communication between a browser and a website, the server sends a certificate chain to the browser. At the end of the chain is a copy of the server’s public key, which TLS then uses to authenticate the site. Before proceeding, the browser verifies this certificate (checking the signature and the URL), using the next certificate in the chain. This verification process continues until a certificate is reached whose public key is already included in the browser’s list of trusted root authorities.
The functions and practices of the web PKI are managed by the CA/Browser Forum (founded in 2005). To promote trust, extended validation certificates (EV certificates) have been available since 2007. A certification authority issuing such certificates must undergo an approval process and verify the certificate applicant more thoroughly than usual. Browsers display more detailed information to users for EV certificates.
Dependence on naming, certification processes, and time¶
Binding a public key to a specific entity requires a stable and controlled naming mechanism, and the entity must be able to prove to the certification authority that they possess the claimed identity. The CA must require such proof, verify it, and act accordingly, issuing certificates only to legitimate parties. This is ultimately a matter of trust and also involves a legal and regulatory perspective.
In the web PKI, numerous cases have occurred where certification authorities have issued incorrect certificates, either because they were compromised (e.g. DigiNotar in 2011), because the issuance process was poorly managed (e.g. TurkTrust in 2013), or because governments have sought surveillance capabilities over their citizens. In other cases, authorities have been found to inadequately protect their signing keys.
In response to the growing number of such cases, Google launched the Certificate Transparency project (2013; see also RFC 9162, 2021). The goal is to use logs and monitoring to record information about all certificates issued by publicly trusted certification authorities, enabling detection of incorrectly or maliciously issued certificates.
A party relying on a certificate requires accurate time information to ensure that the certificate is currently valid. Otherwise, an attacker could use an expired but otherwise valid certificate to trick a victim into using a public key whose corresponding private key has been compromised. Providing accurate time information can be difficult in low-cost or constrained environments, such as IoT systems.
Dependence on certificate status information (advanced)¶
A relying party needs information about the status of a certificate, i.e. whether it is still valid. For this purpose, certification authorities may periodically distribute certificate revocation lists (CRLs) and updates to them. Another option is for the relying party to perform a real-time check with the issuer using the OCSP protocol (Online Certificate Status Protocol). Using lists is a more privacy-preserving approach than using a protocol, but it introduces a time window for attackers between the moment of revocation and the distribution of the CRL. Using a protocol provides up-to-date information, but requires major certification authorities to provide significant bandwidth and computational resources to serve online requests.
In web environments, OCSP has become the dominant method for checking certificate status. The data transfer issue is mitigated by OCSP “stapling”, where the web server holding the certificate performs its own OCSP checks more frequently than CRL publication and attaches the signed response from its certification authority to the certificate.
Dependence on software and cryptographic integrity (advanced)¶
The relying party’s software must function correctly when verifying certificate chains. This is not trivial, given the complexity of X.509 data structures and their encoding. There have been numerous failures. A well-known example is Apple’s “goto fail” incident in 2014. The code line goto fail; was accidentally duplicated. The first occurrence was executed conditionally, based on a preceding if statement, but the second was always executed. The issue occurred in error handling in Apple’s TLS implementation during certificate verification. The result was that all certificate checks were bypassed, meaning that the public key of a web server could be either genuine or generated by an attacker.
The industry relying on certificates has been slow to respond to advances in cryptanalysis. SHA-1 is a good example. The first practical breaks of SHA-1 were demonstrated in 2005. Already at that stage, cautious cryptographers recommended removing SHA-1 from applications requiring collision resistance. After 2005, cryptanalysis of SHA-1 continued to advance, culminating in the first public collision demonstrations in 2017. This was followed in 2019 by a chosen-prefix collision attack, which directly threatened the use of SHA-1 in certificates. Despite this trajectory being clear for over a decade, major web browsers only stopped accepting SHA-1 in Web PKI certificates by 2017. Even today, SHA-1 certificates can still be found in payment systems and elsewhere. Organisations maintaining such systems are naturally resistant to change, as they must manage complex systems that continue operating across technological shifts. They lack cryptographic agility.
Alternative approaches to public key management (advanced)¶
An alternative to hierarchical PKI is the web of trust. In this model, users of the system vouch for each other’s public keys by cross-certifying them. It remains the basis of the PGP system (Pretty Good Privacy, 1991–), but has not become widely adopted in other contexts. Such systems impose significant usability challenges on ordinary users.
Identity-based cryptography (IBC) provides a technically attractive alternative to traditional public-key cryptography. A trusted authority (TA) derives users’ private keys directly from their identities using its own master private key. The advantage is that public keys do not need to be distributed. The relying party need only know the other party’s identity and the TA’s public key. However, this is not suitable for all applications, as sufficient trust cannot always be placed in the TA. It would be capable of forging users’ signatures and decrypting ciphertext intended for them. In enterprise security applications, such a key escrow property may, however, be beneficial. (Key escrow generally refers to providing a “backup key” to a third party.)