# Analysis of Software Implemented Low Entropy Masking Schemes

Authors: Dan Li; Jiazhe Chen; An Wang; Xiaoyun Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Low Entropy Masking Schemes (LEMS) are countermeasure techniques to mitigate the high performance overhead of masked hardware and software implementations of symmetric block ciphers by reducing the entropy of the mask sets. The security of LEMS depends on the choice of the mask sets. Previous research mainly focused on searching balanced mask sets for hardware implementations. In this paper, we find that those balanced mask sets may have vulnerabilities in terms of absolute difference when applied in software implemented LEMS. The experiments verify that such vulnerabilities certainly make the software LEMS implementations insecure. To fix the vulnerabilities, we present a selection criterion to choose the mask sets. When some feasible mask sets are already picked out by certain searching algorithms, our selection criterion could be a reference factor to help decide on a more secure one for software LEMS.


---

## Body

## 1. Introduction

First introduced by Kocher [1], side channel attacks (SCA) can be used to evaluate the implementation security of cryptographic ciphers by analyzing the time, the electromagnetic radiation, the power consumption, and so on [2–6].To resist SCA, several valid countermeasures have been proposed [7–10]. Among those countermeasures, masking schemes are most popular and widely applied. The main idea of masking schemes is to make the side channel information independent of the sensitive data by randomizing the intermediate values. In general first-order masking scheme, any sensitive intermediate variable denoted by Z will be split into two shares so that Z=S0⊕S1, where the randomly drawn variable S0 is called the mask. All the computations of the cryptographic algorithm are performed on the shared values independently. At the same time, the sensitive data must be recovered by recombining the two shares. For this purpose, every computation function f of cryptographic algorithms should be designed to satisfy f(Z)=S0′⊕S1′, where S0′ and S1′ are the new shares after the operation f. If f is a linear operation with respect to XOR, then S0′=f(S0) and S1′=f(S1). When f is the substitution box (S-Box), some adjustment is necessary to make up for its nonlinear property. The adjusted S-Box function changes along with the value of the mask, which makes it hard to compute canceling the sensitive intermediate value analytically. Therefore, precomputing and caching the required masked S-Boxes are more relevant and efficient. However, if the mask is drawn randomly from 2n possible masks, too much memory is required to keep all the possible masked S-Boxes. To offer a reasonable solution to balance the security protection and the performance of implementations, Low Entropy Masking Schemes (LEMS) [10, 11] are designed by limiting the amount of mask entropy.LEMS use the masks drawn from the limited mask setM={m1,m2,…,ms}⊂F2n whose mask entropy is log2(s). The security of LEMS implementations should be guaranteed in two aspects. In the architecture aspect, cryptographic algorithms should carefully be implemented to avoid first-order leakage [12]. Some countermeasure techniques such as shuffling [13] can also be combined to help defeat certain bivariate and higher order attacks [14–17]. Another aspect is the chosen mask set which plays significant roles in security. Some research studied how to select them for hardware implemented LEMS [11, 18]. The selection criterion of the mask sets considered finding secure mask sets under two important assumptions [19]. The first one is that the attackers could only exploit the leakage of the masked value Z⊕M. The second one is that the deterministic part of the leakage function lZ⊕M is linear in the bits of masked variable Z⊕M, such as Hamming weight function. Under those two conditions, the main goal of selecting mask sets for LEMS is to find balanced mask sets resistant to high order univariate CPA (following the definition of [20], the attack combining n different time instances is called n-variate attack and the nth order attack is the one with nth order statistical moments). Therefore, making ElZ⊕Mα∣Z independent of intermediate Z is the selection criterion of the mask sets for the designer of the hardware countermeasures. However, we find it is not enough for software implemented LEMS. The absolute difference lz⊕m-lz′⊕m′ may bring the unbalance to the intermediate pair (z,z′), which allows attackers to get the information of (z,z′) when only the leakages corresponding to the masked values are available.Our Contributions. In this paper, we study the unbalance in terms of absolute difference on software Low Entropy Masking Schemes (LEMS) implementations and make selection criterion for their mask sets.(i)
We find that the mask sets selected according to selection criteria in [11, 18] have the vulnerabilities based on the absolute difference measurements on software LEMS. Such vulnerabilities make the software LEMS implementations insecure when the leakages corresponding to the masked values could be exploited.(ii)
To fix the vulnerabilities and make software LEMS implementations resistant to high order univariate attacks, we further extend the selection criterion of balanced mask sets. Moreover, we prove the perfect balanced mask sets should not be linear, and their cardinalities should satisfy certain conditions.(iii)
When some feasible mask sets are already picked out by searching algorithms like those in [11], our selection criterion could be a reference factor to help decide on a more secure one from them.Organization. The rest of the paper is organized as follows. In Section 2, we introduce the notations and some related background knowledge. Section 3 presents vulnerabilities that make the software LEMS insecure. Section 4 proves the necessary conditions that the balanced mask sets should satisfy and discusses the selection methods of mask sets. Finally, Section 5 concludes the paper.


