10.5.10 OID filters

Using the oid˙filters extension, server Alice can send client Bob a set of pairs (Object Identifier (OID), value) that Bob’s digital certificate should match. If Alice decides to do so, she sends the oid˙filters extension in her CertificateRequest message.

The structure of the oid˙filters extension is shown in Listing 10.7. The filters variable holds a list of certificate extension OIDs with their corresponding values as defined in RFC 5280 Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile.

Listing 10.7: Structure of the oid_filters extension

struct {
   opaque certificate_extension_oid<1..2^8-1>;
   opaque certificate_extension_values<0..2^16-1>;
} OIDFilter;

struct {
   OIDFilter filters<0..2^16-1>;
} OIDFilterExtension;

If server Alice sends client Bob a non-empty oid˙filters extension, the certificate included in Bob’s response must contain all specified extension OIDs that Bob recognizes.

All specified values must be present in server Bob’s certificate for every extension OID that Bob is able to recognize. According to the TLS 1.3 specification, Bob must ignore any unrecognized certificate extension OID.

If client Bob ignores some of the required certificate extension OIDs and, as a result, the certificate that Bob presents to server Alice does not satisfy her request, Alice may either continue with the TLS handshake without appropriate certificate-based client authentication or terminate the TLS handshake and transmit the unsupported˙certificate alert.

10.5.11 Receiving a Certificate message

TLS endpoints have to follow certain rules when validating digital certificates. If client Bob receives an empty Certificate message from server Alice, Bob must immediately terminate the TLS handshake and send the decode˙error alert.

If, on the other hand, client Bob sends an empty Certificate message to server Alice, Alice is free to decide whether she continues the TLS handshake without proper authentication of client Bob—or, more precisely, a party claiming to be Bob—or terminates the TLS handshake and sends the certificate˙required alert.

Moreover, if the certificate chain received from client Bob is flawed—as an example, if it is not signed by a certification authority that Alice knows and trusts—Alice may continue or terminate the TLS handshake as she prefers.

If Alice or Bob receives a certificate that they would need to validate using any signature algorithm that uses the insecure MD5 hash function, they must immediately terminate the TLS handshake and send the bad˙certificate alert. The TLS 1.3 specification recommends Alice and Bob do the same if they receive a certificate that must be verified using a SHA-1 based signature algorithm.

Instead, the TLS 1.3 specification recommends all TLS endpoints transition to signature algorithms that use SHA-256 or stronger hash functions. In addition, TLS 1.3 allows a digital certificate that contains a key for one signature algorithm to be signed with a different signature algorithm.

10.3 Main components of a public-key infrastructure

A Public-Key Infrastructure (PKI) is a system that is able to issue, distribute, and validate certificates. While a CA is an important part of a PKI, the two terms are not the same. In order to limit the potential damage in case of a compromise, it is customary that the various operational tasks of a PKI are taken over by logically separate functional entities within the PKI, which have their own private keys. One of these is the CA. We will now take a closer look at all these entities:

• Certification Authority (CA): Within a PKI, the CA is responsible for creating, signing, and issuing the certificates. Moreover, all certificates issued by the CA should be archived in a secure manner.

When looking at Figure 10.4, it quickly becomes clear that a CA is a single point of failure within a PKI. It is therefore mandatory to run the CA within a specially secured environment with strictly enforced access control rules. Nevertheless, there have been incidents in the past where CAs have been compromised by an attacker, and we will discuss one such incident in the next section.

