International Association
for Cryptologic Research

NIST recently announced Kyber and Dilithium as first winners of their post-quantum cryptography (PQC) standardization effort. While the two are more suitable for constrained applications relative to other PQC schemes, their implementation in commercial embedded platforms still poses a non-trivial challenge, especially since many embedded use cases require hardening against physical attacks. As any delay in the transition to this new standard could have severe consequences for security critical use cases which require certified hardened designs, e.g., payment or automotive, the industrial and academic communities are actively investigating and solving issues that could arise. While for Kyber there is already an extensive list of such issues, Dilithium has been significantly less explored in the context of physical security. As there are multiple variants (deterministic, randomized, hedged) of Dilithium of which only a subset might be included in the standard, it is of utmost importance to quantify and understand the implications of each type on physical security. In this talk, we present the dos and don’ts of hardening Dilithium against a side-channel adversary, which were acquired during a detailed and lengthy analysis inside NXP. To this end, we first list the issues of each Dilithium variant regarding side-channel hardening, quantify the resulting implementation costs and highlight the noticeable overhead introduced by deterministic approaches. By exploring minor modifications to the underlying algorithm, we demonstrate that standardizing a variant, which is not optimized for physical security, would have a significant negative impact on the performance of hardened Dilithium on embedded devices. Instead, we propose that a slightly-modified randomized Dilithium should be considered during the standardization effort and recommended as the default choice for constrained platforms. It is our expectation that this would immensely support the transition to the future PQC standard on embedded devices.

Solely functionally-correct cryptographic implementations are often not sufficient in many real-world use-cases. For example, many payment, transit and identity use-cases require protection against advanced side-channel attacks, using certified implementations to protect the users and their data. In this presentation, we demonstrate that realizing this for post-quantum cryptography (PQC) is significantly more complex and computationally expensive compared to its classical public-key counterparts (RSA and ECC). The core of the issue is the Fujisaki-Okamoto (FO) transform, used in many key-exchange finalists considered for standardization, which allows for very powerful chosen-ciphertext side-channel attacks. While this attack vector is known in academia and used to break unprotected and protected implementations of PQC with very few traces, it is our impression that the practical impact has not yet been fully grasped by the applied cryptographic community. In this talk, we highlight the problems that arise with variants of the FO transformation regarding side-channel analysis, quantify the impact, and show that first order masking alone is not sufficient for many practical use-cases. Through a case study of Kyber, we demonstrate that achieving the same level of protection we are used to in hardened RSA and ECC implementations is much more costly and involved for PQC algorithms that are based on the FO transform. This increased overhead comes on top of the already larger and more computationally expensive PQC algorithms. As the targeted embedded devices for these hardened implementations are often very restricted, it is not trivial to find a balance in practice between sufficient security and acceptable performance. To conclude the talk, we discuss the overarching impact of our results on industry and provide potential directions forward to overcome this threat.

It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits.In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about the exponent than right-to-left. We show how to extend the Heninger-Shacham algorithm for partial key reconstruction to make use of this information and obtain a very efficient full key recovery for RSA-1024. For RSA-2048 our attack is efficient for 13% of keys.