# Side-Channel Attacks and Countermeasures for Identity-Based Cryptographic Algorithm SM9

Authors: Qi Zhang; An Wang; Yongchuan Niu; Ning Shang; Rixin Xu; Guoshuang Zhang; Liehuang Zhu
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Identity-based cryptographic algorithm SM9, which has become the main part of the ISO/IEC 14888-3/AMD1 standard in November 2017, employs the identities of users to generate public-private key pairs. Without the support of digital certificate, it has been applied for cloud computing, cyber-physical system, Internet of Things, and so on. In this paper, the implementation of SM9 algorithm and its Simple Power Attack (SPA) are discussed. Then, we present template attack and fault attack on SPA-resistant SM9. Our experiments have proved that if attackers try the template attack on an 8-bit microcontrol unit, the secret key can be revealed by enabling the device to execute one time. Fault attack even allows the attackers to obtain the 256-bit key of SM9 by performing the algorithm twice and analyzing the two different results. Accordingly, some countermeasures to resist the three kinds of attacks above are given.


---

## Body

## 1. Introduction

With the development of integrated circuit and communication technology, smart devices are not only widely spread in our daily life with the proliferation of Internet of things, but also extensively used in the global IT environments and critical infrastructures. Security becomes a critical issue since attacks on these devices may directly harm the consumers. Several papers [1–4] have studied related security and wireless issues.Identity-Based Cryptography (IBC) which applies user identity as the public key was proposed by Shamir in 1984 [5] to reduce the complexity of key and certificate management. Developed by the Commercial Cryptography Administration of China in 2016, SM9 [6] has become the most typical identity-based cryptographic algorithm in China. Compared with traditional cryptographic algorithms, SM9 not only omits the exchange of digital certificates and public key processes, but also simplifies the deployment and management of the security systems. Because of its usability and simplicity, SM9 has been employed as the standard for commercial cryptography in China. Its digital signature algorithm has become an international standard as the main part of the ISO/IEC 14888-3/AMD1 in November 2017 [7] too. It is also adopted to secure various systems and scenarios like E-mail [8], cloud storage, intelligent devices [9], industrial control, online communications, mobile payment, and so on.As described in [10] by Kocher et al. in 1999, it has been proved that even though mathematical characteristics can guarantee the security of cryptographic algorithms in theory, their implementation may suffer from Side-Channel Attack (SCA). SCA allows attackers to reveal secrets by analyzing the side information of an attacked device which is running a cryptographic algorithm, such as power consumption, electromagnetic radiation, and execution time. Because of the low cost and high efficiency, SCA has successfully cracked lots of devices which run DES [11], AES [12], RSA [13], and ECC [14]. Despite SM9 algorithm being secure in cryptography theory, whether it is against SCA is still a matter of concern.At present, the three main SCA techniques are Simple Power Attack (SPA), template attack, and fault attack. Due to the versatility and operability, they have been studied in depth and used to crack various cryptographic algorithms. SPA [15] exploits one trace to reconstruct the sequence of operations during the secret computation and derive information about the secrets from this sequence. As a special power analysis, template attack [16] makes a better use of all information present in each sample. And it is hence the strongest form of SCA possible in an information theoretic sense given the few samples that are available. Fault attack, as another main branch of SCA, often injects errors into cryptographic computation processes and identifies the secret key by analyzing the mathematical and statistical properties of wrong calculation results. Proposed by Biham and Shamir in [17], the fault attack on RSA has become a milestone for the security of public key cryptographic devices.In this paper, we show that SCA does have a practical threat to the implementation of SM9. We propose the above three kinds of SCA attacks on SM9 algorithm. After this, some corresponding countermeasures are also introduced. The main contributions of this paper are as follows.( 1 ) A SPA attack on SM9 algorithm is proposed. And we also introduce some countermeasures to resist SPA.( 2 ) Different from general Elliptic Curve Digital Signature Algorithm (ECDSA), the key is a point on elliptic curves rather than a scalar in scalar multiplication for SM9 algorithm. According to this feature, a template attack is presented for SPA-resistant SM9 implementation and several countermeasures are provided.( 3 ) We propose a fault attack and conduct experiments to prove that software implementation of SM9 algorithm is vulnerable to this scheme. And then, some corresponding countermeasures are also presented.This paper is organized as follows. In Section2, the summarization of SM9 algorithm and its implementation are introduced. We give the basic idea of SPA on SM9 in detail and put forward some countermeasures in Section 3. Then, in Section 4, a template attack is provided to attack the protected SM9 which can resist SPA and the corresponding countermeasures are also given. In Section 5, a fault attack for SPA-resistant SM9 algorithm is presented and several countermeasures are introduced against this scheme. Finally, we conclude this paper in Section 6.


## 2. The Preliminaries

### 2.1. SM9 Digital Signature Generation Algorithm

SM9 digital signature algorithm usually assumes a scenario where Alice communicates with Bob. Alice generates the signature(h,S) of message M by SM9 digital signature generation algorithm for authentication and sends them to Bob. Bob validates the received message M′ and its signature (h′,S′) with signature verification algorithm to ensure the authenticity and integrity of this digital signature.In order to express clearly, we give the meanings of letters as follows. The signature private key of Alice denoted asdsA is provided by Key Generation Center (KGC). Group G1 and group G2 are addition cyclic groups of order N and their generators are denoted as P1 and P2, respectively. Group GT is a multiplicative cyclic group with order N. Let e denote the bilinear pairs mapping function from G1·G2 to GT. KGC generates a random number ks as the signature master private key and computes Ppub-s=ksP2 as the master public key. Ppub-s is well-known, and ks is kept secretly by KGC. A cryptographic hash function is denoted as H2m,N.Algorithm1 shows SM9 digital signature generation algorithm. At the beginning of the signature process, system parameters are provided as a part of inputs to make this algorithm work.Algorithm 1:SM9 digital signature generation algorithm.
Input: system parameters, signature master public key Ppub-s, message M, signature private key dsA. Output: M, h,S. ( 1 ) Compute g=eP1,Ppub-s in GT. ( 2 ) Generate a random number r∈1,N-1. ( 3 ) Compute w=gr in GT, and convert the data type of w to bit stream. ( 4 ) Compute h=H2M∥w,N. ( 5 ) Compute l=r-hmodN. ( 6 )  if  l==0  then ( 7 )    goto  (2). ( 8 ) Compute S=ldsA in G1. ( 9 ) Convert the data type of h and S to byte stream. ( 10 )  return  M, h,S


### 2.2. The Implementation of SM9 Digital Signature Algorithm

#### 2.2.1. Scalar Multiplication

Scalar multiplication is the most important part in elliptic curve cryptography algorithm and its fast implementation is an inevitable demand of practical applications. As shown in Algorithm1, scalar multiplication is directly related to the signature private key dsA in SM9 digital signature generation algorithm.The operation of adding a pointP to itself for k times is called scalar multiplication and is denoted as Q=kP. For decades, many methods have been proposed to implement this operation and the most common is binary algorithm. There are two ways to implement scalar multiplication, left-to-right and right-to-left. And the former is shown in Algorithm 2 and the special point O is called the point at infinity. In the following sections, we assume that scalar multiplication is executed with the left-to-right binary algorithm.Algorithm 2:Left-to-right binary algorithm.
Input: point P, n-bit integer k=∑i=0n-1‍ki2i, ki∈0,1. Output:  Q=kP. ( 1 )  Q=O. ( 2 )  for  i=n-1 to 0 do ( 3 )  Q = 2 Q. ( 4 )  if  ki==1  then ( 5 )  Q = Q + P. ( 6 )  end for ( 7 )  return  QIn Algorithm2, point doubling is executed n times. In probability, the count of 1 in a scalar integer k is close to n/2, so point addition is executed nearly n/2 times. Let A represent point addition and D represent point doubling; the operation quantity of binary method is approximately n/2·A+n·D.


#### 2.2.2. Point Addition and Point Doubling

An elliptic curve is a set of points(x,y) in which x,y∈F. F denotes a finite field. The set of points on an elliptic curve, together with a special point O called the point at infinity, can be equipped with an Abelian group structure by addition operation. An elliptic curve over F can be expressed as the form of Weierstrass equation:(1)y2+a1xy+a3y=x3+a2x2+a4x+a6,where ai∈F. If prime number p≠2 and 3, the Weierstrass equation can be transformed to(2)y2=x3+ax+b,with a,b∈F.For prime numberp≠2 and 3, let P=x1,y1≠O be a point. The inverse of P is -P=x1,-y1 and Q=x2,y2≠O is a second point with Q≠-P. Point addition P+Q=x3,y3 can be calculated as(3)x3=λ2-x1-x2y3=λx1-x3-y1, with(4)
λ
=
y
2
-
y
1
x
2
-
x
1
,
P
≠
Q
3
x
1
2
+
a
2
y
1
,
P
=
Q
.The operation ofP+Q is called point addition if P≠Q. And it is called point doubling if P=Q. Obviously, point addition differs from point doubling in the form of formula.


