Quantum-Resistant Cryptography Faces Threats, NIST Standardizes Kyber and Dilithium Algorithms

Post-Quantum Cryptography (PQC) is a cryptographic system designed to withstand quantum computers, which could compromise current cryptographic standards due to their superior computational speed. The National Institute of Standards and Technology (NIST) has initiated a call for post-quantum Key Encapsulation Mechanisms (KEM) and Digital Signature Algorithms (DSA), with several schemes selected for standardization. PQC algorithms can be implemented on various software and hardware platforms, with Field-Programmable Gate Arrays (FPGAs) and Application Specific Integrated Circuits (ASICs) offering significant speed advantages. However, PQC hardware implementations may still be vulnerable to attacks, requiring robust security measures throughout the hardware’s lifecycle.

What is Post-Quantum Cryptography and Why is it Important?

Post-Quantum Cryptography (PQC) is a type of cryptographic system designed to be resistant to quantum computers. The need for such systems arises from the fact that once quantum computers become widely available, they will render current cryptographic standards vulnerable. This is because quantum computers have the potential to solve certain mathematical problems much faster than classical computers, which could compromise the security of many existing cryptographic algorithms.

Public-key cryptographic schemes like RSA and ECC have been protecting our communications and data exchanges for the past two decades. They allow two parties who wish to communicate to start a key exchange over an insecure channel and later switch to a simpler private-key cryptographic scheme. However, the impending advent of quantum computers threatens the security of these classical cryptographic algorithms.

Recognizing this challenge, the National Institute of Standards and Technology (NIST) initiated a call for post-quantum Key Encapsulation Mechanisms (KEM) and Digital Signature Algorithms (DSA) in 2017. In early 2023, NIST selected several schemes for standardization, including the lattice-based candidates Kyber and Dilithium. Many federal agencies already have mandates for adopting these post-quantum cryptographic standards.

How are PQC Algorithms Implemented?

PQC algorithms can be implemented on various software and hardware platforms. While software implementations offer flexibility and ease of implementation, dedicated hardware platforms like a Field-Programmable Gate Array (FPGA) or an Application Specific Integrated Circuit (ASIC) offer significant speedups.

FPGAs are flexible as they can be reprogrammed, whereas ASICs deliver significantly higher performance but are static in nature and cannot be reprogrammed. For example, the FPGA implementation of a PQC algorithm can outperform a software-based implementation on a Cortex-M4 processor by a factor of 363.

As the transition to PQC is taking place, FPGAs are suitable platforms. However, once standards are finalized and widely adopted, ASIC designs will be more advantageous since they display smaller area footprint, low power, and higher performance.

What are the Potential Threats to PQC Hardware Implementations?

Even if PQC schemes are mathematically sound, their hardware implementations may still be vulnerable to various attacks. Flaws in the protocols or underlying mathematical assumptions can render a cryptographic scheme weak. For example, an attack on an isogeny-based PQC scheme led to its exclusion from NIST’s consideration.

Moreover, hardware implementations of PQC schemes may be vulnerable to side-channel analysis or fault attacks. These attacks vary in the level of intrusiveness. In principle, side-channel attacks can be performed even remotely, whereas fault attacks require physical access to the device under attack.

What is REPQC and How Does it Threaten PQC Hardware Implementations?

REPQC is a sophisticated reverse engineering algorithm that can be used to identify hashing operations within the PQC hardware accelerator. The location of these operations serves as an anchor for finding secret information to be leaked. An adversary armed with REPQC can insert malicious logic in the form of a stealthy Hardware Trojan Horse (HTH).

The study shows that HTHs that increase the accelerator’s layout density by as little as 0.1% can be inserted without any impact on the performance of the circuit and with a marginal increase in power consumption. The entire reverse engineering process in REPQC is automated, as is the HTH insertion that follows it. This allows adversaries to explore multiple HTH designs and identify the most suitable one.

How Can We Protect PQC Hardware Implementations from Threats?

Protecting PQC hardware implementations from threats like REPQC and HTHs is a complex task. It requires a deep understanding of both the cryptographic algorithms and the hardware platforms on which they are implemented. It also requires constant vigilance to detect and respond to new threats as they emerge.

One approach to protecting PQC hardware implementations is to design them in such a way that they are resistant to reverse engineering and HTH insertion. This could involve using obfuscation techniques to make the hardware design more difficult to understand, or incorporating redundancy and error detection mechanisms to detect and neutralize HTHs.

Another approach is to use formal verification techniques to prove that the hardware implementation correctly implements the cryptographic algorithm and does not contain any unintended functionality. This could provide a high level of assurance that the hardware implementation is secure, but it can be a complex and time-consuming process.

Finally, it is important to consider the entire supply chain when securing PQC hardware implementations. Adversaries could potentially insert HTHs or other malicious modifications at any point in the supply chain, so it is important to have robust security measures in place at all stages of the hardware’s lifecycle.