# Fuzzy Matching Template Attacks on Multivariate Cryptography: A Case Study

Authors: Weijian Li; Xian Huang; Huimin Zhao; Guoliang Xie; Fuxiang Lu
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

Multivariate cryptography is one of the most promising candidates for post-quantum cryptography. Applying machine learning techniques in this paper, we experimentally investigate the side-channel security of the multivariate cryptosystems, which seriously threatens the hardware implementations of cryptographic systems. Generally, registers are required to store values of monomials and polynomials during the encryption of multivariate cryptosystems. Based on maximum-likelihood and fuzzy matching techniques, we propose a template-based least-square technique to efficiently exploit the side-channel leakage of registers. Using QUAD for a case study, which is a typical multivariate cryptosystem with provable security, we perform our attack against both serial and parallel QUAD implementations on field programmable gate array (FPGA). Experimental results show that our attacks on both serial and parallel implementations require only about 30 and 150 power traces, respectively, to successfully reveal the secret key with a success rate close to 100%. Finally, efficient and low-cost strategies are proposed to resist side-channel attacks.


---

## Body

## 1. Introduction

With the upcoming quantum computers, traditional cryptosystems face huge challenges. Public-key cryptosystems such as Rivest–Shamir–Adleman (RSA) and elliptic curve cryptography (ECC), whose security relies on the difficulty of certain number theoretic problems, are under great threat of quantum attack. In as early as 1994, Peter Shor proposed an algorithm on a quantum computer that efficiently solved such number theoretic problems in polynomial time. Afterward, Monz et al. [1] presented the realization of a scalable Shor algorithm in 2016, which means that once large-scale quantum computers appear, public-key cryptosystems will become insecure. Meanwhile, for symmetric-key primitives, larger keys are required to resist the quantum attack to some extent.Since Shor’s discovery, the theory of post-quantum cryptography has developed significantly. Many cryptographic schemes proposed in the literature, such as code-based cryptography [2] and lattice-based cryptography [3], show great potentiality to resist quantum attacks, while multivariate cryptography is one of the most promising candidates [4]. Afterward, numerous cryptosystems based on multivariate quadratic polynomials have been proposed, such as unbalanced oil-and-vinegar (UOV) and its variant [5], Rainbow [5, 6], ZHFE [7], and CHNN-MVC [8].At Eurocrypt 2006, Berbain et al. [9] presented the first multivariate stream cipher scheme denoted as QUAD, which is referred to as a practical and provable secure stream cipher, as well as a pseudorandom number generator (PRNG). In 2009, Berbain et al. [10] revisited the stream cipher of QUAD and proposed the provable security arguments supporting its conjectured strength for suitable parameter values. The provable security of QUAD relies on the hardness of solving systems of multivariate quadratic equations. Bardet et al. [11] presented a cryptanalysis algorithm with a complexity bounded by O(2134.56), which means this cryptanalysis method cannot put into practice.In recent years, GPUs are widely used in cloud computing and blockchain, which faces huge security challenges to guarantee data security and user privacy [12–14]. Several GPU acceleration schemes for multivariate systems are proposed to make it suitable for security of cloud computing and blockchain in the quantum world [15, 16]. In 2014, Tanaka et al. [15] proposed two efficient parallelization algorithms and a GPU-based multivariable quadratic polynomial system. Furthermore, they proposed several effective parallel implementations of QUAD on GPU to accelerate the computing of quadratic polynomials. In 2018, Liao et al. [16] proposed a GPU acceleration framework for high-order multivariate cryptography systems, where the GPU acceleration schemes made multivariate cryptosystems feasible for cloud computing and blockchain.Moreover, multivariate cryptosystems are in general computationally efficient, which supports the use of the Internet of Things (IoT) devices. IoT is essentially a network of pervasive devices such as RFID tags, sensors, ASICs, and smart cards, which have rigid cost constraints in terms of area, memory, computing power, and battery supply. Traditional cryptosystems are not entirely applicable to the IoT devices since they are too expensive for such pervasive devices. At fast software encryption (FSE) 2010, Billet et al. [17] showed that QUAD can be converted to efficiently construct a privacy-preserving authentication protocol for RFID with provable security. Arditti et al. [18] presented a QUAD implementation and regarded it as the smallest provably secure stream cipher so far. The smallest QUAD implementation requires only 2961 GE, which makes it a competitive candidate for IoT security. Also, Hamlet et al. [19] proposed a throughput-optimized parallel implementation of QUAD for more secure application scenarios in 2015.The implementation of cryptography needs to take a wide range of physical attacks into account, especially side-channel attacks and fault attacks. Side-channel attacks exploit the dependency between physical information (e.g., power consumption, electromagnetic leaks, and timing information) and secret key to enable a divide-and-conquer attack to reveal the key part by part. Typical side-channel attacks include nonprofiled attacks (e.g., correlation power analysis (CPA) [20], mutual information analysis (MIA) [21]) and profiled attacks (e.g., template attacks (TA) [22–28] and other machine learning-based side-channel attacks [28–34]). Profiled side-channel attacks are the most powerful attacks, which received a lot of attention in recent years. Samples of power traces are regarded as features, and feature selection methods are needed to reduce the computational complexity and increase the prediction accuracy [28]. Afterward, machine leaning techniques including maximum-likelihood strategy [22–28], SVM [28–30], random forest (RF) [28, 29], k-nearest neighbors (KNN) [31], neural networks (NNs) [32], and deep learning (DL) [33, 34] are widely applied to build the prediction model. Profiled side-channel attacks include a profiling/training phase and a matching/predicting phase. In the profiling/training phase, machine learning algorithms are fed with labelled power traces captured from a reference device to build the prediction model. In the matching/predicting phase, prediction models are used to predict the correct labels for those power traces captured from a target device.Template attack was first proposed at CHES’02 [22], which efficiently revealed the key by a maximum-likelihood strategy, and was rapidly accepted as the strongest form of side-channel attack. Original template attack matched only a single power trace, which sometimes failed in the practical attack. Agrawal et al. [23] proposed template-based DPA attack to accumulate the matching results of power traces, which significantly improved the success rate. Özgen et al. [24] combined classification algorithms with template attacks in the matching phase to improve the efficiency of attacks. Choudary and Kuhn [25] tackled some of the practical obstacles of template attacks, such as pooled covariance matrices, compression methods, and incompatibility of templates across different devices. Zhang [27] theoretically analyzed the exact relationship between the success rate of template attack and values of different parameters, including signal-to-noise, number of interesting points, and number of power traces. From the viewpoint of machine learning, Picek et al. [28] adopted feature selection techniques to improve the attack efficiency. They concluded that L1 regularization wrapper and linear SVM hybrid methods performed consistently well for all data sets.Although side-channel attacks have been developed over 20 years, research about side-channel attacks on multivariate cryptosystems is still in the early stages. Several literatures about side-channel attack on multivariate cryptosystems were published. In as early as 2005, Okeya et al. [35] analyzed the power leakage of addition operations modulo 232 of SHA-1 and successfully recovered the secret information of SFLASH, which is the first successful power analysis attack on multivariate cryptography in practice. Later, in 2013, Hashimoto et al. [36] proposed a theoretical method based on fault attack to reveal the partial key of MPKC systems. Yi and Li [37] proposed a fault attack and DPA on ASIC implementation of enTTS scheme in 2017. In 2018, Park et al. [38] presented a correlation power analysis attack against the Rainbow and UOV schemes on an 8-bit AVR microcontroller that yields full secret key recoveries. In 2019, based on the work of Hashimoto et al., Krämer and Loiero [39] complemented the research on fault attacks of multivariate signature schemes. However, their attacks do not lead to complete key recovery on Rainbow and UOV. Recently, Li et al. [40] proposed a CPA attack against serial implementation of QUAD on FPGA. Their work efficiently revealed the secret key but still requires further work to improve success rate.Li et al. proposed the practical CPA cryptanalysis on serial QUAD (2, 160, 160) with a much lower complexity, but the success rate is only around 85%. Because of the low signal-to-noise ratio, classic template attack and template-attack DPA attack cannot exactly match the templates to achieve a satisfactory success rate. To tackle this issue, we have proposed template-based least-square power analysis on serial QUAD (2, 160, 160). The main contributions of our paper can be highlighted as follows:(1)
By applying the least-square technique to enable fuzzy matching of the templates, which can find the best matching via minimizing the squared sum of errors. As a result, the proposed practical can achieve a success rate of nearly 100%.(2)
We also extend the template-based least-square power analysis attack to explore the leakage of parallel implementation of QUAD (2, 160, 160), which has successfully and efficiently revealed the secret key with a success rate also close to 100%.(3)
For multivariate cryptography, all monomials and polynomials can be computed in an arbitrary order to break the link between the power consumption and the secret key. We propose two low-cost hiding countermeasures for serial and parallel implementations, respectively, which show great potential to resist side-channel attacks.The remaining paper is organized as follows: in Section2, we review the mathematical definition, serial and parallel FPGA implementations of the QUAD stream cipher; in Section 3, the template-based least-square power analysis attacks on the serial and parallel FPGA implementation of the QUAD are presented; experimental results of our attacks are given in Section 4; efficient and low-cost countermeasures to resist side-channel attacks are discussed in Section 5; and Section 6 concludes the paper.