#### 2.2.3. Montgomery Modular Multiplication

Given a modulusN and two integers X and Y of size N in base b, with gcdN,b=1 and r=blogbN, Montgomery modular multiplication algorithm [18] computes:(5)MontMulX,Y,N=X·Y·r-1modN.Montgomery modular multiplication algorithm is shown in Algorithm3. Its essence is to combine X·Y and U·N by traditional multiplication method. As described in line 2 to line 8, U is unknown at first. With obtaining ui calculated by xi·y0, each ui·N can be calculated too. Finally, U can be derived. MontMulX,Y,N can be computed by alternating all xi·Y and ui·N and adding up to A. Figure 1 illustrates the intuitive graphical representation of CIOS modular multiplication [19, 20].Algorithm 3:Montgomery modular multiplication algorithm.
Input:  X=xn-1⋯x1x0b, Y=yn-1⋯y1y0b, N=nn-1⋯n1n0b,  n′=-N-1modb, gcdN,b=1,  r=blogbN. Output:  X⋅Y⋅r-1modN. ( 1 )  A=an-1⋯a1a0b←0. ( 2 )  for  i=0 to n-1  do ( 3 )  A ← A + x i ⋅ Y. ( 4 )  u i ← a 0 ⋅ n ′ m o d  b. ( 5 )  A ← A + u i ⋅ N / b. ( 6 )  if  A≥N  then ( 7 )  A ← A - N. ( 8 )   end for ( 9 )   return  AFigure 1
CIOS modular multiplication.


### 2.3. Power Analysis Attack

In SPA [15], attackers directly observe power consumption for a single execution of target operation without any statistical methods. As a special power analysis, template attack [16] generally consists of the following three phases. The first is template building phase, and attackers build templates to characterize devices by executing a sequence of instructions on fixed data. Next, it allows attackers to match the templates to the power consumption traces of devices in template matching phase. Finally, attackers can do some analysis and derive secret information during offline searching phase.Hamming weight model proposed in [10, 21] analyzes the correlation between power consumption and the register switching from one state to the other. It is generally assumed that power consumption depends on the number of bits switching from 0 to 1 or 1 to 0 within the corresponding time. For n-bit register, binary data D=dn-1dn-2⋯d1d0 is coded as D=∑i=0n-1‍di2i with di=0 or 1; its Hamming weight HWD=∑i=0n-1‍di is the number of bits set to 1. Considering a chip as a large set of elementary electrical components, its power consumption contains not only the state changes but also other variables’ consumption, such as offsets, time dependent components, and noise. Therefore, the basic model for the data dependency can be described as W=aHWD+b, where a is a constant and b indicates the other consumption.


### 2.4. Fault Attack

Fault attack [17] allows attackers to disturb cryptographic devices by physical methods to make them run in wrong states. Due to the injected fault, the devices perform some operations in modified environment and produce incorrect results. Combining with the algorithm in the devices, some knowledge related to the secret key could be gained from the results. Because of the lower cost, simple operation, and obvious effect, fault attack has become one of the most concerned SCA techniques.Faults in devices can be made for a variety of reasons. In general, variations in normal working conditions can be injecting faults into a system effectively. For example, changing supply voltage or clock frequency can disrupt execution process and cause the processor to skip some instructions or change its output. Exposing devices in the temperatures outside its operational range usually makes random modifications to the memory. It is also possible to inject faults more accurately by using the inherent photoelectric effects of electric circuits. Under the exposure of photons, devices can produce induced currents and disrupt normal operations. In fact, lasers can make faults more precise in terms of target area and injection time. Also, faults can be injected in packaged circuits without removing the packaging by X-rays and ion beams.


### 2.5. Problem Formulation

Different from the general ECDSA and SM2 algorithm, the secret key in scalar multiplication is the point on elliptic curves rather than the scalar for SM9 algorithm. The scalar of the classical ECC and SM2 is a secret and the point is known, while the scalar and the point are both unknown in SM9. Therefore, the attack methods of the two are fundamentally different. In this paper, we focus on this issue to present template attack described in Section4 and fault attack described in Section 5 which are only applied to SM9.


## 2.1. SM9 Digital Signature Generation Algorithm

SM9 digital signature algorithm usually assumes a scenario where Alice communicates with Bob. Alice generates the signature(h,S) of message M by SM9 digital signature generation algorithm for authentication and sends them to Bob. Bob validates the received message M′ and its signature (h′,S′) with signature verification algorithm to ensure the authenticity and integrity of this digital signature.In order to express clearly, we give the meanings of letters as follows. The signature private key of Alice denoted asdsA is provided by Key Generation Center (KGC). Group G1 and group G2 are addition cyclic groups of order N and their generators are denoted as P1 and P2, respectively. Group GT is a multiplicative cyclic group with order N. Let e denote the bilinear pairs mapping function from G1·G2 to GT. KGC generates a random number ks as the signature master private key and computes Ppub-s=ksP2 as the master public key. Ppub-s is well-known, and ks is kept secretly by KGC. A cryptographic hash function is denoted as H2m,N.Algorithm1 shows SM9 digital signature generation algorithm. At the beginning of the signature process, system parameters are provided as a part of inputs to make this algorithm work.Algorithm 1:SM9 digital signature generation algorithm.
Input: system parameters, signature master public key Ppub-s, message M, signature private key dsA. Output: M, h,S. ( 1 ) Compute g=eP1,Ppub-s in GT. ( 2 ) Generate a random number r∈1,N-1. ( 3 ) Compute w=gr in GT, and convert the data type of w to bit stream. ( 4 ) Compute h=H2M∥w,N. ( 5 ) Compute l=r-hmodN. ( 6 )  if  l==0  then ( 7 )    goto  (2). ( 8 ) Compute S=ldsA in G1. ( 9 ) Convert the data type of h and S to byte stream. ( 10 )  return  M, h,S


## 2.2. The Implementation of SM9 Digital Signature Algorithm

### 2.2.1. Scalar Multiplication

Scalar multiplication is the most important part in elliptic curve cryptography algorithm and its fast implementation is an inevitable demand of practical applications. As shown in Algorithm1, scalar multiplication is directly related to the signature private key dsA in SM9 digital signature generation algorithm.The operation of adding a pointP to itself for k times is called scalar multiplication and is denoted as Q=kP. For decades, many methods have been proposed to implement this operation and the most common is binary algorithm. There are two ways to implement scalar multiplication, left-to-right and right-to-left. And the former is shown in Algorithm 2 and the special point O is called the point at infinity. In the following sections, we assume that scalar multiplication is executed with the left-to-right binary algorithm.Algorithm 2:Left-to-right binary algorithm.
Input: point P, n-bit integer k=∑i=0n-1‍ki2i, ki∈0,1. Output:  Q=kP. ( 1 )  Q=O. ( 2 )  for  i=n-1 to 0 do ( 3 )  Q = 2 Q. ( 4 )  if  ki==1  then ( 5 )  Q = Q + P. ( 6 )  end for ( 7 )  return  QIn Algorithm2, point doubling is executed n times. In probability, the count of 1 in a scalar integer k is close to n/2, so point addition is executed nearly n/2 times. Let A represent point addition and D represent point doubling; the operation quantity of binary method is approximately n/2·A+n·D.


### 2.2.2. Point Addition and Point Doubling

An elliptic curve is a set of points(x,y) in which x,y∈F. F denotes a finite field. The set of points on an elliptic curve, together with a special point O called the point at infinity, can be equipped with an Abelian group structure by addition operation. An elliptic curve over F can be expressed as the form of Weierstrass equation:(1)y2+a1xy+a3y=x3+a2x2+a4x+a6,where ai∈F. If prime number p≠2 and 3, the Weierstrass equation can be transformed to(2)y2=x3+ax+b,with a,b∈F.For prime numberp≠2 and 3, let P=x1,y1≠O be a point. The inverse of P is -P=x1,-y1 and Q=x2,y2≠O is a second point with Q≠-P. Point addition P+Q=x3,y3 can be calculated as(3)x3=λ2-x1-x2y3=λx1-x3-y1, with(4)
λ
=
y
2
-
y
1
x
2
-
x
1
,
P
≠
Q
3
x
1
2
+
a
2
y
1
,
P
=
Q
.The operation ofP+Q is called point addition if P≠Q. And it is called point doubling if P=Q. Obviously, point addition differs from point doubling in the form of formula.


