Generalized Polynomial Decomposition for S-boxes with Application to Side-Channel Countermeasures
Masking is a widespread countermeasure to protect implementations of block-ciphers against side-channel attacks. Several masking schemes have been proposed in the literature that rely on the efficient decomposition of the underlying s-box(es). We propose
- PDF / 706,483 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 46 Downloads / 173 Views
2
CryptoExperts, Paris, France {dahmun.goudarzi,matthieu.rivain}@cryptoexperts.com ENS, CNRS, INRIA, PSL Research University, Paris, France [email protected] 3 University of Bristol, Bristol, UK [email protected]
Abstract. Masking is a widespread countermeasure to protect implementations of block-ciphers against side-channel attacks. Several masking schemes have been proposed in the literature that rely on the efficient decomposition of the underlying s-box(es). We propose a generalized decomposition method for s-boxes that encompasses several previously proposed methods while providing new trade-offs. It allows to evaluate nλ-bit to mλ-bit s-boxes for any integers n, m, λ ≥ 1 by seeing it a sequence of m n-variate polynomials over F2λ and by trying to minimize the number of multiplications over F2λ . Keywords: S-box decomposition · Multiplicative complexity · Sidechannel countermeasure · Masking · Software implementation · Block-cipher
1
Introduction
Implementing cryptographic algorithms in constrained embedded devices is a challenging task. In the 1990s, Kocher et al. [Koc96,KJJ99] showed that one may often use the physical leakage of the underlying device during the algorithm execution (e.g., the running-time, the power consumption or the electromagnetic radiations) to recover some secret information. Side-channel analysis is the class of cryptanalytic attacks that exploit such physical emanations to hinder the strength of the underlying cryptography. One of the most common technique to protect implementations against sidechannel attacks is to mask internal secret variables. This so-called masking technique [GP99,CJRR99] splits every sensitive data manipulated by the algorithm (which depends on the secret key and possibly on other variables known to the attacker) into d + 1 shares (where d ≥ 1, the masking order, plays the role of a c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 154–171, 2017. DOI: 10.1007/978-3-319-66787-4 8
Generalized Polynomial Decomposition for S-boxes
155
security parameter). The first d shares are usually generated uniformly at random and the last one is computed so that the combination of the d + 1 shares for some group law is equal to the initial value. With this technique, the attacker actually needs the whole set of d+1 shares to learn any information on the initial value. Since each share’s observation comes with noise, the higher is the order d, the more complex is the attack [CJRR99,PR13]. This masking approach permits to achieve provable security in formal security models, notably the probing security model [ISW03] and the noisy leakage model [PR13,DDF14]. Most symmetric cryptographic algorithms manipulate binary data x ∈ {0, 1}n (for some integer n ≥ 1) and the natural group law used for masking is the Boolean XOR ⊕ over F2 (or more generally addition in the finite field F2n or in the vector space Fn2 ). Using this Boolean masking, each sensitive data x is thus split into d+1 shares x0 , . .
Data Loading...
