An Improved Empirical Mode Decomposition for Power Analysis Attack

Han Gan, Hongxin Zhang,2,＊, Muhammad Saad khan, Xueli Wang, Fan Zhang, Pengfei He

1 School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing, 100876, China

2 Beijing Key Laboratory of Work Safety Intelligent Monitoring, Beijing University of Posts and Telecommunications,Beijing, 100876, China

3 School of Science, Beijing University of Posts and Telecommunications, Beijing, 100876, China

4 College of Information Science and Electrical Engineering, Zhejiang University, Hangzhou, 310027, China

5 Institute of Science and Technology for Opto-electronic Information, Yantai University, Yantai, 264005,China

* The corresponding author, email: hongxinzhang@bupt.edu.cn

I. INTRODUCTION

In information security domain, side channel analysis (SCA) attack has become an important direction, which is a big threat for the infor- mation safety of embedded encryption devices. SCA attack can be implemented by physic leakages of cryptographic device that include time consumption, power consumption and electromagnetic leakage. The methods of SCA mainly include differential power analysis (DPA)[1], simple power analysis[2], correlation power analysis (CPA), and mutual information analysis attack[3], etc. Due to the noise caused by random process interrupts (RPIs), a class method is alignment of leakage information, which includes phase-only–correlation[4],am- plitude-only correlation[5], etc. Another is the research for weakening the noise influence by signal processing. It mainly contains filter,four–order cumulant (FOC)[6], wavelet transform(WT)[7], etc. The apply condition of filter is strict, which needs to learn more about the information about traces such as the sample rate. The method of FOC removes Gaussian noise from the whole signals. The WT method restructures the signals in the low and high frequency to realize the noise reduction. Empirical mode decomposition (EMD)[8]is used to decompose and restructure the signals for noise elimination, which is similar with WT about the way of noise reduction. These methods improve the performance on reducing the noise. However, the peaks of the correct curve really need to increase to improve the attack efficiency. The paper proposes a novel method, extracting a class of certain feature signals as the useful information in CPA, sub- tracting others which are considered as noises.

The paper is structured as follows. In Section II, we describe the notations of CPA and previous attacks. In Section III, we introduce the conventional and our improved EMD in detail. Meantime, a new attack assessment is proposed for comparing attack effectiveness.In Section IV, our solution is proved experimentally validated. The attack efficiencies of the experiment are analyzed in the situation with noise and non-noise. Section V is the conclusion part.

In this paper, an improved empirical mode decomposition method is proposed for Correlation Power Analysis attack.

II. RELATED WORKS

2.1 Notations

In the paper, the expression of the random variables as follows. The mean of x is denoted byits variance byThe latter equals toThe covariance of variablesandare denoted byIt can be expressed as follows:

In the encryption algorithm (EA), different plaintextsare encrypted with the same key. The key is composed of sixteen segments.We take one key segmentas an example.After the calculation of SubBytes, we get the resultPower tracesare obtained when EA is encrypted. Andandare random variables;andrepresent the number of sample points and the number of traces separately;andrepresent the values of first sample points of the first and second trace separately.

In conventional CPA (CPA-Covt), we adopt the strategy of ‘divide and conquer’ to combine the guess key segment to recovery the whole key.

For one key segment, we traverse all possible key segments to get intermediate values,the hamming weight of the SubBytes results.Then we get a correlation matrix of hamming weight HW and power traces. After that, we find the maximum peak of correlation matrix to get the corresponding key segment which will be considered as the right one. The correlation formulation is expressed as follows:

2.2 Previous attacks

Youssef Souissi proposed adapt KALMAN FILTER[9,10]for the CPA optimization, which is a recursive filter for time-varying linear systems. And the mentioned method makes the past error estimation into new to estimate the future error and to realize the noise filtering.It proved the mentioned method reduced the number of traces in the situation of same attack result.