### 2.2.3. Montgomery Modular Multiplication

Given a modulusN and two integers X and Y of size N in base b, with gcdN,b=1 and r=blogbN, Montgomery modular multiplication algorithm [18] computes:(5)MontMulX,Y,N=X·Y·r-1modN.Montgomery modular multiplication algorithm is shown in Algorithm3. Its essence is to combine X·Y and U·N by traditional multiplication method. As described in line 2 to line 8, U is unknown at first. With obtaining ui calculated by xi·y0, each ui·N can be calculated too. Finally, U can be derived. MontMulX,Y,N can be computed by alternating all xi·Y and ui·N and adding up to A. Figure 1 illustrates the intuitive graphical representation of CIOS modular multiplication [19, 20].Algorithm 3:Montgomery modular multiplication algorithm.
Input:  X=xn-1⋯x1x0b, Y=yn-1⋯y1y0b, N=nn-1⋯n1n0b,  n′=-N-1modb, gcdN,b=1,  r=blogbN. Output:  X⋅Y⋅r-1modN. ( 1 )  A=an-1⋯a1a0b←0. ( 2 )  for  i=0 to n-1  do ( 3 )  A ← A + x i ⋅ Y. ( 4 )  u i ← a 0 ⋅ n ′ m o d  b. ( 5 )  A ← A + u i ⋅ N / b. ( 6 )  if  A≥N  then ( 7 )  A ← A - N. ( 8 )   end for ( 9 )   return  AFigure 1
CIOS modular multiplication.


## 2.2.1. Scalar Multiplication

Scalar multiplication is the most important part in elliptic curve cryptography algorithm and its fast implementation is an inevitable demand of practical applications. As shown in Algorithm1, scalar multiplication is directly related to the signature private key dsA in SM9 digital signature generation algorithm.The operation of adding a pointP to itself for k times is called scalar multiplication and is denoted as Q=kP. For decades, many methods have been proposed to implement this operation and the most common is binary algorithm. There are two ways to implement scalar multiplication, left-to-right and right-to-left. And the former is shown in Algorithm 2 and the special point O is called the point at infinity. In the following sections, we assume that scalar multiplication is executed with the left-to-right binary algorithm.Algorithm 2:Left-to-right binary algorithm.
Input: point P, n-bit integer k=∑i=0n-1‍ki2i, ki∈0,1. Output:  Q=kP. ( 1 )  Q=O. ( 2 )  for  i=n-1 to 0 do ( 3 )  Q = 2 Q. ( 4 )  if  ki==1  then ( 5 )  Q = Q + P. ( 6 )  end for ( 7 )  return  QIn Algorithm2, point doubling is executed n times. In probability, the count of 1 in a scalar integer k is close to n/2, so point addition is executed nearly n/2 times. Let A represent point addition and D represent point doubling; the operation quantity of binary method is approximately n/2·A+n·D.


## 2.2.2. Point Addition and Point Doubling

An elliptic curve is a set of points(x,y) in which x,y∈F. F denotes a finite field. The set of points on an elliptic curve, together with a special point O called the point at infinity, can be equipped with an Abelian group structure by addition operation. An elliptic curve over F can be expressed as the form of Weierstrass equation:(1)y2+a1xy+a3y=x3+a2x2+a4x+a6,where ai∈F. If prime number p≠2 and 3, the Weierstrass equation can be transformed to(2)y2=x3+ax+b,with a,b∈F.For prime numberp≠2 and 3, let P=x1,y1≠O be a point. The inverse of P is -P=x1,-y1 and Q=x2,y2≠O is a second point with Q≠-P. Point addition P+Q=x3,y3 can be calculated as(3)x3=λ2-x1-x2y3=λx1-x3-y1, with(4)
λ
=
y
2
-
y
1
x
2
-
x
1
,
P
≠
Q
3
x
1
2
+
a
2
y
1
,
P
=
Q
.The operation ofP+Q is called point addition if P≠Q. And it is called point doubling if P=Q. Obviously, point addition differs from point doubling in the form of formula.


## 2.2.3. Montgomery Modular Multiplication

Given a modulusN and two integers X and Y of size N in base b, with gcdN,b=1 and r=blogbN, Montgomery modular multiplication algorithm [18] computes:(5)MontMulX,Y,N=X·Y·r-1modN.Montgomery modular multiplication algorithm is shown in Algorithm3. Its essence is to combine X·Y and U·N by traditional multiplication method. As described in line 2 to line 8, U is unknown at first. With obtaining ui calculated by xi·y0, each ui·N can be calculated too. Finally, U can be derived. MontMulX,Y,N can be computed by alternating all xi·Y and ui·N and adding up to A. Figure 1 illustrates the intuitive graphical representation of CIOS modular multiplication [19, 20].Algorithm 3:Montgomery modular multiplication algorithm.
Input:  X=xn-1⋯x1x0b, Y=yn-1⋯y1y0b, N=nn-1⋯n1n0b,  n′=-N-1modb, gcdN,b=1,  r=blogbN. Output:  X⋅Y⋅r-1modN. ( 1 )  A=an-1⋯a1a0b←0. ( 2 )  for  i=0 to n-1  do ( 3 )  A ← A + x i ⋅ Y. ( 4 )  u i ← a 0 ⋅ n ′ m o d  b. ( 5 )  A ← A + u i ⋅ N / b. ( 6 )  if  A≥N  then ( 7 )  A ← A - N. ( 8 )   end for ( 9 )   return  AFigure 1
CIOS modular multiplication.


## 2.3. Power Analysis Attack

In SPA [15], attackers directly observe power consumption for a single execution of target operation without any statistical methods. As a special power analysis, template attack [16] generally consists of the following three phases. The first is template building phase, and attackers build templates to characterize devices by executing a sequence of instructions on fixed data. Next, it allows attackers to match the templates to the power consumption traces of devices in template matching phase. Finally, attackers can do some analysis and derive secret information during offline searching phase.Hamming weight model proposed in [10, 21] analyzes the correlation between power consumption and the register switching from one state to the other. It is generally assumed that power consumption depends on the number of bits switching from 0 to 1 or 1 to 0 within the corresponding time. For n-bit register, binary data D=dn-1dn-2⋯d1d0 is coded as D=∑i=0n-1‍di2i with di=0 or 1; its Hamming weight HWD=∑i=0n-1‍di is the number of bits set to 1. Considering a chip as a large set of elementary electrical components, its power consumption contains not only the state changes but also other variables’ consumption, such as offsets, time dependent components, and noise. Therefore, the basic model for the data dependency can be described as W=aHWD+b, where a is a constant and b indicates the other consumption.


## 2.4. Fault Attack

Fault attack [17] allows attackers to disturb cryptographic devices by physical methods to make them run in wrong states. Due to the injected fault, the devices perform some operations in modified environment and produce incorrect results. Combining with the algorithm in the devices, some knowledge related to the secret key could be gained from the results. Because of the lower cost, simple operation, and obvious effect, fault attack has become one of the most concerned SCA techniques.Faults in devices can be made for a variety of reasons. In general, variations in normal working conditions can be injecting faults into a system effectively. For example, changing supply voltage or clock frequency can disrupt execution process and cause the processor to skip some instructions or change its output. Exposing devices in the temperatures outside its operational range usually makes random modifications to the memory. It is also possible to inject faults more accurately by using the inherent photoelectric effects of electric circuits. Under the exposure of photons, devices can produce induced currents and disrupt normal operations. In fact, lasers can make faults more precise in terms of target area and injection time. Also, faults can be injected in packaged circuits without removing the packaging by X-rays and ion beams.


## 2.5. Problem Formulation

Different from the general ECDSA and SM2 algorithm, the secret key in scalar multiplication is the point on elliptic curves rather than the scalar for SM9 algorithm. The scalar of the classical ECC and SM2 is a secret and the point is known, while the scalar and the point are both unknown in SM9. Therefore, the attack methods of the two are fundamentally different. In this paper, we focus on this issue to present template attack described in Section4 and fault attack described in Section 5 which are only applied to SM9.


## 3. Simple Power Attack and Countermeasures on SM9

### 3.1. Simple Power Attack on SM9

