HSM-memory-efficient means of providing HSM-based PKI operations for vehicle controllers

A method for certificate chain validation is disclosed for memory-efficient execution inside a secure execution environment of a hardware security module (HSM), despite very limited memory being inside the HSM. This is achieved by allocating enough HSM memory for at least the root certificate, a signer certificate, and a certificate to be validated, and replacing the signer certificate as the certificate chain is traversed. Revalidation of data is implemented by computing secure tags that enable the HSM to quickly recognize previously validated data. Chain validation is only considered provisional until checked against a CRL, which can be provided to the HSM in a streaming fashion, and each received serial number in the CRL is checked against the list of serial numbers representing the provisionally verified chain.

FIELD

The device and method disclosed in this document relates to hardware security modules and, more particularly, to memory-efficient cryptographic operations on a hardware security module.

BACKGROUND

Unless otherwise indicated herein, the materials described in this section are not admitted to be the prior art by inclusion in this section.

Vehicle controllers in modern vehicles are often provided with hardware security modules (HSMs). HSMs are separate compute environments in which secure operations can be performed and in which sensitive data is kept secure from spying and interference, from both external entities as well as from other processors in the vehicle controller itself. Sensitive data may include digital certificates, public keys, private keys, symmetric keys, nonces, and secure counters. However, vehicle controllers are often cost-optimized and, as a result, the amount of data which can be securely located in the HSM of typical vehicle controller is not large. The total memory available to the HSM of a typical vehicle controller is often in the hundreds of kilobytes. In addition to the sensitive data, this limited total memory must contain the program code of the HSM itself.

Vehicle controllers in modern vehicles have increasingly made use of a Public-Key Infrastructure (PKI) to secure their software integrity, updates, and communications. The certificates of the PKI, which potentially need to be stored in the HSM, typically require some small number of kilobytes each. Thus, it often becomes impossible to store all of the sensitive data inside the HSM, such as the PKI certificates, cryptographic keys, and other data, in addition to the program code of the HSM. This means that, in typical vehicle controllers, much of the sensitive data—usually the bulk of the PKI certificate hierarchy—is stored outside of the HSM in a less secure storage environment. As a result, sensitive calculations involving the PKI certificates are often disadvantageously performed outside of the secure execution environment provided by the HSM. Alternatively, vehicle controllers that do perform such calculations inside the HSM are constrained by the limited number of certificates that can be stored in the HSM.

This problem is compounded by the trend for vehicle OEMs to align the design of vehicle controller security architecture with the existing security architecture of the public internet, resulting in the adoption of X.509 certificates for vehicle PKI. The size of an X.509 certificate is typically more than a thousand bytes, greatly increasing the total size of a PKI certificate tree. Furthermore, vehicle OEMs are increasingly deploying multi-level PKIs, with sub-certificate-authorities (sub-CAs) below an OEM root certificate authority, as well as utilizing multiple different signing entities for different purposes, such as software signing, calibration signing, certificate revocation list signing, and signing for other specific components, resulting in an even larger collection of PKI certificates that need to be authentically maintained.

Moreover, in addition to the use of a large number of certificates by vehicle OEMs, any of the certificates in the PKI certificate hierarchy can be revoked by the use of signed lists, usually certificate revocation lists. The number of certificates enumerated in these lists can potentially grow very large, even if only a small fraction of the issued certificates are revoked. Finally, in some applications, such as so-called ‘vehicle to everything’ (V2X) communications, the number of certificates issued is very large, with each vehicle being issued multiple thousands of certificates during its lifetime. In such applications, the difficulty of keeping both certificates and revocation information inside the HSM is even further heightened.

Accordingly, what is needed is a method for performing cryptographic operations, in particular certificate validations, using an HSM in a memory-efficient manner for HSMs having only a very limited amount of memory.

SUMMARY

A method for using a hardware security module is disclosed. The method comprises identifying a first certificate chain comprising a root certificate and a plurality of subordinate certificates. The method further comprises validating, with the hardware security module, the first certificate chain by validating each respective subordinate certificate in the plurality of subordinate certificates. The validation of each respective subordinate certificate comprises receiving, and storing in a memory of the hardware security module, a first certificate in a respective certificate pair including (i) the respective subordinate certificate and (ii) a respective signer certificate of a respective entity that issued the respective subordinate certificate. The validation of each respective subordinate certificate further comprises storing, in the memory of the hardware security module, a second certificate in the respective certificate pair that was previously received by the hardware security module. The validation of each respective subordinate certificate further comprises verifying a signature of the respective subordinate certificate using the respective signer certificate. The validation of each respective subordinate certificate further comprises deleting, after verifying the signature, the second certificate from the memory of the hardware security module if the second certificate is one of the plurality of subordinate certificates.

