Modernizing PKI to prepare for PQC

As the quantum era rapidly approaches, it is no longer a distant possibility. In a significant development, the National Institute of Standards and Technology (NIST) has announced an official deadline for transitioning away from outdated encryption algorithms. By 2030, algorithms such as RSA, ECDSA, EdDSA, DH, and ECDH will be deprecated, and by 2035, they will be entirely disallowed. 

It is imperative to adopt quantum-resistant capabilities to protect sensitive data against quantum threats, such as Harvest Now Decrypt Later. The urgency in this message was highlighted on August 13, 2024, when the first three quantum-resistant algorithms were released: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) in existing cryptographic infrastructure. 

As Dustin Moody, who heads the PQC standardization project, mentioned, “We encourage system administrators to start integrating them into their systems immediately because full integration will take time.” 

The organizations that succeed in this transition won’t be the ones that are the fastest to adapt, they will be the ones who approach PQC with foresight, purpose, and understanding. 

Role of PQC in Public Key Infrastructure (PKI) 

Even as quantum computing presents new threats, Public Key Infrastructure (PKI) remains the backbone of securing digital communications. PKI ensures that digital certificates are trustworthy, and with the integration of PQC, these certificates will continue to protect the integrity and authenticity of communications in the quantum era. 

To establish secure communication, the browser checks a website’s digital certificate to verify its authenticity. This certificate includes a public key used for encryption and is issued by a trusted organization (Certificate Authority). The verification process relies on traditional cryptographic algorithms like RSA or ECDSA to ensure the website is legitimate and the connection is secure. 

Here’s where PQC comes into play. By updating PKI to use quantum-resistant algorithms, we can ensure that these digital certificates remain trustworthy in the quantum era. When we visit that secure website, the browser will verify the site’s certificate using quantum-resistant algorithms, keeping sensitive data safe and secure. 

PKI Modernization is the First Step Towards Quantum-Resilient Security 

As quantum computing looms on the horizon, modernizing PKI is a critical first step toward achieving quantum-resilient security. Let’s break down the key characteristics of PQC-Ready PKI: 

• Adopting new cryptographic standards by integrating quantum-resistant algorithms into PKI systems 

• Modern PKI systems are designed to integrate PQC algorithms without a complete overhaul. Allowing organizations to remain secure today while preparing for tomorrow. 

• Modern PKI systems, built with crypto agility in mind, can easily transition to new quantum-resistant methods as they become available. 

• Effective key management, including handling both traditional and PQC-generated keys, is a must-have. 

PQC-Ready PKI

Achieving a Post-Quantum Cryptography (PQC)-Ready Public Key Infrastructure (PKI) involves several key steps to ensure your cryptographic systems can withstand the threats posed by quantum computing. Below are the following steps on how to achieve PQC-Ready PKI. 

Issuing CA and Root CA for PQC

Creating a Root CA and Issuing CA for PQC involves adopting quantum-resistant cryptographic algorithms for both key management and certificate signing. Here’s a step-by-step breakdown:

Root CA

• Generate a PQC Key Pair

  Start by selecting a quantum-resistant cryptographic algorithm that has been standardized or is in the process of standardization (e.g., ML-KEM, ML-DSA, or hash-based algorithms like XMSS). The selected algorithm generates a key pair (public and private keys) for the Root CA. This will be the cryptographic foundation for the Root CA’s operations and signing capabilities.

• Self-sign the Root CA Certificate

  The Root CA certificate establishes the starting point for the chain of trust. To create this, use the PQC private key to self-sign the Root CA certificate. This is a crucial step because the Root CA is responsible for validating and trusting any intermediate or issuing CAs it signs. The certificate will contain information such as the public key, validity period, and other identifying information.

• Store the Root CA Private Key Securely Offline

  The Root CA private key is the cornerstone of trust within a PKI system. Therefore, private keys should be stored in a FIPS 140-3 level 3 certified hardware security module (HSM) or a dedicated key management solution to prevent unauthorized access and ensure that it cannot be compromised.

Issuing CA