In this paper, we focus the computation of scalar multiplicationS=ldsA to apply our SPA attack which is described in line 8 of Algorithm 1.Our SPA attack against SM9 recoversl by observing the differences in power consumption caused by the difference operations for bit 1 and bit 0. As described in Algorithm 2, it always performs a point doubling operation whether the bit is 0 or 1. And an extra point addition will be performed if the bit is 1. Because of the differences between side-channel pattern of doubling and that of addition, attackers can easily reveal l from a single power trace. As N and S are both known, dsA can be calculated by the formula dsA=l-1S.Attackers can also perform SPA attack onw=gr as shown in line 3 of Algorithm 1. The SPA attack on modular exponentiation is similar to that of scalar multiplication. Employing the different power consumption by manipulating 1 and 0 can derive the exponent r. The lengths of r, l, and N are 256 bits so that l can be obtained by the formula l=r-hmodN. According to the scheme described above, attackers can also restore the secret key dsA.


### 3.2. Countermeasures against Simple Power Attack

Based on our SPA attack, we can draw a conclusion thatr and l are equally important in the security of SM9 digital signature algorithm. It is necessary to deploy some countermeasures on r and l against SPA attack.There are five ways [22, 23] against SPA scheme for l in SM9 digital signature algorithm. In addition, countermeasures to protect the exponent r should be implemented. We would not repeat the descriptions about the methods for r here as they are similar to that of l. We also can refer to the SPA countermeasures of RSA [13] for r against SPA attack.In conclusion, the five ways are as follows.(1) Indistinguishable Point Operation Formulae. Indistinguishable Point Operation Formulae (IPOF) try to eliminate the difference between point addition and point doubling. The usage of unified formulae for point doubling and addition is a special case of IPOF. However, even when unified formulae are in use, the implementation of the underlying arithmetic, especially the operations with conditional instructions, may still reveal the type of the point operation (addition or doubling).(2) Double-and-Add-Always Algorithm. The double-and-add-always algorithm ensures that the sequence of operations during a scalar multiplication is independent of the scalar by inserting dummy point additions. However, due to the use of dummy operations, it makes the time complexity doubled and may cause safe-error fault attack.(3) Atomic Block Algorithm. Instead of making the group operations indistinguishable, one can rewrite them as sequences of side-channel atomic blocks that are indistinguishable for SPA attack. If dummy atomic blocks are added, then this countermeasure may enable safe-error attack.(4) Montgomery Ladder Method. Because the intermediate values are stored in registers randomly in Montgomery ladder method, the Hamming weight of secret information would not leak out to attackers.(5) Random Splitting l and r . There are two different ways to split l and r. Here we take l as an example and r also should be protected by the same principle. One is to transform l to l+kN where k is a random integer and do scalar multiplication by the formula:(6)S=ldsA⟶S=l+kNdsA.Another is to convert l to l+k and k where k is a 256-bit random value. The formula is(7)S=ldsA⟶S=l+kdsA.


## 3.1. Simple Power Attack on SM9

In this paper, we focus the computation of scalar multiplicationS=ldsA to apply our SPA attack which is described in line 8 of Algorithm 1.Our SPA attack against SM9 recoversl by observing the differences in power consumption caused by the difference operations for bit 1 and bit 0. As described in Algorithm 2, it always performs a point doubling operation whether the bit is 0 or 1. And an extra point addition will be performed if the bit is 1. Because of the differences between side-channel pattern of doubling and that of addition, attackers can easily reveal l from a single power trace. As N and S are both known, dsA can be calculated by the formula dsA=l-1S.Attackers can also perform SPA attack onw=gr as shown in line 3 of Algorithm 1. The SPA attack on modular exponentiation is similar to that of scalar multiplication. Employing the different power consumption by manipulating 1 and 0 can derive the exponent r. The lengths of r, l, and N are 256 bits so that l can be obtained by the formula l=r-hmodN. According to the scheme described above, attackers can also restore the secret key dsA.


## 3.2. Countermeasures against Simple Power Attack

Based on our SPA attack, we can draw a conclusion thatr and l are equally important in the security of SM9 digital signature algorithm. It is necessary to deploy some countermeasures on r and l against SPA attack.There are five ways [22, 23] against SPA scheme for l in SM9 digital signature algorithm. In addition, countermeasures to protect the exponent r should be implemented. We would not repeat the descriptions about the methods for r here as they are similar to that of l. We also can refer to the SPA countermeasures of RSA [13] for r against SPA attack.In conclusion, the five ways are as follows.(1) Indistinguishable Point Operation Formulae. Indistinguishable Point Operation Formulae (IPOF) try to eliminate the difference between point addition and point doubling. The usage of unified formulae for point doubling and addition is a special case of IPOF. However, even when unified formulae are in use, the implementation of the underlying arithmetic, especially the operations with conditional instructions, may still reveal the type of the point operation (addition or doubling).(2) Double-and-Add-Always Algorithm. The double-and-add-always algorithm ensures that the sequence of operations during a scalar multiplication is independent of the scalar by inserting dummy point additions. However, due to the use of dummy operations, it makes the time complexity doubled and may cause safe-error fault attack.(3) Atomic Block Algorithm. Instead of making the group operations indistinguishable, one can rewrite them as sequences of side-channel atomic blocks that are indistinguishable for SPA attack. If dummy atomic blocks are added, then this countermeasure may enable safe-error attack.(4) Montgomery Ladder Method. Because the intermediate values are stored in registers randomly in Montgomery ladder method, the Hamming weight of secret information would not leak out to attackers.(5) Random Splitting l and r . There are two different ways to split l and r. Here we take l as an example and r also should be protected by the same principle. One is to transform l to l+kN where k is a random integer and do scalar multiplication by the formula:(6)S=ldsA⟶S=l+kNdsA.Another is to convert l to l+k and k where k is a 256-bit random value. The formula is(7)S=ldsA⟶S=l+kdsA.


## 4. Template Attack and Countermeasures on SM9

### 4.1. Template Attack on SM9

The template attack proposed in this paper revealsdsA in the case that both l and r are unknown. As shown in Section 2, the first step of scalar multiplication performs a point doubling operation. And λ needs to be calculated by (8)λ=3x2+a2y,where x and y represent the x-coordinate and y-coordinate of dsA. We focus this computation x2 to perform our template attack. For ease of description, we use X (256-bit) to replace x in Formula (8) and xi (0≤i<32) denotes one byte of X.Assume that SM9 digital signature algorithm is executed on an 8-bit microcontroller, and the power consumption of intermediate values in the calculation process of CIOS modular multiplication algorithm can be acquired. We give the letters meanings as follows.X=x31,…,x1,x0 is the x-coordinate of dsA(X,Y). And th(xixj) and tl(xixj) are the power consumption traces with the high 8-bit and low 8-bit of the intermediate value xixj (0≤i<32, 0≤j<32). The template with Hamming weight from 0 to 8 is denoted as Tτ=τ0,τ1,…,τ8 and Matcht,Tτ is a method to reflect the degree of t and Tτ. HWh(xixj) and HWl(xixj) denote the Hamming weight of high 8-bit and low 8-bit of xixj, respectively.As shown in Figure2, there are three phases in our template attack. Firstly, in the template building phase, we focus on the operation xixj (0≤i<32, 0≤j<32) and calculate the Hamming weight of high 8-bit and low 8-bit of xixj as the target of template. We build templates of Hamming weight Tτ=τ0,τ1,…,τ8 to characterize devices. Next, we match the templates to the power consumption traces of devices with the match function Matcht,Tτ to obtain HWh(xixj) and HWl(xixj) in template matching phase. Finally, two searching operations are carried out during offline searching phase and the secret key dsA can be derived by analysis.Figure 2
The flowchart of template attack on SM9.Algorithm4 shows our template attack. There are two searching operations used to narrow the range of candidates in offline searching phase. The first is shown in offline searching phase from the line 1 to the line 6. For each xi (0≤i<32), we traverse j from 0 to 255, and add j satisfying HWhj2==HWhxixi and HWlj2==HWlxixi to set U1,i where candidates of xi are stored. The second searching is based on U1,i, as demonstrated in line 7 to the line 14. For each element a in U1,i (0≤i<32) and each element b in U1,j (i<j<32), we calculate the high 8-bit and low 8-bit Hamming weight of ab. Selecting a and b with the conditions of HWh(ab)==HWhxixj and HWlab==HWlxixj and adding them in set U2, U2 consists of many pairs i,j,a,b and represents the correspondence between xi and xj. The pair i,j,a,b means that if xi==a so xj==b. Next, the possible values of X=x31,…,x1,x0 can be obtained. It is necessary to validate whether they are the points of the elliptic curve. Finally, the secret key dsA can be recovered.Algorithm 4:Template attack on SM9.
Input:  th(xixj), tl(xixj) (0≤i<32, 0≤j<32). Output:  dsA(X,Y). Template Building Phase: ( 1 ) Build power consumption templates Tτ=τ0,τ1,…,τ8 based on HWhxixj and HWlxixj where i, j from 0 to 31 and xi, xj from 0 to 255. Template Matching Phase: ( 1 )  for  i=0 to 31 do ( 2 )  for  j=0 to 31 do ( 3 ) calculate phmax= Matchthxixj,Tτ to recover HWhxixj. ( 4 ) calculate plmax= Matchtlxixj,Tτ to recover HWlxixj. ( 5 )  end for ( 6 )  end for Off-line Searching Phase: ( 1 )  for  i=0 to 31 do ( 2 )  for  j=0 to 255 do ( 3 )  If  HWhj2==HWhxixi  &&  HWlj2==HWlxixithen ( 4 ) Add j to set U1,i where stores candidates of xi. ( 5 )  end for ( 6 )  end for ( 7 )  for  i=0 to 31 do ( 8 )  for  j=i + 1 to 31 do ( 9 )  for each a in U1,i  && each b in U1,j  do ( 10 )  If  HWhab==HWhxixj  &&  HWlab==HWlxixj  then ( 11 ) Add the pair i,j,a,b to set U2. ( 12 )  end for ( 13 )  end for ( 14 )  end for ( 15 )  Search X=x31,...,x1,x0 in U2. ( 16 )  for each X in U2  do ( 17 ) Compute the corresponding Y and verify X and Y. ( 18 )  return  dsA(X,Y)


