Armored Core of PKI: Remove Signing Keys for CA via Physically Unclonable Function
Xiaolin Zhang Chenghao Chen Kailun Qin Chi Zhang Shipei Qu Tengfei Wang Yuxuan Wang Dawu Gu






































































































  The protection of CA's signing keys is one of the most crucial security concerns in PKI. However, these keys can still be exposed today by human errors or various carefully designed attacks. Traditional protections like TEE and HSM fail to eliminate this risk since they can be bypassed by skilled attackers. This dilemma motivates us to consider removing CA' signing keys and propose , a PKI security extension applying the physically trusted binding provided by Physically Unclonable Function (PUF) for CA.

  CAs in  issue PUF-based X509v3 TLS certificates, where they use PUF instead of signing algorithms to generate endorsements for domain public keys. The new transparency logging mechanism, built upon CT, will record the PUF calling behaviors of CA, ensuring the monitoring of PUF usage. We provide a formal cryptographic proof of 's main functions. We also implement it on the real-world PKI codebase. The results show that the incorporation of  into original systems do not cause any extra overhead, but instead improves computing efficiency by >4.9% and saves >20% of certificate storage.













  <ccs2012>
     <concept>
         <concept_id>10002978.10003014</concept_id>
         <concept_desc>Security and privacy Network security</concept_desc>
         <concept_significance>500</concept_significance>
         </concept>
     <concept>
         <concept_id>10002978.10002979.10002981</concept_id>
         <concept_desc>Security and privacy Public key (asymmetric) techniques</concept_desc>
         <concept_significance>500</concept_significance>
      </concept>
  </ccs2012>

  
[500]Security and privacy Network security
[500]Security and privacy Public key (asymmetric) techniques


















Armored Core of PKI: Remove Signing Keys for CA via Physically Unclonable Function
    Shipei Qu, Tengfei Wang, Yuxuan Wang, Dawu Gu
    
==================================================================================







§ INTRODUCTION


















Public Key Infrastructure (PKI) systems heavily rely on Certificate Authorities (CAs) who sign and issue digital certificates, providing a trusted binding of a cryptographic public key to an entity. Protecting the private signing keys of CAs is crucial to the security of PKI. If attackers were to obtain these keys, they could easily produce valid certificates for arbitrary unauthorized entities, including those of malicious domains under their control. A single leaked signing key is sufficient to compromise the entire PKI ecosystem.




Despite their significance, keeping private signing keys secret has proven to be challenging in the real world. These keys are prone to be exposed by external attacks or human errors. In the notorious DigiNotar incident <cit.> in 2011, the attacker activated and stole the signing key, and maliciously issued 531 rogue certificates for famous domains such as . The certificate reseller Trustico accidentally leaked private signing keys <cit.> via email in 2018, resulting in about 23,000 Symantec certificates being deemed compromised. In recent years, the private keys of code-signing PKI in Nvidia <cit.>, Samsung <cit.>, and MSI <cit.> were also exposed.

The causes of such incidents can be diverse. We notice that at least 13 CVEs allow attackers to directly read CA's signing keys and spoof signatures. Flawed X.509 implementations <cit.>, CA misconfigurations <cit.>, and insecure privilege management <cit.> have all contributed to the leakage of signing keys. Attackers sometimes only need simple exploitation skills, such as conducting keyword searches <cit.> on public repositories of Github and Docker Hub. These vulnerabilities and incidents show that the private signing keys can be leaked in various unexpected ways. As the cornerstone of the entire system, the protection of these digital keys is actually a weak link in the entire infrastructure, which is error-prone and vulnerable in practice. What' worse, the attackers only need one successful exploitation to acquire the literal value of the key string, then they can issue numerous fraudulent certificates with almost no limits. 





The mitigation of this critical issue of PKI usually fall into two types: split the key or seal the key. On the one hand, threshold signature can be used in PKI <cit.> to split the signing key. However, the involvement of multiple signers (CA) would increase the management burden. Distributed CA operations are time-consuming and unreliable in practice. Besides, the complete signing key can still be exposed if the attackers manage to obtain the majority of the key shares through various exploitations.



On the other hand, modern PKI vendors prefer to adopt hardware-enforced techniques to seal the keys, such as Hardware Security Modules (HSM) <cit.> and Trusted Execution Environments (TEE). However, since not all developers and administrators are security-savvy, attackers can exploit vulnerabilities in HSM SDK <cit.>, system configurations <cit.> and weak permissions <cit.> to bypass the protection and extract the sealed keys. Side-channel attacks <cit.>, passive attacks <cit.>, and some newly proposed attacks like GhostRace <cit.> and Gofetch <cit.> for Apple Silicon can also deduce the secret bytes. This ongoing cycle of "expose-protect-expose again" possibly reveals that, as long as a digital signing key exists, there is a possibility of it being exposed through a targeted attack with the carefully designed exploit chain. It is unlikely to anticipate and handle all possible attack vectors in the real world. 

This dilemma motivates us to reflect on the its root cause, hence the research question in this paper: Can we remove the digital private signing key in PKI/CA to provide complete resistance against various attacks and more trusted certificate binding?















In this paper, we propose [Armored Core is a popular video game series developed by FromSoftware], a design of PKI security extension that utilizes Physically Unclonable Function (PUF)-based trusted binding for certificates as an alternative to a signature. PUF <cit.> is a hardware security primitive that leverages random manufacturing variations to map input challenges to unique responses. Our core insight is to remove the digital signing key of CA using PUF. At a high level, the novelty of  is mainly manifested in harnessing the independent trust and physical authenticity of PUF in current PKI functions. 



 enables “keyless” certificate functionality for CA.  It re-factors partial fields of X.509v3 format with PUF-based endorsements instead of cryptographic signatures. It has a PUF transparency logging mechanism that records PUF invocation entries, allowing for monitoring of its usage. It also forms a PUF pooling layer to organize the multiple PUF instances in CA. Unlike other techniques like TEE or HSM, the signing key of CA is removed here. So it is impossible to generate fraudulent certificates by exposing the key, thereby disabling various key extraction attacks fundamentally. The PKI system can gain stronger trust foundation by armoring its core functions with PUF.



 

We integrate  into real-world PKI software including Let's Encrypt Pebble, Certbot and Google Trillian. We also provide a RISC-V hardware prototype with built-in PUF module on CVA6. The evaluation results show that  can achieve effective signing key removal for CA and introduce no additional performance overhead. In summary, the contributions of this paper are as follows: 



















    
  * New Research Question: We raise and address a novel research question: is it possible to remove the digital signing key of CA in PKI? The solution to this question can help make various key extraction attacks ineffective and establish a more trusted PKI ecosystem.
    
  * New Security Extension for PKI: We propose a new extended design of PKI, , that provides PUF-based CA operations and PUF transparency logging mechanism.  is the first to apply PUF into PKI/CA functions. It can be well incorporated into current PKI systems to prevent the exposure of signing keys.
    
  * Open-sourced Prototype: We implement an open-sourced prototype <cit.>. We evaluate it on the real-world PKI codebase. The results confirm that  is effective and burden-free for current PKI workflows. We also offer a hardware prototype with integrated PUF on RISC-V.


Scope. The general mitigation of malicious CAs and their misbehaviors are out of scope in this work. We focus on addressing the signing key exposure problems instead of the corruption of entire CA. We aim to provide an extended security design compatible with existing PKI systems.












§ BACKGROUND & MOTIVATION




 §.§ Signing Key Exposure in PKI








The CA in a PKI ecosystem is often a primary target for various attacks due to its essential role. The exposure of CA's private signing key is one of the worst-case scenarios where attackers can generate any certificates as they want. In such cases, the only solution is to revoke all suspicious certificates. A surprising fact is that such serious incidents have occurred from time to time in the past decade. We briefly review them as follows.

