International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Combined Fault and Leakage Resilience: Composability, Constructions and Compiler

Authors:
Sebastian Berndt , University of Lübeck
Thomas Eisenbarth , University of Lübeck
Sebastian Faust , Technical University of Darmstadt
Marc Gourjon , NXP Semiconductors
Maximilian Orlt , Technical University of Darmstadt
Okan Seker , NXP Semiconductors
Download:
DOI: 10.1007/978-3-031-38548-3_13 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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.
BibTeX
@inproceedings{crypto-2023-33132,
  title={Combined Fault and Leakage Resilience: Composability, Constructions and Compiler},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38548-3_13},
  author={Sebastian Berndt and Thomas Eisenbarth and Sebastian Faust and Marc Gourjon and Maximilian Orlt and Okan Seker},
  year=2023
}