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
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.,
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
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.
Example of a device update mechanism flow.
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
Classical computing security protocols face significant threats from quantum computers.
NXP is innovating robust
methods for the future.
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
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.
description and analysis of the EtS KEM for secure encrypted update mechanisms was published in the proceedings of CHES 2022, including the corresponding
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.