In the Web PKI, there have been several publicly disclosed incidents of CA signing key exposure, including DigiNotar in 2011 <cit.>, CNNIC in 2014 <cit.>, Lenovo Superfish in 2015 <cit.> and Trustico in 2018 <cit.>. In the code-signing PKI, vendors sign their software products for digital rights protection. Bit9 <cit.>, D-link <cit.>, NVDIA <cit.>, Samsung <cit.>, MediaTek <cit.> and MSI <cit.> have all encountered incidents where their code-signing keys were exposed. Although this work does not aim to offer a comprehensive survey of PKI like <cit.>, there could be more internal incidents worldwide. These incidents may not be publicly disclosed as they could potentially harm the interests of the CAs involved.



We admit that some of these incidents are outdated and the new ones are difficult to be found today due to the better security infrastructure and more experienced CA giants. However, this does not mean that the risk of PKI signing key exposure has been eradicated. As shown in Figure <ref>, we summarize the CVEs that can cause the direct CA signing key exposure. We roughly classify them into three classes based on the causes of vulnerabilities.




  
  * Insecure implementation: Flawed code logic <cit.> and uncensored logging output <cit.> in PKI softwares or crypto libraries <cit.> allow attackers to bypass the authentication or directly download the key <cit.>.
  
  * Vulnerable configuration: Developers erroneously configure the privileges of sensitive directories on PKI servers, making the signing key file publicly readable <cit.>.
  
  * Insufficient key protection: PKI vendors fail to adhere to the guidelines of CB/A Forum and store the private signing keys without protections <cit.>.











However, a closer look into these CVEs reveals that the specific causes of each vulnerability are actually independent, even in the same class. For example, in the vulnerable configuration class, CVE-2015-7328 is caused due to the world-readable permission of a CA's private key in Puppet Server; CVE-2018-17612 involves accidentally writing the key into a public  file; CVE-2020-28053 occurred due to a system command with incorrect permissions of key exporting. No direct connections or dependencies exist among them, and each CVE has a unique attack vector.

Manually identifying and analyzing such risks is impractical since we only list the CVEs that directly cause the key exposure of CA. There are numerous potential vulnerabilities <cit.> that can be a part of a complex attack vector to leak the key. While most CVEs above have been fixed and some of them are not publicly exploitable, the risk of signing key exposure in PKI/CA remains and has not diminished. In summary, the following observation highlights this ongoing risk in PKI.



Observation 2.1

  As many real-life incidents and CVEs have shown, the exposure risk of private signing keys of CA continues to persist. Even today, various vulnerabilities can lead to the direct or indirect exposure of these crucial keys.
  





















 §.§ Problems with Existing Mitigations




The importance of preventing the signing key exposure for CA cannot be overstated. Both academia and industry have developed various mitigations to defend against emerging attacks.






Researchers have proposed decentralized PKI models and operations <cit.> to split the single signing key of CA, thereby distributing the risk across multiple entities. Threshold signature and blockchain are two commonly used techniques <cit.>. However, attackers may still recover the complete key after launching multiple attack attempts on each holder (CA) of key shares. Also, these designs would require a complete overhaul of the PKI architecture, which is incompatible and could introduce extra overhead <cit.>. 





In the real-world PKI industry, vendors including Let's Encrypt, WoSign and Digicert usually utilize hardware mitigations, such as HSM, TEE and TPM, to isolate the key and signing operation. These measures increase the level of difficulty to leak the signing key, which is effective against simple exploits like <cit.>. However, sometimes themselves can be the stepping stone for new attacks.







For HSM, the conjunction with the software components could introduce extra vulnerabilities. Insecure implementations <cit.>, weak permissions <cit.> and internal data leak <cit.> allow attackers to access the key inside HSM, without attacking the secure hardware itself. Other techniques like TEE also faced targeted attacks <cit.> in recent years. Side-channel attacks <cit.> or physical attacks <cit.> are proven to be able to deduce the secret key on various platforms <cit.>. Attackers may even recover the key bytes <cit.> from the signatures. Current protections can become fragile or even insecure when confronted with emerging carefully designed attacks.










Modern PKI systems have become increasingly complex nowadays. An attacker can always collect different exploitation gadgets to find a new attack path to bypass the protection. As evidenced above, it is difficult to ensure the permanent security of a signing key across all links. Existing mitigations just increase the cost of exposing the key, but cannot rule out this risk since a digital key string is always needed for use. Besides, the current situation is more favorable for attackers because we cannot restrict them once the key is compromised. They can generate tons of unauthorized certificates in minutes with a single successful exploitation.





















Observation 2.2

  The existing mitigations are difficult to eliminate the risk of signing key exposure. Attackers can employ targeted exploitation to bypass the defenses. One successful exploitation is enough for them to issue numerous fraudulent certificates.
  






Signing key protection has been a cliché after the nearly 50 years development of PKI, but it seems never having an effective solution to end this loop of "expose-protect-expose again". The fact that the CA's signing key exists digitally cause the possibility of its exposure. This motivates us to think these questions: Can we remove the signing key for CA/PKI? What technique should be used to ensure the authenticity? How can the trust of CA be established without relying on a digital private key?









 §.§ PUF for PKI




PUF Basics. PUF is developed from the physical one-way function <cit.>. It is a hardware primitive that utilizes minor environmental variations in manufacturing and incorporates physical randomness into its structure. For example, Arbiter PUF (APUF) <cit.> (Figure <ref>) compares the arrival delays of competing paths in an arbiter circuit to derive random responses. SRAM PUF <cit.> leverages the start-up state of SRAM cells (Figure <ref>) that exhibit random "0" or "1" values due to the difference in MOSFETs.





PUF can randomly map a given challenge C to a response R by such structures. Therefore, each PUF instance is unique and has a distinct set of challenge-response pairs (CRPs), rendering duplication nearly impossible. PUF can be divided into strong and weak PUF <cit.> by the number of CRPs that one can generate. 








PUF in the real world. Top MCUs manufacturers and FPGA companies have all developed their own commercialized PUFs <cit.> in the last decade. Several PUF-specialized companies have also emerged, such as Verayo, Intrinsic-ID <cit.>, ICTK <cit.> in Korea, and PUFtech in China. PUF has already been quietly integrated in various real-world products, such as Intel SGX <cit.>, IoT <cit.>, medical wearables <cit.> and USIM <cit.>. With ongoing standardization efforts <cit.>, PUF are experiencing widespread deployment and becoming a basic component in the current hardware ecosystems.



The most common application of PUF today is private key generation. A PUF response can be fed into a key derivation function to generate the recoverable private key. However, this usage of PUF is oversimple and does not provide stronger security guarantees than common protections. The digital keys can still be deduced by advanced attacks <cit.> mentioned earlier since it have to be used explicitly. Once it gets exposed, the entire system still becomes compromised. Given this, we intend to fill the gap between the rising PUF industry and underdeveloped PUF applications. 



















Armoring PKI with PUF. The research on PUF in real-world security applications has been given attention in recent years <cit.>. Once PUF is installed into a device, it will serve as a unique and inherent root of trust for that device. It genuinely binds digital behaviors to the physical entity. We notice that unlike traditional hardware-based techniques such as HSM, TPM, and TEE, which enhances security by sealing the private key, PUF harnesses the true physical randomness to establish trust. Even its manufacturers cannot control or predict how a PUF instance will map a challenge (Figure <ref>). PUF can provide independent trust based on physical uniqueness instead of an artificially provisioned key.



