• web of science banner
  • web of science banner
  • scopus banner
  • Engineering Information banner
  • Inspec Direct banner
  • Dialog banner
  • EBSCO banner
Subscription button Subscription button
ETRI J award winner banner
Article  <  Archive  <  Home
Security of Constant Weight Countermeasures
Yoo-Seung Won, Soung-Wook Choi, Dong-Won Park, and Dong-Guk Han
vol. 39, no. 3, June. 2017, pp. 417-427.
http://dx.doi.org/10.4218/etrij.17.0116.0876
Keywords : Constant weight countermeasures, Bitwise CPA, Balanced leakage model, Imbalanced leakage model.

This is an Open Access article distributed under the term of Korea Open Government License (KOGL) Type 4: Source Indication + Commercial Use Prohibition + Change Prohibition (http://www.kogl.or.kr/news/dataView.do?dataIdx=97).
Manuscript received  Nov. 28, 2016;   revised  Jan. 31, 2017;   accepted  Feb. 02, 2017.  
  • Abstract
    • Abstract

      This paper investigates the security of constant weight countermeasures, which aim to produce indistinguishable leakage from sensitive variables and intermediate variables, assuming a constant Hamming distance and/or Hamming weight leakages. To investigate the security of recent countermeasures, contrary to many related studies, we assume that the coefficients of the simulated leakage models follow a normal distribution so that we may construct a model with approximately realistic leakages. First, using our simulated leakage model, we demonstrate security holes in these previous countermeasures. Subsequently, in contrast to the hypotheses presented in previous studies, we confirm the resistance of these countermeasures to a standard correlation power analysis (CPA). However, these countermeasures can allow a bitwise CPA to leak a sensitive variable with only a few thousand traces.
  • Authors
    • Authors

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_a001.jpg

      mathwys87@kookmin.university

      Yoo-Seung Won received his BS and degrees in mathematics from Kookmin University, Seoul, Rep. of Korea in 2012 and 2014, respectively. He is currently a PhD student with the Department of Financial Information Security of Kookmin University. His research interests include side channel attacks, smart card security, symmetric-key cryptosystems, and public-key cryptosystems.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_a002.jpg

      swchoi@ranix.co.kr

      Soung-Wook Choi received his BS and MS degrees in physics from Sungkyunkwan University, Suwon, Rep. of Korea, in 1986 and 1988, respectively. Since then, he has had nearly 30 years of experience in the field of system semiconductor design. He founded RANIX, Inc., Seoul, Rep. of Korea in 2003 and is currently working as the CEO of the company. His main interests are the development of system ICs associated with automotive communication and security.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_a003.jpg

      dwpark@ranix.co.kr

      Dong-Won Park received his BS degree in computer science from Kyoungwon University, Sungnam, Rep. of Korea, in 1995. Since 1996, he has accumulated nearly 19 years of experience in the field of embedded systems and security chip sets. He joined RANIX, Inc., Seoul, Rep. of Korea in 2012 and is charge of developing security chips for IoT and automotive applications as a principal research engineer. His main interests are the development of trusted computing environment for embedded device.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_a004.jpg

      Corresponding Author christa@kookmin.ac.kr

      Dong-Guk Han received his BS degree in mathematics from Korea University, Seoul, Rep. of Korea, in 1999 and 2002, respectively. He received his PhD in engineering in information security from Korea University in 2005. He was a postdoctoral researcher at Future University, Hakodate, Japan. He was subsequently an exchange student in the Department of Computer Science and Communication Engineering in Kyushu University, Fukuoka, Japan, from April 2004 to March 2005. He has also worked as a senior researcher at ETRI, Daejeon, Rep. of Korea. He is currently working as an associate professor with the Department of Mathematics of Kookmin University, Seoul, Rep. of Korea. He is a member of KIISC, IEEK, and IACR.

  • Full Text
    • I. Introduction

      Today, the Internet of Things (IoT) has gradually improved our lives. However, private information is increasingly at risk because IoT objects are now being commonly used in our everyday lives. In other words, our information is increasingly exposed to numerous threats. Physical devices in particular are not naturally resilient to side-channel analysis [1]. It is therefore important that physical devices are defended through masking and/or hiding countermeasures [2], [3]. In terms of software implementation, the main purpose of masking is to destroy the relation between side-channel leakages and sensitive variables. Nevertheless, masking schemes can be threatened by higher-order attacks [4][8]. On the contrary, the main purpose of hiding countermeasures is to mitigate the amount of statistical information between side-channel leakages and sensitive information. Commonly, the cost of a masking countermeasure is more than that of a hiding countermeasure. Moreover, these countermeasures are compatible with each other. Thus, their combination can facilitate high security at a low cost.

      One aim of hiding countermeasures is to make the leakage for all intermediate variables constant. In this way, leakage from sensitive variables becomes indistinguishable to the leakage from intermediate variables. Such countermeasures, however, have usually been implemented in the hardware before software-type countermeasures were suggested. More precisely, Hoogvost and others [9] proposed the concept of a dual-rail with pre-charge logic [10][15] for implementing software. The performed trial, however, did not contain a security evaluation for side-channel analysis.

      Subsequently, symbolic representation, which was proposed by Maekawa and others [16] was considered more efficient than earlier methods from the viewpoint of memory cost. Despite its merit, this analysis also omitted a security evaluation. Consequently, it was unclear whether the implementation of a constant weight countermeasure could be considered secure. More recently, after self-evaluating security against a side-channel analysis, some constant weight countermeasures were re-suggested. Servant and others [17] argued that their design could be sufficiently resilient to an uncomplicated side-channel analysis. Assuming a polynomial leakage function to hold constant coefficients, they demonstrated a constant countermeasure. More precisely, when performing correlation power analysis (CPA) [18] on simulated traces, the success rate of recovering a sensitive variable was less than 10%.

      The previously suggested countermeasures only dealt with Hamming weight leakage. However, in physical devices, most leakage occurs in the software and can be simulated by a Hamming weight model. Thus, hardware leakage cannot be concealed perfectly and might depend on Hamming distance leakage. Thus, a constant countermeasure can theoretically be designed considering the combination of Hamming weight with Hamming distance leakages. For the first time, Chen and others [19] suggested such a scheme, which is referred to as balanced encoding. Specifically, in an AVR board, they argued that this scheme can be resilient to a first-order CPA. Additionally, under a particular leakage model, they showed that leaking a sensitive variable is not allowed.

      In this study, we perform a security evaluation of the countermeasures of Chen and others [19] and Servant and others [17]. In particular, we use the polynomial form of a higher-degree leakage model than that used in previous works. In general, the coefficients of a polynomial form are considered as zero or one. However, such a constraint may make it difficult to identify the security evaluation in practice. Therefore, we use leakage model coefficients that deviate from the regular model. For this, we suppose that the coefficients exhibit a normal distribution. Therefore, we establish two leakage models, balanced and imbalanced leakage models. Furthermore, we conduct CPA on both simulated leakage models and on an AVR implementation using the block cipher PRINCE countermeasure [20] and the block cipher AES countermeasure [17]. Crucially, we show that the leakage of these countermeasures is no longer constant in a simulated or implemented environment when evaluated through bitwise [21]. Therefore, these countermeasures cannot guarantee security against uncomplicated side-channel analytical schemes.

      II. Preliminary

      This section offers an overview of the formal encoding rule of a constant weight countermeasure and an explanation of the encoded operation.

      1. Constant Weight Encoding Scheme Rule

      This subsection provides a formal encoding rule aimed at a constant weight. In other words, every m bit codeword ranges from zero to m + 1. That is, the total number of m bit codewords with Hamming weight w is ( m w ) . Thus, an encoding rule is required to acquire a constant Hamming weight.

      The reason why the Hamming weight is constant in the encoding scheme is that there is a close connection to the side-channel leakage information. In general, the quantity of leakage information between bit 0 and bit 1 is not identical. Therefore, to provide resistance against a side-channel analysis, the number of 0 or 1 bits included in an m bit codeword should be constant. However, the number of 0 bits should not be identical to the number of 1 bits. If so, the side-channel information will always be uniform. The detailed encoding rule is as follows:

      ER ( n , w , m ) : { 0 , 1 } n { z { 0 , 1 } m | HW ( z ) = w }                                  x y = ER ( n , w , m ) ( x ) ,
      (1)

      where HW indicates the Hamming weight function, and ER(n, w, m) is the surjective function. To form a function, the number of elements in an image should be more than those in the domain; that is, ( m w ) 2 n . Moreover, the ER(n,w,m) function is not unique. In other words, there are many ways for an encoding rule to be applied. More precisely, # ER ( n , w , m ) = ( ( m w ) 2 n ) .

      There have been attempts to implement various encoding rules through software. Recently, approaches such those as in [19] and [17] have been suggested. As stated previously, here, we evaluate the security obtained through two approaches, and we provide a brief introduction to both.

      A. Encoding Rule of the Block Cipher PRINCE Countermeasure

      First, Chen and others used the ER(4,4,8) function in [19]. Moreover, they were faithful to the idea initially presented in [9], meaning that a 1-bit codeword was converted into a 2-bit codeword. For example, bit 0 or bit 1 was encoded into 10 or 01, respectively. In Table 1, we list the detailed encoding rule that they employed. In addition, we denote it using 𝕭, which is called the balanced encoding rule in [19], instead of ER(4, 4, 8).

      Table 1.

      Encoding rule proposed by Chen and others [19].

      Original codeword ↦ encoded codewordOriginal codeword ↦ encoded codeword
      00002 ↦ 10101010210002 ↦ 011010102
      00012 ↦ 10101001210012 ↦ 011010012
      00102 ↦ 10100110210102 ↦ 011001102
      00112 ↦ 10100101210112 ↦ 011001012
      01002 ↦ 10011010211002 ↦ 010110102
      01012 ↦ 10011001211012 ↦ 010110012
      01102 ↦ 10010110211102 ↦ 010101102
      01112 ↦ 10010101211112 ↦ 010101012

      B. Servant and Others’ Encoding Rule of the Block Cipher AES Countermeasure

      Another encoding rule is the ER(4,3,6) function, which is also focused on memory efficiency. To convert it from a 4-bit codeword, ( m w ) should be more than 24. The memory size is most appropriate when m = 6 and w = 3. Additionally, we use the notation 𝕮 employed in [17]. This encoding rule is shown in Table 2.

      Table 2.

      Encoding rule proposed by Servant and others [17].

      Original codeword ↦ encoded codewordOriginal codeword ↦ encoded codeword
      00002 ↦ 000111210002 ↦ 0110102
      00012 ↦ 001011210012 ↦ 0111002
      00102 ↦ 001101210102 ↦ 1000112
      00112 ↦ 001110210112 ↦ 1001012
      01002 ↦ 010011211002 ↦ 1001102
      01012 ↦ 010101211012 ↦ 1010012
      01102 ↦ 010110211102 ↦ 1010102
      01112 ↦ 011010211112 ↦ 1011002

      2. Encoded Operation after Applying the Encoding Rule to a Codeword

      We provide the operation rules here. We recommend the general method if the base size of the block cipher is not large. Otherwise, the special approach is better. Their detailed descriptions are as follows.

      A. General Approach for the Encoding Operation

      In accordance with the encoding rule, the operation form is transformed using a pre-computed table T. Thus, when the codeword A (rep. B) is encoded into ER(n, w, m)(A) (resp. ER(n, w, m)(B)), the operation AB can be calculated from the output of the pre-computed table T, such that T[(ER(n, w, m)(A) ≪ t)||ER(n, w, m)(B)] = ER(n, w, m) (AB), where ⊥ is any operation such as an XOR or AND, and t is either the size of the codeword or the size of a processor word.

      B. Special Approach for the Encoding Operation

      The general method can be used when an n bit codeword is the same as the base size of the operation in the block cipher. If not, however, an n/l bit codeword has to be encoded after dividing the base size into l parts. As an example of a univariate operation such as S-box, the input of the pre-computed table T is T[{ER(n/l, w, m)(Al−1) ≪ t(l−1)}||⋯||{ER(n/l, w, m)(A1) ≪ t }|| {ER(n/l, w, m)(A0)}], where A = Al−1||⋯||A1||A0. In addition, the pre-computed table T outputs part of the encoded value ER(n/l, w, m)(S-box(A)i) where i = 0, … , l−1. That is, for an S-box operation, l pre-computed tables are required.

      To utilize the encoding rule developed by Chen and others [19], the block cipher PRINCE was used as an example. Therefore, the general method could be used because the depth of the base bit is a nibble. In contrast, in [17], to calculate a linear/non-linear operation, the special method was required because the authors applied the block cipher AES countermeasure.

      III. Leakage Model and Security Evaluation

      After defining the simulated leakage model in this section, we describe how to evaluate the constant weight countermeasures.

      1. Leakage Model

      In this section, we review the simulated leakage model from [22]. To obtain a more realistic model, the polynomial form is chosen as the simulated leakage model. Unlike many previous models, the value of the coefficients in the leakage model is likely to follow a normal distribution. The model in [22] proves useful when a countermeasure, such as a constant weight, is evaluated. The leakage model is as follows.

      L ( X ) = i a i x i + i , j b i , j ( x i x j ) + i , j , k c i , j , k ( x i x j x k ) ,
      (2)

      where xi indicates the ith bit of the sensitive value X,; ai, bi,j, and ci,j,k are some weighting coefficients; and ai ~ 𝒩 (μi, σi) , bi,j ~ 𝒩 (μi,j, σi,j), and ci,j,k ~ 𝒩 (μi,j,k, σi,j,k), where μi and σi denote the average and variance, respectively.

      We divide the available models for selecting a coefficient value into two types: balanced and imbalanced leakage models. First, the balanced leakage model is a fundamental approach in which the weighting coefficients of (2) are equal to the degree of the polynomial. This approach is used to investigate the effects of the order of the coefficients. The other approach, called the imbalanced leakage model, is used to observe the influence of the coefficients’ distribution. The conditions for the two leakage models are as follows.

      ▪Balanced Leakage Model in (2)

      1) ∀i, μi = μa and σi = σa

      2) ∀i, j, μi,j = μb and σi,j = σb

      3) ∀i, j, k, μi,j,k = μc and σi,j,k = σc

      4) |μa −1| < ϵμ and |μb −1| < ϵμ and |μc −1| < ϵμ

      5) 0 < σa < ϵσ and 0 < σb < ϵσ and 0 < σc < ϵσ

      ▪ Imbalanced Leakage Model in (2)

      1) ∀i, j, bi,j = 0

      2) ∀i, j, k, ci,j,k = 0

      3) |μi −1| < ϵμ

      4) 0 < σi < ϵσ

      Here, ϵμ and ϵσ have very small positive values. Because the realistic leakage roughly conforms to the Hamming weight in the software implementation, this property corresponds to condition 4 in the balanced leakage model, and condition 3 in the imbalanced leakage model. However, we only consider the first degree of the polynomial in the imbalanced leakage model, although the second- or third-degree coefficients could be considered. This means that conditions 1 and 2 in the imbalanced leakage model are required. Consequently, a linear model is only considered as our leakage model. We believe that such a model cannot simulate the properties of the physical device sufficiently because we assigned each coefficient to different distributions. In other words, it is necessary to investigate the security of the constant weight countermeasures when the leakage model parameters are severely biased. In addition, there would be too many cases to consider. Therefore, we simply investigate a single biased bit in this work.

      2. Security Evaluation

      To evaluate the security of the countermeasures, we performed simple side-channel analysis. The experimental results are represented in terms of the guessing entropy [23]. Robust analyses such as a template and stochastic analysis are not taken into account in this paper. First, the newly designed countermeasure should have resistance against a simple side-channel analysis. If not, the countermeasure should be reconstructed from the beginning. Therefore, we investigate here the security evaluation against a simple side-channel analysis indicating a standard and bitwise CPA.

      A. Standard and Bitwise CPA

      To perform the CPA, the adversary computes the correlation between the guessed intermediate variable and the obtained traces, after determining the leakage model appropriately. In general, the total size of a guessed intermediate variable is directly applied to the expected leakage model when evaluating the software countermeasure. In the case of the AES block cipher, an 8-bit intermediate variable can be considered as crucial side-channel information rather than part of the 8-bit intermediate variable. On the contrary, in a hardware countermeasure, a part of a guessed intermediate variable can have a significant meaning because of a glitch or other such occurrence. When conducting standard CPA, we represent the guessed intermediate variable containing the Hamming weight leakage model by HW(·) and the intermediate variable X by HW(X). In bitwise CPA, we denote the least significant ith bit by Xi and use HW(Xi) for the guessed intermediate variable.

      A constant weight countermeasure is a combination of a hardware-type countermeasure and software implementation; performing standard and bitwise CPA on this countermeasure may be required.

      B. Security Metric

      We establish security metrics to quantify the effect of various attacks. Thus, we adopt the guessing entropy as one of the most commonly used metrics.

      Let gq be a vector with the key candidates sorted according to the assessment results after the side-channel analysis is conducted. Variable S indicates the set of key candidates, that is, gq = [g1, g2, ⋯ , g|S| ]. Moreover, let Lq be a random vector of the traces collected q times and lq = [l1, l2 , ... , lq ] be the realization of this vector. The index of a key class s in the side-channel analysis is defined as ls (gq ) = i such that gi = s. The guessing entropy is then the average position of s in this vector, which is given by

      G E S = E s E l q l s ( g q ) .
      (3)

      The guessing entropy refers to the average number of key candidates. In addition, to calculate the guessing entropy in this paper, we obtain the average of 1,000 trials.

      IV. Experimental Results

      Here, we present the experimental results for the simulated and real traces. The simulated traces are generated based on the information in Section III. Subsequently, we evaluate the security of the constant weight countermeasures. To do so, we should be able to determine the position of the main attack. Thus, an intermediate variable, which is the object of the security evaluation, is the output of S-box. Therefore, in the case of [19], 𝕭(S-box(X)) is the main target, where S-box indicates the PRINCE S-box. In contrast, according to [17], the target is 𝕮 (S-box(X)h) (resp. 𝕮 (S-box(X)l)), where S-box refers to the AES S-box, and S-boxh (resp. S-boxl) is the most (resp. least) significant of the four bits of a byte S-box(X).

      In addition, because the number of PRINCE (resp. AES) S-box output bits is four (resp. eight), four and eight results are represented after conducting the bitwise CPA.

      1. Security Evaluation for the Balanced Leakage Model

      As mentioned earlier, we present the results based on the balanced leakage model. The aim of this section is to investigate the effects of the order of coefficients in (2). For this, the detailed parameter settings for the balanced leakage model in (2) are listed below.

      1) μaμbμc and σaσbσc

      2) ϵμ ≥ 0.01 and ϵσ ≥ 0.01

      According to the settings in the first item, there are four possible cases. For example, to identify the effects of the average variation, the average can be converted into the difference when each variance is fixed. That is, μa = 1.02, μb = 1.01, μc = 1.00, and σa = σb = σc = 0.01. The remaining cases can be constructed in a similar way. However, as shown in Appendix A, the guessing entropy consistently preserves the middle value, regardless of the variations of the average and variance. In other words, all cases seem to be secure against an uncomplicated side-channel analysis. When the leakage properties of the physical devices follow the balanced leakage model, there might be some endurance against an uncomplicated side-channel analysis. We believe, however, that there are few physical devices that can satisfy these properties.

      In next subsection, we consider an approach that is more practical than the balanced leakage model.

      2. Security Evaluation for the Imbalanced Leakage Model

      Unlike the balanced leakage model, the imbalanced leakage model is a practical approach. In this model, the hardware properties cannot be completely removed because the device components consist of hardware, even though cryptographic algorithms are implemented in software. More precisely, each bit of the codewords can produce different leakage information. Of course, it is possible to combine multiple bits of leakage information. Thus, we investigate security using two examples of constant weight countermeasures under the imbalanced leakage model.

      A. Encoding Rule of Chen and Others

      Under the definition of the 𝕭 encoding rule, eight results occur, because the operation is implemented in a general manner. In other words, our main target is 𝕭(S-box(X)), which is composed of eight bits. Therefore, the settings of the imbalanced leakage model in (2) are as follows.

      1) ai ~ 𝒩 (1.01, 0.01), aj ~ 𝒩 (1.00, 0.01), where 0 ≤ j < 8, ij.

      2) ∀i, j, bi,j = 0, ∀i, j, k, ci,j,k = 0.

      Based on the above assumption, we conduct an uncomplicated side-channel analysis on the countermeasure proposed by Chen and others [19]. As mentioned previously, eight results can be presented. However, we only illustrate four cases because the 𝕭 encoding rule consists of four original bits and four complementary bits. In other words, we can inject a biased distribution over xi or x ¯ i , , where 𝕭 (S-box(X)) = x 3 ¯ x 3 x 2 ¯ x 2 x 1 ¯ x 1 x 0 ¯ x 0 . In this paper, we apply a biased distribution to each complementary bit, and the results of the standard and bitwise CPAs are depicted in Fig. 1. As we predicted, when conducting the bitwise CPA, a sensitive variable is revealed in all cases.

      Fig. 1.

      CPA results on the countermeasure proposed by Chen and others, which includes imbalance leakage traces.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f001.jpg

      However, when conducting standard CPA, the security of the 𝕭 encoding rule is guaranteed. The exception is μ7, which contains biased information. There is still uncertainty regarding the cause of the observed results. We guess that the relation between the original codeword and the post-conversion codeword slightly influences the results1). Because sensitive information cannot be concealed in all other cases, another countermeasure is required. As in [19], when conducting standard CPA, the leakage information cannot be recovered. However, we demonstrate that the countermeasure of the 𝕭 encoding rule cannot be used to protect sensitive information when performing bitwise CPA.

      B. Encoding Rule of Servant and Others

      Following the definition of the simulation, the number of target bits is six. Thus, the total number of generated traces is six. More precisely, let us denote by 𝕮 (S-box(X)h) = x5x4x3x2x1x0 the encoded output of the variable S-box(X)h. By definition, from Section III, each bit contains biased information. Without a loss of generality, the experimental variables of the imbalanced leakage model in (2) are as follows.

      1) ai ~ 𝒩 (1.01, 0.01), aj ~ 𝒩 (1.00, 0.01), where 0 ≤ j < 6, ij.

      2) ∀i, j, bi,j = 0, ∀i, j, k, ci,j,k = 0.

      The results of the uncomplicated side-channel analysis are shown in Fig. 2. As predicted, a sensitive variable cannot be perfectly concealed in most cases when conducting bitwise CPA. However, excluding Case 2-1, these variables seem to be resilient to standard CPA. Case 2-1 is probably different because of the dependency on the correlation between the pre-encoded data HW(S-box(X)) and the post-encoded data point x0. In addition, another interesting result is that the guessing entropy reaches one only in Cases 2-1 and 2-2. In Case 2-4 (resp. 2-5), the lowest guessing entropy value is about 15 (resp. 7). Although this countermeasure does not completely hide the sensitive variables, the correct key cannot be uniquely decided for any case. Particularly, in Case 2-3, conducting uncomplicated side-channel analysis is ineffective for producing a significant guessing entropy value. Nevertheless, the correct key can be regained directly, if biased information is combined to create a larger bit of biased information. In other words, one cannot easily conceal sensitive variables if the realistic leakage information contains more than one bits of biased information.

      Fig. 2.

      CPA results on the countermeasure proposed by Servant and others, which includes imbalance leakage traces.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f002.jpg

      Compared to the 𝕭 encoding rule in [19], the 𝕮 encoding rule in [17] exhibits weaker resistance against standard CPA. In Cases 2-1, 2-5, and 2-6, the correct key seems to be easily retrieved owing to the low value of the guessing entropy. Without resistance to standard CPA, it has some resilience against bitwise CPA compared to the 𝕭 encoding rule in [19]. However, as mentioned earlier, there is a potential for leaking the correct key. Although the cryptographic devices conform to a strong Hamming weight leakage, they fail to conceal the correct key.

      Note that the performance of the 3rd bitwise CPA over the total number of attacks is the worst in terms of the guessing entropy, because all cases include over 50. This is because the encoded value may be independent of the 3rd bit of the pre-encoded value.

      3. Security Evaluation for an AVR Implementation

      Next, we perform a security evaluation of an 8-bit AVR microcontroller board for the 𝕭 and 𝕮 encoding rules. In particular, we measure the power consumption of the AVR chip. To evaluate the security of the 𝕭 encoding rule, 8-bit ATMega-128 is utilized. In addition, we use a ChipWhisperer-Lite (CW1173) basic board for the 𝕮 encoding rule. For all experiments, we use sampling rates of 500 MHz and 118 MHz for the 𝕭 rule and 𝕮 encoding rule, respectively. In the case of the ChipWhisperer-Lite basic board, the choice of sampling rate lies between the original value and four times the clock frequency of the microcontroller chip. Thus, we use four times the clock frequency here for information that is more detailed. The main target is to obtain a single output S-box and a total of 200,000 traces with random plaintext inputs and a fixed secret key.

      A. Encoding Rule of Chen and Others

      To verify resistance against uncomplicated side-channel analysis, we conduct a test on PRINCE with no countermeasure and the 𝕭 encoding rule. Comparing the attack performances between standard CPA and bitwise CPA, standard CPA is better than bitwise CPA. As Figs. 3(a) and (b) demonstrate, the results of standard CPA are definitely superior to those of bitwise CPA. In contrast, as shown in Figs. 3(c) and (d), the results of the analysis change after countermeasures are applied.

      According to previous studies [19], in the 𝕭 encoding rule, the relation between the real traces and pre-defined leakage model is considerably diminished. Thus, we compare the results of Figs. 3(a) and (c). In the case of PRINCE with no countermeasure, the correlation is approximately 0.6, whereas in the 𝕭 encoding rule, the correlation is almost 0.2. However, the bitwise CPA results are not better than those of the standard CPA. The results shown in Fig. 3 indicate that the 𝕭 encoding rule is more vulnerable to bitwise CPA. Although the guessing entropy in Fig. 3(c) is significantly low, it is not easy to distinguish precisely the correct key from the key candidates. As stated in Section IV. 2, the vulnerability of the 𝕭 encoding rule can be directly detected when the properties of the real leakage become lightly biased at the position of any bit.

      Fig. 3.

      (a), (b) Standard and bitwise CPA results for PRINCE with no countermeasure; and (c), (d) PRINCE with Chen and others’ countermeasure. x-axis and y-axis represent the number of real traces utilized and the absolute Pearson’s correlation coefficient, respectively.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f003.jpg

      B. Encoding Rule of Servant and Others

      The results for the 𝕮 encoding rule do not differ much from those shown in Fig. 3. That is, as indicated in Fig. 4, the correlation is shrunk by approximately half compared to the standard and bitwise CPAs. Furthermore, the correlation drops from about 0.9 to around 0.2. Unfortunately, in terms of bitwise CPA, the vulnerability and correlation are roughly identical to the results of AES with no countermeasure. Therefore, contrary to the hypothesis presented in [17], only few real traces are sufficient to recover the correct key.

      Fig. 4.

      (a), (b) Standard and bitwise CPA results for AES with no countermeasure; and (c), (d), AES with Servant and others’ countermeasure. x-axis and y-axis represent the number of real traces utilized and the absolute Pearson’s correlation coefficient, respectively.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f004.jpg

      Figure 5 indicates the security degree for the constant weight countermeasures. We can acquire sensitive information through bitwise CPA on only a few thousand traces. However, standard CPA alone is insufficient for obtaining sensitive variables. In particular, many power traces are required in order to obtain a low guessing entropy value. However, despite using several thousand traces, the guessing entropy is not much different. For instance, in the results of the standard CPA (Fig. 5(a)), the difference between the maximum and the minimum guessing entropy is only 0.75. Consequently, we can easily recover the correct key, and the experimental results are similar to our simulated results. In comparison with the imbalanced leakage model, the current of the guessing entropy has some resemblance with the results of Case 1-4 in Fig. 1. Again, when conducting a standard CPA, the guessing entropy is usually very low. It is also extremely vulnerable when conducting a 0th bitwise CPA. However, some parts do not fit with the results of the simulations, in particular, the results of the 2nd and 3rd bitwise CPAs. Nevertheless, the real trace reveals sensitive information when conducting bitwise CPA.

      Moreover, as shown in Fig. 5(b), the results of performing the 0th, 3rd, and 4th bitwise CPAs stand out more than the rest. Additionally, we failed to locate the correct key through standard CPA. An asymptote of the guessing entropy of standard CPA is about 10. Therefore, the computational cost to recover the master key is about 1016 (≈ 250). That is, the constant weight countermeasure has sufficient resistance to standard CPA, which is similar to some of the results of the simulated traces.

      Fig. 5.

      Results of a security assessment for constant weight countermeasures against real traces in an AVR board. x-axis and y-axis represent the number of real traces used and the guessing entropy, respectively: (a) Chen and others countermeasure PRINCE and (b) Servant and others countermeasure AES.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f005.jpg

      However, in both cases, the leakage of sensitive variables from real traces is more serious than expected. As previously stated, with only 1,000 traces, the master key can be retrieved effortlessly. The main reason why the results of the real traces are different from those of the simulated traces may be that the biased information has more than a single bit. In other words, the real traces in the AVR board are likely to have more bits of biased information.

      With the exception of the balanced leakage model, sensitive information is not perfectly revealed, even when a bitwise CPA is conducted. This indicates that the real model does not match the balanced leakage model perfectly. As stated previously, if the realistic leakage is fit to the balanced leakage model, security can be guaranteed.

      C. Possible Constant Leakage Countermeasure Remedies

      Recently, another way to improve these countermeasures has been suggested [24]. However, the weakness of this countermeasure is that we need to determine the hardware properties before applying the countermeasure. Additionally, the security evaluation of this countermeasure cannot yet be guaranteed assuming our leakage model.

      As a result, a constant leakage countermeasure is vulnerable to bitwise CPA when the leakage model conforms to our assumption. However, from a practical perspective, these countermeasures can be utilized in combination with other countermeasures, such as masking, shuffling, and hardware noise. Because the amount of information between the encoding data and real traces is significantly less than before the encoding, a realistic countermeasure can be provided by combining constant leakage with another countermeasure. For example, combining constant leakage with masking is harder than applying the generic masking countermeasure, because the critical leakage depends on each bit. Therefore, as with shuffling, a constant leakage countermeasure can be one of the additional countermeasures.

      V. Conclusion

      In this study, we conducted a security evaluation of constant weight countermeasures. To perform a precise security evaluation, we build balanced and imbalanced practical leakage models. Contrary to previous works, we assumed that the coefficients of a polynomial form conform to a normal distribution. Under this assumption, we established a critical leak from the simulated traces. We recommend that the properties of cryptographic devices be examined before applying these countermeasures to cryptographic devices. These countermeasures may be resistant to uncomplicated side-channel analysis if the properties of the devices completely conform to the balanced leakage model.

      However, on an 8-bit microcontroller board, a leak can be easily identified through bitwise CPA. To summarize, we cannot defend against basic side-channel analysis of the imbalanced leakage traces and real traces. In other words, the fatal flaw of these countermeasures remains. To achieve resistance to uncomplicated side-channel analysis, the constant weight countermeasure should be reconstructed from the beginning while considering severely biased information.

      In addition, to ensure the security of the constant weight countermeasure against basic side-channel analysis without real implementation, our model is recommended because the security can be destroyed through severely biased information. In other words, despite this assumption, if the newly designed countermeasure endures basic side-channel analysis, this countermeasure will be suitable for security protection.

      Appendix A.

      This appendix provides the results for the 𝕭 and 𝕮 encoding rules assuming a balanced leakage model (see Fig. 6). Contrary to our expectations, all results produce similar results assuming the balanced leakage model. That is, the security of these countermeasures is impervious to any change of the average and variance. In agreement with a previous study [19], these countermeasures are shown to resist both standard and bitwise CPA.

      Fig. 6.

      CPA results on the countermeasure proposed by Chen and others (left) and the countermeasure proposed by Servant and colleagues (right), which includes balance leakage traces.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f006.jpg

      Footnotes

      Yoo-Seung Won (mathwys87@kookmin.university) is with the Department of Financial Information Security of Kookmin University, Seoul, Rep. of Korea.

      Soung-Wook Choi (swchoi@ranix.co.kr) is CEO of Ranix, Inc., Seoul, Rep. of Korea.

      Dong-Won Park (dwpark@ranix.co.kr) is with the Department of R&D of Ranix, Inc., Seoul, Rep. of Korea.

      Dong-Guk Han (corresponding author, christa@kookmin.ac.kr) is with the Department of Mathematics and Financial Information Security of Kookmin University, Seoul, Rep. of Korea.

      This work was partially supported by the Institute for Information and Communications Technology Promotion (IITP) grant funded by the Korean government (MSIP) (No. B0126-15-1008) and (No. 2017-0-00520, Development of SCR-Friendly Symmetric Key Cryptosystem and Its Application Modes). This work was partially supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2013R1A1A2A10062137). The authors would also like to thank Dooho Choi at ETRI his help with the SCARF boards (http://www.-kscarf.or.kr/). The SCARF boards were supported by the KLA-SCARF project, the ETRI ICT R&D Program.

      1)

      Here, Correlation (x3x2x1x0, x3) ≈ 0.87 (Correlation (A, B) is the absolute value of Pearson’s correlation coefficient between A and B). In other cases, however, it is not more than 0.5.

  • References
    • References

      [1] 

      P. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis,” Int. Cryptology Conf. Adv. Cryptology, Santa Barbara, CA, USA, Aug. 15–19, 1999, pp. 388–397.

      [2] 

      Y. Ishai, A. Sahai, and D. Wagner, “Private Circuits: Securing Hardware Against Probing Attacks,” Int. Cryptology Conf. Adv. Cryptology, Santa Barbara, CA, USA, Aug. 17–21, 2003, pp. 462–481.

      [3] 

      M. Rivain and E. Prouff, “Provably Secure Higher-Order Masking of AES,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Santa Barbara, USA, Aug. 17–20, 2010, pp. 413–427.

      [4] 

      H. Kim, S. Hong, and J. Lim, “A Fast and Provably Secure Higher-Order Masking of AES S-Box,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Nara, Japan, Sept. 28–Oct. 1, 2011, pp. 95–107.

      [5] 

      J.-S. Coron, E. Prouff, and M. Rivain, “Higher-Order Side Channel Security and Mask Refreshing,” Int. Workshop Fast Softw. Encryption, Singapore, Mar. 11–13, 2013, pp. 410–424.

      [6] 

      J. Waddle and D. Wagner, “Towards Efficient Second-Order Power Analysis,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Cambridge, MA, USA, Aug. 11–13, 2004, pp. 1–15.

      [7] 

      J. Pan, J.I. Den Hartog, and J. Lu, “You Cannot Hide Behind the Mask: Power Analysis on a Provably Secure S-Box Implementation,” Int. Workshop Inform. Security Applicat., Busan, Rep. of Korea, Aug. 25–27, 2009, pp. 178–192.

      [8] 

      V. Grosso, F.-X. Standaert, and E. Prouff, “Low Entropy Masking Schemes, Revisited,” Int. Conf. Smart Card Res. Adv. Applicat., Berlin, Germany, Nov. 27–29, 2013, pp. 33–43.

      [9] 

      P. Hoogvorst, G. Duc, and J.-L. Danger, “Software Implementation of Dual-Rail Representation,” Int. Workshop Constructive Side-Channel Anal. Secure Des., Darmstadt, Germany, Feb. 24–25, 2011, pp. 73–81.

      [10] 

      K. Tiri and I. Verbauwhede, “Securing Encryption Algorithms against DPA at the Logic Level: Next Generation Smart Card Technology,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Cologne, Germany, Sept. 8–10, 2003, pp. 125–136.

      [11] 

      D. Sokolov et al., “Improving the Security of Dual-Rail Circuits,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Cambridge, MA, USA, Aug. 11–13, 2004, pp. 282–297.

      [12] 

      K. Tiri and I. Verbauwhede, “A Logic Level Design Methodology for a Secure DPA Resistant ASIC or FPGA Implementation,” Proc. Des. Autom. Test Eur. Conf. Exhibition, Paris, France, Feb. 16–20, 2004, pp. 246–251.

      [13] 

      T. Popp and S. Mangard, “Masked Dual-Rail Pre-charge Logic: DPA-Resistance without Routing Constraints,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Edinburgh, UK, Aug. 29–Sept. 1, 2005, pp. 172–186.

      [14] 

      D. Suzuki and M. Saeki, “Security Evaluation of DPA Countermeasures Using Dual-Rail Pre-charge Logic Style,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Yokohama, Japan, Oct. 10–13, 2006, pp. 255–269.

      [15] 

      S. Guilley, L. Sauvage, and F. Flament, “Evaluation of Power Constant Dual-Rail Logics Countermeasures against DPA with Design Time Security Metrics,” IEEE Trans. Comput., vol. 59, no. 9, July 2010, pp. 1250–1263.  

      [16] 

      A. Maekawa, N. Yamashita, and T. Okamura, “Tamper-Resistance Techniques Based on Symbolic Implementation against Power Analysis,” Symp. Cryptography Inform. Security, Tokyo, Japan, Jan. 22–25, 2013, pp. 73–81.

      [17] 

      V. Servant et al., “Study of a Novel Software Constant Weight Implementation,” Int. Conf. Smart Card Res. Adv. Applicat., Paris, France, Nov. 5–7, 2014, pp. 35–48.

      [18] 

      E. Brier, C. Clavier, and F. Olivier, “Correlation Power Analysis with a Leakage Model,” Int. Workshop Cryptograph. Hardw. Embedded Syst., Cambridge, MA, USA, Aug. 11–13, 2004, pp. 16–29.

      [19] 

      C. Chen et al., “Balanced Encoding to Mitigate Power Analysis: a Case Study,” Int. Conf. Smart Card Res. Adv. Applicat., Paris, France, Nov. 5–7, 2014, pp. 49–63.

      [20] 

      J. Borghoff et al., “PRINCE–a Low-Latency Block Cipher for Pervasive Computing Applications,” Int. Conf. Theory Applicat Cryptology Inform. Security Adv. Cryptology, Beijing, China, Dec. 2–6, 2012, pp. 208–225.

      [21] 

      R. Bevan and E. Knudsen, “Ways to Enhance Differential Power Analysis,” Int. Conf. Inform. Security Cryptology, Seoul, Rep. of Korea, Nov. 28–29, 2002, pp. 327–342.

      [22] 

      Y.S. Won et al., “On the Security of Balanced Encoding Countermeasures,” Int. Conf. Smart Card Res. Adv. Applicat., Bochum, Germany, Nov. 4–6, 2015.

      [23] 

      F.-X. Standaert, T.G. Malkin, and M. Yung, “A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks,” Int. Conf. Theory Applicat. Cryptograph. Techn. Adv. Cryptology, Cologne, Germany, Apr. 26–30, 2009, pp. 443–461.

      [24] 

      H. Margherbi, V. Servant, and J. Bringer. “There Is Wisdom in Harnessing the Strenghts of Your Enemy: Customized Encoding to Thwart Side-Channel Attacks,” Int. Workshop Fast Softw. Encryption, Germany, Mar. 20–23, 2016, pp. 223–243.

  • Cited by
    • Cited by

  • Metrics
    • Metrics

      Article Usage

      360
      Downloaded
      415
      Viewed

      Citations

      0
      0
  • Figure / Table
    • Figure / Table

      Fig. 1.

      CPA results on the countermeasure proposed by Chen and others, which includes imbalance leakage traces.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f001.jpg
      Fig. 2.

      CPA results on the countermeasure proposed by Servant and others, which includes imbalance leakage traces.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f002.jpg
      Fig. 3.

      (a), (b) Standard and bitwise CPA results for PRINCE with no countermeasure; and (c), (d) PRINCE with Chen and others’ countermeasure. x-axis and y-axis represent the number of real traces utilized and the absolute Pearson’s correlation coefficient, respectively.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f003.jpg
      Fig. 4.

      (a), (b) Standard and bitwise CPA results for AES with no countermeasure; and (c), (d), AES with Servant and others’ countermeasure. x-axis and y-axis represent the number of real traces utilized and the absolute Pearson’s correlation coefficient, respectively.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f004.jpg
      Fig. 5.

      Results of a security assessment for constant weight countermeasures against real traces in an AVR board. x-axis and y-axis represent the number of real traces used and the guessing entropy, respectively: (a) Chen and others countermeasure PRINCE and (b) Servant and others countermeasure AES.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f005.jpg
      Fig. 6.

      CPA results on the countermeasure proposed by Chen and others (left) and the countermeasure proposed by Servant and colleagues (right), which includes balance leakage traces.

      images/2017/v39n3/ETRI_J001_2017_v39n3_417_f006.jpg
      Table 1.

      Encoding rule proposed by Chen and others [19].

      Original codeword ↦ encoded codewordOriginal codeword ↦ encoded codeword
      00002 ↦ 10101010210002 ↦ 011010102
      00012 ↦ 10101001210012 ↦ 011010012
      00102 ↦ 10100110210102 ↦ 011001102
      00112 ↦ 10100101210112 ↦ 011001012
      01002 ↦ 10011010211002 ↦ 010110102
      01012 ↦ 10011001211012 ↦ 010110012
      01102 ↦ 10010110211102 ↦ 010101102
      01112 ↦ 10010101211112 ↦ 010101012
      Table 2.

      Encoding rule proposed by Servant and others [17].

      Original codeword ↦ encoded codewordOriginal codeword ↦ encoded codeword
      00002 ↦ 000111210002 ↦ 0110102
      00012 ↦ 001011210012 ↦ 0111002
      00102 ↦ 001101210102 ↦ 1000112
      00112 ↦ 001110210112 ↦ 1001012
      01002 ↦ 010011211002 ↦ 1001102
      01012 ↦ 010101211012 ↦ 1010012
      01102 ↦ 010110211102 ↦ 1010102
      01112 ↦ 011010211112 ↦ 1011002