International Association
for Cryptologic Research

Fresh re-keying is a countermeasure against side-channel analysis where an ephemeral key is derived from a long-term key using a public random value. Popular instances of such schemes rely on key-homomorphic primitives, so that the re-keying process is easy to mask and the rest of the (e.g., block cipher) computations can run with cheaper countermeasures. The main requirement for these schemes to be secure is that the leakages of the ephemeral keys do not allow recovering the long-term key. The Learning with Physical Rounding (LWPR) problem formalizes this security in a practically-relevant model where the adversary can observe noise-free leakages. It can be viewed as a physical version of the Learning With Rounding (LWR) problem, where the rounding is performed by a leakage function and therefore does not have to be computed explicitly. In this paper, we first consolidate the intuition that LWPR cannot be secure in a serial implementation context without additional countermeasures (like shuffling), due to attacks exploiting worst-case leakages that can be mounted with practical data complexity. We then extend the understanding of LWPR in a parallel implementation setting. On the one hand, we generalize its robustness against cryptanalysis taking advantage of any (i.e., not only worst-case) leakage. A previous work claimed security in the specific context of a Hamming weight leakage function. We clarify necessary conditions to maintain this guarantee, based on the degree of the leakage function and the accuracy of its coefficients. On the other hand, we show that parallelism inherently provides good security against attacks exploiting worst-case leakages. We finally confirm the practical relevance of these findings by validating our assumptions experimentally for an exemplary implementation.

32-bit software implementations become increasingly popular for embedded security applications. As a result, profiling 32-bit target intermediate values becomes increasingly needed to evaluate their side-channel security. This implies the need of statistical tools that can deal with long traces and large number of classes. While there are good options to solve these issues separately (e.g., linear regression and linear discriminant analysis), the current state of the art lacks efficient tools to solve them jointly. To the best of our knowledge, the best-known option is to fragment the profiling in smaller parts, which is suboptimal from the information theoretic viewpoint. In this paper, we therefore revisit regression-based linear discriminant analysis, which combines linear regression and linear discriminant analysis, and improve its efficiency so that it can be used for profiling long traces corresponding to 32-bit implementations. Besides introducing the optimizations needed for this purpose, we show how to use regression-based linear discriminant analysis in order to obtain efficient bounds for the perceived information, an information theoretic metric characterizing the security of an implementation against profiled attacks. We also combine this tool with optimizations of soft analytical side-channel attack that apply to bitslice implementations. We use these results to attack a 32-bit implementation of SAP instantiated with Ascon’s permutation, and show that breaking the initialization of its re-keying in one trace is feasible for determined adversaries.

This paper defines Spook: a sponge-based authenticated encryption with associated data algorithm. It is primarily designed to provide security against side-channel attacks at a low energy cost. For this purpose, Spook is mixing a leakageresistant mode of operation with bitslice ciphers enabling efficient and low latency implementations. The leakage-resistant mode of operation leverages a re-keying function to prevent differential side-channel analysis, a duplex sponge construction to efficiently process the data, and a tag verification based on a Tweakable Block Cipher (TBC) providing strong data integrity guarantees in the presence of leakages. The underlying bitslice ciphers are optimized for the masking countermeasures against side-channel attacks. Spook is an efficient single-pass algorithm. It ensures state-of-the-art black box security with several prominent features: (i) nonce misuse-resilience, (ii) beyond-birthday security with respect to the TBC block size, and (iii) multiuser security at minimum cost with a public tweak. Besides the specifications and design rationale, we provide first software and hardware implementation results of (unprotected) Spook which confirm the limited overheads that the use of two primitives sharing internal components imply. We also show that the integrity of Spook with leakage, so far analyzed with unbounded leakages for the duplex sponge and a strongly protected TBC modeled as leak-free, can be proven with a much weaker unpredictability assumption for the TBC. We finally discuss external cryptanalysis results and tweaks to improve both the security margins and efficiency of Spook.