## 2. Preliminaries

In this paper, sets are denoted with calligraphic letters (e.g.,M). We use capital letters (e.g., M) and lowercase ones (e.g., m) for random variables and their realizations, respectively. Throughout the paper, Z and Z′ are independent and uniformly distributed random variables representing intermediates. M and M′ are two independent random variables drawn from the uniform distribution in the mask set M.Letlω be the value of leakage measurements corresponding to the intermediate value ω, ω∈F2n. To match with realistic leakage functions in practice, the widely applied Hamming weight leakage model is used during the choice of the mask sets in this paper. Thus, in software environments, lω=ϵHW[ω]+δ, where ϵ is an unknown constant and δ is the Gaussian distributed (N(0, σ2)) noise. In hardware environments, lω=ϵHW[ω] (to describe the theories in [11, 18] more clearly, we use the same no noise model here). We further denote the absolute difference of two measurements corresponding to the values ω1 and ω2 by |lω1-lω2|.Mean and variance are denoted byE and Var, respectively. Let X1 and X2 be two independent random variables and f be a certain function. X1 is randomly drawn from X. E(f(X1,X2)∣X1=x1) is the conditional expectation when X1=x1. The variance among those conditional expectations is(1)VarEfX1,X2∣X1=1X∑x1∈XEfX1,X2∣X1=x1-EfX1,X22which can measure the dispersion degree of E(f(X1,X2)∣X1). Obviously, when Var(E(f(X1,X2)∣X1))=0, the specific value of X1 cannot be recognized according to E(f(X1,X2)∣X1). This property was mainly applied by some works [11, 18] studying the selection criterion of mask sets for hardware LEMS. Their theories are as follows.To defeat high order univariate CPA, the value of intermediateZ should be independent of the statistic values of lZ⊕M=ϵHW[Z⊕M]. Usually, those statistics indicate αth moments denoted by EϵHWZ⊕Mα. Hence, Var(E(ϵHWZ⊕Mα∣Z))=0 is the selection criterion. The mask set is said to resist univariate dth-order attacks if ∀1≤α≤d, α∈N, Var(E(ϵHWZ⊕Mα∣Z))=0.The work in [11] proved that only 12 mask values are sufficient for d=2 when n=8, (M12=03,18,3F,55,60,6E,8C,A5,B2,CB,D6,F9). The work in [18] further studied the linear code mask sets for different d and n. For example, in [8,4,4] linear code mask set can reach the standard of d=3 with 16 mask values when n=8 (like M16=00,0F,36,39,53,5C,65,6A,95,9A,A3,AC,C6,C9,F0,FF used in DPA Contest v4). The linear mask set M has the property that mi⊕mj∈M, mi, mj∈M [21]. We will discuss and use the property in the following sections.


## 3. Vulnerabilities on Software LEMS