A further method for using a hardware security module is disclosed. The method comprises identifying a first certificate chain comprising a root certificate and a plurality of subordinate certificates. The method further comprises validating, with the hardware security module, the first certificate chain by validating each respective subordinate certificate in the plurality of subordinate certificates. The validation of each respective subordinate certificate comprises verifying a signature of the respective subordinate certificate using a respective signer certificate of a respective entity that issued the respective subordinate certificate. The validation of each respective subordinate certificate further comprises calculating, in response to the respective subordinate certificate being successfully verified, a respective cryptographic value based on the respective subordinate certificate using a cryptographic function. The validation of each respective subordinate certificate further comprises storing the respective cryptographic value in a first data structure in the memory of the hardware security module. The method further comprises revalidating, with the hardware security module, a particular subordinate certificate in the plurality of subordinate certificates by recalculating the respective cryptographic value based on the particular subordinate certificate using the cryptographic function.

Yet another method for using a hardware security module is disclosed. The method comprises identifying a first certificate chain comprising a root certificate and a plurality of subordinate certificates. The method further comprises validating, with the hardware security module, the first certificate chain by validating each respective subordinate certificate in the plurality of subordinate certificates. The validation of each respective subordinate certificate comprises receiving, and storing in a memory of the hardware security module, the respective subordinate certificate. The validation of each respective subordinate certificate further comprises storing, in the memory of the hardware security module, a respective signer certificate of a respective entity that issued the respective subordinate certificate, the respective signer certificate having been previously received by the hardware security module. The validation of each respective subordinate certificate further comprises verifying a signature of the respective subordinate certificate using the respective signer certificate. The validation of each respective subordinate certificate further comprises deleting, after verifying the signature, the respective signer certificate from the memory of the hardware security module if the second certificate is one of the plurality of subordinate certificates.

DETAILED DESCRIPTION

System Overview

FIG.1shows an exemplary host device100that incorporates a hardware security module for cryptographic operations. In at least one embodiment, the host device100is a vehicle controller, in particular a vehicle electronic control unit (ECU). However, it will be appreciated by those of ordinary skill that the systems and methods described herein are equally applicable to any computing device that incorporates a hardware security module for cryptographic operations.

The host device100, which may also be referred to as a host controller or host computer, at least includes at least one host processor110and at least one host memory120. It will be recognized by those of ordinary skill in the art that a “processor” includes any hardware system, hardware mechanism or hardware component that processes data, signals or other information. Accordingly, the host processor110may comprise a central processing unit, graphics processing units, multiple processing units, dedicated circuitry for achieving functionality, programmable logic, or other processing systems. The host memory120may be of any types of devices capable of storing information accessible by the host processor110, such as a flash memory card, ROM, RAM, hard drives, discs, or any of various other computer-readable medium serving as volatile or non-volatile data storage devices, as will be recognized by those of ordinary skill in the art. In at least one embodiment, the host memory120includes both volatile memory and non-volatile memory.

The host memory120stores program code122and unsecure data124. The program code122includes program code for performing any number of operations of the host device100, depending on the application and context of the host device100. Moreover, the program code122at least includes program code for receiving or retrieving certificates, in particular public-key infrastructure (PKI) certificates, which are required or otherwise useful in the performance of the various operations of the host device100. In one embodiment, the PKI certificates comprise X.509 certificates. The receipt of such certificates by the host device100is generally accomplished by communications over the public Internet, via one or more network communications devices (not shown) of the host device100, or by communications via private network and through diagnostic access systems. These certificates are stored in the unsecure data124of the host memory120, among other data of the host device100.

The host device100further includes a hardware security module (HSM)130for performing for cryptographic operations and storing sensitive data in a secure manner. The HSM130generally takes the form of a computer-on-a-chip, a microprocessor, or a microcontroller, which is embedded in a packaging or housing having multiple physical security measures that provide tamper resistance, tamper evident qualities, or tamper-detecting features.

The HSM130at least includes at least one cryptoprocessor140and at least one HSM memory150. It will be recognized by those of ordinary skill in the art that a “processor” includes any hardware system, hardware mechanism or hardware component that processes data, signals or other information. Accordingly, the cryptoprocessor140may comprise a central processing unit, graphics processing units, multiple processing units, dedicated circuitry for achieving functionality, programmable logic, or other processing systems. The HSM memory150may be of any types of devices capable of storing information accessible by the cryptoprocessor140, such as a flash memory card, ROM, RAM, hard drives, discs, or any of various other computer-readable medium serving as volatile or non-volatile data storage devices, as will be recognized by those of ordinary skill in the art. The HSM memory150is advantageously only accessible by the cryptoprocessor140and cannot be read or written to by any other controller or device (e.g., by the host processor110of the host device100). In at least one embodiment, the HSM memory150includes both volatile memory (e.g., RAM) and non-volatile memory (e.g., DFLASH and/or PFLASH).

The HSM memory150stores program code152and secure data154. The program code122includes program code for performing any number of cryptographic operations that might be required by the host device100, at least including validating a certificate chain of a respective certificate, in particular of a respective PKI certificate (e.g., a X.509 certificate). The secure data154of the HSM memory150generally stores, at any given point in time, one or more certificates, cryptographic keys, or other cryptographic data necessary for validating a certificate chain and for performing any number of other cryptographic operations requested by the host device100.

