A Highly Effective DPA Attack Method Based on Genetic Algorithm

ShuaiweiZhang,XiaoyuanYang,,WeidongZhongandYujuanSun

Abstract: As one of the typical method for side channel attack, DPA has become a serious trouble for the security of encryption algorithm implementation. The potential capability of DPA attack induces researchers making a lot of efforts in this area, which significantly improved the attack efficiency of DPA. However, most of these efforts were made based on the hypothesis that the gathered power consumption data from the target device were stable and low noise. If large deviation happens in part of the power consumption data sample, the efficiency of DPA attack will be reduced rapidly. In this work, a highly efficient method for DPA attack is proposed with the inspiration of genetic algorithm. Based on the designed fitness function, power consumption data that is stable and less noisy will be selected and the noisy ones will be eliminated. In this way,not only improves the robustness and efficiency of DPA attack, but also reduces the number of samples needed. With experiments on block cipher algorithms of DES and SM4, 10% and 12.5% of the number of power consumption curves have been reduced in average with the proposed DPAG algorithm compared to original DPA attack respectively. The high efficiency and correctness of the proposed algorithm and novel model are proved by experiments.

Keywords: DPA, efficiency, noise, genetic algorithm, fitness function, novel model.

1 Introduction

Side channel attack has become a powerful attack method after being studied by different researchers all over the world [Kocher (1996)], leading great threat to the security of cryptographic devices. Currently, profiled attack and non-profiled attack are the two main strategies of side channel attack. Profiled attack [Fahn and Pearson (1999)] introduced as the strongest leakage analysis in an information theoretic sense and is divided into two phases: profiled phase and attacking phase such as template attack [Chari, Rao and Rohatgi (2002)] or stochastic attacks [Schindler, Lemke and Paar (2005)]. On the other hand, non-profiled attack is based on Differential Power Analysis (DPA) [Kocher, Jaffe and Jun (1999)] and Correlation Power Analysis (CPA) [Brier, Clavier and Olivier(2004)]. Instead of acquiring and analyzing cryptographic devices beforehand, like in profiled attack, non-profiled attack obtains the secret keys based on processing the information of power consumption gathered from cryptographic devices on-site. Among which, DPA has become the most popular strategy of power attack, benefiting from its low cost and high efficiency. Kocher et al. [Kocher, Jaffe and Jun (1999)] successfully obtained the secret key by exploiting Simple Power Analysis (SPA) and DPA targeting at DES algorithm in 1999. Since DPA utilizes the statistically differential technology to guess secret keys, without having the detailed knowledge of encryption algorithm, a large amount of power consumption data is needed to improve the SNR, and then to accurately recover secret keys. However, acquiring larger amount of power consumption data takes longer time, if under critical conditions (e.g. limited time for the attack) will result in small amount of power consumption sample or high noise power in the acquired samples,which invalidates the accuracy of the obtained secret keys.

2 Related work

Many attempts and contributions have been made, under the same outside environment and controlled parameters, to tackle the problem of how to improve the efficiency of DPA attack. Durvaux et al. [Durvaux and Standaert (2016)] pointed out that finding appropriate attack points at the beginning is the first step to increase the efficiency; after analyzing different ways of finding appropriate attack points, an approach of detecting those points based ont-test has been proposed. Hajra et al. [Hajra and Mukhopadhyay(2013)] come up with a multivariate model for an FPGA platform, which significantly improved the efficiency of DPA attack under the condition of high noise power in 2013.And in 2015, they proposed the multivariate leakage model for the optimal combining of non-profiled DPA attack [Hajra and Mukhopadhyay (2015)], and validated their theory by experiments. Ren et al. [Ren, Wu, Li et al. (2016)] applied advanced correlation power analysis attack to smart card with triple-DES, the attack efficiency was enhanced by combining multivariate leakage points in the process of DES encryption algorithm.Zhang et al. [Zhang, Wu, Wang et al. (2014)] firstly exploited genetic algorithm and put forward a new accurate leakage model based on the power consumption of multi S-box instead of the conventional one single S-box, which tremendously increases the attack efficiency. Together with the development of Artificial Intelligence and Big Data,optimization algorithms are trending to be applied to the area of side channel attack.Many attentions have been paid to profiled attack. As artificial intelligence and machine learning become strong tools to tackle a lot of problems in different research fields, the cryptographic community has been exploring the potential of profiled attacks based on machine learning models [Bartkewitz and Lemke-Rust (2012); He, Jaffe and Zou (2012);Heuser and Zohner (2012); Hospodar, Gierlichs, De Mulder et al. (2011); Jap and Breier(2014); Lerman, Bontempi and Markowitch (2014); Lerman, Bontempi and Markowitch(2015)], and Lerman et al. [Lerman, Martinasek and Markowitch (2016)] has concluded that under the circumstances of having “Dirty Data” in the acquired power consumption samples, the robustness and efficiency of profiling attack based on machine learning are better than template attack.

