Paper 2019/189

An Intelligent Multiple Sieve Method Based on Genetic Algorithm and Correlation Power Analysis

Yaoling Ding, An Wang, and Siu Ming YIU

Abstract

Correlation power analysis (CPA) is widely used in side-channel attacks on cryptographic devices. Its efficiency mostly depends on the noise produced by the devices. For parallel implementations, the power consumption during the S-box operation contains information of the whole intermediate state. When one S-box is analyzed by CPA, the others are regarded as noise. Apparently, the information of the remained S-boxes not only is wasted, but also increases the complexity of analysis. If two or more S-boxes are considered simultaneously, the complexity of exhaustive search on the corresponding key words grows exponentially. An optimal solution is to process all the S-boxes simultaneously and avoid traversing the whole candidate key space. Simple genetic algorithm was used by Zhang et al. to achieve this purpose. While, premature convergence causes failure in recovering the whole key, especially when plenty large S-boxes are employed in the target primitive, such as AES. In this paper, we study the reason of premature convergence, and propose the multiple sieve method which overcomes it and reduces the number of traces required in correlation power attacks. Operators and the corresponding parameters are chosen experimentally with respect to a parallel implementation of AES-128. Simulation experimental results show that our method reduces the number of traces by $63.7\%$ and $30.77\%$ compared to classic CPA and the simple genetic algorithm based CPA (SGA-CPA) respectively when the success rate is fixed to $90\%$. Real experiments performed on SAKURA-G confirm that the number of traces required to recover the correct key in our method is almost equal to the minimum number that makes the correlation coefficients of correct keys outstanding from the wrong ones, and is much less than classic CPA and SGA-CPA.