• Registration Authority (RA): The RA is the instance Alice sends her certificate signing request in the course of the enrollment. The RA checks the data provided by Alice in the CSR. Depending on the security level of the requested certificate, this check can happen online or offline (for example, by Alice having to appear in person at the RA and present her passport). If the check is successful, the data is forwarded to the CA, which generates a corresponding certificate.
• Directory Server (DIR): The directory server stores the certificates issued by the CA and makes them publicly available over a searchable directory.
• Validation Authority (VA): The VA is responsible for issuing CRLs and/or running the OCSP server. As such, they form another critical component of the PKI and should be secured accordingly.
• Time Stamping Server (TSS): A TSS signs documents along with the current time and date. Therefore, it can be used to prove that a document existed at a certain time. If Alice, for example, loses her private key and revokes her certificate, it is important to know which of the documents Alice has signed previously already existed before she revoked her certificate. Otherwise, Alice could claim that basically all documents she has ever signed were actually not signed by herself but by an attacker who stole her private key.

Another application is the so-called Signed Certificate Timestamps (SCTs). By way of an SCT, the CA records the exact time a certificate was issued. SCTs can be delivered to a relying party either by directly embedding them into the certificate’s extension (see Figure 10.5), by sending them in a TLS extension during the TLS handshake or as part of a response to an OCSP stapling request [51].

Figure 10.5: SCTs embedded in a certificate

10.5.12 The certificate_authorities extension

Finally, we turn to certificate authorities within TLS. TLS in itself places hardly any requirement on CAs, except that they should be able to issue X.509 certificates. However, Alice and Bob can use the certificate˙authorities extension to specify which certification authorities they support and which should be used by the receiving TLS party to select the appropriate certificates.

Client Bob sends the certificate˙authorities extension in his ClientHello message. Server Alice sends the certificate˙authorities extension in her CertificateRequest message. certificate˙authorities contains the CertificateAuthoritiesExtension data structure, as shown in Listing 10.8.

Listing 10.8: CertificateAuthoritiesExtension data structure

opaque DistinguishedName<1..2^16-1>;

struct {
   DistinguishedName authorities<3..2^16-1>;
} CertificateAuthoritiesExtension;

In CertificateAuthoritiesExtension, field authorities holds a list of the distinguished names of suitable CAs. The CA names are represented in the DER-encoded format. The authorities variable also contains the name of the trust anchor or the subordinate CA. As a result, server Alice and client Bob can use the certificate˙authorities extension to specify the known trust anchors as well as the preferred authorization space.

10.6 Summary

In this chapter, we have discussed digital certificates as a means to provide authenticity for public keys, and the bodies that issue certificates, Certification Authorities (CAs). In particular, we looked at the minimum set of data that needs to be presented within a certificate, and the optional parts of a certificate.

Regarding CAs, we discussed their tasks and the processes for obtaining and validating certificates. We have also seen how CAs fit into the larger structure needed to manage public keys, the Public-Key Infrastructure (PKI).

After these more general considerations, we looked in detail at how digital certificates are handled within the TLS 1.3 handshake protocol.

The next chapter will be more technical again, as it discusses hash functions and message authentication codes. Apart from digital signatures (which also use hash functions), they are the main cryptographic mechanisms for providing authenticity to handshake messages.

11.1 The need for authenticity and integrity

Imagine Alice being a control computer in a train control system and Bob being a board computer installed within a train. For a more realistic scenario, let’s assume the train control system is a positive train control. This means that the train is only allowed to move if it receives an explicit move message from the train control. Otherwise, the train does not move.

Further, assume that there are two different move messages that onboard computer Bob can receive from control computer Alice:

• Message ms instructing the train to move slowly, for example, before entering a train station
• Message mf instructing the train to move fast

In addition, to secure the train control against cyberattacks, the communication channel between Alice and Bob is protected using a cryptographic mechanism that provides confidentiality only. That is, Alice and Bob share a secret key k and can compute an encryption function ek to make their communication unintelligible to the attacker, Mallory. However, they have no means to detect manipulation of the encrypted messages. The setup is illustrated in Figure 11.1.

Now, while Mallory cannot read the clear text communication between Alice and Bob, she can record and manipulate the encrypted messages. So, when Alice sends Bob the message ek(mf), Mallory simply changes it to the message ek(ms). Upon receiving the manipulated message, Bob decrypts it and obtains ms. Because ms is a legitimate message in the train control system, the onboard computer Bob accepts it and makes the train go slower than it is supposed to go, resulting in a delay at the next train station.

