Analysis and improvement of the generic higher-order masking scheme of FSE 2012

Abstract. Masking is a well-known technique used to prevent block ci-pher implementations from side-channel attacks. Higher-order side chan-nel 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 se-cure 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, ormask-ing complexity, of this scheme is related to a variant of the well-known problem of efficient exponentiation (addition chain), and evaluation of polynomials. In this paper we investigate optimal methods for exponentiation in F2n by studying a variant of addition chain, which we call cyclotomic-class addition chain, or CC-addition chain. Among several interesting prop-erties, we prove lower bounds on min-length CC-addition chains. We define the notion of F2n-polynomial chain, and use it to count the num-ber of non-linear multiplications required while evaluating polynomials over F2n. 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 mask-ing 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 evalua-tion 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 improve-ment for them