Furthermore, the value of PUF in cryptography has been recognized in many research <cit.>. It exhibits a similar style with a pseudorandom function (PRF), except that its pseudorandomness is from unique structures rather than predetermined keys. PUF offers physical authenticity to its responses because each instance has a unique CRP mapping. Therefore, PUF can perform a signing-like function like RSA, ECDSA, etc. The difference between a cryptographic signature and PUF is that PUF can ensure the trusted binding between the responses and the actual entity installing PUF, whereas the signature only imply the legitimacy of the private key without ensuring who holds that key. To some extent, PUF itself is the physical private key and a physical PRF.
 





In summary, PUF provides a keyless signing functionality on physical independent trust, which has never been provided by other techniques. To the best of our knowledge, we are the first to offer such insight. Therefore, in PKI, it can bind the CA entity with its issued certificates through such physical trust, which effectively removes the original signing keys and addresses the concerns from the given observations. Specifically, we will armor CA with PUF-based operations to fully reap the benefits of PUF for PKI.
















§ OVERVIEW




 §.§ Threat Model


We assume that an adversary  can launch the following attacks with the goal of compromising the private signing key of the CA. 





    
  A1 (Channel attacks) Perform typical network attacks in the Dolev-Yao model <cit.>. Specifically,  can eavesdrop, intercept, modify and replay messages in the open channel.
    
  A2 (Remote attacks) Exploit insecure system configurations, flawed cryptographic implementations and other vulnerabilities to directly dump the signing key. Or launch targeted attacks against the CA servers to leak the sealed key.
    
  A3 ((Semi) invasive physical attacks) Use (semi) invasive measures including power side-channel analysis, fault injection, and chip delayering to deduce or physically extract the fused secrets.
    
  A4 (PUF modeling attacks) Collect a large number of raw PUF CRPs from the messages transmitted in the public network. These CRPs can then be used to train a PUF model by machine learning or deep learning techniques <cit.>. 


The objective of  is to obtain the signing key of the targeted CA by the partial or all attacks above. This work does not intend to detect or mitigate compromises of the entire CA, as other research has effectively addressed that aspect <cit.>. Our primary focus is on the security of the CA's signing key itself. 









 §.§ Design Challenges


In a nutshell, our work aims to remove the private signing key of CA through PUF. However, this cannot be readily achieved by using PUF. The characteristics of PKI systems make it more difficult to devise compatible functions based on PUF than in other networks or protocols. The following design challenges immediately arise.





CH1: Non-queryable PUF of CA. CAs are usually offline for clients. The clients cannot interact with CA during the establishment of a TLS connection with some domain. Consequently, the PUF instances installed in a CA are non-queryable for them. And PUF can only be invoked by CA, which is logically equivalent to the private signing key but with stronger physical guarantees. Therefore, the clients cannot challenge the corresponding PUF instance to verify the PUF-based endorsement in certificates. Other participants also cannot know the PUF status, or the legitimacy of PUF calling behaviors for certificate issuance. This leads us to the next design challenge.



CH2: Pre-storage of CRPs on Clients. Considering the non-queryable PUF of CAs, a straightforward way <cit.> to enable the real-time certificate verification for clients is to have them pre-store sufficient CRPs. They can compare the responses in certificates with the ones locally stored. However, this approach is not suitable for the PKI scenario because clients cannot anticipate which domain they will access or which PUF instance the CA will use. Besides, the storage of excessive CRPs for each certificate can cause large overhead and potential security issues if they get leaked. 





CH3: Hardware-bound CA functions. The introduction of PUF to PKI makes the functions of CA tightly coupled with a hardware security primitive. This is different than any other hardware-based techniques like using HSM or TPM for key protection. We understand that this change may impact the usability of our design in practice. Therefore, it is necessary to consider how PUF should be integrated into CA in the design of relevant functions. Also, it may take time for PUF to become adopted by PKI vendors and embedded in the worldwide hardware infrastructure. 







	








 §.§  Overview




Primitives. We denote (·) as the abstract oracle of PUF where C←(R), C∈𝒞, R∈ℛ. Here, 𝒞, ℛ represent the challenge and response domain, respectively. A detailed definition of (·) is given in <ref>. Let ^* be the set of all bit strings, and X ^n means the random selection of a string X from ^n. The notation |X| represents the length of X. For X, Y ∈^n, X || Y denotes their concatenation, and X ⊕ Y is their bitwise XOR result. We let H_k(·) denote a keyed cryptographic hash function, , H(k || ·). 





System Architecture.  is an enhanced PKI design to address the ongoing security issue of CA signing key exposure. Its architecture is depicted in Figure <ref>. It consists of four actors: CA, Domain, Client and Transparency Logger, which aligns with modern PKI systems with certificate transparency (CT). However, CAs here are required to be equipped with multiple PUF instances. Other actors maintain the same settings as in standard PKI systems.


 does not change the main PKI/CA workflows. The core difference lies in that CAs issue certificates (<ref>) using PUF-based operations (<ref>) to bind the public key and the issued domain on physical trust. The clients finish verification (<ref>) with the help of PUF invocation entries maintained by the transparency loggers (<ref>).  reuses the current infrastructure for smooth integration in various PKIs, such as web PKI, code-signing PKI and email PKI. By leveraging PUF in CA, it eliminates the provision of a private signing key, which varies from other designs <cit.>. The involved components and functions will be detailed in the next two sections.












§ ARMORED CORE COMPONENTS






Before fleshing out 's workflow, we first introduce its key components in this section. These components serve as the basis of the PKI functions described in <ref>.




 §.§ PUF-based Certificates


In this work, we assume that a CA with name 𝙽_CA are installed with a set of PUF ={_i, …, _n}. CA will use one of them to establish physically trusted binding of a domain 𝙽_D to its public key in a certificate. Certain fields in an X.509v3 formatted certificate _D need to be changed as depicted in Figure <ref>.











  §.§.§ Signature field.



Let _D be the to-be-signed certificate entries including the domain name, public key, issuer name and other fields. The signature field _D is usually calculated as _D=Sign(_D) where Sign is a standard cryptographic signing algorithm. In PUF-based certificates, _D=R_D⊕ H(R_CA || hc_D || h_CA) where R_D= (hc_D) and hc_D = H(𝚌𝚛𝚝_D||||𝙽_CA). This operation means that 𝙽_CA uses PUF to physically “sign” _D with timestamp  and its name. R_CA and h_CA are the endorsements for 𝙽_CA from the higher-level CA in the chain of trust, which is detailed in <ref>. 




This design directly applies PUF into the CA endorsement of PKI certificates. It provides a physically trusted proof for 𝙽_CA to bind the public key to the domain 𝙽_D. This modified field indicates that the CA itself has genuinely approved and conducted the issuance.




  §.§.§ Public key field.



The public key field  in _D remains unchanged. The domain still uses its own key pair to establish TLS connections with the clients. However, since a traditional private-public key pair does not exist in 's CAs, for _CA, we set this field  as an XOR-based accumulated proof π_CA where π_CA=⊕_i=1^n_i(C_CA), and _1,⋯,n are the installed PUF instances on a CA, C_CA is a proving challenge arbitrarily chosen by the CA. 


The purpose of the accumulated proof π_CA is to allow the client to verify whether the instance _k used to generate R_D is included in that CA's set of PUFs. The detailed function of PUF inclusion proof is given in <ref>. The proof is functionally equivalent to a traditional _CA because they both serve as the unique public information related to a private credential (a private key or PUF) of the CA. π_CA combines the response of each PUF instance in a constant size. CA can easily update it by XORing the corresponding response when there are new instances or removed ones.











  §.§.§ Extension field.