## 2. Preliminaries

### 2.1. Multivariate Cryptography

Generally, the mathematical definition of a multivariate quadratic equation withn variables over GF (q) can be written as follows:(1)Qx1,…,xn=∑1≤i≤j≤nαijxixj+∑1≤i≤nβixi+γ,where αij, βi, and γ are all coefficients over GF (q). Note that the degree of polynomial is up to 2; otherwise, new variables will be introduced to keep the polynomial of degree 2. A multivariate quadratic system QX consisting of m multivariate quadratic equations in n variables over GF (q) is defined as(2)QX=Q1X,…,QmX,X=x1,…,xn.Given a multivariate quadratic systemQX, the MQ problem is defined as to find a value X=x1,…,xn, if any, such that QiX=0 for all 1≤i≤m. The MQ problem is proved to be NP hard, even in the smallest finite filed GF (2) [10].A particular QUAD stream cipher inn variables over GF (q) is specified as QUAD (q, n, r), which computes n+r polynomials per round. As shown in Figure 1, QUAD (q, n, r) consists of an output function SoutX=Qn+1X,…,Qn+rX to produce r outputs as the keystream, and an update function SinX=QX1,…,QnX is used to generate n outputs to update X for the next round. The parameters q, n, and r and the coefficients αij, βi, and γ for Sin and Sout are public. The QUAD cipher expands a secret initial state X0∈GFqn into a sequence of secret states X0,X1,X2,…∈GFqn and a sequence of output vectors Y0,Y1,Y2,…∈GFqr.Figure 1
Stream cipher generation in QUAD [9].QUAD (2, 160, 160) is a practical version with the security level of at least 280, which is strongly recommended in [10]. QUAD (2, 160, 160) has 160 variables over GF (2), which outputs 160 bits per round, resulting in a set of 320 multivariate quadratic equations.From a perspective of implementation, operations over GF (2) are more efficient than those over larger fields. Moreover, the monomial formsxi⋅xi and xi are equal over GF (2); therefore, αijxixj and βixi can be computed together. In the case of randomly generated αij and γ, equations of QUAD over GF (2) can be simplified as(3)QX=∑1≤i≤j≤nαijxixj+γ,which brings great benefits in terms of efficiency and security.


### 2.2. FPGA Serial Implementation of QUAD

Arditti et al. [18] proposed a compact serial implementation of QUAD, which is believed to be the smallest provably secure stream cipher. As shown in Figure 2, the implementation consists of two main components. The first one is a nonlinear feedback shift register (NFSR), in which the coefficients of α and γ are randomly generated. Each monomial of the equation is computed by the second component at every clock tick and accumulated to a result register. Multivariate quadratic equations Q1X, Q2X, …, Qn+rX are computed sequentially. At every clock tick, the NFSR generates the coefficient. Once a new monomial αijxixj of polynomial QkX is computed, its contribution will be accumulated to the temporary register Qk. After nn+1/2+1 clock cycles, the polynomial QkX is computed, and the above process is repeated for Qk+1X.Figure 2
Serial implementation of QUAD (2, 160, 160) [18].


### 2.3. FPGA Parallel Implementation of QUAD

Hamlet and Brocato [19] presented two throughput-optimized parallel implementations of QUAD for a much higher throughput. A QUAD (2, 128, 128) version with the security level of approximately 264 is considered, which can be easily extended to another version in GF (2) such as QUAD (2, 160, 160). The coefficients α and γ are randomly generated and stored in ROM. Multivariate quadratic equations Q1X,Q2X,…,Qn+rX are still computed sequentially, while n monomials of polynomial QkX are computed in parallel at a time to achieve a higher throughput.As shown in Figure3, the FPGA parallel implementation of QUAD (2, 160, 160) is summarized as follows:(1)
Sequentially compute the equationsQ1X, Q2X, …, Q320X by step (2) to step (6).(2)
Initialize the internal stateX and rotated X with the secret key and the initialization vector.(3)
Calculateηi=xiAND rotatedxi,1≤i≤160 simultaneously.(4)
Load 160-bit coefficientsα from ROM, feed η and α into 8-input AND-XOR modules to compute Mc=∑3≥i≥0α4c−iη4c−i,1≤c≤40, and store Mc in temporary register Pc.(5)
CalculateVc1=∑3≥i≥0M4c1−i, 1≤c1≤10, by XOR modules. Compute QkX=QkX⊕∑1≤i≤10Vi and store the value in result register Q.(6)
Rotate the internal state rotatedX by one bit, and go to step 3 to compute next 160 monomials until all monomials of polynomial QkX are completed, which requires ⌈n+1/2⌉=81 loops. Note that, in the last loop, only half of the above modules are enabled to compute the last 80 monomials.(7)
Repeat the above steps until all quadratic equations are computed.Figure 3
Parallel implementation of QUAD (2, 160, 160) [19].


## 2.1. Multivariate Cryptography

Generally, the mathematical definition of a multivariate quadratic equation withn variables over GF (q) can be written as follows:(1)Qx1,…,xn=∑1≤i≤j≤nαijxixj+∑1≤i≤nβixi+γ,where αij, βi, and γ are all coefficients over GF (q). Note that the degree of polynomial is up to 2; otherwise, new variables will be introduced to keep the polynomial of degree 2. A multivariate quadratic system QX consisting of m multivariate quadratic equations in n variables over GF (q) is defined as(2)QX=Q1X,…,QmX,X=x1,…,xn.Given a multivariate quadratic systemQX, the MQ problem is defined as to find a value X=x1,…,xn, if any, such that QiX=0 for all 1≤i≤m. The MQ problem is proved to be NP hard, even in the smallest finite filed GF (2) [10].A particular QUAD stream cipher inn variables over GF (q) is specified as QUAD (q, n, r), which computes n+r polynomials per round. As shown in Figure 1, QUAD (q, n, r) consists of an output function SoutX=Qn+1X,…,Qn+rX to produce r outputs as the keystream, and an update function SinX=QX1,…,QnX is used to generate n outputs to update X for the next round. The parameters q, n, and r and the coefficients αij, βi, and γ for Sin and Sout are public. The QUAD cipher expands a secret initial state X0∈GFqn into a sequence of secret states X0,X1,X2,…∈GFqn and a sequence of output vectors Y0,Y1,Y2,…∈GFqr.Figure 1
Stream cipher generation in QUAD [9].QUAD (2, 160, 160) is a practical version with the security level of at least 280, which is strongly recommended in [10]. QUAD (2, 160, 160) has 160 variables over GF (2), which outputs 160 bits per round, resulting in a set of 320 multivariate quadratic equations.From a perspective of implementation, operations over GF (2) are more efficient than those over larger fields. Moreover, the monomial formsxi⋅xi and xi are equal over GF (2); therefore, αijxixj and βixi can be computed together. In the case of randomly generated αij and γ, equations of QUAD over GF (2) can be simplified as(3)QX=∑1≤i≤j≤nαijxixj+γ,which brings great benefits in terms of efficiency and security.


## 2.2. FPGA Serial Implementation of QUAD

Arditti et al. [18] proposed a compact serial implementation of QUAD, which is believed to be the smallest provably secure stream cipher. As shown in Figure 2, the implementation consists of two main components. The first one is a nonlinear feedback shift register (NFSR), in which the coefficients of α and γ are randomly generated. Each monomial of the equation is computed by the second component at every clock tick and accumulated to a result register. Multivariate quadratic equations Q1X, Q2X, …, Qn+rX are computed sequentially. At every clock tick, the NFSR generates the coefficient. Once a new monomial αijxixj of polynomial QkX is computed, its contribution will be accumulated to the temporary register Qk. After nn+1/2+1 clock cycles, the polynomial QkX is computed, and the above process is repeated for Qk+1X.Figure 2
Serial implementation of QUAD (2, 160, 160) [18].


## 2.3. FPGA Parallel Implementation of QUAD

Hamlet and Brocato [19] presented two throughput-optimized parallel implementations of QUAD for a much higher throughput. A QUAD (2, 128, 128) version with the security level of approximately 264 is considered, which can be easily extended to another version in GF (2) such as QUAD (2, 160, 160). The coefficients α and γ are randomly generated and stored in ROM. Multivariate quadratic equations Q1X,Q2X,…,Qn+rX are still computed sequentially, while n monomials of polynomial QkX are computed in parallel at a time to achieve a higher throughput.As shown in Figure3, the FPGA parallel implementation of QUAD (2, 160, 160) is summarized as follows:(1)
Sequentially compute the equationsQ1X, Q2X, …, Q320X by step (2) to step (6).(2)
Initialize the internal stateX and rotated X with the secret key and the initialization vector.(3)
Calculateηi=xiAND rotatedxi,1≤i≤160 simultaneously.(4)
Load 160-bit coefficientsα from ROM, feed η and α into 8-input AND-XOR modules to compute Mc=∑3≥i≥0α4c−iη4c−i,1≤c≤40, and store Mc in temporary register Pc.(5)
CalculateVc1=∑3≥i≥0M4c1−i, 1≤c1≤10, by XOR modules. Compute QkX=QkX⊕∑1≤i≤10Vi and store the value in result register Q.(6)
Rotate the internal state rotatedX by one bit, and go to step 3 to compute next 160 monomials until all monomials of polynomial QkX are completed, which requires ⌈n+1/2⌉=81 loops. Note that, in the last loop, only half of the above modules are enabled to compute the last 80 monomials.(7)
Repeat the above steps until all quadratic equations are computed.Figure 3
Parallel implementation of QUAD (2, 160, 160) [19].


## 3. Proposed Attack on Implementation of QUAD

### 3.1. Power Leakage Model