Finally, the host device100further includes an HSM driver160configured to facilitate communications between the host processor110and the HSM130. The HSM driver160interconnects with a host communication interface170of the HSM130. As an example, when a cryptographic operation is required to be performed, the host processor110operates the HSM driver160communicate commands and the necessary data, including cryptographic data such as certificates or keys, to the HSM130. The HSM130receives commands and the necessary data from the host processor110via the host communication interface170and cryptoprocessor140executes the requested cryptographic operations in a secure execution environment.

Methods for HSM Memory-Efficient Certificate Cryptography

A variety of methods and processes are described below for operating the HSM130and/or the host device100to perform cryptographic operations, at least including certificate chain validation. In these descriptions, statements that a method, processor, and/or system is performing some task or function refers to a controller or processor (e.g., the host processor110or the cryptoprocessor140) executing programmed instructions (e.g., the program code122or the program code152) stored in non-transitory computer readable storage media (e.g., the host memory120or the HSM memory150) operatively connected to the controller or processor to manipulate data or to operate one or more components in the host device100or the HSM130to perform the task or function. Additionally, the steps of the methods may be performed in any feasible chronological order, regardless of the order shown in the figures or the order in which the steps are described.

FIG.2shows a method200for certificate chain validation using a hardware security module. It will be appreciated by those of ordinary skill in the art that certificate chain validation refers to the verification of all of the signatures in a certificate chain from a root certificate down to a leaf certificate in a certificate tree.

The method200begins with identifying a certificate chain comprising a root certificate and a plurality of subordinate certificates (block210). Particularly, the host processor110of the host device100(or the cryptoprocessor140of the HSM130) identifies a certificate chain that is to be validated. In general, the certificate chain that is to be validated is that of a respective certificate that is to be used for a cryptographic operation requested by the host device100. A certificate chain is a set of certificates comprising a root certificate and one or more subordinate certificates, in which there is a chain of issuance/signature from the root certificate to a lowest level subordinate certificate. The root certificate is a certificate that identifies a root certificate authority (CA). The root certificate is self-signed by the root certificate authority and establishes a root of trust in a PKI. In at least one embodiment, the HSM130is provisioned with some number of root certificates, which it will trust, in a secure way, typically in an initial secure environment. In contrast, each subordinate certificate has been either (i) issued by the root CA identified by the root certificate or (ii) issued by an intermediate entity identified by another of the subordinate certificates (e.g., a subordinate CA). The certificate chain to be validated is generally part of a larger multi-level certificate tree.

FIG.3shows an exemplary multi-level certificate tree300. At the root of the certificate tree300is a root certificate310that identifies a root CA. The certificate tree300further includes subordinate CA certificates320A and320B, which are issued by the root CA and identify a first subordinate CA and a second subordinate CA, respectively. The certificate tree300further includes an intermediate CA certificate330, which is issued by the first subordinate CA and identifies an intermediate CA. The certificate tree300further includes a firmware signer certificate340, which is issued by the intermediate CA and identifies a firmware signing entity. The certificate tree300further includes an identity certificate350, which is issued by the intermediate CA and identifies a subject entity. Additionally, the certificate tree300includes certificate revocation list (CRL) signer certificates340A and340B, which are issued by the intermediate CA and the second subordinate CA, respectively. The CRL signer certificates340A and340B identify a first CRL issuing entity and a second CRL issuing entity, respectively. Finally, the certificate tree300further includes CRLs370A and370B, which are issued by the first CRL issuing entity and the second CRL issuing entity, respectively

In the example ofFIG.3, the firmware signer certificate340or the identity certificate350may need to be validated prior to usage of the public key contained therein. In order to validate the identity certificate350, the certificate chain of the identity certificate350must be identified and then validated.

In order to identify the certificate chain of a respective certificate (e.g., a certificate to be used in some cryptographic operation requested by the host device100), the processor110and/or the cryptoprocessor140begins by identifying the issuing entity of the respective certificate and, then, identifying or retrieving the certificate of that issuing entity. In this same manner, the processor110and/or the cryptoprocessor140iteratively traverses up the certificate tree, identifying each certificate in the certificate chain of the respective certificate until the root certificate is reached.

In each case, the issuing entity of a certificate is listed in the data of the certificate. Particularly, as will be understood by those of ordinary skill in the art, a certificate generally comprises, among other things, at least (1) a public key of the subject entity to which the certificate was issued, (2) a digital signature of issuing entity that issued the certificate, and (3) identifying information about subject entity and issuing entity. A certificate will generally include additional data such as a serial number of the certificate, a validity period of the certificate, information identifying an encryption algorithm of the public key, and information identifying a signature algorithm of the digital signature.

If the certificates of the certificate chain that is to be validated are not already available in the host memory120, the host processor110retrieves a copy of each certificate in the certificate chain and stores the copy of each certificate in the certificate chain in the host memory120, in particular in the certificate storage slots510. The retrieval of such certificates by the host processor110is generally accomplished by looking for the certificates in host memory120or by communications over the public Internet, via one or more network communications devices (not shown) of the host device100.