### 4.2. Template Attack Experiments on SM9

We present concrete experiments on side-channel traces captured from a real device. We implemented the Montgomery modular multiplication algorithm and focused on a single precision multiplication power consumption on AT89S52 8-bit microcontroller. Traces were acquired on a Lecroy WaveRunner oscilloscope with a sampling rate of 10 GS/s. In our experiments, the parametersX and Y of dsA are shown in Table 1.Table 1
Template attack experiment parameters.
Parameter Value (hexadecimal) X 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD Y 21FE8DDA 4F21E607 63106512 5C395BBC 1C1C00CB FA602435 0C464CD7 0A3EA616The templates of Hamming weight from 0 to 8 built in our attack are illustrated in Figures3 and 4.Figure 3
The templates of Hamming weight from 0 to 8.Figure 4
The templates of Hamming weight from 0 to 8 (zoom in).During our template attack, the power consumption of intermediate values in the calculation process of CIOS modular multiplication algorithm is acquired. Figure5 shows the th(x0x0) (black-line) and tl(x0x0) (dark-gray-line) which are the power consumption traces with the high 8-bit and low 8-bit of x0x0. The Matcht,Tτ applied in our attack is least square method to reflect the distance of t and Tτ. Hence, HWh(x0x0) and HWl(x0x0) were revealed which were equal to 6 and 4, respectively. For each i from 0 to 31, HWh(xixi) and HWl(xixi) can be recovered by the steps described above.Figure 5
Template matching results ofth(x0x0) and tl(x0x0).Then, the first searching phase is performed. For eachi from 0 to 31, we traverse j from 0 to 255 and calculate high 8-bit and low 8-bit Hamming weight of j2. Selecting j with the conditions of HWh(j2)==HWhxixi and HWlj2==HWlxixi and adding j to set U1,i, the set U1,i where candidates of xi are stored is given as shown in Table 2.Table 2
The sets of candidates ofxi.
Parameter U1,i The set of candidates ofxi (hexadecimal) x0 U 1,0 DB, DD, ED x1 U 1,1 DB, DD, ED x2 U 1,2 1D, 1F, 26, 29, 31, 32, 33, 43, 4F, 61, 66, 9D, B6 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ x29 U 1,29 05, 07, 09, 0A, 0E x30 U 1,30 1E, 34, 5E, 6F, DE x31 U 1,31 2B, 37, 3B, 47, 55, 56, 67, 71, 93, AA, B9, E7And then, the second searching phase is carried out. For each elementa in U1,i (0≤i<32) and each element b in U1,j (i<j<32), we calculate the high 8-bit and low 8-bit Hamming weight of ab. Select a and b with the conditions of HWh(ab)==HWhxixj and HWlab==HWlxixj and adding them in set U2. U2 consists of many pairs i,j,a,b and represents the correspondence between xi and xj. Next, the possible values of X=x31,…,x1,x0 can be obtained. The result of offline searching phase is shown in Figures 6 and 7. Finally, the value of X is 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD and it is validated to be correct. And dsA can be revealed successfully. The experiments have proved that our attack works well. If attackers employ the template attack on an 8-bit microcontrol unit, the key often can be obtained just by analyzing algorithm procedure of one message.Figure 6
The result of offline searching phase.Figure 7
The setU2 after offline searching phase.


### 4.3. Countermeasures Against Template Attack

There are four ways [23, 24] to resist the template attack presented above.(1) Base Point Blinding. This method is to select a random point R and convert S=ldsA to S=lR+dsA-lR. The value of lR+dsA is computed first and the known value lR is subtracted at the end of scalar multiplication to ensure its correctness. The lR and R are stored secretly in the cryptographic devices and updated at each iteration.(2) Random Projective Coordinates. Let dsA′X′,Y′,Z denote the mapping value of dsAX,Y in the Jacobian coordinates where X=X′/Z2 and Y=Y′/Z3. Point dsA′X′,Y′,Z is considered to be the same as point Qr2X′,r3Y′,rZ where r is a random number. For different r, dsA is not the same. The random variable r can be updated in every execution or after each doubling or addition. Attackers could not accurately gain the values of dsA and 2dsA, so this method does resist the attack.(3) Random EC Isomorphism. Based on the isomorphism of elliptic curves, we transform scalar multiplication algorithm to another stochastic mapping domain. A random isomorphism curve E′Fp is generated and dsA is mapped to dsA′ which is on E′Fp. The calculation of S is on E′Fp rather than EFp. Finally, we should map dsA′ to dsA and get S. As dsA′ can not be estimated, this method can resist the template attack.(4) Random Field Isomorphism. This method makes use of isomorphisms between fields. To compute S=ldsA, it first randomly chooses a field K′ to K through isomorphism ψ and then computes(9)Q=ψ-1kψP.It means that Q∈E′K′ is used to represent dsA∈EK and S′=lQ is calculated on E′K′. Finally we need to transform S′ to S∈EK. The value of dsA is hidden in this method so as to resist the above attack.Figures8 and 9 show the templates of Hamming weight from 0 to 8 after applying some countermeasures.Figure 8
The protected templates of Hamming weight.Figure 9
The protected templates of Hamming weight (zoom in).


## 4.1. Template Attack on SM9