However, as for non-profiled attack, “Dirty Data” need to be taken into considerations as well. “Dirty Data” is the measured power consumption during the processing of algorithm within the encryption chip, which vastly differs from regular power consumption value because of the influence of outer environment and high noise.Carrying samples of “Dirty Data” into the leakage model and further applied into the DPA attack, will reduce the SNR of entire power consumption sample, significantly decreasing the attack efficiency. Thus, verifying “Dirty Data” from regular power consumption is one of the key factors to improve attack efficiency.

This work is inspired by conventional procedures of DPA attack and evaluation model of efficiency, while realizing that there is a possibility of acquiring “Dirty Data” during the real attacks. Hence, we put forward a high efficiency method for DPA attack based on genetic algorithm. The gathered power consumption data will be selected, during which the “Dirty Data” will be eliminated, integrated and assorted by the specifically designed fitness function, and then combined with conventional DPA attack procedure to recover secret keys. Besides, we also propose a highly practical evaluation model of DPA attack efficiency. And by experimenting with power consumption data from DES and SM4 algorithm, the amount of power consumption samples is proven to be reduced with our algorithm, and the proposed evaluation model of efficiency has better accuracy than the conventional model.

Our contribution. The novel contributions of this paper are as follows:

(1) In this paper, we put forward a highly efficient DPA attack based on genetic algorithm, which is able to eliminate most of the “Dirty Data” generated by influence of noises in the raw power consumption data, and in the meanwhile, integrates and assorts the effective data, down-sizing the amount of samples for attack curve, elevating the attack efficiency.

(2) We come up with a new evaluation model of DPA attack efficiency. Comparing to the conventional model without taking “Dirty Data” into consideration, which severely interferes with the information provided by effective data, our model processes “Dirty Data” to develop the utilization of effective data, resulting in a much more accurate model.(3) The genetic algorithm and evaluation model of efficiency proposed in our works can be applied to any encryption algorithm based on DPA. Furthermore, regarding other power consumption attack method, similar results can be achieved by slightly adjusting the fitness function.

This paper is organized as follows. Section 3 includes preliminaries of conventional DPA procedures. Section 4 introduces our highly effective DPA attack method. In Section 5,the results of the experiments are presented for validation of our algorithm and novel model. Section 6 presents the conclusions. Section 7 is dedicated to future work.

3 Preliminaries

3.1 Conventional procedures of DPA attack

(4) Observing the differential power consumption curves, if there is one peak point,bits cryptographic key is correctly guessed, otherwise, it is a false guessing, a new round of anticipation should be started.

(5) Applying the same procedures to anticipatebits cryptographic key to other S-boxes.

3.2 Conventional evaluation model of DPA attack efficiency

DPA attack efficiency has two important factors:

(1) Minimum number of power consumption curve needed to recover key, model is as follows:

Table 1: Evaluation algorithm for minimum number of power consumption curves

Figure 1: Efficiency function for conventional DPA attack

(2) Possibility of cryptographic key recovering:

Figure 2: Success rate with conventional DPA attack

4 DPA attack based on genetic algorithm (DPAG)

4.1 Main idea of our algorithm

According to the analysis above, the gathered power consumption data contains many“Dirty Data”, due to the fact that attacker would not be able to anticipate the environment while attacking beforehand, and the working environment for the chip, which processes the cryptographic key, is not ideal and interfered by noises. Thus, in order to improve the attack efficiency and reduce the number of power consumption curve sample, a fitness function is designed as in Eq. (6). Through evaluating the fitness value of each power consumption curve with Eq. (6), curves with the high value of fitness will be preserved and curves with the low value of fitness or sample with “Dirty Data” will be eliminated.