Returning toFIG.2, the method200continues with provisionally validating the certificate chain, with an HSM, by sequentially validating each respective subordinate certificate (block220). Particularly, once the certificate chain is identified, the certificate chain can be provisionally validated by at least validating each subordinate certificate in the certificate chain. More particularly, each respective subordinate certificate of the certificate chain is validated by at least verifying the signature of the respective subordinate certificate. If each respective subordinate certificate is determined to be valid, that is to say has a verified signature by from the respective issuing entity, then the certificate chain can be considered provisionally validated. However, the certificate chain cannot be considered fully validated until the certificate chain is checked against a valid certificate revocation list (as will be discussed below with respect to block240).

Rather than performing the provisional validation of the certificate chain with the host processor110using the host memory120, the provisional validation of the certificate chain is instead performed with the secure execution environment of the HSM130. However, in some applications, due to optimizations of cost or otherwise, the HSM130may have limited very limited memory for storing certificates of the certificate chain that is to be validated. In particular, the HSM130may have insufficient memory to store the entirety of the certificate chain that is to be validated.

FIG.4shows a method400for provisionally validating a certificate chain in a memory-efficient manner. The method400is advantageously adapted for performance in the secure execution environment of an HSM (e.g., the HSM130) having very limited memory for storing certificates of the certificate chain that is to be validated and, in particular, an HSM having insufficient memory to store the entirety of the certificate chain that is to be validated. The method400advantageously enables a certificate chain to be validated while storing as few as only two certificates at any point in time during the certificate validation process.

Particularly,FIG.5illustrates exemplary memory usage of the host device100and of the HSM130during provisional chain validation. As can be seen, the host memory120and the HSM memory150have certificate storage slots510and520, respectively or, in other words, portions of memory at least temporarily dedicated to the storage of certificates. The certificate storage slots510in the non-volatile memory of the host memory120permanently or semi-permanently store a large number of certificates (e.g., certificates 0-19). In contrast, the certificate storage slots520in the HSM memory include only a few dedicated certificate storage slots for temporary certificate storage (e.g., in RAM). The certificate storage slots520at least include a subordinate certificate slot522that stores a respective subordinate certificate that is being validated at a particular iteration of the method400and a signer certificate slot544that identifies the signer/issuer entity that signed and issued the respective subordinate certificate. As described below, the method400advantageously validates each certificate in the certificate chain sequentially and needs only to temporarily store the pair of certificates involved in each validation process in the sequence.

Additionally, in the illustrated example, the certificate storage slots520further include a root certificate slot526that permanently or semi-permanently stores a root certificate (e.g., in PFLASH or DFLASH). However, the method400does not strictly rely on the root certificate being available in this root certificate slot, and permanent availability of the root certificate can optionally be omitted in some implementations.

Returning toFIG.4, in summary, the method400includes sequentially verifying the signature of each subordinate certificate in the certificate chain. Thus, the method400comprises a sequence of signature verifications requiring, in each case, a respective certificate pair including (i) the subordinate certificate having the signature to be verified and (ii) the signer certificate of the entity that issued the subordinate certificate having the signature to be verified. In principle, this sequence of signature verifications may proceed in any order, at least including (1) a forward direction through the certificate chain from root to leaf or (2) an reverse direction through the certificate chain from leaf to root. In either case, for each signature verification process, the HSM130generally receives one certificate in the necessary certificate pair from the host device100and already has the other certificate in the necessary certificate pair from the previous signature verification. After each signature verification process, the HSM130generally deletes the certificate that is not necessary for the next signature verification.

Particularly, for each respective subordinate certificate in the certificate chain, the method400begins with receiving, with the HSM, and storing in a memory of the HSM, a first certificate of a respective certificate pair including (i) the respective subordinate certificate and (ii) a respective signer certificate of a respective entity that issued the respective subordinate certificate (block410). Particularly, for each respective signature verification process, the host processor110operates the HSM driver160to transmit one of the certificates of a certificate pair necessary for the respective signature verification to the HSM130. The cryptoprocessor140receives, via the host communication interface170, the certificate and stores the received certificate in the HSM memory150.

In the case that the sequence of signature verifications proceeds from root to leaf, the received certificate in each signature verification process is the respective subordinate certificate having the signature that is to be verified. In at least one embodiment, the cryptoprocessor140writes the received certificate to the subordinate certificate slot522.

Conversely, in the case that the sequence of signature verifications proceeds from leaf to root, the received certificate in each signature verification process is the respective signer certificate of the signer/issuer entity that signed and issued the respective subordinate certificate having the signature that is to be verified. In at least one embodiment, the cryptoprocessor140writes the received certificate to the signer certificate slot524. However, in the final signature verification process, the signer certificate is the root certificate, which may already be stored in the HSM memory150e.g., in the root certificate slot526, but was previously received at some earlier point in time.

