基于并行计算的侧信道攻击加速方法.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(5):922935密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]基于并行计算的侧信道攻击加速方法*苏 杨1,季凡杰1,许 森4,王伟嘉1,2,31.山东大学 网络空间安全学院,青岛 2662372.泉城省实验室,济南 2501033.山东大学 密码技术与信息安全教育部重点实验室,青岛 2662374.观源(上海)科技有限公司,上海 200241通信作者:王伟嘉,E-mail:摘要:侧信道攻击是一种从大量的泄漏数据中挖掘秘密信息的攻击方法.例如典型的相关性能量分析(CPA),在一次完整的攻击过程中,往往对几十、几百万的功耗曲线进行分析,而且其分析过程也需要对密钥进行穷举,这导致了大量的重复性攻击试验.因此计算时间成为影响侧信道攻击效率的重要瓶颈之一.本文提出了一种基于并行计算加速侧信道攻击的方法.该方法提出首先对功耗曲线做快速转置预处理操作,再利用并行计算加速攻击效率,预处理后的曲线能够更好地适用于并行计算平台,从而大幅度提升计算速度.实验表明,同等条件下,该方法能够高效地攻击更大范围的密钥空间,这极大提高了侧信道攻击的适用性.另外,考虑到现实攻击者需要大量重复性攻击试验,此方法通过数据预处理避免了重复访存所带来的时间成本,因此随着密钥空间的扩大,该方法节省的时间成本更加可观.关键词:AES 算法;相关性能量分析(CPA);并行计算中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000642中文引用格式:苏杨,季凡杰,许森,王伟嘉.基于并行计算的侧信道攻击加速方法J.密码学报,2023,10(5):922935.DOI:10.13868/ki.jcr.000642英文引用格式:SU Y,JI F J,XU S,WANG W J.A new method of accelerating side-channel at-tack based on parallel computingJ.Journal of Cryptologic Research,2023,10(5):922935.DOI:10.13868/ki.jcr.000642A New Method of Accelerating Side-Channel Attack Based onParallel ComputingSU Yang1,JI Fan-Jie1,XU Sen4,WANG Wei-Jia1,2,31.School of Cyber Science and Technology,Shandong University,Qingdao 266200,China2.Quan Cheng Laboratory,Jinan 250103,China3.Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education,ShandongUniversity,Qingdao 266237,China*基金项目:国家重点研发计划(2021YFA1000600);国家自然科学基金(62002204,62372273);山东省泰山学者基金;山东大学齐鲁青年学者基金(61580082063088);山东省科技厅山东省实验室项目(SYS202201);泉城省实验室重点项目(QCLZD202306)Foundation:National Key Research and Development Program of China(2021YFA1000600);National Nat-ural Science Foundation of China(62002204,62372273);Fund of Taishan Scholars of Shandong Province;Qilu Young Scholars Fund of Shandong University(61580082063088);ProgramofScience&TechnologyBureauofShandongProvince(SYS202201);Major Program of Quan Cheng Laboratory(QCLZD202306)收稿日期:2022-09-18定稿日期:2022-11-15苏杨 等:基于并行计算的侧信道攻击加速方法9234.ShanghaiViewsourceInformation Science&Technology Co.Ltd.,Shanghai 200241,ChinaCorresponding author:WANG Wei-Jia,E-mail:Abstract:Side-channel attack(SCA)is a powerful attack method which is able to extract secretinformation from power consumption.For example,correlation power analysis(CPA)can exploitmillions of power traces to conduct an exhaustive search of the subkey,which leads to numerousrepeated trials.Hence,time complexity becomes one of the most important bottlenecks of SCA.Thispaper describes a new method based on parallel computing to accelerate the SCA.Compared withthe existing method,our new one first performs pre-processing to power traces,so that pre-processedtraces can be better applied to parallel computing to significantly improve the computation speed.Ourexperiments show that this method can efficiently attack a larger size of the key space under the samecondition,which greatly improves the practicality of SCA.In addition,this method avoids the timecost of repeated memory accesses due to data pre-processing,if an attacker tries a number of attackattempts.This method is more significant for the large size of subkey space.Key words:AES;correlation power analysis(CPA);parallel computing1引言自 1996 年 Kocher 博士首次提出侧信道攻击以来1,侧信道攻击及其防御对策的研究已经逐渐成为密码学研究中的一个重要分支,受到了国际学术界与产业界的广泛关注.侧信道攻击不同于传统的密码安全,传统的密码安全通常假设攻击者最多能接触到密码算法的输入、输出和公开参数2,但是在现实中,攻击者往往可以观察到密码算法运行在具体软硬件上时泄漏的额外信息,如运行时间、功耗等,并利用这些信息对密码进行更有效的分析.这一类绕过密码算法本身繁琐的分析,而利用其运行过程泄漏信息的攻击方法称为侧信道攻击.能量分析攻击是最重要、最有效的侧信道攻击形式之一3,这是一种非侵入式攻击,主要利用密码设备运行的物理特征而非密码算法的数学特性4进行攻击.能量分析攻击包括简单能量分析 SPA(simplepower analysis)、差分能量分析 DPA(differential power analysis)5、相关性能量分析 CPA(correlationpower analysis)等主流攻击方式.其中 CPA 是一种利用功耗曲线执行侧信道分析的强大方法6,并且伴随着相关研究的进展,业界对 CPA 的研究逐渐从攻击的准确性过渡到攻击时计算的有效性.随着科学技术的飞速发展及计算机硬件水平的不断提升,计算机的性能也在不断提升,并行计算越来越成为科学计算的选择.而 CUDA(compute unified device architecture)是由 NVIDIA 公司7推出的一个通用并行计算架构,该架构使 GPU(graphics processing unit)能够并行地解决复杂的计算问题.由于 CUDA 在并行计算方面表现良好,如今的 GPU 使用数百个并行处理器内核执行数以万计的并行线程,足以解决具有实质并行性的大型问题.它们是有史以来最普遍的大规模并行处理平台,也是最具有性价比的平台8.因此,多个学科依托 NVIDIA CUDA 平台来实现相关算法的优化9.近几年来优化侧信道攻击效率的相关方法主要分为两类:第一类一般集中于对功耗曲线的处理.例如减少待处理数据的维度,从而降低攻击数据的计算复杂度,进而提高攻击效率等1014.第二类则主要考虑提升攻击的计算速度.2010 年,Lee15等人提出 CPU 与 GPU 组合使用的方式可以显著提升侧信道攻击的效果,但未考虑到更大密钥空间的需要,存在一定的局限性;2014 年,Gamaarachchi16等人提出将图形处理器(GPU)应用于 CPA 的方法.Gamaarachchi 认为,在通用的 CPU 上进行 CPA 的时间成本不可观,因此在 GPU 上为每一个密钥字节、每一个密钥猜测和每一组功耗曲线分配了一个三维的(目前所能实现的最大维度)CUDA 线程,因此高维的线程实现了更高的数据并行性,但由于显存容量有限,无法处理较多的功耗数据和密钥猜测数量.2016 年,Schellenberg17提出了基于 GPU 并行加速的一阶和高阶 CPA 攻击框架.该框架的可扩展属性可以实现在任意大型服务器集群之间平均分配攻击的工作,从硬件资源角度提高了并行计算的效率.2019 年,王凌云18等人提出将 CPA 攻击中计算密集的部分都转移至 GPU 上实现,带来了较好的攻击效果.但未考虑功耗曲线较多时的传输效率.总的来说,目前相关924Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023的研究主要集中于理论上并行程度的提高,大部分未考虑到现实攻击的数据量问题.在现实攻击中由于功耗曲线按行分块存储,读取一个采样点的功耗数据需要多次访存,严重影响攻击的效率.所以本文针对现实的攻击提出了一种基于并行计算加速 CPA 的方法.该方法基于现实功耗曲线分块存储、载入内存时会产生大量时间成本的特点,提出将功耗曲线先转置再并行加速,由此读取曲线一次即可获得该采样点对应的所有功耗数据,再根据 CUDA 适用于并行计算的特性,将 CPA 部署至 GPU,以此获得较高的攻击时间效益.实验数据表明,采用这种方法,可以将一次密钥攻击的范围由一个字节扩增至最大四个字节,能够高效地攻击更大范围的密钥空间.此方法通过数据预处理避免了重复访存所带来的时间成本,同传统的并行计算加速方法相比,密钥空间越大,该方法能够节省的时间越多.本文第2节主要介绍 CPA 的基本原理,以及利用 GPU 的 CUDA 编程平台加速 CPA 的可行性.同时也介绍计算相关系数时所采用的在线更新算法(Welfords online algorithm).第34节介绍基于并行计算的侧信道攻击算法的设计与具体实现.第5节介绍该加速方法的具体实验及优化效果.第6节总结全文.2背景技术2.1相关性能量分析(CPA)相关性能量分析(CPA)是目前最流行的能量分析手段之一,本文将其作为侧信道攻击的具体实例.攻击时主要有以下步骤:(1)采集足够多的功耗曲线并以矩阵形式存储,矩阵每行为每条功耗曲线,每列为采样点;(2)选择合适的中间值函数,例如在 AES-128 算法中选取位置中间值函数为 f(d,k),d 为已知数据,k 为猜测子密钥;(3)根据中间值函数计算出中间值,假如子密钥有 8 位,则对应 256 种可能值,即密钥猜测值;(4)将计算得出的中间值映射为假设能量功耗值,常见映射模型有汉明重量模型和汉明距离模型等;(5)比较假设能量功耗值与实际功耗值,与实际功耗值相关性最高的假设值即为该子密钥的正确密钥猜测值.在该攻击过程中,攻击者无需了解被攻击设备的详细知识,即使功耗曲线包含噪声难以区分,只要具备足够多的功耗曲线便可成功恢复密钥3.2.2GPU 与 CUDACUDA19是英伟达(NVIDIA)公司推出的一个通用的并行编程平台.NVIDIA 显卡是支持大量线程并发执行的设备.与现代通用处理器 CPU 相比,两者结构类似,都具有用于计算的核,但 CPU 内核较少,内核集中用于快速处理单个任务,因此 CPU 适合处理复杂的串行计算.GPU 核数较多,适合较简单的并行工作.CPA 数据独立性较高,GPU 的并行特点可以极大地提高其攻击性能.Block 和 Grid 是CUDA 编程上的概念,Grid、Block 和 Thread 都是线程的组织形式,Thread 是最小的逻辑单位,一定数量的 Thread 组成一个 Block,一定数量的 Block 组成一个 Grid,核函数在执行时应配置合适的 Grid 和Block 大小.Numba20开源软件包的提出使我们可以使用 Python 编程语言21对 CUDA 进行编程,并且Numba 提供了一系列函数实现了分配设备内存、在主机与设备间拷贝数据等功能.另外 CUDA 支持高达三维的线程索引,多维线程层次结构使我们能够方便地将并行化算法的组件映射到 GPU 线程上.例如,一维线程索引映射为向量操作,而二维线程索引映射为矩阵操作.在使用时,核函数会根据需要被分配给 N 个不同的线程(Thread),N 个线程并行执行,以达到并行计算加速的作用.对于一个特定的 CUDA内核,线程块的大小是相等的.用户必须在调用 CUDA 内核时指定线程块大小,一个线程块最多设置1024 个线程.线程块的大小是影响 CUDA 并行性能的一个重要因素,需要谨慎选择合适的参数.2.3在线更新算法在 CPA 中,皮尔逊相关系数计算需要计算方差,但是经典方差公式涉及平方和,这极容易出现数值不稳定或算术溢出等问题.在线更新算法22使用逐次更新的加法计算方差,因此解决了前文提出的安全隐患.同时在处理侧信道数据时可以做到每读取一条曲线,对结果进行一次更新.计算相关系数需要预先计苏杨 等:基于并行计算的侧信道攻击加速方法925算协方差和方差,因此使用以下公式进行计算:xn=xn1+(xn xn1)n,2n=2n1+(xn xn1)(xn xn)2n1n,Covn(X,Y)=Covn1(X,Y)(n 1)+(xn xn1)(yn yn)n.2.4常用的侧信道攻击并行模式常用的侧信道攻击并行模式:目前常见的基于 CUDA 并行计算加速 CPA 的基本方法是将攻击过程中的几个要素并行化.例如将密钥猜测数量、采样点、密钥位数等映射为 CUDA 核函数对应的维度,以此来实现合适的并行计算16,18.此处以 AES-12823第一轮 S-box 之后的泄漏为例,一个完整的二维 GPU 加速 CPA 攻击设计流程如下:(1)获取中间值矩阵 D.将密码设备每次执行的数据值 di通过穷举密钥猜测得到假设中间值矩阵D,再通过能量映射模型对中间值进行能量映射,本文采用汉明重量能量映射模型,最终得到假设能量消耗矩阵 D 和对齐的功耗曲线 T.(2)设计核函数.其中图1展示了 CPA 攻击二维核函数结果矩阵的组织,图1中网格代表了一次密钥猜测的相关性结果矩阵 R,灰色格子代表了一个二维线程执行核函数的结果,即针对相关性结果矩阵 R 每个点对应的核函数分配二维的线程,所以灰色格子是密钥猜测以及功耗曲线泄漏位置的组合.攻击时,在 GPU 中将每一个计算相关性系数的过程并行化,分配二维 CUDA 线程,建立计算相关性的核函数.该核函数的功能是计算假设能量值矩阵每一列 dk=(d1,k,d2,k,dD,k)与功耗曲线的每一列 tj=(t1,j,t2,j,tD,j)的相关系数,并存储到相关性矩阵 R.其中 dk,j与 tj计算的结果为 Rk,j.图 1 二维 CUDA 核函数Figure 1 2-D kernel example(3)二维核函数的实施.该核函数的功能是计算假设能量功耗值 D 每列数据(即每种密钥猜测)同功耗曲线 T 每列数据(即每个采样点)的相关性系数.根据功耗曲线按行存储、按行读取的原则,相关性系数计算公式一般使用此公式:(X,Y)=nni=1xiyini=1xini=1yinni=1x2i(nni=1xi)2nni=1y2i(nni=1yi)2.只需遍历一次功耗曲线,遍历时计算 nni=1xiyi,ni=1xi,ni=1x2i,ni=1yi,ni=1y2i的值,便可计算均值、方差和协方差三值.核函数设置为二维核函数,线程的 id 是线性增长的,用于在硬件和软件上唯一标识每一个线程.二维核函数需分配二维线程,因此线程的 idx 映射为不同的密926Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023钥猜测,线程 idy 映射为功耗曲线的采样点.(4)直至所有假设能量功耗值数据和功耗曲线全部载入内存,即可根据最终的每列的方差和协方差计算相关系数.在这个过程中,每组数据之间的相关性系数互相独立可以并行计算.(5)将相关性系数矩阵为 Rk,j拷贝至 CPU.对相关性系数矩阵为 Rk,j进行处理获取最大值及其对应的横纵索引,这个阶段需要并行的任务数量较少,调用 CUDA 内核成本较高,因此本文选择在CPU 端进行该阶段的处理.由此,即可获得相关性系数的最大值对应的密钥猜测以及功耗曲线中的泄漏位置.2.5需要解决的问题并行计算应用于侧信道攻击,给该领域带来了显著的计算性能提升,但并行计算通常需要同时调度多个计算单元.目前,计算机硬件的性能参数有上限,难以负载较大规模的功耗曲线.大多数情况下,使用将收集曲线存储在外部存储器中的方法来缓解硬件设备的不足,但这种方法增加了现实攻击的难度.因为数据的分块存储会导致读取传输时间的增加.特别是 CPA 需要特定采样点的全部功耗数据,功耗曲线按照曲线条数进行存储,这意味着在进行 CPA 攻击时,需要多次访问外部存储,以获得与特定采样点对应的所有功耗数据.这将产生相当大的时间成本.所以要解决的问题为:(1)尽可能降低攻击数据在外部存储器与内存之间频繁传输带来的时间成本;(2)在有限的硬件资源条件下合理权衡并行计算性能与攻击所用数据规模的问题;(3)进一步扩大一次攻击密钥的范围,提高实际应用中密钥攻击的灵活度.3新的并行方法因此本文提出另外一种并行方式.这种并行方式首先对功耗曲线进行快速转置预处理,具体为将每个采样点数据从分块存储的一列转化为集中存储的一行,实施正式攻击时只需访问一次存储设备便可获得该采样点的所有功耗数据.然后将穷举不同密钥猜测的过程并行化,一次攻击一个采样点.3.1总体流程总的来说,如图2所示,本文的并行方法主要分为两个阶段.图 2 攻击总体流程图Figure 2 Attacking overall flow of DPA第一阶段:对大规模分块存储的功耗曲线进行转置.该步骤可以得到按行存储的逐个采样点数据.这个阶段的难点是如何对大规模分块存储矩阵进行快速转置,这也是该部分介绍的重点.第二阶段:在并行计算模型上部署 CPA.由于第一阶段得到了按行存储的逐个采样点数据,因此针对某个采样点进行攻击时,只需读取外部存储器一次便可得到所需全部数据,然后选择合适的并行策略,设计核心攻击函数,针对多个密钥猜测同时进行攻击.这个阶段将在第4节详细介绍.苏杨 等:基于并行计算的侧信道攻击加速方法9273.2功耗曲线预处理功耗曲线的预处理阶段目标是在现实攻击时,读取文件一次,便可获得某个采样点的全部功耗数据,同时这个转置操作应尽可能降低时间复杂度,减少访问外部存储器的开销.如算法1和图3所示,Ai为功耗曲线分块矩阵;功耗曲线块数为 N;每块矩阵重新分组数为 M;Ai转置过程中的中间矩阵为 Ci;Bj为最终转置完成的功耗曲线.算法 1 大规模矩阵转置算法Input:功耗曲线分块矩阵 Ai;功耗曲线块数 N;每块重新分组数 M;中间矩阵 Cj,i;/*Ci表示第 i 块功耗曲线被平均分成 M 块的曲线集合*/Output:转置完成的曲线块 Bj1for i 0 to N do2Read(Ai);3Transposition(Ai);4Cj,i DIVIDE(Ai);5end6for j 0 to M do7Read(Cj,i);8Bj Combination(Cj,i);9Save(Bj);10end图 3 矩阵转置后分块存储Figure 3 Transposition and storage of a matrix3.2.1矩阵转置后存储至外部存储器在这个阶段,本文主要对分块存储的功耗曲线进行以下操作:(1)将每块功耗曲线读取至内存进行转置操作.由于每块功耗曲线的大小是根据硬件资源来进行设置,因此在该硬件资源环境下可以直接进行矩阵的转置操作.本文使用 NumPy24提供的开源转置算法,其转置效率较高.Ai转置后矩阵为 Ci.(2)将转置后功耗曲线进行分块存储.这个阶段首先根据被攻击设备的硬件内存计算出攻击时所能提供的运行内存上限 MAX(Memory),攻击时一块数据的大小命名为 SIZEOF(Bj).再根据数据块的数量 N,以 Bj/M N MAX(Memory)原则(即不超过硬件资源上限),设置合适大小的每块重新分组数 M.(3)重新分块后每块数据成为 Cj,i,i 对应原始数据 Ai的块顺序 i,j 对应转置后数据 Ci内部分块928Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023存储的块顺序 j,即 Cj,i代表第 i 块原始分块存储功耗曲线转置后分块存储的第 j 块.3.2.2重新组织为新矩阵上一阶段获得了重新分块的数据 Cj,i.接下来在硬件内存允许条件下,根据 Bj/M NMAX(Memory)的原则,如图4所示,将 i 值不同 j 值相同的数据块按列顺序拼接,即将同一采样点的数据拼接,即可得转置后的包含原始功耗曲线整列的转置矩阵.处理完毕后,相关系数矩阵中的每一行数据对应原始功耗曲线中某个采样点所采集出的功耗数据.算法1展示了功耗曲线预处理转置的全部流程.图 4 Cj,i拼接Figure 4 Combination of Cj,i3.3预处理转置算法性能分析对于现实 CPA 来说,攻击所需的功耗曲线是大量的、分块存储的矩阵.我们无法避免分块读入功耗曲线导致的频繁访存,但采取上文方法只需遍历所有功耗曲线两次便可实现整个数据文件的完全转置,这极大地提高了矩阵转置的效率,进一步保障了后续 CPA 的攻击性能.4GPU 平台上的并行算法4.1CUDA 核函数实现本文给出的核函数实现如算法2所示,具体如下:同时启动多个线程,每个线程处理一种密钥猜测.众所周知,数据传输一直是 GPU 并行计算的瓶颈所在.为减少数据传输所用时间成本,本文将计算中间值矩阵的过程转移至 GPU.因此,需要从 CPU 传输给 GPU 的只有两种数据:明文以及转置后的功耗曲线.由于一次只传输一个采样点的全部数据,这种情况下,可以不考虑曲线的分块存储,所有需要的数据可以一次从 CPU 拷贝至 GPU.如图5所示,这里 p 描述了一组明文,其中 i 是明文序号.在该图中,明文的数量为 n,因此对应的功耗曲线数量同样为 n;k 代表了一次攻击的密钥,j 代表了不同的密钥猜测,图中一次攻击 m 个密钥猜测.每个明文与所有的密钥猜测通过中间值计算函数(具体的加密或解密算法以及功耗能量映射模型)计算出中间值 value,由此得到中间值矩阵.每个密钥猜测被分配给一个线程.例如线程 1 被分配给密钥猜测为k1对应的中间值矩阵的一列,而线程 2 被分配给密钥猜测为 k2对应的中间值矩阵的一列,以此类推.CUDA 内核函数规定了一个线程应该执行的所有工作:该线程读取参与攻击的拷贝至 GPU 的明文,计算出明文针对具体算法的汉明重量映射的假设能量功耗值,再将其同实际功耗曲线进行相关性系数的计苏杨 等:基于并行计算的侧信道攻击加速方法929图 5 CUDA 核函数设计Figure 5 Design of CUDA kernal算.因此当多个线程并行启动时,每个线程计算一种密钥猜测,所有线程都会调用相关性计算函数并计算出功耗数据与假设能量功耗值的相似度.最后调用原子函数获取相关性系数的最大值.算法 2 核函数算法/*假设能量功耗值的方差 var_data;*/*假设能量功耗值的均值 mean_data;*/*功耗曲线的方差 var_traces;*/*功耗曲线的均值 mean_traces;*/*协方差 result_cov 每次更新统计数值 gpu_temp;*/*假设能量功耗值的数量/长度 N;*/*相关性结果 cor;*/*algorithmn()为具体的加密算法,此处用于计算算法中的中间值;*/*HW()为汉明重量映射模型;*/*GET_MAX()为获取最大相关值的原子函数;*/Input:明文:plain_data;某一采样点的功耗数据:traces;Output:相关性最大的值及其位置索引:value,index;1SETPARAMS(blocks_per_grid,threads_per_block);2copy.to_device(traces);3copy.to_device(plain_data);4algorithmn(plain_data);5data HW(algorithmn(plain_data);6for i 0 to N do7UPDATE(gpu_temp);8UPDATE(var_data);9UPDATE(mean_data);10UPDATE(var_traces);11UPDATE(mean_traces);12UPDATE(result_cov);13end14cor (result_cov)/(var_traces var_data);15value,index GET_MAX(cor);16synchronize();17copy_to_host(value,index).930Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023在配置 CUDA 核函数时,Block 的设置应该遵循 SM 占用率最大化原则,Warp 是 SM 的基本执行单元.一个 Warp 包含 32 个并行 Thread.即使最后一个 Warp 中有效的线程数量不足 32,也要使用相同的硬件资源,所以 Block 的大小最好是 32 的倍数.Warp 与 Block 的关系为:WarpPerBlock=ThreadPerBlockWarpSize.根据多次实验验证,Block 的大小取 128 效果最优.4.2总体流程总的来说,如图6所示.图 6 使用 GPU 平台部署攻击总体流程图Figure 6 Attack overall flow using GPU(1)实现矩阵快速转置:该过程需遍历全部功耗曲线两轮.处理完毕后,相关系数矩阵中的每一行数据对应原始功耗曲线中某个采样点所采集出的功耗数据.(2)攻击:对应数据矩阵,为减少数据从外部存储器拷贝到显卡内存的时间成本,将假设能量功耗值矩阵的计算转移至 GPU 中,为每一个密钥猜测分配一个 Thread.以 AES-128 为例.核函数的组织如下:根据明文和密钥猜测计算出 AES-128 第一轮 MixColumn 或 S-box 之后的中间值,并将汉明重量作为能量映射模型,最终得到假设功耗值矩阵.若密钥猜测的比特数为 N,则有 2N种密钥猜测,每种密钥猜测对应一列假设能量功耗值.故对一组明文来说,有 2N列中间值.因此分配 2N个线程.(3)从外部存储器读取处理后的功耗曲线矩阵,将一行数据从 CPU 拷贝至 GPU,在 GPU 上关于每种密钥猜测同该行数据计算相关系数.并将结果暂时存储在 GPU 中.(4)运行核函数,得到关于所有密钥猜测假设能量功耗值与采样功耗值的 2N个相关系数之后,通过调用原子函数 atomic.max,在 2N个相关性系数中取最大值 max_value,并记录下对应的索引下标 max_index,索引下标即为密钥猜测,最后将 GPU 计算结果传至 CPU 即可得到关于某采样点相关性最大的密钥猜测.(5)通过对功耗曲线的转置,本文的方法成功避免了功耗曲线分块读取带来的时间损耗.这种情况下,密钥猜测位数的范围极大地延伸,以 AES 为例,以往攻击位置一般选择第一轮的 S-box 之后或最后一轮 S-box 之后,而密钥并行方式则可以将攻击位置向后推至 MixColumn 之后,一次可攻击更多的密钥.这在 CPU 上是计算上不可行的.苏杨 等:基于并行计算的侧信道攻击加速方法9315实验5.1实验设置本文中实验使用了 Python 3.8、CUDA 11.2 以及 Numba 0.44 环境,搭载了 Intel(R)Xeon(R)Gold6330 CPU 处理器,NVIDIA RTX A5000 显卡、NVIDIA RTX 3090 显卡以及 NVIDIA GTX 1050Ti显卡,其中三种显卡的算力为:8.6、8.6、6.1.使用了 AES_HD 公共数据集,该数据集分块存储,每块有25000 条功耗曲线,每条功耗曲线有 1250 个采样点.需要注意的是,由于实验目标是验证本文的并行加速方法能够带来比 CPU 和以往的并行计算方式更好的效果,因此比较的指标是对相同数据进行攻击操作时消耗的时间.另外,为了尽可能攻击更多位数的密钥,本文一次只攻击一个采样点的数据.5.2CPU/GPU 计算时间开销对比该实验选取了 25000 条功耗曲线.图7显示同一数据集在 CPU 和不同 GPU 平台上的执行时间随密钥猜测位数的变化而变化,并且密钥位数相同的情况下 CPU/GPU 计算时间成本差异较大.当密钥猜测位数在 614 位之间时,CPU 上的执行时间几乎随密钥猜测位数的增长呈指数增长.而 GPU 上的时间成本从图7看似乎始终接近于 0,这是因为与单线程的 CPU 计算相比,并行计算的 GPU 时间远远低于单线程 CPU 的运算时间.图 7 不同密钥位数情况下 CPU/GPU 计算时间对比Figure 7 Running time comparison on different key lengths因此把两种 GPU 单独拿出来放大展示.图8为 A5000 以及 GTX 1050Ti 的时间成本对比.在起步阶段使用 GPU 进行攻击运算不会提高性能.原因是密钥猜测位数较少的情况下并行运行启动的线程也比较少,这不足以隐藏 GPU 中的内存延迟.因此当密钥猜测数量很少时,GPU 架构可能会比 CPU 消耗更多的时间.但总的来说,随着密钥猜测位数的增长,并行计算可以带来较好的加速效果.图 8 6-14 位密钥猜测 GPU 计算时间对比Figure 8 GPU running time comparison regarding 614 bits of guessing key932Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.20235.3不同 GPU 并行效果A5000 有 8192 个 CUDA 核,3090 有 10496 个 CUDA 核,而 1050Ti 有 768 个 CUDA 核.因此在计算量较大、需要的并行线程数量较多时,理论上 3090 显卡应优于 A5000,A5000 应优于 1050Ti.本实验使用 25000 条功耗曲线.如图9所示,当密钥猜测位数低于 20 时,三种 GPU 效果基本相同.这是因为,如果密钥猜测位数少,并行运行的线程启动的也比较少,这不足以在 GPU 中隐藏内存延迟.如果密钥猜测位数超过 20,GPU的执行时间将随着密钥猜测位数的增加而以指数方式增加近一倍.在这样的并行度下,内存延迟是隐藏的.但是,随着密钥猜测位数的增加,如果密钥猜测位数大于 22,则在加速相同大小的数据集时,3090 GPU 的时间将明显少于 A5000 和 1050 Ti.图 9 三种 GPU 时间对比Figure 9 Running time comparison on different GPUs因此,如图10所示,当攻击 32 bit 密钥时,选择使用 Nvidia RTX 3090 显卡,最终所用时间为 17646.4 s,约 4.9 h.图 10 Nvidia RTX 3090 性能Figure 10 Nvidia RTX 3090s performance5.4不同加速方式对比5.4.1不同加速方式详细对比首先对并行加速侧信道分析工作做分析对比,如表1所示.由于 Schellenberg17文中一阶 CPA 的加速实现与 Lee 等15基本一致,故表中仅列出 Lee 的方法.5.4.2不同并行加速方式性能对比实验选取 5000 条功耗曲线.使用 NVIDIA RTX A5000 显卡,显卡内存为 24 G.如图11所示,该图体现了处理相同数据集时,随着攻击密钥猜测数量的增加,不同计算方式性能的变化.从图中得出,经典 CPA5由于未考虑并行加速计算密集部分,加速效果始终低于其他加速方法;Lee15的方法使用 CPU 与 GPU 组合使用的方式相比于经典 CPA 方法可以显著提升侧信道攻击的效果,但未考虑到更大密钥空间的需要,因此随着密钥空间的增大,其优化效果有限;而 Gamaarachchi苏杨 等:基于并行计算的侧信道攻击加速方法933表 1 不同并行加速方式对比Table 1Comparison of different parallel method方法策略特点Gamaarachchi 等16针对攻击不同阶段建立不同的并行策略有限硬件资源难以满足较大的数据集王凌云等18考虑到了功耗曲线分块逐行进行读取受制于硬件资源,密钥攻击范围有限Lee 等15,17提出将 CPU 与 GPU 结合加速侧信道分析未考虑较大密钥位数,并行算法可进一步优化本文预先转置处理功耗曲线,计算密集部分并行化扩大了密钥攻击范围,考虑到了硬件资源问题等16的方法由于建立了较高维度的计算模型可以实现较高的并行度,但这种高度并行策略会占用较多的硬件资源,不适用于密钥空间较大的情况.当密钥猜测位数较少时,王凌云等人18的并行计算方法性能优于本文方法,这是因为密钥猜测位数较少的情况下并行运行的线程启动的也比较少,这不足以隐藏 GPU 中内存延迟;但随着密钥猜测位数的增加,需要传输的数据越来越多,显卡的硬件资源面临的压力逐渐达到上限,必须通过减小数据规模、增多数据分块数的方式来以时间换空间,最终达到硬件上限,止步于密钥猜测位数 27,此时本文方法计算时