International Association
for Cryptologic Research

Power analysis of public-key algorithms is a well-known approach in the community of side-channel analysis. We usually classify operations based on the differences in power traces produced by different basic operations (such as modular exponentiation) to recover secret information like private keys. The more accurate the segmentation of power traces, the higher the efficiency of their classification. There exist two commonly used methods: one is equidistant segmentation, which requires a fixed number of basic operations and similar trace lengths for each type of operation, leading to limited application scenarios; the other is peak-based segmentation, which relies on personal experience to configure parameters, resulting in insufficient flexibility and poor universality.

In this paper, we propose an automated power trace segmentation method based on reinforcement learning algorithms, which is applicable to a wide range of common implementation of public-key algorithms. Reinforcement learning is an unsupervised machine learning technique that eliminates the need for manual label collection. For the first time, this technique is introduced into the field of side-channel analysis for power trace processing. By using prioritized experience replay optimized Deep Q-Network algorithm, we reduce the number of parameters required to achieve accurate segmentation of power traces to only one, i.e. the key length. We also employ various techniques to improve the segmentation effectiveness, such as clustering algorithm, enveloped-based feature enhancement and fine-tuning method. We validate the effectiveness of the new method in nine scenarios involving hardware and software implementations of different public-key algorithms executed on diverse platforms such as microcontrollers, SAKURA-G, and smart cards. Specifically, one of these implementations is protected by time randomization countermeasures. Experimental results show that our method has good robustness on the traces with varying segment lengths and differing peak heights. After employ the clustering algorithm, our method achieves an accuracy of over 99.6% in operations recovery. Besides, power traces collected from these devices have been uploaded as databases, which are available for researchers engaged in public-key algorithms to conduct related experiments or verify our method.