With continued reference toFIG.4, for each respective subordinate certificate in the certificate chain, the method400continues with storing, in the memory of the HSM, a second certificate in the respective certificate pair that was previously received by the hardware security module (block420). Particularly, for each respective signature verification process, the HSM memory150already stores the other certificate of the certificate pair necessary for respective signature verification. The already stored certificate was previously received, e.g., in the previous signature verification or at some other earlier time.

In the case that the sequence of signature verifications proceeds from root to leaf, the already stored certificate is generally the signer certificate of the certificate pair necessary for the respective signature verification. Thus, in the first signature verification process of the method400, the already stored certificate is the root certificate, e.g., stored in the root certificate slot526of the HSM memory150. Alternatively, if the root certificate is not already permanently stored, the root certificate must be initially received from the host device100and stored in the HSM memory150, e.g., in the root certificate slot526. In the each subsequent signature verification process, the already stored certificate is the previously received (and validated) subordinate certificate from the previous signature verification.

Conversely, in the case that the sequence of signature verifications proceeds from leaf to root, the already stored certificate is the respective subordinate certificate having the signature that is to be verified. In the first signature verification process of the method400, this certificate having the signature that is to be verified must be initially received from the host device100. However, in the each subsequent signature verification process, the respective subordinate certificate having the signature that is to be verified is already stored in the HSM memory150from the previous signature verification.

For each respective subordinate certificate in the certificate chain, the method400continues with verify, with the HSM, a signature of the respective subordinate certificate using the respective signer certificate (block430). Particularly, at this point in each validation process of the method400, the HSM memory150stores the respective subordinate certificate having the signature that is to be verified (e.g., in the subordinate certificate slot522) and the respective signer certificate (e.g., in the signer certificate slot524). With these certificates available in the HSM memory150, the cryptoprocessor140validates the respective subordinate certificate using the respective signer certificate. More particularly, the cryptoprocessor140verifies the signature of the respective subordinate certificate using the public key of the respective signer certificate by executing a corresponding public-key verification algorithm (e.g., RSA PKCS 1.5 or PSS signature verification) in the program code152. The cryptoprocessor140determines that the respective subordinate certificate is provisionally valid in response to the signature being verified.

In at least some embodiments, the cryptoprocessor140performs additional steps to validate the respective subordinate certificate, beyond merely verifying the signature. For example, in at least one embodiment, the cryptoprocessor140checks whether the current time and date is within the validity period of the certificate. Additionally, in some embodiments, the cryptoprocessor performs various other validity checks on the data of the certificate, such as checking the formatting of the data. In another example, the cryptoprocessor140performs basic constraint checks to determine if a sub-CA is allowed to sign other certificates. As yet another example, the cryptoprocessor140examines various certificate extension data to determine what type of certificates the CA can sign, or if able to sign data, what data may be signed, or in general what operation the entity is allowed to perform. These constrains will also be contained in the signed certificate data.

For each respective subordinate certificate in the certificate chain, the method400continues with deleting the second certificate of the respective certificate pair from the memory of the HSM if the second certificate of the respective certificate pair is one of the subordinate certificates of the certificate chain (block440). Particularly, after the signature of the respective subordinate certificate is validated, the cryptoprocessor140deletes from the HSM memory150the certificate of the respective certificate pair that will not be necessary for the next signature verification process, unless it is the root certificate, which is to be permanently maintained in the HSM memory150. Conversely, the certificate of the respective certificate pair that will be necessary for the next signature verification process is retained in the HSM memory150for usage in the next signature verification process.

In the case that the sequence of signature verifications proceeds from root to leaf, the deleted certificate is generally the signer certificate of the certificate pair that was used in the previous signature verification. In the first signature verification process of the method400, the signer certificate that was used in the previous signature verification is the root certificate. In at least some embodiments, the root certificate may be retained in memory (i.e., no certificate is deleted in the first signature verification process). However, in the each subsequent signature verification process, the signer certificate of the certificate pair that was used in the previous signature verification is no longer needed and is deleted from the HSM memory150. In at least one embodiment, the cryptoprocessor140achieves this deletion by moving the respective subordinate certificate from the subordinate certificate slot522into the signer certificate slot524, thereby overwriting the respective signer certificate in the HSM memory150and opening up the memory designated to the subordinate certificate slot522. In this way, the HSM memory150is primed for receipt of the next respective subordinate certificate of the certificate chain to be validated (i.e., in block410), in the next signature verification process.

Conversely, in the case that the sequence of signature verifications proceeds from leaf to root, the deleted certificate is the respective subordinate certificate having the signature that was verified in the previous signature verification. Since this certificate will not be necessary for the next signature verification process, it is deleted from the HSM memory150. In at least one embodiment, the cryptoprocessor140achieves this deletion by moving the respective signer certificate from the signer certificate slot524into the subordinate certificate slot522, thereby overwriting the respective subordinate certificate in the HSM memory150and opening up the memory designated to the signer certificate slot524. In this way, the HSM memory150is primed for receipt of the next respective signer certificate of the certificate chain for the next signature verification process.