As stated in Section2, the selection of the mask sets for hardware LEMS considers the balance between the intermediate values Z and the leakage measurements lZ⊕M to avoid leaking the information of Z. Nonetheless, the unbalance of absolute difference measurements lZ⊕M-lZ′⊕M′ may leak the information of intermediate pair Z,Z′ in software LEMS. In this section, we will study (α represents the order with respect to the absolute difference; indeed, the absolute difference itself is not first order according to Taylor expansion [22]; hence, the order with respect to the original leakage measurement here is higher than α)   EZ,Z′(α)=E(lZ⊕M-lZ′⊕M′α∣Z,Z′), α=1,2. The proofs will show that EZ,Z′(2) is independent of Z,Z′ if the mask set satisfies the hardware selection criterion: Var(E(HWZ⊕Mα∣Z))=0, α=1,2. And it is uncertain for EZ,Z′(1). The unbalanced EZ,Z′(1) leads to the unbalanced variance and coefficient of variation (coefficient of variation is the ratio of standard deviation to mean), which can also help identify the intermediate pair Z,Z′ in attacks. The results of experiments show that the unbalance of EZ,Z′(1) makes the implementations insecure. Those vulnerabilities are the properties of mask sets and cannot be fixed by the architectures of specific implementations like shuffling. So finding the balanced mask sets in terms of absolute difference is necessary for software LEMS, which will be discussed in the next section.Aslz⊕m-lz′⊕m′~NϵHWz⊕m-ϵHWz′⊕m′,2σ2, Elz⊕m-lz′⊕m′2=ϵHWz⊕m-ϵHWz′⊕m′2+2σ2 and Elz⊕m-lz′⊕m′=fϵHWz⊕m-HWz′⊕m′,2σ according to Appendix A. We deduce that (2)Ez,z′1=ElZ⊕M-lZ′⊕M′∣Z=z,Z′=z′(3)=1M2∑m,m′∈MElz⊕m-lz′⊕m′(4)=1M2∑m,m′∈MfϵHWz⊕m-HWz′⊕m′,2σ,(5)Ez,z′2=ElZ⊕M-lZ′⊕M′2∣Z=z,Z′=z′(6)=1M2∑m,m′∈MElz⊕m-lz′⊕m′2(7)=1M2∑m,m′∈MϵHWz⊕m-ϵHWz′⊕m′2+2σ2(8)=EϵHWZ⊕M2∣Z=z+EϵHWZ⊕M2∣Z=z′-2EϵHWZ⊕M∣Z=zEϵHWZ⊕M∣Z=z′+2σ2.Obviously, for the mask setM which satisfies the hardware selection criterion (Var(E(ϵHWZ⊕Mα∣Z))=0, α=1,2), EZ,Z′(2) is independent of Z,Z′.E Z , Z ′ ( 1 ) is associated with the noise. For certain value σ, the value of EZ,Z′(1) converges from 2σ/π to ϵ/M2∑m,m′∈M‍HWz⊕m-HWz′⊕m′ along with ϵ/σ=0→∞. Hence, we can evaluate the unbalance of EZ,Z′(1) for a certain mask set with 1/M2∑m,m′∈M‍HWz⊕m-HWz′⊕m′. We take the mask set M12⊂F28 mentioned in Section 2 as an example and draw values of EZ,Z′(1) for 22∗8 intermediate pairs Z,Z′ in Figure 1 which shows that M12 has vulnerabilities in terms of the absolute difference. Univariate attacks using these vulnerabilities can be performed on one S-Box.Figure 1
E Z , Z ′ ( 1 ) over M12.The results of experiments in AppendixB verify that such vulnerabilities we highlighted can really threaten the security of software LEMS implementations. To make software LEMS implementations resistant to high order univariate attacks (CPA and also attacks based on the vulnerabilities above), specific implementations like shuffling are not enough and selecting the balanced mask sets in terms of the absolute difference is necessary.


## 4. Selection of Balanced Mask Sets

