International Association
for Cryptologic Research

We present a set of physical profiled attacks against CRYSTALS-Dilithium that accumulate noisy knowledge on secret keys over multiple signatures, finally leading to a full key recovery attack. The methodology is composed of two steps. The first step consists of observing or inserting a bias in the posterior distribution of sensitive variables. The second step is an information processing phase which is based on belief propagation and effectively exploits that bias. The proposed concrete attacks rely on side-channel information, induced faults or possibly a combination of the two. Interestingly, the adversary benefits most from this previous knowledge when targeting the released signatures, however, the latter are not strictly necessary. We show that the combination of a physical attack with the binary knowledge of acceptance or rejection of a signature also leads to exploitable information on the secret key. Finally, we demonstrate that this approach is also effective against shuffled implementations of CRYSTALS-Dilithium.

CRYSTALS-Dilithium has been selected by the NIST as the new standard for post-quantum digital signatures. In this work, we revisit the side-channel countermeasures of Dilithium in three directions. First, we improve its sensitivity analysis by classifying intermediate computations according to their physical security requirements. Second, we provide improved gadgets dedicated to Dilithium, taking advantage of recent advances in masking conversion algorithms. Third, we combine these contributions and report performance for side-channel protected Dilithium implementations. Our benchmarking results additionally put forward that the randomized version of Dilithium can lead to significantly more efficient implementations (than its deterministic version) when side-channel attacks are a concern.

The post-quantum digital signature scheme CRYSTALS-Dilithium has been recently selected by the NIST for standardization. Implementing CRYSTALSDilithium, and other post-quantum cryptography schemes, on embedded devices raises a new set of challenges, including ones related to performance in terms of speed and memory requirements, but also related to side-channel and fault injection attacks security. In this work, we investigated the latter and describe a differential fault attack on the randomized and deterministic versions of CRYSTALS-Dilithium. Notably, the attack requires a few instructions skips and is able to reduce the MLWE problem that Dilithium is based on to a smaller RLWE problem which can be practically solved with lattice reduction techniques. Accordingly, we demonstrated key recoveries using hints extracted on the secret keys from the same faulted signatures using the LWE with side-information framework introduced by Dachman-Soled et al. at CRYPTO’20. As a final contribution, we proposed algorithmic countermeasures against this attack and in particular showed that the second one can be parameterized to only induce a negligible overhead over the signature generation.

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.

We revisit the popular adage that side-channel countermeasures must be combined to be efficient, and study its application to bitslice masking and shuffling. Our main contributions are twofold. First, we improve this combination: by shuffling the shares of a masked implementation rather than its tuples, we can amplify the impact of the shuffling exponentially in the number of shares, while this impact was independent of the masking security order in previous works. Second, we evaluate the masking and shuffling combination’s performance vs. security tradeoff under sufficient noise conditions: we show that the best approach is to mask first (i.e., fill the registers with as many shares as possible) and shuffle the independent operations that remain. We conclude that with moderate but sufficient noise, the “bitslice masking + shuffling” combination of countermeasures is practically relevant, and its interest increases when randomness is expensive and many independent operations are available for shuffling. When these conditions are not met, masking only is the best option. As additional side results, we improve the best known attack against the shuffling countermeasure from ASIACRYPT 2012. We also recall that algorithmic countermeasures like masking and shuffling, and therefore their combination, cannot be implemented securely without a minimum level of physical noise.

Over the last years, the side-channel analysis of Post-Quantum Cryptography (PQC) candidates in the NIST standardization initiative has received increased attention. In particular, it has been shown that some post-quantum Key Encapsulation Mechanisms (KEMs) are vulnerable to Chosen-Ciphertext Side-Channel Attacks (CC-SCA). These powerful attacks target the re-encryption step in the Fujisaki-Okamoto (FO) transform, which is commonly used to achieve CCA security in such schemes. To sufficiently protect PQC KEMs on embedded devices against such a powerful CC-SCA, masking at increasingly higher order is required, which induces a considerable overhead. In this work, we propose to use a conceptually simple construction, the ΕtS KEM, that alleviates the impact of CC-SCA. It uses the Encrypt-then-Sign (EtS) paradigm introduced by Zheng at ISW ’97 and further analyzed by An, Dodis and Rabin at EUROCRYPT ’02, and instantiates a postquantum authenticated KEM in the outsider-security model. While the construction is generic, we apply it to the CRYSTALS-Kyber KEM, relying on the CRYSTALSDilithium and Falcon signature schemes. We show that a CC-SCA-protected EtS KEM version of CRYSTALS-Kyber requires less than 10% of the cycles required for the CC-SCA-protected FO-based KEM, at the cost of additional data/communication overhead. We additionally show that the cost of protecting the EtS KEM against fault injection attacks, necessarily due to the added signature verification, remains negligible compared to the large cost of masking the FO transform at higher orders. Lastly, we discuss relevant embedded use cases for our EtS KEM construction.

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.