• Generate a PQC Key Pair for the Issuing CA

  Similar to the Root CA, generate a PQC key pair for the Issuing CA. This key pair will be used to sign certificates for end entities (such as servers, clients, etc.). The Issuing CA must use the same quantum-resistant algorithm as the Root CA or an algorithm of similar strength, depending on the security requirements.

• Request a Certificate from the Root CA

  The Issuing CA will generate a Certificate Signing Request (CSR). This CSR contains the Issuing CA’s public key and identifying information and will be used to request a certificate from the Root CA. The CSR is signed by the private key of the Issuing CA to prove its identity and request a signed certificate from the Root CA.

• Sign the Issuing CA Certificate Using the Root CA’s Private Key

  The Root CA will verify the CSR and, if valid, use its private key (securely stored) to sign the Issuing CA certificate. This signed certificate is then returned to the Issuing CA, which can use it to prove its identity when signing end-entity certificates.

• Issuing CA Signs End-Entity Certificates

  Once the Issuing CA has its certificate, it can use its private key to sign end-entity certificates (such as for websites, clients, etc.), creating a trust chain from the Root CA to the end entity.

Issue PQC Composite Certificates

PQC composite certificates combine traditional and post-quantum algorithms, easing the transition to quantum-safe systems. By managing these hybrid certificates, organizations can integrate Dilithium (ML-DSA) or other quantum-safe algorithms alongside RSA/ECDSA algorithms.

Switch to TLS 1.3

It is recommended that TLS 1.3 be used as a base for PQC implementation. Configure the server to use TLS 1.3 and select appropriate cipher suites that incorporate post-quantum key exchange algorithms (like ML-KEM) and digital signature schemes (like Dilithium) instead of traditional, non-quantum resistant algorithms, effectively replacing the current key exchange and signature mechanisms with PQC counterparts within the TLS 1.3 handshake process.

Although integrating PQC into TLS 1.3 may result in slightly increased handshake overhead due to larger key sizes, optimization is ongoing to minimize the performance impact.

Governance is the Key

Without clear cryptographic policies and defined roles, a sophisticated Public Key Infrastructure (PKI) system can become chaotic. It is important to have standardized processes for managing keys, certificates, and cryptographic operations so everything operates smoothly. Here are some tips to manage the Governance factor in the PKI environment.

• Establish a detailed roadmap for migrating from current cryptographic algorithms to PQC. This timeline should include key milestones, deadlines for each phase, and final implementation goals.
• Start with assessing and migrating critical systems, followed by a gradual rollout to less critical systems.
• Evaluate how well current systems and infrastructure are compatible with PQC algorithms. Identify any legacy systems that require updates or replacements.
• For systems in transition, consider using hybrid models (e.g., combining legacy algorithms and quantum-safe algorithms) to ensure smooth integration and interoperability.

Modernization Equals Automation

Automation plays a critical role in PKI modernization. From certificate issuance to revocation and renewal, automating these processes will streamline operations, reduce manual errors, and enhance the efficiency of your PKI infrastructure. It is always a good idea to keep the Certificate Lifecycle Management on tip-toe for the crypto-agility using features like one-click CA shifts.

The clock is ticking. The shift from SHA-1 to SHA-2 took over 12 years across industries. With quantum threats emerging sooner than expected, we cannot afford to wait another decade for this transition. 

Key Recommendations to achieve PQC readiness in PKI

The following recommendations will guide organizations in adapting their PKI infrastructure to be quantum-resistant and future-proof. 

1. Evaluate PQC Algorithms

   As part of the NIST PQC standardization process, several quantum-resistant algorithms are being evaluated. Choose those that align with your organization’s security requirements, considering factors like key size, security level, and performance. Ensure that the selected algorithms are suitable for integration with your existing PKI infrastructure and can offer long-term security against potential quantum attacks.

2. Pilot Testing

   Conduct proof-of-concept tests within your PKI to assess the compatibility and performance of the selected PQC algorithms. This pilot phase is essential to identify any potential issues, such as integration challenges, performance bottlenecks, or compatibility with existing applications.

   Testing in a controlled environment allows you to understand the impact of adopting PQC on existing systems and processes without introducing security risks to your operational environment.

