International Association
for Cryptologic Research

Real-world cryptographic implementations nowadays are not only attacked via classical cryptanalysis but also via implementation attacks. Roughly, these attacks can be divided into passive attacks, where the adversary observed information about the internals of the computation; and active attacks where an adversary attempts to induce faults. While there is a rich literature on countermeasures targeting either of these attacks, preventing \emph{combined} attacks only recently received wider attention by the research community. In order to protect against passive side-channel attacks the standard technique is to use masking. Here, all sensitive information is secret shared such that leakage from individual shares does not reveal relevant information. To further lift the masking countermeasure to protect against active attacks, two different approaches have been considered in the literature. First, we may run $\epsilon$ copies of the masked computation and verify the outputs in order to detect faulty computation in one of the copies. This, approach, however has the following shortcomings. Firstly, we either require a huge amount of randomness ($O(\epsilon)$ more than a single masked circuit consumes), or we re-use the randomness among all $\epsilon$ copies, which makes the computation highly vulnerable to so-called horizontal attacks. Secondly, the number of shares is quadratic resulting in quadratic complexity even for affine computations. An alternative approach is to use polynomial masking, where instead of using additive masking, we use a sharing based on Reed Solomon codes. This has the advantage that the encoding itself already provides some resilience against faults, which is not the case for the simple additive encoding. Unfortunately, however, current state of the art schemes either led to an overhead of $O(n^5)$ for non-linear gates (here $n$ is the number of masks), or only worked against very restricted faults. In this work, we present a compiler based on polynomial masking that uses only $n=d+\epsilon+1$ shares and achieves linear computational complexity for affine computation (as previous polynomial approaches) and cubic complexity for non-linear gates (as previous approaches using the duplication method). Hence, our compiler has the best-known asymptotic efficiency among all known approaches. Furthermore, our compiler provides security against much stronger attackers that use region probes and adaptive faults and is thus secure against horizontal attacks. To achieve our construction, we introduce the notion of fault-invariance that allows us to lift probing secure gadgets to also be secure against combined attacks without considering all possible fault combinations. This technique improves previous approaches verifying probing security for all possible fault combinations and allows for much simpler constructions.

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.

We propose a new approach for building efficient, provably secure, and practically hardened implementations of masked algorithms. Our approach is based on a Domain Specific Language in which users can write efficient assembly implementations and fine-grained leakage models. The latter are then used as a basis for formal verification, allowing for the first time formal guarantees for a broad range of device-specific leakage effects not addressed by prior work. The practical benefits of our approach are demonstrated through a case study of the PRESENT S-Box: we develop a highly optimized and provably secure masked implementation, and show through practical evaluation based on TVLA that our implementation is practically resilient. Our approach significantly narrows the gap between formal verification of masking and practical security.

In the final phase of the post-quantum cryptography standardization effort, the focus has been extended to include the side-channel resistance of the candidates. While some schemes have been already extensively analyzed in this regard, there is no such study yet of the finalist Kyber.In this work, we demonstrate the first completely masked implementation of Kyber which is protected against first- and higher-order attacks. To the best of our knowledge, this results in the first higher-order masked implementation of any post-quantum secure key encapsulation mechanism algorithm. This is realized by introducing two new techniques. First, we propose a higher-order algorithm for the one-bit compression operation. This is based on a masked bit-sliced binary-search that can be applied to prime moduli. Second, we propose a technique which enables one to compare uncompressed masked polynomials with compressed public polynomials. This avoids the costly masking of the ciphertext compression while being able to be instantiated at arbitrary orders.We show performance results for first-, second- and third-order protected implementations on the Arm Cortex-M0+ and Cortex-M4F. Notably, our implementation of first-order masked Kyber decapsulation requires 3.1 million cycles on the Cortex-M4F. This is a factor 3.5 overhead compared to the unprotected optimized implementationin pqm4. We experimentally show that the first-order implementation of our new modules on the Cortex-M0+ is hardened against attacks using 100 000 traces and mechanically verify the security in a fine-grained leakage model using the verification tool scVerif.