Generally speaking, there are three steps in verifying a certificate:
Verify that the certificate has not been revoked
Verify that the certificate is valid (for instance, verify the certificate’s extensions and its validity period)
Verify the signature of the CA over the certificate
As discussed earlier, the first step consists of either consulting a CRL or an OCSP server. But to verify the signature over a certificate (or a CRL or an OCSP response), we need an authentic copy of the CA’s public key – in other words, we need another certificate, in which the original CA is the subject. In X.509, these CA certificates are issued by a higher-order CA, which in turn has a certificate from an even higher-order CA, so that a hierarchical tree structure emerges with a Root CA at the top, which certifies itself (see Figure 10.4).
Figure 10.4: X.509 hierarchical trust model. An arrow from X to Y means that X certifies Y . EE stands for End Entity
The Path Length Constraint within the Basic Constraints extension field limits the number of CA certificates that may follow a CA certificate down the tree until the EE certificate under consideration is reached. For CA0 in Figure 10.4, for example, the path length constraint could be set to 0, whereas for CA1, the path length constraint should be at least 1, lest verification of the end entity certificates for C,D, and E fails.
In practice, a CA is rarely certified by another, independent CA. Rather, there are instances within the same company that act as root CAs for their own intermediate CA instances. From a security perspective, this is equivalent to a CA self-signing its own public key. This means that, in most cases, the relying parties cannot transfer the question of whether to trust a particular CA to some independent higher-order instance, but must base their trust decisions entirely on the publicly available information about a CA, for example, the CPS. Although modern browsers contain lists of trusted CAs, it is not entirely clear how these lists come about, and they should be no substitute for making your own decisions.
If a CA is compromised, it will issue certificates for web servers with a fake identity, and impersonation attacks are the consequence, breaking entity authentication within TLS. The most serious incident of this kind goes by the name of Operation Black Tulip: In July 2011, an attacker took control of the Dutch CA DigiNotar (for more details, see Section 19.5.2 in Chapter 19, Attacks on Cryptography) and issued fraudulent certificates for *.google.com and other important domains [199].
The main target of the attack seemed to be 300,000 Iranian Gmail users, who lost their credentials for various Google services, including Google Mail and Google Docs due to the attack. The real source of the attack was never disclosed. Initially, many signs pointed toward the Iranian government, but later on, the well-known security researcher Bruce Schneier also blamed the NSA [41].
How should we deal with a rogue CA, especially the certificates issued by it? Of course, a CA compromise is a valid reason for certificate revocation, but we can neither trust a CRL nor an OCSP response signed by a rogue CA. Moreover, in most cases, we cannot rely on some independent, higher-order CA to revoke the certificate of the rogue CA. There is, however, a list of trusted CAs within modern browsers (see Figure 10.6), and indeed, trust in the DigiNotar CA was withdrawn by all major browsers by September 2011.
Figure 10.6: List of trusted CAs within Firefox
This example shows that the major browser manufacturers do have the potential to act like some global root CA. In 2015, Mozilla introduced OneCRL, where CA certificate revocation information is gathered centrally, then pushed out to client browsers on an almost daily basis. For this, all available CRLs are crawled, and revoked CA certificates as well as revoked high-profile end entity certificates, which may have a large impact on Firefox users, are included. Moreover, following a security incident such as Black Tulip, CA certificates may be entered manually into OneCRL [60]. Google’s Chrome browser uses a similar mechanism known as CRLSets. The basic idea behind both OneCRL and CRLSets is to concentrate on CA certificates to reduce the size of the lists and to rely on OCSP stapling for end entity certificates.
Another promising innovative initiative from browser manufacturers is called CRLite [108]. CRLite aims to include all revoked certificates and is currently being tested by Mozilla [89]. In CRLite, the browsers locally store certificate revocation information in a compressed form that needs only a few megabytes of storage. The browser downloads daily updates, taking up storage space in the order of kilobytes. Most importantly, these lists can be held locally, so that no privacy issues arise from checking the status of a certificate.
The CertificateVerify message provides explicit proof that the sender—either client Bob or server Alice—indeed has the private key corresponding to its certificate. Moreover, the CertificateVerify message allows you to verify the integrity of the TLS handshake up to this point. Listing 10.6 shows the structure of the CertificateVerify message:
Listing 10.6: Structure of the CertificateVerify message
The algorithm field in Listing 10.6 holds the signature algorithm used to generate the signature. The content covered by the signature includes the TLS handshake context and the certificate.
The signature is computed over a concatenation of the following data:
A string consisting of 64 bytes having a value of 32
The TLS 1.3, server CertificateVerify string for server Alice’s signature and the TLS 1.3, client CertificateVerify string for client Bob’s signature
A single byte having value 0 that acts as a separator
The content to be signed
The context string secures TLS against cross-protocol attacks by providing a way to differentiate between the signatures generated in different contexts.
Server Alice sends the CertificateVerify message when she authenticates herself to client Bob using a certificate. Client Bob sends CertificateVerify whenever he authenticates himself using a certificate. If sent, the CertificateVerify message is transmitted immediately after the Certificate message and immediately before the Finished message.
For example, if the transcript hash consists of 32 bytes having the value 01, the content covered by the signature in server Alice’s CertificateVerify message reads like this:
The sender of the CertificateVerify message computes the signature by taking the following data as input:
The data covered by the signature
The private key corresponding to the public key in the sender’s certificate transmitted in the previous TLS message
When server Alice sends the CertificateVerify message, the digital signature algorithm Alice uses must be one of the algorithms that client Bob specified in his signature˙algorithms extension.
When client Bob sends the CertificateVerify message, the digital signature algorithm must be among those specified in the supported˙signature˙algorithms field of the signature˙algorithms extension in the CertificateRequest message.
The above illustrates how TLS addresses potential compatibility issues in a heterogeneous environment where different clients must communicate with different servers, with the endpoints likely supporting different digital signature algorithms.
The receiver of the CertificateVerify message verifies the digital signature. The verification process takes the following data as input:
The data covered by the signature
The public key in the certificate from the corresponding Certificate message
The digital signature in the received CertificateVerify message
If the verification is not successful, the receiver terminates the TLS handshake and sends a decrypt˙alert alert to the other communicating party.
When server Alice sends her certificate to client Bob, the certificate must have the following properties:
The certificate must be an X.509v3 certificate (unless Alice and Bob negotiate a different certificate type).
The public key of the server must be compatible with the selected authentication algorithm from client Bob’s signature˙algorithms extension. Possible signature algorithms are RSA, ECDSA, or EdDSA.
The Certificate Key Usage field (discussed earlier in this chapter, in the X.509V3 Extension Fields section), must include the digitalSignature value. The signature algorithm must match the signature scheme specified in Bob’s signature˙algorithms and signature˙algorithms˙cert extensions.
The server˙name and certificate˙authorities extensions are used to select the certificate.
All certificates sent by server Alice must be signed by the digital signature algorithm specified by client Bob. Self-signed certificates are not validated and, therefore, can be signed with any digital signature algorithm.
If server Alice is not able to provide a certificate chain where all certificates are signed using the signature algorithms specified by client Bob, she continues the TLS handshake by sending Bob a certificate chain of her choice that might use signature algorithms not supported by client Bob.
If Bob is not able to construct a valid certificate chain using the certificates provided by Alice and decides to abort the TLS handshake, he sends a corresponding certificate-related alert. The default alert is unsupported˙certificate.
10.5.9 Client certificate selection
When client Bob sends his certificate to server Alice, Bob’s certificate must have the following properties:
The certificate must be an X.509v3 certificate (unless Alice and Bob negotiate a different certificate type).
If the certificate˙authorities extension was present in the CertificateRequest message, at least one of the certificates in Bob’s certificate chain should be issued by one of the specified certification authorities.
The certificate must be signed using one of the digital signature algorithms specified in the signature˙algorithms extension of the CertificateRequest message.
If the CertificateRequest message from server Alice has a non-empty oid˙filters extension, the client certificate must contain all extension OIDs recognized by client Bob. This extension is covered in detail in the next subsection, OID filters.
This concludes the list of requirements on client certificates in TLS. These requirements become relevant only if server Alice sends a CertificateRequest message to client Bob.
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
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].
In Chapter 5, Entity Authentication, we showed how passwords can be stored in a secure way on a server using hash functions. More specifically, each password is hashed together with some random value (the salt) and the hash value is stored together with the corresponding user ID. This system can only be secure if it is computationally difficult to invert the hash function, that is, to find a matching input for a known output. The same requirement emerges if the hash function is used in a key-dependent way in order to form a MAC (see Section 11.5, Message authentication codes).
In order to put this requirement in a more precise way, we only need to apply our earlier definition of a one-way function from Section 11.3, One-way functions, to hash functions:
A hash function hash is said to be one-way or preimage resistant, if it is computationally infeasible to find an input m for a given output y so that y = hash(m).
As is the case for second preimages, preimages for a given n-bit output will occur automatically after O(2n) trial inputs. Hash functions that are preimage resistant and second preimage resistant are called one-way hash functions (OWHF).
11.4.3 Merkle-Damgard construction
Our previous discussion of requirements on a secure hash function shows that in order to achieve collision resistance, it is important that all input bits have an influence on the hash value. Otherwise, it would be very easy to construct collisions by varying the input bits that do not influence the outcome.
How can we accommodate this requirement when dealing with inputs m of indeterminate length? We divide m into pieces (or blocks) of a fixed size, then you deal with the blocks one after the other. In one construction option, the block is compressed, that is mapped onto a smaller bit string, which is then processed together with the next block.
The Merkle-Damgard scheme has been the main construction principle for cryptographic hash functions in the past. Most importantly, the MD5 (128-bit hash), SHA-1 (160-bit hash), and SHA-2 (256-bit hash) hash functions are built according to this scheme. Later in this chapter, in Section 11.7, Hash functions in TLS, we will look at the SHA-family of hash functions in detail, as these functions play an important role within TLS.
For now, we’ll concentrate on the details of the Merkle-Damgard scheme. In order to compute the hash value of an input message m of arbitrary length, we proceed according to the following steps:
Separate message m into k blocks of length r, using padding if necessary. In the SHA-1 hash function, input messages are always padded by a 1 followed by the necessary number of 0-bits. The block length of SHA-1 is r = 512.
Concatenate the first block m1 with an initialization vector IV of length n.
Apply a compression function comp : {0,1}n+r → {0,1}n on the result, to get
Process the remaining blocks by computing
Note that each hi has length n.
Set
Note that finding a collision in comp implies a collision in hash. More precisely, if we can find two different bit strings y1,y2 of length r so that comp(x||y1) = comp(x||y2) for some given n−bit string x, then we can construct two different messages m,m with the same hash value:
The article [8] lists a number of generic attacks on hash functions based on the Merkle-Damgard scheme. Although in most cases these attacks are far from being practical, they are still reason for concern about the general security of the scheme.
Sponge construction is used in the formulation of the SHA-3 standard hash algorithm Keccak [26]. It works by first absorbing the input message into some state vector →S (the sponge). After one block has been absorbed, the state vector is permuted to achieve a good mixing of the input bits. After all input blocks have been processed, the n bits of the hash value are squeezed out of the sponge.
The detailed construction is as follows:
Separate message m into k blocks of length r.
Form the first state vector →S0 = 0b, that is, a string consisting of b 0’s, where b = 25 × 2l, and b > r.
Absorb: For each message block, modify state vector →Si−1 by message block mi and permute the result via some bijective round function f : {0,1}b → 0,1b:
The final result is a b-bit vector →Sk, into which the message blocks have been absorbed.
4. Squeeze: We are now squeezing n bit out of the state vector →Sk.
If n < r, we simply take the first n bit of →Sk:
Otherwise, we form the following string of length (12 + 2l + 1) × r by repeatedly applying the round function f on →Sk:
Afterward, we pick the first n bits again:
We will now see how hash functions are used to form Message Authentication Codes (MACs).
11.5 Message authentication codes
If Alice wants to securely transmit a message m to Bob, she must use a so-called Message Authentication Code (MAC) to prevent Eve from tampering with that message. More precisely, a MAC prevents Mallory from doing the following:
Modifying m without Bob noticing it
Presenting Bob a message m′ generated by Mallory, m′≠m, without Bob noticing that m′ was not sent by Alice
Therefore, a MAC helps us to achieve the two security objectives integrity protection and message authentication (see Chapter 2, Secure Channel and the CIA Triad and Chapter 5, Entity Authentication). Note that a MAC cannot prevent the tampering itself, nor can it prevent message replay. The active attacker Mallory can always manipulate the genuine message m, or present Bob with the message m′ and pretend that it was sent by Alice. A MAC only gives Bob the ability to detect that something went wrong during the transmission of the message he received. Bob cannot reconstruct the genuine message m from a MAC. In fact, he cannot even determine whether the wrong MAC results from an attack by Mallory or from an innocuous bit flip caused by a transmission error. Later in this chapter, we will see that this property has fundamental implications on the use of MACs in safety-critical systems.
If Alice and Bob want to secure their messages with MACs, they need to share a secret k in advance. Once the shared secret is established, Alice and Bob can use MACs as illustrated in Figure 11.2. The sender Alice computes the MAC t as a function of her message m and the secret key k she shares with Bob. She then appends t to message m—denoted by m∥t—and sends the result to Bob. Upon receiving the data, Bob uses the message m, the MAC t, and the shared secret k to verify that t is a valid MAC on message m.
Basically, there are two options to form a MAC. The first option closely follows the approach we adopted to compute digital signatures in Chapter 9, Digital Signatures. Back then, we hashed the message m first and encrypted the hash value with the signer’s private key:
Analogously, using their shared secret k, Alice and Bob could compute
as MAC. Here, encryption is done via some symmetric encryption function, for example, a block cipher (see Chapter 14, Block Ciphers and Their Modes of Operation). Note that if Alice sends m||t to Bob and Eve manages to find another message m so that hash(m) = hash(m), then Eve can replace m with m without being noticed. This motivates the collision resistance requirement on hash functions described in Section 11.4, Hash functions.
However, even if we are using a collision-resistant hash function, in a symmetric setting where Alice and Bob both use the same key k, one might ask whether it is really necessary to agree on and deploy two different kinds of algorithms for computing a MAC. Moreover, hash functions are built for speed and generally have a much better performance than block ciphers.
The second option for computing a MAC therefore only uses hash functions as building blocks. Here, the secret k is used to modify the message m in a certain way and the hash function is applied to the result:
This option is called a key-dependent hash value. In which way k should influence the message m, depends on how the hash function is constructed. In any case, if Eve is able to reconstruct the input data from the output value hash(m,k), she might be able to get part of or even the complete secret key k. This motivates the one-way property requirement on hash functions described in Section 11.4, Hash functions. A well-proven way to construct a key-dependent hash called HMAC is defined in [103].
11.5.2 HMAC construction
The HMAC construction is a generic template for constructing a MAC via a key-dependent hash function. In this construction, the underlying hash function hash is treated as a black box that can be easily replaced by some other hash function if necessary. This construction also makes it easy to use existing implementations of hash functions. It is used within TLS as part of the key derivation function HKDF (see Section 12.3, Key derivation functions in TLS within Chapter 12, Key Exchange).
When looking at the way hash functions are built, using either the Merkle-Damgard or the Sponge Construction, it quickly becomes clear that input bits from the first message blocks are well diffused over the final output hash value. Input bits in the last message blocks, on the other hand, are only processed at the very end and the compression or the round function, respectively, is only applied a few times on these bits. It is therefore a good idea to always append the message to the key in key-dependent hash functions. The simple construction
however, suffers from so-called Hash Length Extension Attacks, if the hash function is constructed according to the Merkle-Damgard scheme. Here, an attacker knowing a valid pair (m,MACk(m)) can append another message mA to the original message m and compute the corresponding MAC without knowing the secret key k. This is because
where comp is the compression function used for building the hash function.
In the HMAC construction, the input message m is therefore appended twice to the keying material, but the second time in a hashed form that cannot be forged by an attacker. More specifically, for an input message m and a symmetric key k, we have
where:
hash : {0,1}∗ → {0,1}n is some collision-resistant OWHF, which processes its input in blocks of size r.
k is the symmetric key. It is recommended that the key size should be ≥ n. If k has more than r bits, one should use hash(k) instead of k.
k′ is the key padded with zeros so that the result has r bits.
opad and ipad are fixed bitstrings of length r: opad = 01011100 repeated r∕8 times, and ipad = 00110110 repeated r∕8 times. Both opad and ipad, when added via ⊕, flip half of the key bits.
In this construction, the hash length extension attack will not work, because in order to forge MACk(m||mA), an attacker would need to construct hash(k′⊕ ipad||m||mA). This is impossible, however, as the attacker does not know hash(k′⊕ ipad||m).
More generally, the HMAC construction does not rely on the collision-resistance of the underlying hash function, because a collision in the hash function does not imply the construction of a colliding HMAC.
So, to encode a two-byte message 0x0102, Bob would interpret it as the polynomial m(x) = x8 + x, divide it by x2 + x + 1 using polynomial division, and get a remainder polynomial r(x) = 1. In hexadecimal notation, the remainder has the value 0x01. He would then append the remainder value as the CRC check value and transmit the message 0x010201 to Alice.
Upon receiving the message, Alice would perform the same computation and check whether the received CRC value 0x01 is equal to the computed CRC value. Let’s assume there was an error during transmission – an accidental bit flip – so that Alice received the message 0x010101. In that case, the CRC value computed by Alice would be 0x02 and Alice would detect the transmission error.
At first glance, this looks very similar to a MAC and, especially in systems that already support CRCs, it might be tempting to use CRC as a replacement for a MAC. Don’t! Recall that MACs are built on top of cryptographic hash functions, and cryptographic hash functions are collision-resistant. CRCs, on the other hand, are not collision resistant.
As an example, Listing 11.1 shows the Python code for computing CRC-8. This CRC uses generator polynomial x2 + x + 1 and outputs an 8-bit CRC value.
Listing 11.1: Python code for computing CRC-8 using generator polynomial x2+x+1
def crc8(data, n, poly, crc=0): g = 1 << n | poly # Generator polynomial for d in data: crc ^= d << (n – 8) for _ in range(8): crc <<= 1 if crc & (1 << n): crc ^= g return crc
Now, if you compute CRC-8 checksum values for different 2-byte messages using the code shown in Listing 11.2, you can quickly verify yourself that messages 0x020B, 0x030C, 0x0419, and many others have the same CRC value of 0x1B.
Listing 11.2: Python code to compute CRC-8 for different 2-byte messages
for i in range(0,256): for j in range(0, 256): if crc8([i,j], 8, 0x07) == 0x1b: print(f”Message {hex(i)}, {hex(j)} has CRC 0x1b”)
Consequently, if Alice and Bob were to use CRCs to protect their message integrity against malicious attacker Mallory rather than accidental transmission errors, it would be very easy for Mallory to find messages that have an identical CRC check value. That, in turn, would allow Mallory to exchange a message that Bob sent to Alice without her noticing it (and vice versa). And that is exactly the reason why a MAC needs to be collision-resistant. Moreover, and maybe even more importantly, even if Mallory cannot be bothered to find collisions for the CRC value already in place, he can simply compute the matching CRC value for a message of his choice and replace both the message and the CRC. This is possible because there is no secret information going into the CRC. To summarize, a CRC will only protect you against accidental, random transmission errors, but not against an intelligent attacker.