In cryptographic terms, the above attack works because Bob cannot verify the integrity of the message he received. After decrypting the message, Bob can determine whether it is in principle a valid train control message, but he has no way to check if it was manipulated en route.

Figure 11.1: Example setting ensuring confidentiality, but not integrity and authenticity

Next, imagine a scenario where the train is halted for safety reasons, say, waiting for another train coming from the opposite direction to pass. Since our example is a positive train control, no messages are sent by the control computer Alice to the onboard computer Bob and, as a result, the train remains halted. What happens if Mallory sends the message ek(ms) to Bob?

Upon receiving ek(ms), Bob decrypts it and obtains the clear text message ms telling the train to move slowly. Again, ms is a valid message in the train control system and so is processed by onboard computer Bob. The train is set in motion and, as a result, causes an accident if there is no human operator in the loop to react in a timely way.

From the cryptographic perspective, the above attack is possible because Bob cannot verify the authenticity of the received message ek(ms). While he can check that the plain text message ms is a valid message, Bob cannot determine whether it was actually sent by Alice or by someone else. In other words, Bob is not able to verify the origin of the message. Moreover, there is no way for Bob to verify the freshness of the message, which opens up further attack possibilities for Mallory (this was already discussed earlier, in Section 2.5, Authentication in Chapter 2, Secure Channel and the CIA Triad).

11.2 What cryptographic guarantees does encryption provide?

On a more fundamental level, the attacks described in the above examples work because Alice and Bob, as illustrated in Figure 11.1, can only use encryption ek.

Intuitively, it might seem as if encryption protects Alice’s and Bob’s messages against manipulation by Mallory because the ciphertext hides the plaintext message and Mallory cannot know how to manipulate the encrypted message in a meaningful way. But this is completely wrong! Encryption provides no guarantees for message integrity or authenticity.

We can convince ourselves that this is indeed the case by taking a closer look at the one-time pad encryption scheme from Chapter 4, Encryption and Decryption.

Recall that the one-time pad encrypts a message m under the key k as:

where ⊕ denotes a bit-wise exclusive OR (XOR) operation. If you take two bits b0,b1 and apply the XOR operation to them, b0 ⊕ b1 will yield zero whenever both bits have the same value (that is, both are zero or both are one) and one whenever the bits have a different value.

To decrypt a message encrypted under the one-time pad scheme, the receiver computes:

In the case a one-time pad is used, it is very easy for Mallory to manipulate the ciphertext c because every bit flip in the ciphertext leads to the same bit being flipped in the decrypted message.

In other words, if Mallory has a ciphertext c that encrypts Bob’s message m, she can easily generate a manipulated ciphertext c′ that encrypts the same message as m, but with one or more bits of Mallory’s choice flipped.

Thus, even a perfectly secret – that is, information-theoretically secure – encryption scheme does not provide message integrity. The same is true for stream ciphers because, as we have seen in Chapter 4, Encryption and Decryption, their encryption operation is identical to encryption using the one-time pad: the plaintext is simply XORed with the key stream.

Intuitively, one might think that block ciphers – a class of much stronger encryption algorithms we will learn about in Chapter 14, Block Ciphers and Their Modes of Operation – are resilient against the above manipulations and would offer some degree of integrity. After all, modern block ciphers are pseudorandom permutations where a one-bit change in the plaintext results in the change of roughly half of the bits in the ciphertext.

As a result, if Mallory changes only a single bit in ciphertext c to obtain a manipulated ciphertext c′, the decryption result p′ = dk(c′) will be totally different from the genuine decryption result p = dk(c). It turns out, however, that even this property does not help with message integrity and authenticity!

As an example, if a block cipher is used in the so-called electronic codebook (ECB) mode (more on this in Chapter 14, Block Ciphers and their Modes of Operation) and Mallory flips a bit in the i-th block of the ciphertext, only the i-th block of the plaintext will change when Bob decrypts the manipulated ciphertext.

