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.,
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.
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 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.
description and analysis of the EtS KEM for secure encrypted update
mechanisms was published in the proceedings of CHES 2022, including the
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
NIST’s Fourth PQC Standardization Conference.