Protecting Post-Quantum Cryptography Against Side-Channel Attacks

In our previous blog, Post-Quantum Cryptography: Physical Attacks and Countermeasures, we described the challenges of securing embedded PQC implementations in practice. Mainly, we discussed how implementations of cryptographic algorithms cannot be considered as “black boxes” and rather need to be secured against physical attackers. In particular, side-channel attackers can infer information on secret keys by observing physical characteristics of the device such as execution time, power consumption or electro-magnetic emanation.

The FO transform is a mechanism used by many PQC schemes, including the to-be-standardized PQC scheme Kyber. This transform is, however, particularly vulnerable to physical attacks, which results in new challenges for securing PQC, as highlighted in our contributed talk “Surviving the FO-calypse: Securing PQC Implementations in Practice” at RWC 2022.

In this blog post, we highlight how NXP innovates to overcome these challenges and efficiently achieves side-channel protection for Kyber.

Surviving the FO-Calypse: Masking Kyber

One of the most common countermeasures against such side-channel attacks is masking, which applies a secret sharing scheme to decompose all vulnerable intermediate variables of an algorithm into a set of random values. This forces an attacker to target multiple values to extract any meaningful secret information. Masking has been widely studied and applied to efficiently protect classical cryptographic algorithms against physical attacks, e.g., AES and DES.

In contrast, masking for PQC has been significantly less studied, which resulted in a lot of open questions regarding the secure deployment of these new primitives. In 2021, NXP presented the first high-order masked implementation of Kyber at the embedded cryptography flagship conference, Cryptographic Hardware and Embedded Systems (CHES), enabling its protection against more powerful attackers. This work involved inventive masked algorithms and laid the foundation for future strongly protected Kyber implementations. Further information can be found in our publication and the corresponding presentation. While this allows for secure implementations, masking Kyber still introduces a noticeable overhead to protect against the strong side-channel attacks on the FO transform.

To mitigate this issue, NXP is exploring alternative protection approaches that can significantly improve the performance of protected implementations in specific use cases, such as secure update mechanisms.

Secure Updates: A Vital Mechanism

Updates are vital to the functionality and the performance of embedded devices, including but not limited to the internet-of-things (IoT). They are used to improve performance, provide new features and patch vulnerabilities. Therefore, failure to provide adequate security for the update mechanism allows an attacker (possibly utilizing side-channel or quantum resources), to gain control over the device or to access proprietary and potentially confidential update code.

Cryptography, and in particular, public key cryptography, is essential for accomplishing secure updates. An update image is usually signed, such that any receiving device can authenticate its source. In addition, it is often encrypted to protect any sensitive information or intellectual property it might contain. The figure below shows an exemplary update flow. Initially, before the device is deployed, secret and public keys and any corresponding certificates can be provisioned into the device. This includes the update provider’s public signature key. If the device requires an update at any point during its lifetime, in the second step the update provider and the device establish an ephemeral shared secret key to symmetrically encrypt and decrypt the update image. In the post-quantum era, this secret key could be shared using the Kyber Key Encapsulation Mechanism (KEM). The update is then signed, encrypted and transmitted to the device during the third and fourth step. Finally, the device verifies the signature of the received update to authenticate its source and decrypts it in order to install it.

Avoiding the FO-Calypse: The EtS KEM

In the embedded context, we need to ensure that, in addition to being “black box” secure, the update mechanism is also side-channel secure. Notably, the KEM decapsulation step executed on the device requires protection, however, as previously mentioned, traditional hardening approaches like masking can incur non-negligible performance overheads due to the FO transform. Another way to protect PQC KEMs against side-channel attacks on the FO transform is to replace the latter by a new transform which is more resilient against side-channel leakage. However, currently there is no such transform that can be applied to Kyber.

To close this gap, NXP cryptographers designed an alternative hardening strategy for KEMs, so as to not rely on the FO transform to efficiently achieve the required security for encrypted updates. The core idea is to replace the very leaky FO transform in the decapsulation by a digital signature verification which only manipulates public data and hence does not leak any sensitive information. This construction is called the EtS KEM, since it is based on the Encrypt-then-Sign  paradigm. The EtS KEM uses the underlying public key encryption of Kyber but reduces the side-channel attack surface, making it overall less vulnerable and easier to protect and thereby 8 to 12 times faster than the masked FO-based Kyber decapsulation.

A description and analysis of the EtS KEM for secure encrypted update mechanisms  was published in the proceedings of CHES 2022, including the corresponding slides  and presentation.

Many Challenges Ahead for a Secure Post-Quantum Future

This post features NXP’s contributions to securing post-quantum KEMs. However, many challenges remain to secure both post-quantum KEMs and digital signatures against physical attacks. For more details, please read our recent publication  dealing with the security of Dilithium, the to-be-standardized PQC digital signature standard, and stay tuned for our upcoming presentation at the NIST’s Fourth PQC Standardization Conference.

Authors

Melissa Azouaoui

Melissa Azouaoui is a senior cryptographer at the Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. She completed her PhD in 2021 at UCLouvain in Belgium, and NXP in Germany with a focus on side-channel countermeasures and evaluations for symmetric and asymmetric cryptography. Melissa is a member of the Post-Quantum Cryptography team and her work at NXP includes side-channel and fault injection attacks and countermeasures, with a particular focus on lattice and hash-based cryptography.

Olivier Bronchain

Olivier Bronchain is a cryptographer at the Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. He is also a member of the Post-Quantum Cryptography team. He obtained his PhD from UCLouvain in Belgium where he focused on side-channel countermeasures and advanced evaluation strategies mostly for symmetric cryptography. Olivier co-authored over 20+ publications in internal conferences.

Christine Cloostermans

Christine Cloostermans is a senior cryptographer at the Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. She acquired her doctorate from TU Eindhoven on topics related to lattice-based cryptography. Christine is a co-author on 10+ scientific publications, and has given many public presentations in the area of post-quantum cryptography. Beyond PQC, she is active in multiple standardization efforts, including IEC 62443 for the Industrial domain, ISO 18013 for the mobile driver’s license, and the Access Control Working Group of the Connectivity Standards Alliance.

Tobias Schneider

Tobias Schneider is a senior cryptographer at the NXP Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. He is also a member of the Post-Quantum Cryptography team. He received his PhD in cryptography from Ruhr-Universität Bochum in 2017 and authored over 25 international publications. His research topics include the physical security of cryptographic implementations, in particular of post-quantum cryptography, and cyber resilience.