CHARVET Xavier et al proposed a kind of improving power analysis attack by wavelet transform. By the reconstruction of the information with low and high frequency, the method smoothed the signals in the situation of asynchrony and improved the attack effect.

Thanh-Ha Le et al proposed to use FOC to improve the attack performance. The mentioned method is assumed that the noise is Gauss noise which will be removed to produce new signals. It proved the time shift of asynchrony signals was eliminated by the superposition of new signal with FOC.

These methods are proposed for power traces processing. They have different ways of dealing with noise, and their attack effects are different.

III. PROPOSED METHOD

EMD is used for time-frequency analysis of signal process[11], which extracts the local signals of different frequency bands from the original data, to reconstruct the data for noise elimination. Its decomposition steps are shown as follows.

1 Find all the extreme points of original signals

3 Repeat the second step for k times until the first intrinsic mode function (IMF)satisfies the condition. The expression is as follows:

4 Remove the first IMF from the original signal to get the new signal, and repeat the second and the third step to generate a plurality of intrinsic mode functions (IMFs).

In conventional EMD (EMD-Covt) method,is reconstructed signals containing IMFand a remainderThe express is shown as follows:

where L and L are the minimum and maximum number of IMFs. In the phase of signal reconstruction, not all the IMFs are selected.If IMF is selected that depends on its actual and theoretical energies. If the comparison has significant distinction, the IMF will be chosen.

In our proposed EMD method, we consider that signals with different frequency range have different effects on CPA attack. So we intend to apply the first, second, and third IMF as three kinds of new signals which will be used in CPA.

3.1 Attack assessment

Commonly the way to recover the secret key is to find the maximum peak from the correlation curves. However, if the maximum peak is not obvious, it will increase the difficulty of the attack. To effectively evaluate the attack effectiveness of our proposed method, this paper presents a new assessment for CPA attack.

We find the correct correlation curve and select a segment of the curve which has no obvious larger peak. The number of peaks for this segment is denoted by q(q=1,2,...N). Get the mean of these peak values to be benchmark amplitude w. Then calculate the ratio R of the maximum peak value H and w, named peak visibility (PV).

IV. EXPERIMENT AND ANALYSIS

4.1 Analysis in non-noise environment

We select a set of traces about Advanced Encryption Standard with RPIs and assume that the traces are collected in the external environment of non-noise. To evaluate the effectiveness of our proposed method, CPA- Covt attack, EMD-Conv and our proposed EMD methods are compared.

We compress the traces firstly by summing the values of traces[12]. After the signal processing of EMD-Covt and our proposed method,we get the new signals for CPA attack. With the number of traces increase, these attack results present rising trend. In figure 1, it can be seen that the first and second IMFs show excellent performances on attack effects, which are better than EMD-Covt, which will be considered as new effective signals to attack. The third IMF is second-to-last, but better than CPA-Covt.

Fig. 1 The results of different methods (non-noise)

Fig. 2 The results of different methods (SNR-5dB)

Fig. 3 The results of different methods (SNR-10dB)

As the traces to attack is 1000, the maximum value of PV of the first IMF is 10.04,increasing by 64% than EMD-Covt. And it also increases by 3.46 times than CPA-Covt(shown in figure 1).

4.2 Analysis in noise environment

In order to research the influence of the external environment on the power traces, we analyze the attack effect of the proposed method on the conditions of signal-to-noise ratio(SNR) of 5dB, 10dB, 15dB and 20 dB.

On condition of the SNR of 5dB, except the PV of CPA-Covt, the others’ show tendency to ascend. The first and second IMFs still show better performance than EMD-Covt and CPACovt. As the number of traces is 1000, the value of PV for the first IMF is 11.12, increasing by 88.2% than EMD-Covt, and also increasing by 4.32 times than CPA-Covt (shown in figure 2).

With the SNR is increased to 10dB (shown in figure 3), the attack results show similar tendency with the non-noise environment.The order of the results is also same. As the number of traces is 1000, the value of PV for the first IMF is 9.76, increasing by 53% than EMD-Covt, and also increase by 3.33 times than CPA-Covt.

The attack results of these methods with SNR of 15dB tend to increase slowly (shown in figure 4). As the number of trace is 1000,for EMD-Covt, its value of PV is closed to 6.73. For the first IMF, its value of PV increases by 65.4% than EMD-Covt, and also increases by 4.48 times than CPA-Covt.

V. CONCLUSION

In this paper, an improved EMD method is proposed for CPA attack, whose result shows better than EMD-Covt and CPA-Covt. To test the effect of new method, the paper proposes a new attack assessment. The new method is tested in the environment of noise and nonnoise. In the absence of noise interference, the attack effect of the first IMF is optimal, and the second IMF is the second choice. In the case of noise interference, the orders of attack effects are still the same. But the noise has impact on the value of PV. The attack effect of the first IMF shows excellent performance on the condition of noise with 15dB.

This work has been supported by The National Natural Science Foundation of China under Grants 61571063, 61501100 and 61472357.

Fig. 4 The results of different methods (SNR-15dB)

Fig. 5 The results of different methods (SNR-20dB)

[1] B. Mazumdar and D. Mukhopadhyay, “Construction of Rotation Symmetric S-Boxes with High Nonlinearity and Improved DPA Resistivity”. IEEE Transactions on Computers, vol. 66, no. 1, pp.59-72, 2017.

[2] AA. Zadeh, HM. Heys. “Simple power analysis applied to nonlinear feedback shift registers”.IET Information Security, vol. 9, no. 1, pp. 90-90,2015.

[3] D. Bellizia, S. Bongiovanni, P. Monsurro, G. Scotti, A. Trifiletti, “Univariate Power Analysis Attacks Exploiting Static Dissipation of Nanometer CMOS VLSI Circuits for Cryptographic Applications”. IEEE Transactions on Emerging Topics in Computing, vol.PP, no.99, pp.1-1, 2016.

[4] Catherine H. Gebotys and Brian A. White. “A Sliding Window Phase-Only Correlation Method for Side- Channel Alignment in a Smartphone”.ACM Trans. Embed. Comput. vol.14, no 4, pp.80,2015.

[5] N. Debande, Y. Souissi, M. Nassar. ”Re-synchronization by Moments: an efficient solution to align Side-Channel traces”. IEEE International Workshop on Information Forensics & Security.pp.1 - 6 2011.

[6] T. Ha Le, J. Clédière, C. Servière, and J.L. Lacoume. “Noise Reduction in Side Channel Attack Using Fourth-Order Cumlant”. IEEE Transaction on In- Formation Forensics and Secu-Rity, vol. 2, no. 4, pp. 710- 720, 2007.

[7] H Patel and R Baldwin. “Differential Power Analysis Using Wavelet Decomposition”. Military Communica- tions Conference, pp. 1-5, 2012.

[8] M.L. Feng, Y.B. Zhou, Z.M Yu. “EMD- Based Denoising for Side-channel Attacks and Relationships between the Noises Extracted with Different Denoising Methods”. ICICS 2013, LNCS 8233, pp. 259- 274, 2013.

[9] Y Souissi, S Guilley, JL Danger, S Mekki, G Duc.“Improvement of Power Analysis Attacks Using Kalman Filter”. ICASSP, pp.1778-1781, 2010.

[10] JY Wang, Y Wang, BY Jing, X Gao. “Maximum correntropy Kalman filter”. Automatica. Vol. 76,pp.70- 77, 2017

[11] X. Wang, Z. Chen, J. Luo, J. Meng and Y. Xu, “ECG compression based on combining of EMD and wavelet transform”. Electronics Letters, vol.52,no.19, pp. 1588 -1590, 2016.

[12] S Mangard, E Oswald, T Popp. Power Analysis Attacks [M]. Dengguo Feng, YB. Zhou, JY. Liu.Beijing: Science Press, 100-109, 2010.