The X.509v3 format includes an extension field  to allow PKI developers to customize the certificates. In , we utilize this field to store a public response RP^k=_k(C_CA) where puf_k is the PUF instance used by the issuer to generate . The complementary part ~RP^k=π_CA⊕ RP^k is placed in the puf_k's invocation entry (<ref>). The client (verifier) can use ~RP^k and RP^k to perform the PUF inclusion proof (<ref>).







  §.§.§ Certificate chain.
 We consider a four-level certificate chain with a root CA 𝙽_CA_0, two intermediate CAs 𝙽_CA_1, 𝙽_CA_2 and domain 𝙽_D. The modified fields of certificates are given in Table <ref>.



In Table <ref>, h_CA_0=H(_CA_0 ||  || _CA_0), R_CA_0= (h_CA_0), and h_CA_1=H(R_CA_0 || hc_CA_1 || h_CA_0) and so on. The  field R_CA_0 in _CA_0 is generated using the root CA's own PUF instance, which is similar to self-signing in traditional constructions. Here we use PUF and cryptographic hash function to establish the chain of trust instead of signatures. A client can use the root certificate provisioned in their devices to verify the “signed” certificate chain all the way down to _D. It will combine the invocation entries to complete the verification (<ref>).


Compatibility with X.509v3. PUF-based certificates only modify three mentioned fields while adhering to the other specifications of the X.509v3 format. For domains, only one field () is changed from the traditional certificates.  provides the extra benefit of physical trust through PUF for certificate operations without compromising compatibility with existing systems.


























 §.§ Transparency Logging of PUF