With reference again toFIG.5, in at least some embodiments, the HSM130incorporates a provisional certificate list530which permanently or semi-permanently identifies certificates that have been previously provisionally validated, so as to avoid the need for revalidation of these certificates. The provisional certificate list530is a data structure on the HSM memory150that identifies each certificate that has been previously provisionally validated. In at least one embodiment, provisional certificate list530stores (1) the serial number for each certificate that has been previously provisionally validated and (2) a secure tag, which enables the HSM130rapidly confirm that a received certificate having a serial number identified in the provisional certificate list530is, in fact, the same certificate that was previously provisionally validated. Additionally, in at least some embodiments, the HSM130further stores information defining the structure of the certificate chain.

To these ends, with reference again toFIG.4, for each respective subordinate certificate in the certificate chain, the method400continues with calculating, with the HSM, a secure tag for the respective subordinate certificate using a cryptographic function (block450). Particularly, in response to the respective subordinate certificate being validated, the cryptoprocessor140calculates, using a cryptographic function, a respective cryptographic value (referred to herein as a “secure tag”) based on the respective validated subordinate certificate. In one embodiment, the cryptoprocessor140calculates the secure tag in the form of a cryptographic hash using a cryptographic hash function/algorithm. In another embodiment, the cryptoprocessor140calculates the secure tag in the form of a Message Authentication Code (MAC) using a MAC function/algorithm.

Finally, for each respective subordinate certificate in the certificate chain, the method400continues with storing the secure tag in a provisional certificate list in the memory of the HSM, in association with a serial number of the respective subordinate certificate (block460). Particularly, the cryptoprocessor140stores the respective secure tag for the respective validated subordinate certificate in the provisional certificate list530in the HSM memory150. Additionally, the cryptoprocessor140also stores a respective unique identifier for the respective validated subordinate certificate in association the secure tag in the provisional certificate list530. In at least one embodiment, the respective unique identifier is a serial number of the respective validated subordinate certificate.

As will be described in greater detail below, the provisional certificate list530enables the rapid revalidation or provisional validation of previously validated certificates, without needing to revalidate the signature thereof or revalidate entire certificate chain thereof. Instead, the HSM130simply recalculates the secure tag to confirm that a certificate having a serial number identified in the provisional certificate list530is, in fact, the same certificate that was previously provisionally validated.

The processes of block410,420,430,440,450, and460are repeated in an iterative and sequential manner for each subordinate certificate of the certificate chain, until all subordinate certificates in the certificate chain have been validated. In some embodiments, the root certificate itself may also be validated by verifying its signature with its public key, in the manner discussed above. Finally, once all of the certificates in the certificate chain are determined to be valid, the certificate chain is considered to be provisionally valid. However, the certificate chain cannot be considered fully validated until the certificate chain is checked against a valid and trusted CRL.

Returning toFIG.2, the method200continues with validating, with the HSM, a certificate revocation list (block230). Particularly, after the certificate chain is provisionally validated, the certificates of the certificate chain must be compared against a valid and trusted CRL (certificate revocation list). A CRL comprises a list of unique identifiers (e.g., serial numbers) that have been revoked. All certificates in the certificate chain validation must be checked to ensure that they are not named in the CRL. The HSM130recognizes one version of the CRL as being valid at any given time, and this CRL is registered with the HSM130by either (1) storing the valid CRL in its entirety in the HSM memory150or (2) calculating a secure tag from the CRL and storing this secure tag, a serial number, and a version number in the HSM memory150.

Much like a certificate, the CRL is also signed data, signed by another entity in the PKI. Thus, CRL must also be validated. If the most recent version of the CRL has not yet registered with the HSM130, then the certificate chain of the CRL must be validated and registered with the HSM130. Likewise, if there is a new version of the CRL compared to a currently registered version, then the new version must be validated and registered with the HSM130. In some embodiments, the CRL may include a version number that can be compared to determine whether there is a new version of the CRL.

To this end, the host processor110of the host device100(or the cryptoprocessor140of the HSM130) identifies a further certificate chain for the relevant CRL, using the same procedure described above with respect to block210. Next, the HSM130provisionally validates the certificate chain of the CRL using the same procedure described above with respect to blocks220and the method400. Additionally, the signature on the CRL itself must be similarly verified, in addition to those of the certificate chain thereof. In order to fully validate the CRL, the certificates of the certificate chain of the new CRL must be compared with the serial numbers contained in the new CRL itself to determine whether any certificates in the certificate chain have been revoked. Particularly, the cryptoprocessor140compares the serial numbers of each certificate in the certificate chain of the new CRL with the revoked serial numbers listed in the new CRL itself. These comparisons are performed by the cryptoprocessor140in a similar manner that will be described in greater detail below with respect to block240and a method600. Additionally, in the case the new CRL is too large to be stored in its entirety on the HSM memory150, the cryptoprocessor140performs these comparisons in a streaming fashion, in a similar manner that will be described in greater detail below with respect to block240and the method600.