4.2 DPAG algorithm process

4.3 Novel evaluation model of DPA attack efficiency

(1) Minimum number of power consumption curve needed to recover key.

Different from conventional evaluation model of DPA attack efficiency, our novel model adopts the optimal number of power consumption curve as an independent variable for fitness functionH, while evaluating the minimum number of power consumption curve needed to recover the key. The model is as follows:

Evaluation figure of the minimum number of power consumption curves can be obtained with the evaluation algorithm in Tab. 2.

Table 2: Novel evaluation algorithm for minimum number of power consumption curves

?

Fig. 3 shows the minimum number of power consumption curve needed to recover the secret key. Curveis the changing tendency of, with the increasing of, while the anticipation ofis true;is the changing tendency of the maximum of , with the increasing of, while the anticipation ofis false. Curveandseparates at intersection point of; meaning thatis the minimum number of power consumption curve needed for DPA attack.

Figure 3: Efficiency function for novel DPA attack

Figure 4: Efficiency function for novel DPA attack

5 Experiments

In order to validate the efficiency and correctness of the proposed DPAG and novel evaluation model for DPA attack efficiency, experiments with the power consumption data gathered form the data acquisition system, as Fig. 5 shown, running block cipher algorithm of DES and SM4 separately on FPGA platform have been carried out. Results are as shown below:

Figure 5: System for acquisition of power consumption from target device

(1) Experiments on DES algorithm:

Figure 6: Comparison between original DPA and DPAG in DES

Figure 7: Success rate between original DPA and DPAG in DES

Illustrated in Fig. 6, as the results of attack between original DPA and DPAG in the DES algorithm, the trace number reduced from 267 to 184 when the right key curve can be separated from the wrong key curves. And in Fig. 7, clearly shows that under 100%success rate, 10% of the number of power consumption curves have been reduced in average with the proposed DPAG algorithm compared to original DPA attack.

(2) Experiments on SM4 algorithm:

Figure 8: Comparison between original DPA and DPAG in SM4

Figure 9: Success rate between original DPA and DPAG in SM4

Demonstrated in Fig. 8, as the results of attack between original DPA and DPAG in the SM4 algorithm, the trace number reduced from 443 to 353 when the right key curve can be separated from the wrong key curves. And in Fig. 9, clearly shows that under 100%success rate, 12.5% of the number of power consumption curves have been reduced in average with the proposed DPAG algorithm compared to original DPA attack.

To sum up, the high efficiency and correctness of the proposed method in this paper have been proved by experiments on block cipher algorithm of DES and SM4.

6 Conclusion

In this work, a highly efficient DPA attack based on genetic algorithm has been designed.With the established fitness function, power consumption data curve with larger or smaller value of fitness can be selected, sorted and integrated into effective data, eliminating samples with “Dirty Data” introduced by noise interference. Furthermore, a novel evaluation model of DPA attack efficiency has been proposed based on the designed algorithm. Comparing to conventional evaluation model of DPA attack efficiency, our model adopts the optimal number of power consumption curve as independent variable for fitness functionH, instead of using superposition of single curve samples as an independent variable for differential power consumption, while evaluating the minimum number of power consumption curve needed to recover the key. After the experiments, both the DPA attack based on genetic algorithm and novel evaluation model of DPA attack efficiency are supported correctly and accurately by experimental evidence: power consumption data of DES and SM4 algorithm processed with FPGA platform.

7 Future works

On the one hand, development of conventional methods of side channel attack has reached bottleneck; on the other hand, with the rapid development of Artificial Intelligence and Big Data, more and more optimization algorithms with excellent performances have been invented and improved. There is a great potential for the improvement of attack efficiency by applying algorithm of artificial intelligence into side channel attack. Our next step is to investigate more appropriate, better performed optimization algorithms for side channel attack to further improve the attack efficiency.

Acknowledgement:This work was supported by National Key R&D Program of China(Grant No. 2017YFB0802000), National Natural Science Foundation of China (Grant No.U1636114, 61772550, 61572521), National Cryptography Development Fund of China(Grant No. MMJJ20170112).