Alternatively, Mallory can manipulate the order of blocks in the original ciphertext c to obtain a manipulated ciphertext c′. When Bob decrypts c′, he will obtain a manipulated plaintext p′ where the individual blocks are identical to those of the genuine plaintext p, but their order is manipulated (their order is the same as in c′).

If only encryption is used, Bob is not able to detect these manipulations. Moreover, this is independent of the type of symmetric key encryption algorithm used by Bob. We can therefore conclude that encryption alone provides only confidentiality, but not message integrity or authenticity.

11.3 One-way functions

In Chapter 4, Encryption and Decryption, we learned that the notion of computational security is built on the concept of pseudorandomness, the idea that bit strings can look completely random even though they are not. In fact, pseudorandom generators, functions, and permutations form the basis of modern symmetric key cryptography. As being one-way is also one of the defining properties of a cryptographic hash function, we chose to include a more formal discussion of this property in this section, even though it is fundamental for the whole of cryptography.

This is because mathematicians have proved that pseudorandom generators, functions, and permutations can be constructed from one-way functions.

As a result, the existence of one-way functions is equivalent to the existence of any non-trivial symmetric-key cryptography [97]. This means, if we can find functions that we can prove to be one-way, we can use them to construct symmetric-key cryptographic schemes, for example, symmetric-key encryption algorithms or keyed hash functions, that are provably computationally secure.

The good news is that there is a number of functions mathematicians have studied for decades that exhibit one-way properties. We will cover some of the most prominent examples of such candidate one-way functions in a minute.

The bad news is that the currently known candidate one-way functions are much less efficient than constructions actually used in practice, say a modern block cipher. Bridging this gap between theory and practice is one of the most important open research problems in modern cryptography as it allows you to build provably-secure pseudorandom generators, functions, and permutations.

11.3.1 Mathematical properties

A function f : X → Y is called a one-way function if f(x) is easy to compute for all x ∈ X, but for essentially all elements y ∈ Y it is computationally infeasible to find any x ∈ X such that f(x) = y [117]. Such an x is called a preimage of y.

Here, easy to compute simply means that for any given x ∈ X, Alice and Bob can compute f(x) in polynomial time.

The requirement that it is computationally infeasible for Eve to find any x ∈ X such that f(x) = y means that a one-way function must be hard to invert. Since modern cryptography is about specifying cryptographic algorithms that are secure against a probabilistic polynomial-time attacker – to put it more precisely, that can be broken by a probabilistic polynomial-time attacker with only negligible probability – a function f is considered hard to invert if no probabilistic polynomial-time algorithm is capable of finding a preimage x ∈ X for any given element y ∈ Y , except with negligible probability.

The definition of what it means for a function to be hard to invert might seem complicated at first. But it actually only excludes two extremes:

• It is always possible to guess a preimage x. Since we can choose the size of the range of f, that is, the set {y = f(x) ∈ Y |x ∈ X}, when designing a cryptographic algorithm, we can make the likelihood of a successful guess arbitrarily small, but never zero. As a result, we need to account for the fact that Eve could find a preimage y for a randomly chosen x with negligible probability.
• It is always possible to find a preimage of y by brute-force searching the domain of f(x), that is, by simply trying all values of x until one produces the correct y. Such a brute-force search requires exponential time. As a result, we exclude this extreme by requiring f to be computationally infeasible to invert only for probabilistic polynomial-time algorithms.

Summing up, a function y = f(x) is said to be one-way, if it is hard to invert for all values of y. If there is a probabilistic polynomial-time algorithm that can invert f for some values of y with a non-negligible probability—even if this probability is very small—then f is not a one-way function.

Because the brute-force search runs in exponential time and always succeeds, the existence of one-way functions is an assumption about computational complexity and computational hardness [97]. In other words, it is an assumption about the existence of mathematical problems that can be solved in principle, but cannot be solved efficiently.