Once the certificate chain of the new CRL and the new CRL itself is validated, the cryptoprocessor140registers the new CRL with the HSM130by either (1) storing the new CRL in the HSM memory150, overwriting any old CRL in the HSM memory150or (2) by calculating a secure tag of the new CRL and storing the secure tag with the associated serial number (and optionally a version number) for the new CRL in a certificate list540in the HSM memory150(described in greater detail below). The cryptoprocessor140calculates the secure tag of the new CRL using the same procedure described above with respect to block450. If necessary, the secure tag of the new CRL may be calculated in a streaming fashion, in a similar manner that will be described in greater detail below with respect to block240and the method600.

Whenever the HSM registers a CRL which is newer than the one that was previously registered, all validations must be recalculated. The cryptoprocessor140removes any certificates from the provisional certificate list530or the certificate list540that are listed in the newly registered. Any remaining entries from the provisional certificate list530or the certificate list540will need to be revalidated, in case any parent certificate higher up in the chain was revoked. Storing serial numbers alongside the secure tags in the certificate list can speed up this operation. One method to perform this re-checking against a new CRL is to begin validation afresh, given only the roots trusted by the HSM130.

The method200continues with fully validating the certificate chain by checking, with the HSM, the provisionally validated certificate chain against the validated certificate revocation list (block240). Particularly, in order to fully validate the provisionally validated certificate chain, the certificates of the certificate chain must be compared with the serial numbers contained in a valid and trusted CRL that is registered with the HSM130. To this end, the HSM130compares the serial numbers of each certificate in the certificate chain with the serial numbers listed in the registered CRL to determine whether any certificates in the certificate chain have been revoked. If it is determined that none of the certificates of the certificate chain are revoked, the HSM130determines the certificate chain to be fully validated. One embodiment of this process is detailed below.

FIG.6shows600a method for fully validating a provisionally validated certificate chain. The method600begins with a step of receiving, with the HSM, and storing in the memory of the HSM, a valid certificate revocation list (block610). Particularly, in the case that the currently registered CRL is not stored locally in the HSM memory150, the host processor110operates the HSM driver160to transmit the CRL to the HSM130. The cryptoprocessor140receives, via the host communication interface170, the CRL and stores the CRL in the HSM memory150. The cryptoprocessor140recalculates the secure tag for the received CRL and compares it with the stored secure tag in the certificate list540to confirm that the received CRL is, in fact, the same CRL that was previously validated.

In at least some embodiments, the CRL is too large to be stored in its entirety on the HSM memory150. In this case, the processes of block610and block620(below) must be repeated for a plurality of smaller portions (or chunks) of the CRL. To this end, for each respective portion of the CRL, the host processor110operates the HSM driver160to transmit the respective portion of the CRL to the HSM130. The cryptoprocessor140receives, via the host communication interface170, the respective portion of the CRL and stores the respective portion of the CRL in the HSM memory150. For each respective portion of the CRL, the cryptoprocessor140calculates and/or updates a partially calculated secure tag for the CRL. Once the whole CRL has been seen by the HSM130, the cryptoprocessor140compares the complete recalculated secure tag it with the stored secure tag in the certificate list540to confirm that the received CRL is, in fact, the same CRL that was previously validated.

The method600continues with a step of checking, with the HSM, whether each certificate in the certificate chain is revoked according to the valid certificate revocation list (block620). Particularly, for each respective certificate in the certificate chain, the cryptoprocessor140checks whether the respective certificate is revoked according to the certificate revocation list by comparing the respective serial number of the respective certificate with each serial number listed in the currently registered CRL. If the respective serial number of the respective certificate is listed in the CRL, then the cryptoprocessor140determines that the respective certificate has been revoked. Conversely, if the respective serial number of the respective certificate is not listed in the CRL, then the cryptoprocessor140determines that the respective certificate has not been revoked. In the case that the CRL is not permanently stored locally in the HSM memory150, once all the certificates in the certificate chain have been check against the CRL, the cryptoprocessor140deletes the CRL from the HSM memory150.

As noted above, in at least some embodiments, the CRL is too large to be stored in its entirety on the HSM memory150. In this case, the processes of block610(above) and block620must be repeated for a plurality of smaller portions (or chunks) of the CRL. To this end, the cryptoprocessor140checks whether each respective certificate is revoked according to the certificate revocation list by, for each respective portion of the CRL, comparing the respective serial number of the respective certificate with each serial number listed in the respective portion of the CRL. Once all the certificates in the certificate chain have been checked against the respective portion of the CRL, the cryptoprocessor140deletes the CRL from the HSM memory150. This process is repeated for every portion of the CRL and, if a serial number of a respective certificate in the certificate chain is listed in any portion of the CRL, then the cryptoprocessor140determines that the respective certificate has been revoked. Conversely, if the respective serial number of the respective certificate is not listed in any portion of the CRL, then the cryptoprocessor140determines that the respective certificate has not been revoked.

Once the whole CRL has been seen by the HSM130, the HSM130determines if the CRL itself is valid. This is done by updating a hash value for each component of the streamed CRL, and checking a signature, or, if the CRL has previously been seen by the HSM130, the HSM130may perform this determination quickly by checking a recalculating the secure tag for the CRL and checking it against the secure associated with a previously validated CRL. The secure tag value will also be updated as the CRL is streamed into the HSM130.