The template attack proposed in this paper revealsdsA in the case that both l and r are unknown. As shown in Section 2, the first step of scalar multiplication performs a point doubling operation. And λ needs to be calculated by (8)λ=3x2+a2y,where x and y represent the x-coordinate and y-coordinate of dsA. We focus this computation x2 to perform our template attack. For ease of description, we use X (256-bit) to replace x in Formula (8) and xi (0≤i<32) denotes one byte of X.Assume that SM9 digital signature algorithm is executed on an 8-bit microcontroller, and the power consumption of intermediate values in the calculation process of CIOS modular multiplication algorithm can be acquired. We give the letters meanings as follows.X=x31,…,x1,x0 is the x-coordinate of dsA(X,Y). And th(xixj) and tl(xixj) are the power consumption traces with the high 8-bit and low 8-bit of the intermediate value xixj (0≤i<32, 0≤j<32). The template with Hamming weight from 0 to 8 is denoted as Tτ=τ0,τ1,…,τ8 and Matcht,Tτ is a method to reflect the degree of t and Tτ. HWh(xixj) and HWl(xixj) denote the Hamming weight of high 8-bit and low 8-bit of xixj, respectively.As shown in Figure2, there are three phases in our template attack. Firstly, in the template building phase, we focus on the operation xixj (0≤i<32, 0≤j<32) and calculate the Hamming weight of high 8-bit and low 8-bit of xixj as the target of template. We build templates of Hamming weight Tτ=τ0,τ1,…,τ8 to characterize devices. Next, we match the templates to the power consumption traces of devices with the match function Matcht,Tτ to obtain HWh(xixj) and HWl(xixj) in template matching phase. Finally, two searching operations are carried out during offline searching phase and the secret key dsA can be derived by analysis.Figure 2
The flowchart of template attack on SM9.Algorithm4 shows our template attack. There are two searching operations used to narrow the range of candidates in offline searching phase. The first is shown in offline searching phase from the line 1 to the line 6. For each xi (0≤i<32), we traverse j from 0 to 255, and add j satisfying HWhj2==HWhxixi and HWlj2==HWlxixi to set U1,i where candidates of xi are stored. The second searching is based on U1,i, as demonstrated in line 7 to the line 14. For each element a in U1,i (0≤i<32) and each element b in U1,j (i<j<32), we calculate the high 8-bit and low 8-bit Hamming weight of ab. Selecting a and b with the conditions of HWh(ab)==HWhxixj and HWlab==HWlxixj and adding them in set U2, U2 consists of many pairs i,j,a,b and represents the correspondence between xi and xj. The pair i,j,a,b means that if xi==a so xj==b. Next, the possible values of X=x31,…,x1,x0 can be obtained. It is necessary to validate whether they are the points of the elliptic curve. Finally, the secret key dsA can be recovered.Algorithm 4:Template attack on SM9.
Input:  th(xixj), tl(xixj) (0≤i<32, 0≤j<32). Output:  dsA(X,Y). Template Building Phase: ( 1 ) Build power consumption templates Tτ=τ0,τ1,…,τ8 based on HWhxixj and HWlxixj where i, j from 0 to 31 and xi, xj from 0 to 255. Template Matching Phase: ( 1 )  for  i=0 to 31 do ( 2 )  for  j=0 to 31 do ( 3 ) calculate phmax= Matchthxixj,Tτ to recover HWhxixj. ( 4 ) calculate plmax= Matchtlxixj,Tτ to recover HWlxixj. ( 5 )  end for ( 6 )  end for Off-line Searching Phase: ( 1 )  for  i=0 to 31 do ( 2 )  for  j=0 to 255 do ( 3 )  If  HWhj2==HWhxixi  &&  HWlj2==HWlxixithen ( 4 ) Add j to set U1,i where stores candidates of xi. ( 5 )  end for ( 6 )  end for ( 7 )  for  i=0 to 31 do ( 8 )  for  j=i + 1 to 31 do ( 9 )  for each a in U1,i  && each b in U1,j  do ( 10 )  If  HWhab==HWhxixj  &&  HWlab==HWlxixj  then ( 11 ) Add the pair i,j,a,b to set U2. ( 12 )  end for ( 13 )  end for ( 14 )  end for ( 15 )  Search X=x31,...,x1,x0 in U2. ( 16 )  for each X in U2  do ( 17 ) Compute the corresponding Y and verify X and Y. ( 18 )  return  dsA(X,Y)


## 4.2. Template Attack Experiments on SM9

We present concrete experiments on side-channel traces captured from a real device. We implemented the Montgomery modular multiplication algorithm and focused on a single precision multiplication power consumption on AT89S52 8-bit microcontroller. Traces were acquired on a Lecroy WaveRunner oscilloscope with a sampling rate of 10 GS/s. In our experiments, the parametersX and Y of dsA are shown in Table 1.Table 1
Template attack experiment parameters.
Parameter Value (hexadecimal) X 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD Y 21FE8DDA 4F21E607 63106512 5C395BBC 1C1C00CB FA602435 0C464CD7 0A3EA616The templates of Hamming weight from 0 to 8 built in our attack are illustrated in Figures3 and 4.Figure 3
The templates of Hamming weight from 0 to 8.Figure 4
The templates of Hamming weight from 0 to 8 (zoom in).During our template attack, the power consumption of intermediate values in the calculation process of CIOS modular multiplication algorithm is acquired. Figure5 shows the th(x0x0) (black-line) and tl(x0x0) (dark-gray-line) which are the power consumption traces with the high 8-bit and low 8-bit of x0x0. The Matcht,Tτ applied in our attack is least square method to reflect the distance of t and Tτ. Hence, HWh(x0x0) and HWl(x0x0) were revealed which were equal to 6 and 4, respectively. For each i from 0 to 31, HWh(xixi) and HWl(xixi) can be recovered by the steps described above.Figure 5
Template matching results ofth(x0x0) and tl(x0x0).Then, the first searching phase is performed. For eachi from 0 to 31, we traverse j from 0 to 255 and calculate high 8-bit and low 8-bit Hamming weight of j2. Selecting j with the conditions of HWh(j2)==HWhxixi and HWlj2==HWlxixi and adding j to set U1,i, the set U1,i where candidates of xi are stored is given as shown in Table 2.Table 2
The sets of candidates ofxi.
Parameter U1,i The set of candidates ofxi (hexadecimal) x0 U 1,0 DB, DD, ED x1 U 1,1 DB, DD, ED x2 U 1,2 1D, 1F, 26, 29, 31, 32, 33, 43, 4F, 61, 66, 9D, B6 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ x29 U 1,29 05, 07, 09, 0A, 0E x30 U 1,30 1E, 34, 5E, 6F, DE x31 U 1,31 2B, 37, 3B, 47, 55, 56, 67, 71, 93, AA, B9, E7And then, the second searching phase is carried out. For each elementa in U1,i (0≤i<32) and each element b in U1,j (i<j<32), we calculate the high 8-bit and low 8-bit Hamming weight of ab. Select a and b with the conditions of HWh(ab)==HWhxixj and HWlab==HWlxixj and adding them in set U2. U2 consists of many pairs i,j,a,b and represents the correspondence between xi and xj. Next, the possible values of X=x31,…,x1,x0 can be obtained. The result of offline searching phase is shown in Figures 6 and 7. Finally, the value of X is 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD and it is validated to be correct. And dsA can be revealed successfully. The experiments have proved that our attack works well. If attackers employ the template attack on an 8-bit microcontrol unit, the key often can be obtained just by analyzing algorithm procedure of one message.Figure 6
The result of offline searching phase.Figure 7
The setU2 after offline searching phase.


## 4.3. Countermeasures Against Template Attack

There are four ways [23, 24] to resist the template attack presented above.(1) Base Point Blinding. This method is to select a random point R and convert S=ldsA to S=lR+dsA-lR. The value of lR+dsA is computed first and the known value lR is subtracted at the end of scalar multiplication to ensure its correctness. The lR and R are stored secretly in the cryptographic devices and updated at each iteration.(2) Random Projective Coordinates. Let dsA′X′,Y′,Z denote the mapping value of dsAX,Y in the Jacobian coordinates where X=X′/Z2 and Y=Y′/Z3. Point dsA′X′,Y′,Z is considered to be the same as point Qr2X′,r3Y′,rZ where r is a random number. For different r, dsA is not the same. The random variable r can be updated in every execution or after each doubling or addition. Attackers could not accurately gain the values of dsA and 2dsA, so this method does resist the attack.(3) Random EC Isomorphism. Based on the isomorphism of elliptic curves, we transform scalar multiplication algorithm to another stochastic mapping domain. A random isomorphism curve E′Fp is generated and dsA is mapped to dsA′ which is on E′Fp. The calculation of S is on E′Fp rather than EFp. Finally, we should map dsA′ to dsA and get S. As dsA′ can not be estimated, this method can resist the template attack.(4) Random Field Isomorphism. This method makes use of isomorphisms between fields. To compute S=ldsA, it first randomly chooses a field K′ to K through isomorphism ψ and then computes(9)Q=ψ-1kψP.It means that Q∈E′K′ is used to represent dsA∈EK and S′=lQ is calculated on E′K′. Finally we need to transform S′ to S∈EK. The value of dsA is hidden in this method so as to resist the above attack.Figures8 and 9 show the templates of Hamming weight from 0 to 8 after applying some countermeasures.Figure 8
The protected templates of Hamming weight.Figure 9
The protected templates of Hamming weight (zoom in).


## 5. Fault Attack and Countermeasures on SM9

### 5.1. Fault Attack on SM9

