[Resource Topic] 2013/345: Analysis and Improvement of the Generic Higher-Order Masking Scheme of FSE 2012

Welcome to the resource topic for 2013/345

Analysis and Improvement of the Generic Higher-Order Masking Scheme of FSE 2012

Authors: Arnab Roy, Srinivas Vivek


Masking is a well-known technique used to prevent block cipher implementations from side-channel attacks. Higher-order side channel attacks (e.g. higher-order DPA attack) on widely used block cipher like AES have motivated the design of efficient higher-order masking schemes. Indeed, it is known that as the masking order increases, the difficulty of side-channel attack increases exponentially. However, the main problem in higher-order masking is to design an efficient and secure technique for S-box computations in block cipher implementations. At FSE 2012, Carlet et al. proposed a generic masking scheme that can be applied to any S-box at any order. This is the first generic scheme for efficient software implementations. Analysis of the running time, or \textit{masking complexity}, of this scheme is related to a variant of the well-known problem of efficient exponentiation (\textit{addition chain}), and evaluation of polynomials. In this paper we investigate optimal methods for exponentiation in \mathbb{F}_{2^{n}} by studying a variant of addition chain, which we call \textit{cyclotomic-class addition chain}, or \textit{CC-addition chain}. Among several interesting properties, we prove lower bounds on min-length CC-addition chains. We define the notion of \GFn-polynomial chain, and use it to count the number of \textit{non-linear} multiplications required while evaluating polynomials over \mathbb{F}_{2^{n}}. We also give a lower bound on the length of such a chain for any polynomial. As a consequence, we show that a lower bound for the masking complexity of DES S-boxes is three, and that of PRESENT S-box is two. We disprove a claim previously made by Carlet et al. regarding min-length CC-addition chains. Finally, we give a polynomial evaluation method, which results into an improved masking scheme (compared to the technique of Carlet et al.) for DES S-boxes. As an illustration we apply this method to several other S-boxes and show significant improvement for them.

ePrint: https://eprint.iacr.org/2013/345

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .