Paper 2019/189

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

Yaoling Ding, An Wang, and Siu Ming YIU


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Multiple sieveGenetic algorithmCorrelation power analysisParallel implementationAES
Contact author(s)
dyl13 @ mails tsinghua edu cn
wanganl @ bit edu cn
smyiu @ cs hku hk
2019-02-26: received
Short URL
Creative Commons Attribution


      author = {Yaoling Ding and An Wang and Siu Ming YIU},
      title = {An Intelligent Multiple Sieve Method Based on Genetic Algorithm and Correlation Power Analysis},
      howpublished = {Cryptology ePrint Archive, Paper 2019/189},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.