Base point is one of the system parameters in scalar multiplication, and it is determined by protocols. So we inject a single-bit fault on base point to recover the secret key. Two assumptions are made before the fault attack on SM9 is performed. One hypothesis is that attackers can inject a fault ondsA(X,Y) at an unknown location during the moments of error detection and signature computation. Let dsA′(X′,Y′) denote the fault key. Another assumption is that the injected fault causes a bit value to flip from 0 to 1.Figure10 illustrates the flowchart of fault attack on SM9. As an example, we performed the fault attack on E:y2=x3+b. The correct signature for message M is calculated by the formula SXS,YS=ldsAX,Y. Then, a single-bit fault is injected to the x-coordinate of dsA(X,Y) and the fault key is denoted as dsA′(X′,Y′). The wrong signature for message M is calculated by the formula S′(XS′,YS′)=l′dsA′X′,Y′. Obviously, S(XS,YS) and dsA(X,Y) are on E:y2=x3+b, while S′(XS′,YS′) and dsA′(X′,Y′) are on E′:y′2=x′3+b′. As S(XS,YS) and S′(XS′,YS′) are both known, b and b′ can be calculated. So we have(10)Y2=X3+b,Y′2=X′3+b′,Y=Y′.Figure 10
The flowchart of fault attack on SM9.Then, (11) can be gained:(11)X3-X′3+b-b′=0modp.Letα=b-b′; (11) is equal to(12)X3-X′3+α=0modp.Because only one bit is different between X and X′, (12) can be expressed as(13)X3-X+2n3+α=0modp,where n∈0,1,…,255. And n represents the location of the different bit.Convert (13) into the following form:(14)3·2n·X2+3·22n·X+23n-α=0mod⁡p.For eachn from 0 to 255, its corresponding equation like (14) can be obtained. All values of X satisfying this equation are calculated by mathematical methods and added to set UX. If UX is an empty set, that means the fault position n corresponding to this equation is incorrect. Otherwise, the fault position n is correct and we need to validate each X∈UX for getting the real X. It is worth noting that as long as n is correct, the equation must have solutions. Once the X is derived, the value of dsA(X,Y) can be calculated correctly.Obviously, if the fault is injected into they-coordinate of dsA(X,Y), the above fault attack is still performed validly. And our fault attack also has the ability to break the SPA-resistant SM9 implementation.To sum up the above, the fault attack algorithm is shown in Algorithm5.Algorithm 5:Fault attack on SM9.
Input: SM9 system parameters, message M. Output:  dsA(X,Y). ( 1 ) Calculate the correct signature value SXS,YS=ldsAX,Y. ( 2 ) Inject fault on dsA(X,Y) and denote as dsA′(X′,Y′). ( 3 ) Calculate the wrong signature value S′XS′,YS′=l′dsA′(X′,Y′). ( 4 ) Calculate b=YS2-XS3. ( 5 ) Calculate b′=YS′2-XS′3. ( 6 ) Establish equations of X and X′. ( 7 )   for  n=0 to 255 do ( 8 )  Compute X by 3⋅2n⋅X2+3⋅22n⋅X+23n-α=0modp. ( 9 )  end for ( 10 )  Calculate Y by y2=x3+b and verify X and Y. ( 11 )   return  dsA(X,Y)Remark 1.
In the above attack, we assume that the injected fault causes a bit to flip from 0 to 1. As we all know, common faults are single-bit flipping fault, single-bit constant fault, and multibits fault. In fact, no matter which fault is injected, as long asα≠0, the above attack can be performed. If α≠0, for single-bit constant fault, we can think of it as a single-bit flipping fault. For multibits fault, the only difference is that multi-n should be searched. We believe that using mathematical methods to solve this issue is not a difficult task.


### 5.2. Fault Attack Experiments on SM9

Assume that the elliptic curve used in our experiments isE:y2=x3+b. The q is a prime number, and N means the order of group G1. The dsA(X,Y) denotes a point of G1, and the scalar is denoted as l. S(XS,YS) is computed by S(XS,YS)=[l]dsA(X,Y). Let dsA′(X′,Y′) denote the fault point, and the wrong signature of message M is computed by the formula S′(XS′,YS′)=l′dsA′(X′,Y′). The experiment parameters are listed in Table 3. We can see that the fault location is equal to 1.Table 3
Fault attack experiment parameters.
Parameter Value (hexadecimal) q B6400000 02A3A6F1 D603AB4F F58EC745 21F2934B 1A7AEEDB E56F9B27 E351457D N B6400000 02A3A6F1 D603AB4F F58EC744 49F2934B 18EA8BEE E56EE19C D69ECF25 X 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD X ′ 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDF Y 21FE8DDA 4F21E607 63106512 5C395BBC 1C1C00CB FA602435 0C464CD7 0A3EA616 l 291FE3CA C8F58AD2 DC462C8D 4D578A94 DAFD5624 DDC28E32 8D293668 8A86CF1AWe conduct some experiments with the attack in Algorithm5, and the intermediate values of SM9 digital signature algorithm are shown in Table 4. When n=1, the equation has two solutions that may be the correct X. Let X1 and X2 denote the two solutions, and Y11, Y12, Y21, and Y22 denote the corresponding Y calculated by y2=x3+b. Comparing with Table 3, X1 and Y12 are the correct x-coordinate and y-coordinate of dsA, so the fault attack also shows its feasibility. Usually, attackers can reveal the 256-bit dsA by enabling the device to execute twice and comparing the two different results by our fault attack.Table 4
The intermediate values of fault attack.
Intermediate values Value (hexadecimal) XS A5702F05 CF131530 5E2D6EB6 4B0DEB92 3DB1A0BC F0CAFF90 523AC875 4AA69820 Y S 78559A84 4411F982 5C109F5E E3F52D72 0DD01785 392A727B B1556952 B2B013D3 b 05 X S ′ 48F78AA4 9A9443DE 0DC72D8C A91BB73C 1B2D6C4F 1FB2DA61 2E9EFACA 45D87116 Y S ′ 1FC550A9 CE2DCEAD 83CF500D AEB690A4 4401D3E6 11DC9F02 B3D5FE40 482C72E6 b ′ 66B99EE0 079E3769 9982B5B7 280386ED D0DA26F4 BB2CE030 3F07C542 841F257C α 66B99EE0 079E3769 9982B5B7 280386ED D0DA26F4 BB2CE030 3F07C542 841F2577 n 01 X 1 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD Y 11 94417225 B381C0EA 72F3463D 99556B89 05D6927F 201ACAA6 D9294E50 D9129F67 Y12 21FE8DDA 4F21E607 63106512 5C395BBC C1C00CB FA602435 0C464CD7 0A3EA616 X 2 2261FAE2 9FE43561 E016A44B AD11C56E 400E8AE2 109EBC5A FCAAB6A6 66EA679E X 21 9A426326 D3E2BCF1 AFA21657 5CF85BA8 B347DB94 ECF14C97 104FCE07 67C23979 Y 22 1BFD9CD9 2EC0EA00 266194F8 98966B9C 6EAAB7B6 2D89A244 D51FCD20 7B8F0C04


### 5.3. Countermeasures against Fault Attack

We introduce three countermeasures against the above fault attack [25–27]; they are as follows.(1) Point Validation.This method verifies if a point lies on the specified curve or not. It should be performed before and after scalar multiplication. If the point dsA or result does not belong to the original curve, no output should be given. It is an effective countermeasure against our fault attack.(2) Curve Integrity Check.The curve integrity check is to detect faults on curve parameters. Before starting an SM9 algorithm the curve parameters are read from the memory and verified using an error detecting code (i.e., cyclic redundancy check) before the algorithm execution. It is an effective method to prevent the fault attack above.(3) Coherence Check.A coherence check verifies the intermediate or final results with respect to a valid pattern. Randomly coding the intermediate variables such as scalar, base point, and curve parameters is a most common operation.(4) Combined Curve Check.This method uses a reference curve to detect faults. It makes use of two curves: a reference curve E≔EFp and a combined curve E′ that is defined over the ring Z′. In order to compute S=ldsA on curve E, it first generates a combined point dsA′ from dsA and dsA∈E(Fp) (with prime order). Two scalar multiplications are then performed: S′=ldsA′ on E′ and S=ldsA on E. If no error occurred, S and S′ (modp) will be equal. Otherwise, the one of the results is faulty and the results should be aborted. It is also an effective countermeasure against the fault attack presented in this paper.(5) Security Curve Selection. Using the NIST curves [28] with the fragile twin curves should be avoided.


## 5.1. Fault Attack on SM9

