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

Arnab Roy; Srinivas Vivek

Paper 2013/345

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

Arnab Roy and Srinivas Vivek

Abstract

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 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 . 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.

Note: Full version

Metadata

Available format(s): PDF
Category: Implementation
Publication info: A major revision of an IACR publication in CHES 2013
Keywords: block cipher S-box masking complexity addition chain polynomial evaluation side-channel attack
Contact author(s): Arnab Roy @ uni lu
srinivasvivek venkatesh @ uni lu
History: 2014-03-23: revised; 2013-06-09: received; See all versions
Short URL: https://ia.cr/2013/345
License: CC BY

BibTeX

@misc{cryptoeprint:2013/345,
      author = {Arnab Roy and Srinivas Vivek},
      title = {Analysis and Improvement of the Generic Higher-Order Masking Scheme of {FSE} 2012},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/345},
      year = {2013},
      url = {https://eprint.iacr.org/2013/345}
}