A typical CMOS transistor consumes dynamic power when its output signal is converted. Figure4(a) shows the changing process of a register when the output signal is converted from 0 to 1. A charging current from the power supply to the output capacitance CL and a transient short-circuit current from CMOS transistor are generated. On the contrary, Figure 4(b) shows the discharging process when the output signal is converted from 1 to 0. Only the instantaneous short-circuit current is generated through CMOS transistor.Figure 4
Charging and discharging process of register.
(a)(b)As a result, conversions of the output signal are focused since dynamic power is the major power consumption of the digital logical circuits of ASIC and FPGA. Denote the power consumption of CMOS transistor byPij when its signal converts from i to j, where i and j equal to 0 or 1. P01 and P10 consume dynamic power, while P00 and P11 consume only static power. As a result, it generally holds that P00≈P11≪P01,P10.Therefore, the power consumption when writing data to a register depends on the number of bit-flips. A hamming distance (HD) model well summarizes the power consumption of a register transition from a previous state to a new state.Regarding multivariate cryptosystems, which consist of a large number of monomials and polynomials, registers are indeed required to store monomial and polynomial values during the encryption. Serial implementation, for instance, monomials are computed sequentially and accumulated to the temporary registerQk, as identified by rectangle in Figure 2.The value of registerQk changes to Qk⊕αijxixj for all monomials. The power consumption of register Qk can be concluded as follows:(4)LQx=HDQk,Qk⊕αijxixj=HWαijxixj,1≤k≤160.Consequently, an attacker is possible to predict secret keysxi and xj by observing the power consumption of registers Ql.Other than serial implementations, parallel implementations compute 160 monomials simultaneously. 4 monomials are accumulated by an AND-XOR module and stored into temporary registerPc. According to the parallel implementation described in Section 2.3, when computing the first 160 monomials, the values Mc,1≤c≤40, stored into the temporary register Pc are(5)Mc=a4c−3,4c−3x4c−3x4c−3⊕a4c−2,4c−2x4c−2x4c−2⊕a4c−1,4c−1x4c−1x4c−1⊕a4c,4cx4cx4c,1≤c≤40.After rotating the internal state rotatedx by one bit to compute the next 160 monomials, the values Mc′,1≤c≤40, stored into registers Pc are(6)Mc′=a4c−3,4c−2x4c−3x4c−2⊕a4c−2,4c−1x4c−2x4c−1⊕a4c−1,4cx4c−1x4c⊕a4c,4c+1x4cx4c+1,1≤c≤39,Mc′=a157,158x157x158⊕a158,159x158x159⊕a159,160x159x160⊕a1,160x160x1,c=40.Therefore, the values of registersPc,1≤c≤40, change from Mc to Mc′, and the power leakage model of parallel implementations can be defined as(7)LQx=HDMc,Mc′=HWMc⊕Mc′,1≤c≤40.


### 3.2. Template-Based Least-Square Power Analysis Attack

Classic side-channel attacks, such as DPA, CPA, and MIA, require a large number of power traces to reveal the key, which means that different plaintexts are needed to be encrypted with the same key for obtaining as much power traces as possible. However, multivariate cryptosystems usually contain limited quadratic equations. Take QUAD as an example, and the key of QUAD is constantly updated after each round of encryption, which only generatesn+r power traces with the same key. In this case, machine learning-based side-channel attacks such as template attack have inherent advantages, which can extract the key with much fewer target power traces.Machine learning-based side-channel attacks are the most powerful attacks. Based on a maximum-likelihood strategy, template attacks reveal the secret key efficiently, which consist of a profiling phase and a matching phase. Classic template attacks match only a single power trace and reveal the key by the Bayes theorem in the matching phase. However, there is not enough valuable information in a single power trace to reveal the correct key in practical situation; hence, the classic template attack has little prospect of success rate.To solve this problem, template-based DPA attack was proposed as follows [23]:(8)pkjT=∏1≤i≤Dptikj⋅pkj∑1≤l≤K∏1≤i≤Dptikl⋅pkl,which accumulates the matching degree of each power trace during template matching to improve the success rate.Unfortunately, due to the low signal-to-noise ratio, the accurate matching method of template-based DPA attack is not applicable. For this reason, we proposed a template-based least-square (LSQ) power analysis attack, which reveals the key by fuzzy matching. As described in Figure5, the main idea of template-based LSQ is as follows:(1)
Choose a strategy to build templates: according to the power leakage models in equations (4) and (7), two templates need to be built, corresponding to leakage values 0 and 1.(2)
Collect power traces to build templates: two groups of power traces are collected according to different leakage values.(3)
Select interesting points (features): samples of power traces are regarded as features, which include relevant, irrelevant, and redundant features. Feature selection methods are needed to select the most relevant features to improve the attack efficiency. Feature selection methods [28] such as squared pairwise T-differences (SOST), Pearson correlation, principal component analysis (PCA), linear SVM wrapper, and L1 regularization are investigated. In our experiments, the Pearson correlation method is chosen to search interesting points, which can lead to excellent classification performance. 25 interesting points for serial implementation and 35 interesting points for parallel implementation with the highest ρt,hw are selected, where ρt,hw is defined as(9)ρt,hw=covt,hwσtσhw.(4)
Build templates with interesting points: two templateshi=mi,Ci corresponding to leakage values 0 and 1 are built, respectively, by covariance matrix Ci and mean vector mi, where mi and Ci are defined as(10)mi=1d∑1≤j≤dtji,Ciu,v=1d−1∑1≤l≤dNul−N¯u⋅Nvl−N¯v,(5)
Match templates: power tracesT=t1,t2,…,tD with the same key are captured from the device under attack to match the templates, respectively. Template that leads to the highest probability ptj;mi,Ci indicates the correct leakage value, where ptj;mi,Ci is defined as(11)ptj;mi,Ci=exp−1/2⋅tj−mi′⋅Ci−1⋅tj−mi2⋅πT⋅detCi.Denote such leakage values corresponding toT=t1,t2,…,tD as H=h1,h2,…,hD.(6)
Reveal the correct key. We map the hypothetical intermediate values into leakage values by equation (7) and compare with H=h1,h2,…,hD to reveal the correct key. Taking attack on parallel implementations, for instance, denote the hypothetical leakage values by S=s1,s2,…,s32, where si=si1,si2,…,siD. The least-square method defined as(12)Fi=∑1≤j≤Dsij−hj2,1≤i≤32,1≤j≤D,is applied to compare the hypothetical leakage values with the leakage values revealed by the template attack, where i is the key hypothesis. Finally, the correct key is revealed by(13)key=argminFi.Figure 5
The flow of template-based LSQ attack.