Base point is one of the system parameters in scalar multiplication, and it is determined by protocols. So we inject a single-bit fault on base point to recover the secret key. Two assumptions are made before the fault attack on SM9 is performed. One hypothesis is that attackers can inject a fault ondsA(X,Y) at an unknown location during the moments of error detection and signature computation. Let dsA′(X′,Y′) denote the fault key. Another assumption is that the injected fault causes a bit value to flip from 0 to 1.Figure10 illustrates the flowchart of fault attack on SM9. As an example, we performed the fault attack on E:y2=x3+b. The correct signature for message M is calculated by the formula SXS,YS=ldsAX,Y. Then, a single-bit fault is injected to the x-coordinate of dsA(X,Y) and the fault key is denoted as dsA′(X′,Y′). The wrong signature for message M is calculated by the formula S′(XS′,YS′)=l′dsA′X′,Y′. Obviously, S(XS,YS) and dsA(X,Y) are on E:y2=x3+b, while S′(XS′,YS′) and dsA′(X′,Y′) are on E′:y′2=x′3+b′. As S(XS,YS) and S′(XS′,YS′) are both known, b and b′ can be calculated. So we have(10)Y2=X3+b,Y′2=X′3+b′,Y=Y′.Figure 10
The flowchart of fault attack on SM9.Then, (11) can be gained:(11)X3-X′3+b-b′=0modp.Letα=b-b′; (11) is equal to(12)X3-X′3+α=0modp.Because only one bit is different between X and X′, (12) can be expressed as(13)X3-X+2n3+α=0modp,where n∈0,1,…,255. And n represents the location of the different bit.Convert (13) into the following form:(14)3·2n·X2+3·22n·X+23n-α=0mod⁡p.For eachn from 0 to 255, its corresponding equation like (14) can be obtained. All values of X satisfying this equation are calculated by mathematical methods and added to set UX. If UX is an empty set, that means the fault position n corresponding to this equation is incorrect. Otherwise, the fault position n is correct and we need to validate each X∈UX for getting the real X. It is worth noting that as long as n is correct, the equation must have solutions. Once the X is derived, the value of dsA(X,Y) can be calculated correctly.Obviously, if the fault is injected into they-coordinate of dsA(X,Y), the above fault attack is still performed validly. And our fault attack also has the ability to break the SPA-resistant SM9 implementation.To sum up the above, the fault attack algorithm is shown in Algorithm5.Algorithm 5:Fault attack on SM9.
Input: SM9 system parameters, message M. Output:  dsA(X,Y). ( 1 ) Calculate the correct signature value SXS,YS=ldsAX,Y. ( 2 ) Inject fault on dsA(X,Y) and denote as dsA′(X′,Y′). ( 3 ) Calculate the wrong signature value S′XS′,YS′=l′dsA′(X′,Y′). ( 4 ) Calculate b=YS2-XS3. ( 5 ) Calculate b′=YS′2-XS′3. ( 6 ) Establish equations of X and X′. ( 7 )   for  n=0 to 255 do ( 8 )  Compute X by 3⋅2n⋅X2+3⋅22n⋅X+23n-α=0modp. ( 9 )  end for ( 10 )  Calculate Y by y2=x3+b and verify X and Y. ( 11 )   return  dsA(X,Y)Remark 1.
In the above attack, we assume that the injected fault causes a bit to flip from 0 to 1. As we all know, common faults are single-bit flipping fault, single-bit constant fault, and multibits fault. In fact, no matter which fault is injected, as long asα≠0, the above attack can be performed. If α≠0, for single-bit constant fault, we can think of it as a single-bit flipping fault. For multibits fault, the only difference is that multi-n should be searched. We believe that using mathematical methods to solve this issue is not a difficult task.


## 5.2. Fault Attack Experiments on SM9

Assume that the elliptic curve used in our experiments isE:y2=x3+b. The q is a prime number, and N means the order of group G1. The dsA(X,Y) denotes a point of G1, and the scalar is denoted as l. S(XS,YS) is computed by S(XS,YS)=[l]dsA(X,Y). Let dsA′(X′,Y′) denote the fault point, and the wrong signature of message M is computed by the formula S′(XS′,YS′)=l′dsA′(X′,Y′). The experiment parameters are listed in Table 3. We can see that the fault location is equal to 1.Table 3
Fault attack experiment parameters.
Parameter Value (hexadecimal) q B6400000 02A3A6F1 D603AB4F F58EC745 21F2934B 1A7AEEDB E56F9B27 E351457D N B6400000 02A3A6F1 D603AB4F F58EC744 49F2934B 18EA8BEE E56EE19C D69ECF25 X 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD X ′ 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDF Y 21FE8DDA 4F21E607 63106512 5C395BBC 1C1C00CB FA602435 0C464CD7 0A3EA616 l 291FE3CA C8F58AD2 DC462C8D 4D578A94 DAFD5624 DDC28E32 8D293668 8A86CF1AWe conduct some experiments with the attack in Algorithm5, and the intermediate values of SM9 digital signature algorithm are shown in Table 4. When n=1, the equation has two solutions that may be the correct X. Let X1 and X2 denote the two solutions, and Y11, Y12, Y21, and Y22 denote the corresponding Y calculated by y2=x3+b. Comparing with Table 3, X1 and Y12 are the correct x-coordinate and y-coordinate of dsA, so the fault attack also shows its feasibility. Usually, attackers can reveal the 256-bit dsA by enabling the device to execute twice and comparing the two different results by our fault attack.Table 4
The intermediate values of fault attack.
Intermediate values Value (hexadecimal) XS A5702F05 CF131530 5E2D6EB6 4B0DEB92 3DB1A0BC F0CAFF90 523AC875 4AA69820 Y S 78559A84 4411F982 5C109F5E E3F52D72 0DD01785 392A727B B1556952 B2B013D3 b 05 X S ′ 48F78AA4 9A9443DE 0DC72D8C A91BB73C 1B2D6C4F 1FB2DA61 2E9EFACA 45D87116 Y S ′ 1FC550A9 CE2DCEAD 83CF500D AEB690A4 4401D3E6 11DC9F02 B3D5FE40 482C72E6 b ′ 66B99EE0 079E3769 9982B5B7 280386ED D0DA26F4 BB2CE030 3F07C542 841F257C α 66B99EE0 079E3769 9982B5B7 280386ED D0DA26F4 BB2CE030 3F07C542 841F2577 n 01 X 1 93DE051D 62BF718F F5ED0704 487D01D6 E1E40869 09DC3280 E8C4E481 7C66DDDD Y 11 94417225 B381C0EA 72F3463D 99556B89 05D6927F 201ACAA6 D9294E50 D9129F67 Y12 21FE8DDA 4F21E607 63106512 5C395BBC C1C00CB FA602435 0C464CD7 0A3EA616 X 2 2261FAE2 9FE43561 E016A44B AD11C56E 400E8AE2 109EBC5A FCAAB6A6 66EA679E X 21 9A426326 D3E2BCF1 AFA21657 5CF85BA8 B347DB94 ECF14C97 104FCE07 67C23979 Y 22 1BFD9CD9 2EC0EA00 266194F8 98966B9C 6EAAB7B6 2D89A244 D51FCD20 7B8F0C04


## 5.3. Countermeasures against Fault Attack

We introduce three countermeasures against the above fault attack [25–27]; they are as follows.(1) Point Validation.This method verifies if a point lies on the specified curve or not. It should be performed before and after scalar multiplication. If the point dsA or result does not belong to the original curve, no output should be given. It is an effective countermeasure against our fault attack.(2) Curve Integrity Check.The curve integrity check is to detect faults on curve parameters. Before starting an SM9 algorithm the curve parameters are read from the memory and verified using an error detecting code (i.e., cyclic redundancy check) before the algorithm execution. It is an effective method to prevent the fault attack above.(3) Coherence Check.A coherence check verifies the intermediate or final results with respect to a valid pattern. Randomly coding the intermediate variables such as scalar, base point, and curve parameters is a most common operation.(4) Combined Curve Check.This method uses a reference curve to detect faults. It makes use of two curves: a reference curve E≔EFp and a combined curve E′ that is defined over the ring Z′. In order to compute S=ldsA on curve E, it first generates a combined point dsA′ from dsA and dsA∈E(Fp) (with prime order). Two scalar multiplications are then performed: S′=ldsA′ on E′ and S=ldsA on E. If no error occurred, S and S′ (modp) will be equal. Otherwise, the one of the results is faulty and the results should be aborted. It is also an effective countermeasure against the fault attack presented in this paper.(5) Security Curve Selection. Using the NIST curves [28] with the fragile twin curves should be avoided.


## 6. Conclusion

In this paper, we propose SPA attack, template attack, and fault attack on SM9 algorithm. After this, some corresponding countermeasures are also introduced. We also conduct some experiments to prove the validity of these attacks. Although this paper mainly studies SCA attacks of SM9 digital signature algorithm, we have reason to believe that these schemes are equally effective for SM9 encryption algorithm.Overall, a security SM9 digital signature algorithm implementation should pay attention to these points shown in Table5. And we also provide the overhead to deploy these countermeasures as a reference guidance for the SM9 algorithm security implementation [27].Table 5
Countermeasures and overhead. Cost estimation: negligible (<10%), low (10%–50%), and high (>50%).
Countermeasures Target attacks Computation overhead Indistinguishable point operation SPA Low Double-and-add-always SPA Low Atomic block SPA Negligible Montgomery ladder SPA Low Random splitting SPA High  Base point blinding Template attack Negligible Random projective coordinates Template attack Negligible Random EC isomorphism Template attack Low Random field isomorphism Template attack Low  Point validation Fault attack Negligible Curve integrity check Fault attack Negligible Coherence check Fault attack Low Combined curve check Fault attack Low Security curve selection Fault attack -



---

*Source: 9701756-2018-04-05.xml*