In this section, we will modify the selection criterion to find the balanced mask sets. The proofs give two conditions that the balanced mask sets should satisfy, which considerably narrow down the search for the mask sets.The selection of the mask sets should first satisfy the criteria for hardware selections:Var(E(HWZ⊕Mα)∣Z)=0 at least for α=1,2. In such a condition, EZ,Z′(2) is balanced as analyzed in Section 3. Hence, if Var(EZ,Z′1∣Z,Z′)=0, E(1), VarZ,Z′ and CVZ,Z′ will also be balanced. According to (4), EZ,Z′(1) can further be denoted by σfeϵ/σ,z,z′. We can deduce that (9)VarEZ,Z′1∣Z,Z′=EEZ,Z′12-EEZ,Z′12=σ222n∑z,z′∈F2nfeϵσ,z,z′2-σ22n∑z,z′∈F2nfeϵσ,z,z′2.V a r ( E Z , Z ′ 1 ∣ Z , Z ′ ) will converge from 0 to γ=Var(E(ϵHWZ⊕M-ϵHWZ′⊕M′∣Z,Z′)) when ϵ/σ=0→∞ for any fixed value σ.The value ofγ is an intrinsic property of the mask set. Thus, γ=0 is the selection criterion. In this case, EZ,Z′(1) will be balanced for any ϵ/σ. Aiming at the selection criterion, we can deduce the following conclusions to help select mask sets.γ = 0 indicates E(HWZ⊕M-HWZ′⊕M′∣Z,Z′) is a constant, the value of which is EHWZ⊕M-HWZ′⊕M′. We have the following.Lemma 1.
E H W Z ⊕ M - H W Z ′ ⊕ M ′ = ( 2 n - 1 ) ! ! / 2 n ( n - 1 ) !.Proof.
LetWa=E(HWZ-HWZ′∣HWZ⊕Z′=a). W0=0, obviously. For k∈N, we can deduce that (10)W2k+1=122k+1∑i=02k+12k+1i2k+1-2i=122k+1∑i=0k22k+1i2k+1-2i=122k2k+122k-22k+1∑i=0k-12ki=2k+12kk22k=2k+12k!22kk!2=2k+1!!2k!!.
The second equality uses2k+1i=2k+12k+1-i.
The third one is according to∑i=0k‍2k+1i=22k and i2k+1i=(2k+1)2ki-1.
Similarly,W2k+2=(2k+1)!!/(2k)!!=W2k+1=2k+1/2kW2k. Hence (11)EHWZ⊕M-HWZ′⊕M′=1M24n∑z,z′∈F2n∑m,m′∈MHWz⊕m-HWz′⊕m′=1M24n∑m,m′∈M∑z,z′∈F2nHWz-HWz′=14n∑z,z′∈F2nHWz-HWz′=12n∑i=0nniWi.We will use mathematical induction to prove An=∑i=0n‍niWi=(2n-1)!!/(n-1)!.
Whenn=1, A1=∑i=01‍1iWi=1=2-1!!/(0)!.
SupposeAn=2n-1!!/(n-1)!. If n is odd, we have(12)An+1=∑i=0n+1n+1iWi=∑i=1nni+ni-1Wi+Wn+1=An+∑i=0nniWi+1=An+∑i=0n-1/2n2i+n2i+1W2i+1=An+∑i=0n-1/2n2in+1nW2i+n2i1-n+12in2i+1+n2i+1W2i+1=An+n+1n∑i=0n-1/2n2iW2i+n2i+1W2i+1=2n+1nAn=2n+1!!n!.
The second equality is based onn+1i=ni+ni-1. The fourth one follows W2i+1=W2i+2, and the fifth one uses W2i=2i/2i+1W2i+1.
The situation whenn is even can be proved similarly.
Thus,EHWZ⊕M-HWZ′⊕M′=An/2n=(2n-1)!!/2n(n-1)!.As stated above,E(HWZ⊕M-HWZ′⊕M′∣Z,Z′) for any pair (Z,Z′) and the means of their combinations such as EM=E(E(HWZ⊕M-HWZ⊕M′∣Z)) should be equal to the constant value (2n-1)!!/2n(n-1)!. We can prove two necessary conditions for balanced mask set M by analyzing EM=(2n-1)!!/2n(n-1)!.Theorem 2.
One necessary condition forγ=0 is M=k2n/2+1, k∈N.Proof.
We deduce that(13)EM=EEHWZ⊕M-HWZ⊕M′∣Z(14)=1M22n∑z∈F2n∑m,m′∈MHWz⊕m-HWz⊕m′(15)=1M2∑m,m′∈M12n∑z∈F2nHWz⊕m-HWz⊕m′(16)=1M2∑m,m′∈MEHWZ-HWZ′∣Z⊕Z′=m⊕m′.
LetCi=∑m,m′∈M‍ϱim⊕m′, where (17)ϱix=1,HWx=i,0,otherwise.
Asm⊕m′=m′⊕m, Ci, i>0, is even. Let Ci=2Ci′, i>0. As W0=0, EM=1/M2∑i=0nCiWi=2/M2∑i=1nC′iWi. If EM=(2n-1)!!/2n(n-1)!, we can deduce (18)2M2∑i=1nC′iWi=2n-1!!2nn-1!⟹2n+1M2∑i=1nC′in-1!Wi=2n-1!!⟹2n+1∣M2.
The reason of the second arrow is as follows: RecallW2k+2=W2k+1=(2k+1)!!/(2k)!! in Lemma 1. ∀n≥2k+1, (n-1)!W2k+2=(n-1)!W2k+1=2k-1!!2(2k+1)∏i=2k+1n-1‍i∈N. In other words, ∀i≤n, (n-1)!Wi∈N. 2n+1∑i=1n‍C′i((n-1)!Wi)∈N and (2n-1)!! is odd. Therefore, M2 must be divisible by 2n+1.
Hence,|M|=k2n/2+1, k∈N.Theorem 3.
∀ M < 2 n ∈ N, if M is a linear mask set, γ≠0.Proof.
IfM is linear, m⊕m′∈M, m,m′∈M. Let Dm={m⊕m′∣m′∈M}. Obviously, ∀m∈M, Dm=M. And (16) will further be (19)EM=1M2∑m,m′∈MEHWZ-HWZ′∣Z⊕Z′=m⊕m′=1M2∑m∈M∑m′∈MEHWZ-HWZ′∣Z⊕Z′=m′=1M∑i=0nCiWi,where Ci=∑m∈M‍ϱi(m). ϱi· is defined by (17).
IfEM=2n-1!!/2nn-1!, we can deduce (20)1M∑i=1nCiWi=2n-1!!2nn-1!⟹2nM∑i=1nCin-1!Wi=2n-1!!⟹2n∣Mwhich contradicts |M|<2n. Thus, EM≠(2n-1)!!/2n(n-1)!, which indicates Var(E(HWZ⊕M-HWZ′⊕M′∣Z,Z′))≠0.Theorem2 indicates that the search should be among mask sets satisfying |M|=k2n/2+1, k∈N, to find the perfect balanced mask set with γ=0. However, in consideration of the effect of the noise, γ=0 could not be necessary. According to Theorem 3 and the results in Appendix B, the linear mask sets will be more vulnerable because of their linear property. Hence, one can first use the searching algorithms like those in [11] to get some nonlinear mask sets and use our selection criterion as a reference factor to select the one with smaller γ.


## 5. Conclusion

In this paper, we analyzed the vulnerabilities on the mask sets of software Low Entropy Masking Schemes implementations. We found that satisfying the conditions in [11, 18] was not enough for mask sets used in software LEMS implementations. The experiments verified that such vulnerabilities certainly made the software LEMS implementations insecure. To fix the vulnerabilities, we further gave a selection criterion. Moreover, two theorems were proved, and our selection criterion could be a reference factor when selecting the mask sets picked out by searching algorithms like those in [11].For future work, there remain two research directions. The first direction is the proof of the existence of such perfect balanced mask sets. The second one is designing more feasible search algorithms and giving the masking values selection rules based on those conditions.



---

*Source: 7206835-2018-03-26.xml*