International Association
for Cryptologic Research

While passive side-channel attacks and active fault attacks have been studied intensively in the last few decades, strong attackers combining these attacks have only been studied relatively recently. Due to its simplicity, most countermeasures against passive attacks are based on additive sharing. Unfortunately, extending these countermeasures against faults often leads to quite a significant performance penalty, either due to the use of expensive cryptographic operations or a large number of shares due to massive duplication. Just recently, Berndt, Eisenbarth, Gourjon, Faust, Orlt, and Seker thus proposed to use polynomial sharing against combined attackers (CRYPTO 2023). While they construct gadgets secure against combined attackers using only a linear number of shares, the overhead introduced might still be too large for practical scenarios.In this work, we show how the overhead of nearly all known constructions using polynomial sharing can be reduced by nearly half by embedding two secrets in the coefficients of one polynomial at the expense of increasing the degree of the polynomial by one. We present a very general framework that allows adapting these constructions to this new sharing scheme and prove the security of this approach against purely passive side-channel attacks, purely active fault attacks, and combined attacks. Furthermore, we present new gadgets allowing us to operate upon the different secrets in a number of useful ways.

<p> Machine learning applications gain more and more access to highly sensitive information while simultaneously requiring more and more computation resources. Hence, the need for outsourcing these computational expensive tasks while still ensuring security and confidentiality of the data is imminent. In their seminal work, Tramer and Boneh presented the Slalom protocol for privacy-preserving inference by splitting the computation into a data-independent preprocessing phase and a very efficient online phase. In this work, we present a new method to significantly speed up the preprocessing phase by introducing the Carnival protocol. Carnival leverages the pseudo-randomness of the Subset sum problem to also enable efficient outsourcing during the preprocessing phase. In addition to a security proof we also include an empirical study analyzing the landscape of the uniformity of the output of the Subset sum function for smaller parameters. Our findings show that Carnival is a great candidate for real-world implementations. </p>

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.

The microarchitectural behavior of modern CPUs is mostly hidden from developers and users of computer software. Due to a plethora of attacks exploiting microarchitectural behavior, developers of security-critical software must, e.g., ensure their code is constant-time, which is cumbersome and usually results in slower programs. In practice, small leakages which are deemed not exploitable still remain in the codebase. For example, sub-cache-line leakages have previously been investigated in the CacheBleed and MemJam attacks, which are deemed impractical on modern platforms.In this work, we revisit and carefully analyze the 4k-aliasing effect and discover that the measurable delay introduced by this microarchitectural effect is higher than found by previous work and described by Intel. By combining the rediscovered effect with a high temporal resolution possible when single-stepping an SGX enclave, we construct a very precise, yet widely applicable attack with sub-cache-line leakage resolution. o demonstrate the significance of our findings, we apply the new attack primitive to break a hardened AES T-Table implementation that features constant cache line access patterns. The attack is up to three orders of magnitude more efficient than previous sub-cache-line attacks on AES in SGX. Furthermore, we improve upon the recent work of Sieck et al. which showed partial exploitability of very faint leakages in a utility function loading base64-encoded RSA keys. With reliable sub-cache-line resolution, we build an end-to-end attack exploiting the faint leakage that can recover 4096-bit keys in minutes on a laptop. Finally, we extend the key recovery algorithm to also work for RSA keys following the standard that uses Carmichael’s totient function, while previous attacks were restricted to RSA keys using Euler’s totient function.

We study masking countermeasures for side-channel attacks against signature schemes constructed from the MPC-in-the-head paradigm, specifically when the MPC protocol uses preprocessing. This class of signature schemes includes Picnic, an alternate candidate in the third round of the NIST post-quantum standardization project. The only previously known approach to masking MPC-in-the-head signatures suffers from interoperability issues and increased signature sizes. Further, we present a new attack to demonstrate that known countermeasures are not sufficient when the MPC protocol uses a preprocessing phase, as in Picnic3.We overcome these challenges by showing how to mask the underlying zero-knowledge proof system due to Katz–Kolesnikov–Wang (CCS 2018) for any masking order, and by formally proving that our approach meets the standard security notions of non-interference for masking countermeasures. As a case study, we apply our masking technique to Picnic. We then implement different masked versions of Picnic signing providing first order protection for the ARM Cortex M4 platform, and quantify the overhead of these different masking approaches. We carefully analyze the side-channel risk of hashing operations, and give optimizations that reduce the CPU cost of protecting hashing in Picnic by a factor of five. The performance penalties of the masking countermeasures ranged from 1.8 to 5.5, depending on the degree of masking applied to hash function invocations.