## 3.1. Power Leakage Model

A typical CMOS transistor consumes dynamic power when its output signal is converted. Figure4(a) shows the changing process of a register when the output signal is converted from 0 to 1. A charging current from the power supply to the output capacitance CL and a transient short-circuit current from CMOS transistor are generated. On the contrary, Figure 4(b) shows the discharging process when the output signal is converted from 1 to 0. Only the instantaneous short-circuit current is generated through CMOS transistor.Figure 4
Charging and discharging process of register.
(a)(b)As a result, conversions of the output signal are focused since dynamic power is the major power consumption of the digital logical circuits of ASIC and FPGA. Denote the power consumption of CMOS transistor byPij when its signal converts from i to j, where i and j equal to 0 or 1. P01 and P10 consume dynamic power, while P00 and P11 consume only static power. As a result, it generally holds that P00≈P11≪P01,P10.Therefore, the power consumption when writing data to a register depends on the number of bit-flips. A hamming distance (HD) model well summarizes the power consumption of a register transition from a previous state to a new state.Regarding multivariate cryptosystems, which consist of a large number of monomials and polynomials, registers are indeed required to store monomial and polynomial values during the encryption. Serial implementation, for instance, monomials are computed sequentially and accumulated to the temporary registerQk, as identified by rectangle in Figure 2.The value of registerQk changes to Qk⊕αijxixj for all monomials. The power consumption of register Qk can be concluded as follows:(4)LQx=HDQk,Qk⊕αijxixj=HWαijxixj,1≤k≤160.Consequently, an attacker is possible to predict secret keysxi and xj by observing the power consumption of registers Ql.Other than serial implementations, parallel implementations compute 160 monomials simultaneously. 4 monomials are accumulated by an AND-XOR module and stored into temporary registerPc. According to the parallel implementation described in Section 2.3, when computing the first 160 monomials, the values Mc,1≤c≤40, stored into the temporary register Pc are(5)Mc=a4c−3,4c−3x4c−3x4c−3⊕a4c−2,4c−2x4c−2x4c−2⊕a4c−1,4c−1x4c−1x4c−1⊕a4c,4cx4cx4c,1≤c≤40.After rotating the internal state rotatedx by one bit to compute the next 160 monomials, the values Mc′,1≤c≤40, stored into registers Pc are(6)Mc′=a4c−3,4c−2x4c−3x4c−2⊕a4c−2,4c−1x4c−2x4c−1⊕a4c−1,4cx4c−1x4c⊕a4c,4c+1x4cx4c+1,1≤c≤39,Mc′=a157,158x157x158⊕a158,159x158x159⊕a159,160x159x160⊕a1,160x160x1,c=40.Therefore, the values of registersPc,1≤c≤40, change from Mc to Mc′, and the power leakage model of parallel implementations can be defined as(7)LQx=HDMc,Mc′=HWMc⊕Mc′,1≤c≤40.


## 3.2. Template-Based Least-Square Power Analysis Attack