3. Upgrade PKI

   Ensure that your PKI vendor supports the latest PQC standards and provides the necessary updates. As PQC standards are evolving, it’s crucial to work with vendors who actively integrate these capabilities into their software, ensuring that your PKI infrastructure remains compatible with emerging quantum-safe algorithms.

   It may include new cryptographic libraries, updated certificate management protocols, and enhanced key management procedures to handle the increased complexity of PQC.

4. Develop a Transition Plan

   Develop a detailed strategy for gradually migrating from traditional cryptography to PQC. This transition should be planned carefully to minimize service disruption to business operations and ensure that systems remain secure during the migration.

   The plan should include key management procedures that account for the need to handle both classical and quantum-resistant algorithms in parallel during the transition phase. This hybrid approach ensures that legacy systems continue to operate securely while quantum-resistant solutions are integrated.

5. Quantum Computing Timeline

   While quantum computers capable of breaking current encryption are not yet widely available, it is essential to start planning for the transition to PQC now to avoid potential security vulnerabilities in the future. Waiting too long to adopt PQC may leave your organization exposed once quantum computers become capable of breaking existing cryptographic systems.

PKI Migration Strategies

These strategies refer to how an organization can transition from traditional PKI systems to quantum-safe PKI systems. Here’s a breakdown of each strategy: 

Challenges in PKI transition for post-quantum era

While transitioning to PQC is essential, there are several challenges, such as: 

• Choosing the Right PQC Algorithms: Integrating PQC into legacy systems can require major updates to cryptographic libraries, protocols, and hardware. 

• Legacy System Compatibility: Systems using classical cryptographic libraries may struggle with integrating PQC algorithms without compatibility issues. 

• Public Trust: Gaining public trust in new quantum-safe technologies will take time and effective communication. 

• Integration Challenges: The shift to PQC is a complex, phased process that requires compatibility testing and thorough validation. 

• Need for Hybrid Approaches: Most organizations will need to support both traditional and quantum-safe algorithms during the transition period. 

How can Encryption Consulting help? 

1. Quantum Threat Assessment

   Our detailed Quantum Threat Assessment service utilizes advanced cryptographic discovery to analyze and secure your cryptographic infrastructure.

   • Evaluate the state of the cryptographic environment as it is, identify any gaps in the current standards and controls that are in place for cryptography (such as key lifecycle management and encryption methods), and do a thorough analysis of any possible threats to the cryptographic ecosystem. 
   • We assess the effectiveness of existing governance protocols and frameworks and provide recommendations for optimizing operational processes related to cryptographic practices.
   • Identify and prioritize the crypto assets and data based on their sensitivity and criticality for the PQC migration.
2. Quantum Readiness Strategy and Roadmap
   • Identify PQC use cases that can be implemented within the organization’s network to protect sensitive information
   • Define and develop a strategy and implementation plan for PQC process and technology challenges. 
3. Build Crypto-Agility
   • We assist in determining the cryptographic challenges, compromises, and threats for your organizations.
   • We support seamless migration to new CAs, certificates, and PQC algorithms.
   • We support automating certificates and key lifecycle management for stronger security and continuous compliance.
4. Compliance Enhancement
   • Ensure compliance enhancement with industry standards.
   • We help you stay updated with the new PQC algorithms and their usage and utilization for your organization.
5. Understanding Challenges and Providing Transition Support
   • Assist in acknowledging and overcoming challenges during the transition to post-quantum cryptographic algorithms, ensuring a smooth and secure migration.
6.  Vendor Evaluation & POC (Proof of Concept)
   • Provide an overview of solution capabilities and vendor/product mapping to the identified use cases.
   • Document the test/ evaluation scenarios.

Conclusion

In conclusion, the shift to Post-Quantum Cryptography (PQC) is an essential step to secure digital communications in the quantum era. By transitioning Public Key Infrastructure (PKI) systems to accommodate quantum-resistant algorithms, organizations can ensure their cryptographic systems remain resilient against emerging quantum threats. While the transition presents challenges, including algorithm selection and legacy system integration, proactive planning, pilot testing, and clear governance will help ease the process. Organizations that embrace PQC readiness today will not only secure their data but also position themselves as leaders in preparing for a secure, quantum-resilient future.