基于多种群遗传算法的相关能量分析中个体结合策略探究

On Individual Combination Strategy in Correlation Power Analysis Based on Multi-Population Genetic Algorithm

相关能量分析(correlation power analysis,CPA)是侧信道攻击中的经典有效方法之一,基于假设能量消耗与实际功耗的相关系数恢复密钥.在密码算法并行实现场景下,CPA“分而治之”的思想恢复密钥会导致低信噪比,有效信息无法被充分利用,大大降低攻击效率.基于简单遗传算法的CPA借助遗传算法的启发式搜索特性,可以充分利用有效信息,提高攻击效率,但遗传算法存在固有缺点,容易早熟收敛,这种现象在S盒较大数量较多的场景下更严重.基于多种群遗传算法的CPA在单个种群恢复密钥失败时,保留最优个体,并继续新的单种群进化,得到的最优个体与前面保留的最优个体通过“组合”得到更优的个体,一定程度可以缓解早熟收敛的问题,本文中“原始方法”就是这种方法的代称.本文针对多个种群进化结束得到的优秀个体的结合方式进行探究,引入三种新的多种群优秀个体结合策略,分别是:小组赛、投票法和二次进化.小组赛将每两个优秀个体分成一组再“组合”.投票法以适应度为权重进行投票,使得适应度高的个体决策权更大.二次进化保留多个单种群进化结束得到的最优个体,构成初始种群,并以稳态遗传方式进行再次进化.以AES-128算法为例,通过不同噪声标准差下的仿真实验和真实实验将这三种方法与原始方法进行成功率和计算代价的比较,发现二次进化是其中效果最好的,在噪声标准差为3的实验中,二次进化方法在190条波形时密钥恢复成功率达到91%,计算代价0:63×10^(6),此时原始方法的成功率仅60%,计算代价1:60×10^(6).

Correlation Power Analysis(CPA)is one of the classic and effective methods in sidechannel attacks.It recovers the key based on the correlation coefficient between assumed power consumption and actual power consumption.In the scenario of parallel implementation of cryptographic algorithms,CPA’s“divide and conquer”idea of restoring keys will result in a low signal-to-noise ratio,thus,effective information cannot be fully utilized,which will greatly reduce the attack efficiency.The CPA based on simple genetic algorithm can take advantage of the heuristic search feature of genetic algorithm to make full use of effective information and improve attack efficiency.However,genetic algorithms have an inherent shortcoming,i.e.,they are easy to converge prematurely,especially in scenarios with a large number of bigger S-boxes.CPA based on multi-population genetic algorithm retains the optimal individual when a single population fails to recover the key,and continues the evolution of a new single population,and the obtained optimal individual and the previously retained optimal individual are“combined”to obtain a better individual,which alleviates the problem of premature convergence to a certain extent.The“primitive method”in this paper is a synonym for this method.This paper explores the combination of outstanding individuals obtained by the evolution of multiple populations,and introduces three new strategies for combining outstanding individuals with multiple populations,namely:group competition,voting method and secondary evolution.The group competition puts two outstanding individuals into a group and then“combines”.The voting method uses fitness as the weight to vote,so that individuals with high fitness have greater decision-making power.The secondary evolution retains the optimal individuals obtained at the end of the evolution of multiple single-populations to form the initial population,and evolves again in a steady-state genetic method.Taking the AES-128 algorithm as an example,the three methods are compared with the original method in terms of success rate and computational cost through simulation experiments with different noise standard deviation and real experiments,and it is found that the secondary evolution gets the best results.In the simulation experiments with the noise standard deviation of 3,the key recovery success rate of the secondary evolution reaches 91%when there are 190 traces,with the computational cost of 0:63×10^(6),while the success rate of the original method is only 60%,with the computational cost of 1:60×10^(6).