Classic side-channel attacks, such as DPA, CPA, and MIA, require a large number of power traces to reveal the key, which means that different plaintexts are needed to be encrypted with the same key for obtaining as much power traces as possible. However, multivariate cryptosystems usually contain limited quadratic equations. Take QUAD as an example, and the key of QUAD is constantly updated after each round of encryption, which only generatesn+r power traces with the same key. In this case, machine learning-based side-channel attacks such as template attack have inherent advantages, which can extract the key with much fewer target power traces.Machine learning-based side-channel attacks are the most powerful attacks. Based on a maximum-likelihood strategy, template attacks reveal the secret key efficiently, which consist of a profiling phase and a matching phase. Classic template attacks match only a single power trace and reveal the key by the Bayes theorem in the matching phase. However, there is not enough valuable information in a single power trace to reveal the correct key in practical situation; hence, the classic template attack has little prospect of success rate.To solve this problem, template-based DPA attack was proposed as follows [23]:(8)pkjT=∏1≤i≤Dptikj⋅pkj∑1≤l≤K∏1≤i≤Dptikl⋅pkl,which accumulates the matching degree of each power trace during template matching to improve the success rate.Unfortunately, due to the low signal-to-noise ratio, the accurate matching method of template-based DPA attack is not applicable. For this reason, we proposed a template-based least-square (LSQ) power analysis attack, which reveals the key by fuzzy matching. As described in Figure5, the main idea of template-based LSQ is as follows:(1)
Choose a strategy to build templates: according to the power leakage models in equations (4) and (7), two templates need to be built, corresponding to leakage values 0 and 1.(2)
Collect power traces to build templates: two groups of power traces are collected according to different leakage values.(3)
Select interesting points (features): samples of power traces are regarded as features, which include relevant, irrelevant, and redundant features. Feature selection methods are needed to select the most relevant features to improve the attack efficiency. Feature selection methods [28] such as squared pairwise T-differences (SOST), Pearson correlation, principal component analysis (PCA), linear SVM wrapper, and L1 regularization are investigated. In our experiments, the Pearson correlation method is chosen to search interesting points, which can lead to excellent classification performance. 25 interesting points for serial implementation and 35 interesting points for parallel implementation with the highest ρt,hw are selected, where ρt,hw is defined as(9)ρt,hw=covt,hwσtσhw.(4)
Build templates with interesting points: two templateshi=mi,Ci corresponding to leakage values 0 and 1 are built, respectively, by covariance matrix Ci and mean vector mi, where mi and Ci are defined as(10)mi=1d∑1≤j≤dtji,Ciu,v=1d−1∑1≤l≤dNul−N¯u⋅Nvl−N¯v,(5)
Match templates: power tracesT=t1,t2,…,tD with the same key are captured from the device under attack to match the templates, respectively. Template that leads to the highest probability ptj;mi,Ci indicates the correct leakage value, where ptj;mi,Ci is defined as(11)ptj;mi,Ci=exp−1/2⋅tj−mi′⋅Ci−1⋅tj−mi2⋅πT⋅detCi.Denote such leakage values corresponding toT=t1,t2,…,tD as H=h1,h2,…,hD.(6)
Reveal the correct key. We map the hypothetical intermediate values into leakage values by equation (7) and compare with H=h1,h2,…,hD to reveal the correct key. Taking attack on parallel implementations, for instance, denote the hypothetical leakage values by S=s1,s2,…,s32, where si=si1,si2,…,siD. The least-square method defined as(12)Fi=∑1≤j≤Dsij−hj2,1≤i≤32,1≤j≤D,is applied to compare the hypothetical leakage values with the leakage values revealed by the template attack, where i is the key hypothesis. Finally, the correct key is revealed by(13)key=argminFi.Figure 5
The flow of template-based LSQ attack.


## 4. Experimental Results and Discussion