Transparency Loggers. We directly leverage the existing CT infrastructure to implement the PUF transparency logging mechanism. The loggers are a group of semi-public servers that are usually maintained by CA vendors[<https://certificate.transparency.dev/logs/>] in practice. Each logger () has its own key pair (pk_L, sk_L). We do not require them to be equipped with PUFs since this would involve large-scale of hardware modification and greatly hinders the compatibility. However, if loggers do have PUFs installed,  welcome this configuration and provides a customized attestation function <ref>. It does not introduce any new entities to modern PKI architectures and can be seamlessly integrated into existing systems.


PUF Invocation Entry.  We design a PUF invocation entry to capture the calling behavior of PUF instances in CA. Specifically, we define the entry as I=⟨ Z, T⟩ where the description tuple Z is composed of the name of the CA invoking PUF 𝙽_CA, invoking timestamp  (same as <ref>), PUF manufacturer name 𝙽_P, PUF instance ID 𝙸𝙳_, and the complementary proof ~RP, , Z=𝙽_CA||𝙽_P||||𝙸𝙳_||~RP. The tag T=H_R(Z||𝙲𝚎𝚛𝚝) where R is the PUF response used in . Each time CA invokes some PUF instance _k for a certificate, it generates an invocation entry I to record this event. Then CA uploads the certificate  with I to the transparency loggers . 


 will perform attestation protocols with CA (<ref>) to verify the entries. After the verification, they arrange these entries according the chaining relationship of certificates. Then they update each T as T=H_R(Z||𝙲𝚎𝚛𝚝||T_h) where T_h is from the higher-level CA's PUF entry as shown in Figure <ref>. This hash chain organizes the entries in the same order as the corresponding certificate chain.  would use Merkle Tree as well to organize the certificates and the related entries that can be indexed by certificate hash. Loggers can compress these entries to save storage cost, especially since some fields of Z like _P may be repeated in an entry chain.






The transparency logging for PUF is essential because it enables the public audits of PUF's usage, which is lacking in previous PUF-based designs <cit.>. This mechanism effectively addresses the challenge [challenge1]CH1, [challenge2]CH2 by integrating PUF transparency on top of CT. As a result, clients in the PKI can verify the PUF-based certificates and the inclusion of PUF with minimal extra overhead. s not only store necessary PUF-related data but also provide authentic proof of PUF's calling behaviors. Their role extends beyond that in traditional CT, which may incentivize PKI vendors to elevate the transparency mechanism in the ecosystem.









 §.§ PUF Pooling in CA


In practice, a CA can install multiple PUF instances based on various techniques from different vendors. To effectively manage these instances, we propose the concept of abstracting the installed PUFs on the CA as a pool of PUF resources, similar to the pooling mechanism in cloud computing. This PUF pooling layer can act as a proxy between the CA software and the PUF hardware.

The CA servers can treat PUF instances as schedulable resources to optimize the performance of relevant operations, and even enable the parallelization of PUF invoking. This concept aims to decouple the hardware and the PUF-agnostic functions built upon them, thereby addressing [challenge3]CH3. Its implementation is not the focus of this work so we leave this aspect for future work.



































§  FUNCTIONS



The components described above serve as the heart of . The actual functions of PKI are built upon them. We now specify these functions in chronological order including certificate issuance, transparency logging, certificate validation and rotation. 













 §.§ Certificate Issuance



172 Domain validation.  does not modify the domain validation (DV) procedure of the original PKI system. The domain _D generates a standard certificate signing request (CSR) using its private key sk_D and submits it to the intermediate CA 𝙽_CA_2. The CA then performs common HTTP-based or DNS-based DV protocols to verify the applicant's authority. 


173 Certificate generation. After 𝙽_CA_2 confirms the identity of _D, it invokes the PUF interface formed by pooling multiple instances to generate 𝚜𝚒𝚐_D (<ref>) according to the submitted domain public key pk_D and other information. This operation ensures that the issuance is genuinely conducted by the CA itself instead of some entity in possession of that signing key. 𝙽_CA_2 also provides RP in 𝚎𝚡𝚝_D (<ref>) for the inclusion proof π_CA_2 (<ref>) to show which PUF instance is used for 𝚜𝚒𝚐_D. It then assembles the complete certificate 𝙲𝚎𝚛𝚝_D for the domain.

Meanwhile, 𝙽_CA_2 generates the corresponding PUF invocation entry I_D (<ref>). It will upload both 𝙲𝚎𝚛𝚝_D and I_D to a logger  for transparency auditing after the issuance.




 §.§ Transparency Logging & CA Attestation


174 Data logging. The distributed loggers maintain an append-only log powered by Merkle Trees. They record certificates and PUF entries in separate trees by reusing the same mechanism of CT. Both of them can be indexed by the hash fingerprint of the certificate. We assume that the loggers are synchronized within a rough time window. Note that the only change to the CT functionality is the additional logging of a new data type, , PUF invocation entry. 








175 PUF Attestation. We design an attestation protocol that enables s to verify the used PUF instances of CA, as illustrated in Figure <ref>. This protocol is conducted offline with the certificate submission from _CA_2. Loggers can periodically to execute this protocol to ensure PUF's integrity. The steps are described as follows.







    
  * _CA_2 generates a nonce n_1^n and sends it with the submitted certificate _D.
    
  *  extracts the certificate entries _D and timestamp  from _D. It then calculates hc_D = H(_D||||_CA_2), which is equivalent to the challenge used to generate _D.  computes m_1 = H(hc_D||n_1) ⊕ R_l where R_l^n.
    
  * The logger selects n_2^n and sends (m_1, n_2) to _CA_2, along with a signature using its private key sk_L.
    
  * After verifying the signature, _CA_2 can recover hc_D by itself and uses PUF to re-obtain R_D that is equivalent to the one used in _D. It also recovers R_l from m_1 using hc_D, n_1.
    
  * _CA_2 sends m_2=H(R_l||I_D||n_2)⊕ R_D and I_D to . The logger checks I_D and recovers R_D to complete the verification.




This protocol makes CAs re-invoke their PUF instances to prove their integrity to the loggers. Its purpose is to hold CAs accountable for their PUF "signed" certificates. s can retrieve R_D to perform the certificate validation, which will be soon introduced in <ref>.


This protocol can be executed periodically by loggers and CAs. R_l, which is obtained in the first execution described above, can serve as a ticket for future attestation session of _D. It can be used as the nonce n_1 of the next round. Furthermore, if s are also equipped with PUF like CAs, this protocol can be transformed to enable mutual PUF-based attestation for both parties. This version is provided in Appendix <ref>.








 §.§ Certificate Validation



We now describe how to verify the certificates (and the invocation entries) in . This procedure can co-exist with existing mechanism as a security enhancement option.

176 Verifying the domain certificate. Since the signature field is formed by PUF-based operations, the verification of certificate chain in this work is accordingly changed. In this process, a validator (a client or a logger ) will verify the integrity and authenticity of the domain certificate _D combined with the PUF invocation entries stored on the loggers. It also confirms the inclusion proof of the used PUF instance. The revocations, validity period and other regular constraints will also be checked.












Algorithm <ref> provides pseudocode for the validation process. The validator starts from the root certificates and resolves the "signature" response at each level. It verifies the hash chain all the way down to the domain certificate. The validator also resolves and verify another hash chain in the PUF invocation entries ℐ. The validation process can only succeed if both hash chains are verified. During this process, the inclusion proofs of PUF are also checked by combing RP and ~RP to recover π in CA's  field.

The loggers, which are deployed in a distributed manner, usually share the same business interests as CAs. We utilize this observation to shift some security burden from CAs to them. The attackers have to compromise both CAs and loggers to generate a valid PUF-based certificate. Also, our validation process does not introduce additional communication round trip due to the reuse of existing CT infrastructure. The software aspect of 's implementation can drop seamlessly into existing platforms. It can be installed through remote updates as an enhanced extension co-existing with the original code.


177 Domain certificates confirmed. Once the validator receives the  result from Algorithm <ref>, if it is a normal client, it then can establish standard TLS connections with the domain _D. For a , it then can finish the attestation process (<ref>) for the CA. 










 §.§ Certificate Revoke & Renewal






176 Certificate Rotation. The PUF-based certificates also have defined lifetime for revocation like traditional certificates. The revocation and renewal mechanisms, such as OCSP and CRL, remain unchanged in . It is compatible with various certificate rotation techniques commonly used in practice.

These mechanisms may require CAs to sign the revocation messages, where PUF can also be applied. CAs can treat these messages as PUF input challenges and the corresponding responses as physical "signatures" on them. Combined with transparency logging of PUF, the set of CA operations we designed in this work (<ref> and <ref>) are not limited to certificate signing. They can also be used to endorse other data in PKI. They can be implemented easily to provide physically trusted binding without using signing keys.




















§ SECURITY







 §.§ Security Proof


We first formalize the cryptographic PUF definition as follows.

(Ideal PUF)
    Let  be a PUF family where R=(C) for ∀∈ and C, R ∈{0, 1}^n.  is ϵ_P-ideal if n is a computationally secure length and for any probabilistic polynomial-time (PPT) distinguisher , we have,
    
		
  * (Pseudorandomness) ∀∈, ∀ C ∈{0,1}^n, 
		
    |Pr[^(C)⇒ 1] - Pr[^$(C)⇒ 1 ]| ≤1/2^n·ϵ(n),

		where ϵ(n) is some negligible value related to n and $ denotes a random bits oracle, i.e., $:{0,1}^n→{0,1}^n.
		
  * (Uniqueness) ∀_1, _2∈, ∀ C ∈{0,1}^n, let p(C)=_1(C)⊕_2(C), 
		
    |Pr[^p(C)⇒ 1]-Pr[^$(C)⇒ 1]| ≤1/2^n·ϵ(n).

        
  * (Almost XOR Universality) ∀∈ and ∀ C_1,C_2∈^n, C_1 C_2,
		
    Pr[(C_1)⊕(C_2)=c |c {0,1}^n] ≤1/2^n·ϵ(n).

		
        
  * (Unclonability and Tamper Resistance) Every ∈ has a unique physical structure. Any invasive measures to evaluate the installed PUF instance in adversarial simulation environments such as hardware debugging and chip delayering would turn it into a different instance.
    


We give the following security theorem on the certificate chain construction and validation.


	When H is a standard cryptographic hash function with collision resistance and XOR universality, if PUF  is ϵ_P-ideal PUF family, then for any PPT adversary  that makes at most q signing queries, its advantage 𝙰𝚍𝚟_^IND in distinguishing 𝚜𝚒𝚐 field in certificate chain and random strings are negligible.



	If PUF  is ϵ_P-ideal PUF family, then for any PPT adversary  that makes at most q certificate issuing queries, its advantage 𝙰𝚍𝚟_^EUF in the EUF-CMA (Existing Unforgeability under Chosen Message Attack) game is negligible.


The complete proof is given in Appendix <ref>.














 §.§ Security Analysis


The main security goal of  is to eliminate the risk of exposing a CA's signing key. It is the first to  achieve this level of security by harnessing the physically trusted binding of PUF in PKI. We now analyze its effectiveness against potential attacks. 




  §.§.§ Signing Key Exposure Attack


 genuinely removes the signing key for CA in different functions. It can neutralize various key exposure attacks in PKI as the key itself no longer exists. It can be deployed as an enhanced security extension in some highly sensitive scenarios, such as root CA systems.

The attacks vectors appeared in the CVEs before are no longer viable since the crucial target - the signing key - is no longer present. The adversaries are unable to generate fraudulent certificates by leaking it in PKI with , even through physical attacks or side-channel attacks. However, they may attempt to exploit the PUF interface to issue malicious certificates. The impracticality of such exploitation is discussed in detail in <ref>.



  §.§.§ Participant Corruption


If an entire CA facility gets compromised, attackers can do anything whether it is key leakage or PUF abusing. The common mitigation of this attack is usually introducing redundancy in CA workflow <cit.>. Therefore, we exclude this type threat of CA from our threat model (<ref>) as our main focus is on the exposure of the signing key.

In our design, transparency loggers are given more responsibility, exposing them to higher security risks than in the CT. We argue that due to the distributed manner of append-only logging servers, tampering with partial entries on a single machine is infeasible. The CT infrastructure in PKI has been equipped with public monitors to actively detect any malicious behaviors. Therefore, our design is not affected by the participant corruption attack in practice





  §.§.§ PUF Modeling Attack


One of the most common threats to PUF is the modeling attack <cit.>. Attackers collect enough CRPs and train a simulated PUF model. However, such attack can only break one instance that has been extracted CRPs from. The trained model is not applicable to new instance, even if they are based on the same PUF design. Therefore, an offline CA with a group of PUF instances installed is quite challenging for this attack.


We can analyze the modeling hardness intuitively. Assume that a CA randomizes the usage of N PUF instances through the pooling mechanism. δ represents the required minimum CRP number (>100K usually) to model a instance. The condition q/N≥δ should be met to model one instance, where q is the times of CRP collections. The attacker would need least 1M collections if N=10. Furthermore, our design is PUF-agnostic so vendors can choose those PUF with better modeling resilience <cit.>.



















§ PROTOTYPE IMPLEMENTATION



We implemented a prototype of  with an open-sourced codebase <cit.>. Table <ref> shows the components of this prototype. We have developed and integrated the main PKI functions of  in Pebble <cit.>. Pebble is a simplified version of Let's Encrypt CA software. It is suitable to test new features and functions. We also created a browser extension using Mozilla Web Extension API, enabling clients to perform customized certificate verification. Our PUF transparency logging mechanism is built upon Trillian <cit.>, which also serves as the back-end for Google CT project. The software part of our prototype can be easily integrated into these mainstream PKI implementations.








Developing a complete platform with built-in PUF is quite challenging and requires support from manufacturers. Here we provide a simple hardware prototype that integrates PUF into CVA6, a 6-stage RISC-V CPU on RISC-V. It is running on Genesys-2 FPGA board. More details are given in <ref>.





§ EVALUATION


In this section, we conduct several evaluation experiments of  prototype to answer the following questions:


    
  Q1: Is  effective as claimed? What is the overall performance of the prototype?
    
  Q2: What is the performance of PUF? How does it compare to the traditional signing primitive?
    
  Q3: How much overhead does  introduce to the original system? 
    
  Q4: How much does  and PUF cost for real-world deployment?





  
Experiment setups. We evaluate the prototype in a local network with 1 Gbps bandwidth. The program of CA, transparency loggers and domain are deployed on an Dell Workstation running Ubuntu LTS 20.04 with 64 GB RAM and Intel Core i7-10700 CPU (2.9 GHz). It is SGX-enabled and SDK version is 2.23.100.2.The client browser extension is tested on a MacBook laptop with 16 GB RAM and Intel Core i5-8279U CPU (2.4 GHz).  















 §.§ Q1: Microbenchmarks



We first demonstrate a microbenchmark of  and present the performance of each operation in terms of elapsed time as shown in Figure <ref>. In our testbed, Pebble with  takes about 200~350 ms to generate and construct a complete four-level certificate chain (excluding PUF operations). The elapsed time for other operations are all below 10 ms. CA's operations account for about 93% of the overall time (Figure <ref>d). The generation of PUF invocation entry chain takes less than 1.5 ms because the computation is mainly the hash calculation.

The overall system integrated with  can perform a complete PKI workflow involving the Lets' Encrypt CA (Pebble), domain client (Certbot) and the client web browser. It is functionally effective and provides stable benchmarks for each operation. Note that the above metrics do not include the evaluation of PUF, which is given separately in <ref> (Q2). Besides, both our design and software implementation treat PUF as a standalone module that can replaced as needed. In real world deployment, the hardware integration of PUF does cause much overhead to the current implementation and the results can be found in <ref> and <ref>.



Answer to Q1
     can provide practical PKI functions on real-world PKI software. The prototype requires 200~350 ms to generate the certificate chain and 1 ms to generate the PUF invocation entry chain. It also requires <7 ms and <15 ms to perform the transparency logger and client operations, respectively. 





 §.§ Q2: Primitive Comparison


This part of our evaluation aims to show the performance of PUF, the core primitive of our design, and compare it with other techniques used in CA. The functions in our design are PUF-agnostic and can be compatible with most PUF implementations. We present some of them in Table <ref> as references for PUF performances.





The selected PUFs here are examples of a wide spectrum of research of PUF circuit designs. We can see that the latency of most FPGA-based PUF designs typically falls in the millisecond range. With a variety of designs available, CA vendors can select those that meet their specific performance and security requirements. 


We also compare PUF with other signing primitives in CA as shown in Figure <ref>. RSA 2048 and ECDSA with  in TEE and HSM are used here since standalone cryptographically signing operations are not allowed in the real-world PKI/CA software. They must reside in secure hardware to be called by other functions. We use Intel SGX and AWS CloudHSM<cit.> that both have been widely applied in real-world industries as the testbed. 




See <https://github.com/niclabs/tcrsa> and <https://github.com/bnb-chain/tss-lib>

As shown in Figure <ref>, PUF consumes fewer clock cycles than other signing primitives in SGX. The context switch caused by TEE incurs an additional overhead of approximately 30%~40%. PUF only consumes additional cycles for bus communication, which would be far lower than this ratio. In Figure <ref>, the operations of signing algorithms per second outperform a single PUF instance only with the help of multithreading (5 threads). Therefore, with the integration of PUF, vendors will not experience a loss in performance.

Answer to Q2
    PUF is a lightweight security primitive on both hardware resources and usage compared with traditional techniques. It effectively strengthen the trust basis of CA. It is expected that integration of PUF does not introduce much overhead to the implementations of original PKI systems.






    



 §.§ Q3: Runtime Overhead



We further demonstrate the runtime overhead that  brings to the original PKI codebases. First, we compare the size of PUF-based certificates with the original ones, as shown in Table <ref>.




The table shows that the modified certificates used in  are 20%~27% smaller than the standard certificates. This is because the size of  and  fields are aligned with the PUF response length, , 256 bits in this work. Consequently, our design requires less storage for certificates on devices.


Figure <ref> compares the end-to-end runtime performance of the implementation with and without the integration of our design. Surprisingly, the one implementing  functions outperforms the original code, even considering the PUF operations. The results indicate that, by eliminating expensive signing operations, our prototype can achieve >4.9% computational performance improvement, even though it is not optimized yet.

Answer to Q3

    The implementations of 's certificates and functions do not introduce any extra overhead to the original system. The elapsed time of calling operations of PUF only takes up about <5% of the entire Pebble CA workflow.










 §.§ Q4: Real-world Deployment Cost


 does not require a “flag day” when vendors deploy it in new systems. It offers incremental deployment but the introduction of PUF will incur extra cost on equipment updates. We estimate it for a hypothetical PKI vendor as shown in Table <ref>.








PUF offers low power consumption and cost efficiency compared with TEE or HSM. It significantly decreases energy cost for cloud servers and benefits green computing in PKI. Also, it is directly composed of common electronic units such as memory cells, gates, capacitors and so on. This distinct way of establishing physical trust enables PUF to provide novel security functionality at a much lower cost than HSM or TEE.











Answer to Q4
     offers a cost-effective solution and can scale to the global PKI infrastructure. It can be deployed with reasonable financial and energy cost in real-world systems. 















§ DISCUSSION






 §.§ Soundness of Using PUF in PKI/CA


PUF interface control. Once the private key is removed, the PUF's invoking interfaces become the primary target for various attacks in PKI. However, in real-world products, PUF is typically integrated into chip circuitry as IP cores <cit.>. A standalone PUF instance with exposed raw CRP interface does not occur in practice. Therefore, it is highly unlikely for attackers to directly access the PUF itself without invasive methods. However, hardware invasive attacks such as FIB or LVP would permanently destroy the PUF instance according the tamper resistance property.




Reduced post-compromise damage. It is more common that attackers target the software APIs of certificate operations that are developed on top of PUF. They may exploit upper-level APIs to generate unauthorized certificates remotely. However, since the 's functions rely on the PUF hardware, attackers have to continually reside in the exact CA server to obtain the certificates. This greatly limits the attacks, and CA operators only need to monitor suspicious PUF calling behaviors to mitigate the attack. In contrast, for unprotected PKI, attackers can generate fake data anywhere once they know the value of the private key bytes, making the attack difficult to be identified and mitigated.


Additionally, attackers cannot predict the new CRPs of the PUF instance even if they have already abused it. Thanks to the inherent randomness and uniqueness of PUF, the newly issued certificates are statistically independent of those generated by attackers. Therefore, PUF can significantly reduce the post-compromise damage. 








Potential solution for weak key issue. Current PKI vendors may use unsafe random source, making the generated keys and signatures vulnerable to algebraic analysis <cit.>. This weak key issue has been widely identified in the past decade <cit.>. In our work, the burden of key generation is shifted from CA developers to the PUF manufacturers. Fortunately, according to the standards <cit.>, the randomness, uniqueness, reliability and other properties must pass the required standard tests like NIST SP 800-90B <cit.>. It is mandatory for manufacturers to conduct such evaluation. Therefore, PUFs for commercial use are expected to offer guaranteed performance metrics. Even if one instance is defective, the risks are significantly lower compared to using a weak private signing key.












 §.§ PUF as a Service


The PUF pooling layer proposed in this work turn the PUF instances from physical units to schedulable resources that can be rearranged to accommodate the application needs. Furthermore, it can be packaged and exposed as a remote service, , PUF as a Service (PaaS). Vendors can rent PUF for users who require physically trusted proof for their code. PaaS serve as a trusted physical anchor to prove that the users' code is genuinely running on the expected platforms. The CRPs are regarded as the commitments for proof verification. PaaS can be applied in cloud computing and various general businesses.


Treating physical widgets as an abstract service is not a new concept. Cloud-based HSM <cit.> has been commercialized a few years ago, allowing users to manage private keys or process sensitive information using rented servers. In comparison, PUF clusters in PaaS are more lightweight in terms of their interfaces and manufacturing costs. They have the potential to offer the same functions as HSM, such as key generation <cit.>, data encryption <cit.>, and certificate issuance in this work.








 §.§ Limitations


Hardware modification hinders the instant deployment. The advantage of our work actually yields its limitation. PUF are required to be installed on servers. This hardware modification hinders deployment in the real world. PKI vendors need to purchase specific equipment for immediate use. To alleviate this limitation, we designed 's functions to only require incremental changes. As discussed in <ref>, one can envision that this limitation will no longer exist in the future infrastructure.




PUF is only applied for certificate operations on the CA side. The core idea of our design is to armor CA with PUF-based certificate operations to address the signing key exposure problem. The benefits that PUF brings are only for CA. However, PUF can actually play a broader role on clients to defend various attacks <cit.>. We plan to address this limitation in future work: a truly PUF-based PKI system where PUF is used for all certificate operations.






§ RELATED WORK










In the past decade, a substantial body of studies <cit.> have contributed to the improved design for PKI security.

Enhanced design of PKI/CA. ARPKI <cit.> is an attack-resilient PKI with accountable operations against participant corruption. It introduces an extra CA and a log server for on-line validation. DTKI <cit.> defines a cross-signed certificate validation mechanism where clients only accept specified key-signed certificates. IKP (Instant Karma PKI) <cit.> use blockchain to capture CA' misbehaviors and incentivize the automatic detection. Let's Encrypt <cit.> has provided millions of free and automated TLS certificates. The heart of it is the ACME protocol that provides automatic CA operations over a challenge-response process. However, it is not developed for CA-side security issues. CAPS <cit.> has a signaling mechanism based on deterministic finite automaton to promptly inform clients about legitimate domains. It can defend against malicious CA without making significant modifications to existing architectures. V'CER <cit.> enables efficient certificate validation in constrained networks, such as small satellite systems. It utilizes a compact data structure called validation forest that allows updated devices to propagate the revocation information for peers. F-PKI <cit.> provides flexible certificate policies to enable domains to define their trust preferences of CAs. It introduces a map server with global certificates and policies maintained by sparse Merkle trees. Clients can verify certificates based on different trust levels.












We notice that some research on DNS security share common interests with our focus in a broad sense. Brandt propose DV (Domain Validation) ++ <cit.>. It transforms the centralized validation into a multi-vantage points approach, which prevents MiTM attackers from conducting DNS poisoning attacks. Duan propose RHINE <cit.>, an authenticated naming system for end-to-end DNS record verification. RHINE uses delegation transparency to formalize the hierarchical relationships among domain zones. Compared to DNSSEC <cit.>, it offers robust authentication functionality and resistance against partial CA and logger compromises. 


Furthermore, some work use blockchain to design a decentralized PKI where users do not need an oligopolistic CA to build trust. Fromknecht <cit.> propose using Namecoin <cit.> to uniquely bind a public key to an entity. Toorani <cit.> employ PBFT consensus algorithm to confirm the proof of domain certificates. CertLedger <cit.> formalizes a blockchain-based bulletin board model for public transparency. However, these designs may require excessive modifications to the existing PKI infrastructure, and highly reliable network communications.


PUF-based Security Scheme. PUF has been used as a security primitive in many applications <cit.>. Chatterjee <cit.> design a PUF-based anonymous authentication protocol using identity-based encryption to eliminate the need for explicit storage of CRPs on endpoint devices. Gope <cit.> and Chatterjee <cit.> respectively design a PUF-based efficient anonymous attestation protocol and both provide formal security proofs. PUF-RAKE <cit.> is a key exchange protocol with a CRP obfuscation mechanism to establish PUF keys quickly between multiple nodes. Zheng <cit.> propose a provably secure PUF-based authentication protocol for lightweight peer-to-peer communication. SPEAR <cit.> is the first PUF-based authenticated encryption algorithm.


PUF can also serve as the system RoT. It was introduced into remote attestation first in <cit.>. PAtt <cit.> adopts the concepts of PUF on programmable controllers for attestation. Dijk <cit.> construct an extended PUF interface for attestation key insulation. Janus <cit.> introduces PUF into TEE to provide intrinsic trust and nested measurements. Until now, there has been no study yet on leveraging PUF into redesigning PKI/CA. 


Transparency Log Designs. Some research focus on improving the efficiency and security of transparency logs. CIRT <cit.> uses two Merkle trees to store information in chronological and lexicographical order. It is an extension to CT to enhance the revocation transparency efficiency. CONIKS <cit.> utilizes verifiable unpredictable functions to compute the storage index privately. AAD <cit.> is an authenticated transparency log based on bilinear accumulators. Merkle^2 <cit.> is a nested data structure for lightweight auditing. It places prefix trees into a Merkle tree in chronological order. TAP <cit.> combines the several aforementioned designs and realizes zero-knowledge range proofs for independent audits. The PUF transparency in this work can be a extended functionality for CT. It can be potentially combined with the above designs.
















§ CONCLUSION AND FUTURE WORK




In this paper, we propose , a security extension for PKI that removes CA's signing keys using PUF. It can co-exist with traditional signature-based PKI functions and workflows. It enables PUF-based domain public key endorsement with modified TLS certificate fields. Its PUF transparency logging mechanism ensures the auditability of PUF invocations of CA. We have integrated 's functions into real-world PKI software including Pebble and Certbot. The evaluation results show that it is fully compatible with the original workflow to provide enhanced PKI functions without relying on CA's signing key. Also, this integration incurs no extra overhead and, in fact, offers minor performance improvements on both computation and storage. In conclusion,  is a lightweight and secure PKI enhancement that can be used in security-intensive scenarios to eliminate the security risk of CA's signing key exposure.


For future work, we plan to further explore the use of PUF in PKI clients. It can be divided into two directions. First, to address the "hidden root" issue <cit.>, we aim to build a PUF-based certificate root store mechanism to offer unified and physically trusted protection for various platforms. Second, we could construct the decentralized trust chain for public key endorsement using PUF on any device, rather than relying solely on a CA giant. 


















§ ACKNOWLEDGMENTS


The authors would like to thank the reviewers and committee for their work.


















ACM-Reference-Format







§ PUF-BASED ATTESTATION PROTOCOL


The following PUF-based protocol can be employed when both CAs and loggers are equipped with PUF instances. It shares a similar procedure with the one in <ref>. This protocol enables mutual verification of the legitimacy of PUF instances by both parties.



  
  * _CA_2 generates n_1^n and sends it with the certificate _D, which remains the same as before.
  
  *  extracts _D and  from _D. It calculates the challenge hc_D = H(_D||||_CA_2).  then uses its own PUF instance to generate R_l=(hc_D) and obtains m_1 = H(hc_D||I_l || n_1) ⊕ R_l, where I_l is the PUF invocation entry of R_l generated by .
  
  * The logger selects n_2^n and sends (m_1, I_l, n_2) to _CA_2, along with a signature using sk_L.
  
  * After verifying the signature, _CA_2 recover hc_D by itself and uses PUF to re-obtain R_D. It then confirms the validity of the entry I_l and recovers R_l from m_1 using hc_D, I_l, n_1.
  
  * _CA_2 sends m_2=H(R_l||I_D|| n_2)⊕ R_D and I_D to , where I_D is the entry for R_D. The logger recovers R_D to verify the certificate and completes the attestation.




§ SECURITY PROOF DETAILS

We first formalize the security properties of a keyed cryptographic hash function H_k(·).



	
	H is an ϵ_H-almost XOR universal (ϵ_H-AXU) hash function, if ∀ M, M^'∈^*, M  M^' and ∀ c ∈^n,
	
    Pr[H_k(M)⊕ H_k(M^')=c | k ^n] ≤1/2^n·ϵ_H.

	
	The AXU definition is another way of expressing the collision resistance of H when c=0. Thus, an AXU hash function is necessarily collision-resistant. 


We adopt the classic reduction-based proof technique to derive the probability upper bound of  winning the security games. As stated in <ref>,  is a PPT adversary whose operations are bound in polynomial time and size constraints. 



 §.§ Security Proof of Theorem <ref>


In Theorem <ref>, 's goal is to distinguish the output of the certificate issuing oracle _I of between the output of a random bit oracle $(n). It is allowed to make at most q queries to obtain the signed certificates with submitting certificate entries to _I. Also, we assume that the length of submitted certificate chains during the queries is at most l_M.



To prove the distinguishing advantage of , we now define two games G_1 and G_2, where G_1 is the actual certificate issuing oracle of . G_2 is identical to G_1 except that the invocation of PUF is replaced with the collision-free random sampling of $(n).

The purpose of G_1 and G_2 is to isolate the observation on PUF operations, thereby reducing the overall security of the design to the PUF primitive. When the adversary is interacting with _I or $(n), its distinguishing advantage 𝙰𝚍𝚟_^IND cannot exceed the probability of collisions of PUF responses. That is, if the generated responses do not collide,  cannot distinguish whether it is interacting with a real  oracle or the random bit oracle.

Therefore, for all q queries, we have this relation by Definition 1,


    𝙰𝚍𝚟_^IND   ≤   ql_M2·ϵ_P
       =   ql_M(ql_M + 1)/2^n+1·ϵ_P


When ϵ_P is negligible, the advantage of 𝙰𝚍𝚟_^IND is also negligible.




 §.§ Security Proof of Theorem <ref>



In Theorem <ref>, 's goal is to output a valid pair of certificate chain and the signatures after making at most q queries to an issuing oracle, , the chosen message attack model.


  We can deduce the following statement from the contrapositive of the original theorem: If  wins the EUF-CMA game, then there exists a PPT adversary  who can use  as a subroutine to break the security assumptions of . Hence, we can analyze the adversarial advantages by constructing  based on .

  In this proof, we fix the length of certificate chains in this proof to l. For the i-th issuing query and 1 ≤ j ≤ l,  generates M_i,j={𝚌𝚛𝚝_i, _i,j, 𝙽_i,j} and sends M_i,j to the issuing oracle that is simulated by .  calculates hc_i,j as in the original design and sends hc_i,j to a PUF oracle _P. _P returns a PUF response R_i,j to . It then locally calculates 𝚜𝚒𝚐_i,j and returns it to  as the signature.

  In each query, , , _P would make such interaction l times to construct the complete certificate chain _i. During this procedure,  genuinely constructs a simulated interactive environment for  to make it seem to engage with the real algorithm oracle of . After q queries, let out_ represent the final output of  in the EUF-CMA game, where out_ contains a set of M_j^* with the corresponding signatures 𝚜𝚒𝚐_j^* where 1 ≤ j ≤ l. A verification oracle _V will capture the result and output the flag bit (1 for success and 0 for failure).  will generate out_ according to out_. The final output of  determines whether  succeeds by utilizing 's result.
  
  Now we analyze the probability of  failing in this game.  will be considered to have failed the attack in the following three cases.
  
    
  * Case (1):  fails, ,  outputs 0;
    
  * Case (2): out_ is invalid. At least one of the generated M^* cause the collision of H. That is, ∃ i∈[1, q], j^'∈ [1,l] such that hc_i, j^' = hc_j^*;  
    
  * Case (3):  succeeds and  outputs 1, but out_ is invalid.
  

  The probability of 's failure is at most the sum of the probabilities of these three cases:
  
    fails≤Case (1) + Case (2) + Case (3),

  where Case (1)=1 - 𝙰𝚍𝚟_^EUF, Case (2)=ql^2·ϵ_H/2^n. For Case (3), it suggests that  does not create a hash collision but manages to generate a valid  field. Therefore, we have,
  
    (1-ql^2ϵ_P/2^n)· (1 - ql^2ϵ_H/2^n) ≤ (1 - 𝙰𝚍𝚟_^EUF) + ql^2ϵ_H/2^n + 𝙰𝚍𝚟_^EUF·ql^2·ϵ_H/2^n.

  Then we can derive the advantage upper bound for ,
  
    𝙰𝚍𝚟_^EUF   ≤   ql^2(ϵ_H + ϵ_P)/2^n + ql^2ϵ_H/2^n - q^2l^4ϵ_P·ϵ_H/2^2n/1-ql^2ϵ_H/2^n
        ≤   l^2(ϵ_H + ϵ_P)/2^n + l^2ϵ_H/2^n/1-l^2ϵ_H/2^n
        =   l^2(2ϵ_H + ϵ_P )/2^n-l^2·ϵ_H

  Therefore, if the consumption holds (ϵ_P and ϵ_H are negligible values), then the adversarial advantage of forging valid certificates and signatures will also be negligible.






§ HARDWARE PROTOTYPE INTEGRATED WITH PUF ON RISC-V


This work provides a preliminary hardware prototype <cit.> to prove that current computing infrastructure is able to satisfy the hardware requirements of . This prototype integrates PUF into the generic CPU on RISC-V platform to offer the built-in PUF functions. We choose CVA6[<https://github.com/openhwgroup/cva6>], a well-known RISC-V 64-bit CPU project with 6-stage pipeline and single issue, in-order execution. It supports the 64-bit RISC-V instruction set and exhibits good scalability. We can modify or extend some of its components, , adding an FPGA-based PUF module into the CPU, as shown in Figure <ref>.





The PUF-enhanced CVA6 processor is running on a Genesys 2 FPGA board. As illustrated in Figure <ref>, the prototype integrates PUF directly into the CPU core, alongside functional units such as the arithmetic logic unit, branch predictor, and multiplier/divider, as a new functional unit in the pipeline execution phase. The input and output of PUF are passed through the pipeline's registers, following the same communication mechanism as other units. It ensures that the input and output of PUF are not exposed on the bus, thereby enhancing the system security.


We choose IPUF <cit.>, a complex delay-based strong PUF, as the implemented PUF design in this prototype. Therefore, the number of cycles required for the PUF response needs to be taken into account. We design a PUF wrapper called  to address this issue.  is a finite-state machine that controls how the module responds to input signals and manages the internal process flow. It has two states:  (default) and . 


If PUF is ready to receive data, the input is directly passed to it. Otherwise,  enters the  state. In this state,  suspends the reception of new inputs until the internal PUF is ready to process the stalled input. The module also use the previously stored data through specific signals. Once the internal PUF instance indicates its readiness to receive data,  transitions back to  after processing challenge, preparing the module to accept new challenges again.