The method600continues with a step of determining that the certificate chain is valid in response to none of the certificates in the certificate chain being revoked (block630). Particularly, the cryptoprocessor140determines that the certificate chain is fully valid in response to none of the certificates in the certificate chain being revoked according to the currently registered CRL. Conversely, the cryptoprocessor140determines that the certificate chain is invalid in response to any one of the certificates in the certificate chain being revoked according to the currently registered CRL. If the certificate chain is invalid, the cryptoprocessor140deletes the serial numbers and secured tags corresponding to the certificates in the certificate chain from provisional certificate list530.

Finally, the method600continues with a step of moving, in response to the certificate chain being valid, the secure tags for each certificate in the certificate chain from the provisional certificate list to a valid certificate list in the memory of the HSM (block640). Particularly, in response to determining that the certificate is fully valid (or, equivalently, in response to none of the certificates in the certificate chain being revoked according to the currently registered CRL), the cryptoprocessor140moves the serial numbers and secure tags corresponding to the certificates in the certificate chain from the provisional certificate list530to the certificate list540(i.e., delete from the provisional certificate list530and write to the certificate list540). With reference again toFIG.5, the certificate list540is a data structure in the HSM memory150that identifies each certificate that has been previously fully validated. Much like the provisional certificate list530, the certificate list540stores (1) the serial number for each certificate that has been previously fully validated and (2) a secure tag, which enables the HSM130rapidly confirm that a received certificate having a serial number identified in the certificate list540is, in fact, the same certificate that was previously validated.

Returning toFIG.2, once a certificate chain is fully validated, the certificates thereof can be utilized by the HSM130for various cryptographic operations required by the host device100. Particularly, in at least some embodiments, the host processor110operates the HSM driver160to transmit a certificate and other data required for a cryptographic operation to the HSM130. The cryptoprocessor140receives, via the host communication interface170, the certificate and other data and stores the certificate and other data in the HSM memory150. The cryptoprocessor140performs the cryptographic operation on the data using the certificate or, in at least some cases, using a public key of the certificate.

If a certificate (or at least the contained public key) is needed to perform a cryptographic operation immediately after the chain validation thereof, then the certificate can be used directly from the HSM memory150after being fully validated. However, it the certificate has been deleted from the HSM memory150subsequent to being fully validated, then the HSM130must revalidate the certificate. Particularly, the HSM130revalidates a subordinate certificate that has previously been validated using the previously calculated secure tag, which is stored by the HSM memory150.

FIG.7shows a method700for revalidating a certificate using a secure tag. The method700has the benefit of eliminating the need to revalidate a previously validated certificate. Additionally, the method700has the further benefit of simplifying recovery in the case that the certificate storage slots510, located in an insecure memory region of the host memory120is corrupted, because restoration of the certificate storage simply amounts to downloading the certificates again without validation.

The method700begins with receiving, with the HSM, and storing in a memory of the HSM, a subordinate certificate that has previously been validated (block710). Particularly, the host processor110operates the HSM driver160to transmit a subordinate certificate to the HSM130. The cryptoprocessor140receives, via the host communication interface170, the subordinate certificate and stores the subordinate certificate in the HSM memory150. In response to receiving the subordinate certificate, the cryptoprocessor140determines whether the received certificate was previously validated by checking whether a serial number of the received certificate is present in the certificate list540, which lists all previously fully validated certificates. If the serial number of the received certificate is present in the certificate list540, the cryptoprocessor140precedes with revalidation using the previously calculated secure tag. Otherwise, the cryptoprocessor140performs a complete chain validation, as discussed above.

The method700continues with recalculating the secure tag based on the subordinate certificate using the cryptographic function (block720). Particularly, the cryptoprocessor140recalculates, using a cryptographic function, the secure tag based on the received certificate. In one embodiment, the cryptoprocessor140calculates the secure tag in the form of a cryptographic hash using a cryptographic hash function/algorithm. In another embodiment, the cryptoprocessor140calculates the secure tag in the form of a Message Validation Code (MAC) using a MAC function/algorithm.

The method700continues with determining, with the HSM, that the subordinate certificate is valid if the recalculated secure tag matches the secure tag that was previously stored in the memory of the HSM (block730). Particularly, the cryptoprocessor140determines that the received certificate is valid if the value of the recalculated secure tag matches the value of the secure tag that was previously stored in certificate list540in the HSM memory150. In this way, the cryptoprocessor140uses the secure tag to rapidly determine that the previously validated certificate is, in fact, the same certificate that was previously validated.

Embodiments within the scope of the disclosure may also include non-transitory computer-readable storage media or machine-readable medium for carrying or having computer-executable instructions (also referred to as program instructions) or data structures stored thereon. Such non-transitory computer-readable storage media or machine-readable medium may be any available media that can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such non-transitory computer-readable storage media or machine-readable medium can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store desired program code means in the form of computer-executable instructions or data structures. Combinations of the above should also be included within the scope of the non-transitory computer-readable storage media or machine-readable medium.