As shown in Figure6, our experimental setup includes a standard evaluation board SAKURA-G, an oscilloscope, and a computer. SAKURA-G is designed for hardware security, which equips with two separate Spartan-6 FPGA chips. One chip serves as the control chip, while another serves as the cryptographic chip. Cryptographic chip performs encryption operations, while the control chip controls the data flow and communicates with the oscilloscope and computer. During encryption, power consumptions of the cryptographic chip are measured by the oscilloscope which is triggered by the control chip. Finally, power analysis attacks are performed on the computer.Figure 6
Experimental setup.We first perform a side-channel attack on serial implementation of QUAD (2, 160, 160). In the template building phase, 3000 power traces with different keys and coefficients are captured from a reference device, based on which 25 interesting points are selected by the CPA peak method. Next, we collect two groups of power traces corresponding to leakage values 0 and 1 in equation (4), and each group consists of 25 power traces. Finally, we build two templates, and the result is shown in Figure 7.Figure 7
Templates built for serial QUAD.In the template matching phase, 320 power traces with the same key are captured from the target device. Template that leads to the highest probability indicates the correct key. The success rate of template-based LSQ attack on serial implementation is shown in Figure8. When the number of power traces approach 30, the success rate tends to 100%. Therefore, a successful attack only requires 30 power traces in serial implementation.Figure 8
Success rates of our attack on serial implementation.To further illustrate the effectiveness of our attack, the time required for our practical attack on serial QUAD is discussed here. Our attack is performed on a personal computer, which integrates an Intel i5-7500 CPU and 12 GB of RAM. The time for templates building and templates matching depends on the number of power traces for building and matching, respectively. Figure9 shows the time required for the template building with the number of power traces ranging from 1 to 3000. Figure 10 shows the time required for template matching with the number of power traces ranging from 1 to 30. As our successful attack on the serial implementation of QUAD (2, 160, 160) requires less than 3000 power traces for templates building and 30 power traces for templates matching, the total time required for our successful attack is less than 1010 seconds, according to Figures 9 and 10.Figure 9
Time required for templates building.Figure 10
Time required for templates matching of serial QUAD of serial QUAD.According to the leakage model of parallel implementation in equation (7), 4 bits of the key are simultaneously accumulated into temporary register. Consequently, we need to guess 4 bits at a time. In the template building phase, 10000 power traces with different keys and coefficients are captured from a reference device, based on which 35 interesting points are selected by the CPA peak method. Next, we collect two groups of power traces corresponding to leakage values 0 and 1 in equation (7), and each group consists of 35 power traces. Finally, we build two templates, and the result is shown in Figure 11.Figure 11
Templates built for parallel QUAD.In the template matching phase, 320 power traces with the same key are captured from the target device. Template that leads to the highest probability indicates the correct key. The success rate of template-based LSQ attack on parallel implementation is shown in Figure12. When the number of power traces approach 150, the success rate tends to 100%. Therefore, 150 power traces are sufficient for a successful attack in parallel implementation.Figure 12
Success rates of our attack on parallel implementation.Figure13 shows the time required for the template building with the number of power traces ranging from 1 to 10000. Figure 14 shows the time required for template matching with the number of power traces ranging from 1 to 180. As our successful attack on the parallel implementation of QUAD (2, 160, 160) requires less than 10000 power traces for templates building and 150 power traces for templates matching, the total time required for our successful attack is less than 1977 seconds, according to Figures 13 and 14.Figure 13
Time required for templates building.Figure 14
Time required for templates matching of parallel QUAD.In order to compare the success probability of the attacks, we performed our attack, template attack, and template-based DPA attacks dozens of times, respectively. We compare the typical results in Table1, which shows that our proposed attack has the highest accuracy, greatly outperforming template attack, and template-based DPA attack.Table 1
Comparison of the success rates of different template attacks.
No. of experiments/success rate of attack12345678910Template-based LSQ attack (%)98.1297.2510097.2510010010097.2596.875100Template-based DPA attack (%)71.8865.6371.8868.7581.257581.2578.1368.7575Template attack (%)61.7571.8853.12565.637568.7561.7565.6363.7559.375


## 5. Suggested Countermeasures

Side-channel countermeasures aim at reducing the data dependency between physical information and secret key. Usually, masking and hiding technologies are adopted. For multivariate cryptography, all monomials and polynomials can be computed in an arbitrary order. Therefore, the basic idea of countermeasures for multivariate cryptography is to randomly change the sequence of these operations.A QUAD (q, n, r) has n+r×nn+1/2 monomials, which can be randomly computed in n+r×nn+1/2! orders. However, it is too expensive to implement such algorithm. We propose a low-cost shuffling countermeasure by partially changing the orders of monomials for each polynomial equation QkX. Starting with two randomly generated index isandjs, 1<is≤js≤n, each polynomial is computed in the order as follows:(14)Qx=∑js≤j≤nαisjxisxj+∑is+1≤i≤j≤nαijxixj+∑1≤i≤is−1,i≤j≤nαijxixj+∑is≤j≤js−1αisjxisxj+γ.A random index generator is required to generate such an order index, as shown in Figure15, whose implementation requires only 556 GE.Figure 15
The random index generator of shuffle countermeasure.For the parallel implementations, we proposed a low-cost hiding countermeasure by partially randomizing the initial value of rotatedx to shuffle the computation orders of monomials. Before each calculation of QkX, the initial value of rotated x is partially randomized with the random starting index is as follows:(15)rotatedx=xis,xis+1,…,xn,x1,…xis−1.


## 6. Conclusions

Multivariate cryptosystems consist of a large number of monomials and polynomials, where registers are required to store monomial and polynomial values during the encryption. Therefore, a hamming distance (HD) model of the register will leak the secret of the implementation.By applying the least-square technique to enable fuzzy matching of the templates, we propose a practical template-based least-square power analysis, where both the serial and parallel implementations of QUAD (2, 160, 160) can achieve a success rate close to 100%. The proposed two low-cost hiding countermeasures for serial and parallel implementations are also validated to be effective, where all monomials and polynomials can be computed in an arbitrary order to break the link between the power consumption and the secret key in multivariate cryptography. Our proposed attacks require only 30 and 150 power traces, respectively, to successfully reveal the secret key. Future work will focus on low-cost countermeasures of multivariate cryptography for IoT devices to resist side-channel attacks.



---

*Source: 9475782-2020-06-20.xml*