基于并行计算的侧信道攻击加速方法.pdf
《基于并行计算的侧信道攻击加速方法.pdf》由会员分享,可在线阅读,更多相关《基于并行计算的侧信道攻击加速方法.pdf(14页珍藏版)》请在咨信网上搜索。
1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(5):922935密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618基于并行计算的侧信道攻击加速方法*苏 杨1,季凡杰1,许 森4,王伟嘉1,2,31.山东大学 网络空间安全学院,青岛 2662372.泉城省实验室,济南 2501033.山东大学 密码技术与信息安全教育部重点实验室,青岛 2662374.观源(上海)科技有限公司,上海 200241通信作者:王伟嘉,E-mail:摘要:侧信道攻击是一种从大量
2、的泄漏数据中挖掘秘密信息的攻击方法.例如典型的相关性能量分析(CPA),在一次完整的攻击过程中,往往对几十、几百万的功耗曲线进行分析,而且其分析过程也需要对密钥进行穷举,这导致了大量的重复性攻击试验.因此计算时间成为影响侧信道攻击效率的重要瓶颈之一.本文提出了一种基于并行计算加速侧信道攻击的方法.该方法提出首先对功耗曲线做快速转置预处理操作,再利用并行计算加速攻击效率,预处理后的曲线能够更好地适用于并行计算平台,从而大幅度提升计算速度.实验表明,同等条件下,该方法能够高效地攻击更大范围的密钥空间,这极大提高了侧信道攻击的适用性.另外,考虑到现实攻击者需要大量重复性攻击试验,此方法通过数据预处理
3、避免了重复访存所带来的时间成本,因此随着密钥空间的扩大,该方法节省的时间成本更加可观.关键词: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 par
4、allel 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.Qua
5、n 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);泉城省实验室重
6、点项目(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&Technology
7、BureauofShandongProvince(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
8、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 i
9、mportant 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 t
10、he 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 tri
11、es 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,
12、但是在现实中,攻击者往往可以观察到密码算法运行在具体软硬件上时泄漏的额外信息,如运行时间、功耗等,并利用这些信息对密码进行更有效的分析.这一类绕过密码算法本身繁琐的分析,而利用其运行过程泄漏信息的攻击方法称为侧信道攻击.能量分析攻击是最重要、最有效的侧信道攻击形式之一3,这是一种非侵入式攻击,主要利用密码设备运行的物理特征而非密码算法的数学特性4进行攻击.能量分析攻击包括简单能量分析 SPA(simplepower analysis)、差分能量分析 DPA(differential power analysis)5、相关性能量分析 CPA(correlationpower analysis)等
13、主流攻击方式.其中 CPA 是一种利用功耗曲线执行侧信道分析的强大方法6,并且伴随着相关研究的进展,业界对 CPA 的研究逐渐从攻击的准确性过渡到攻击时计算的有效性.随着科学技术的飞速发展及计算机硬件水平的不断提升,计算机的性能也在不断提升,并行计算越来越成为科学计算的选择.而 CUDA(compute unified device architecture)是由 NVIDIA 公司7推出的一个通用并行计算架构,该架构使 GPU(graphics processing unit)能够并行地解决复杂的计算问题.由于 CUDA 在并行计算方面表现良好,如今的 GPU 使用数百个并行处理器内核执行数
14、以万计的并行线程,足以解决具有实质并行性的大型问题.它们是有史以来最普遍的大规模并行处理平台,也是最具有性价比的平台8.因此,多个学科依托 NVIDIA CUDA 平台来实现相关算法的优化9.近几年来优化侧信道攻击效率的相关方法主要分为两类:第一类一般集中于对功耗曲线的处理.例如减少待处理数据的维度,从而降低攻击数据的计算复杂度,进而提高攻击效率等1014.第二类则主要考虑提升攻击的计算速度.2010 年,Lee15等人提出 CPU 与 GPU 组合使用的方式可以显著提升侧信道攻击的效果,但未考虑到更大密钥空间的需要,存在一定的局限性;2014 年,Gamaarachchi16等人提出将图形处
15、理器(GPU)应用于 CPA 的方法.Gamaarachchi 认为,在通用的 CPU 上进行 CPA 的时间成本不可观,因此在 GPU 上为每一个密钥字节、每一个密钥猜测和每一组功耗曲线分配了一个三维的(目前所能实现的最大维度)CUDA 线程,因此高维的线程实现了更高的数据并行性,但由于显存容量有限,无法处理较多的功耗数据和密钥猜测数量.2016 年,Schellenberg17提出了基于 GPU 并行加速的一阶和高阶 CPA 攻击框架.该框架的可扩展属性可以实现在任意大型服务器集群之间平均分配攻击的工作,从硬件资源角度提高了并行计算的效率.2019 年,王凌云18等人提出将 CPA 攻击中
16、计算密集的部分都转移至 GPU 上实现,带来了较好的攻击效果.但未考虑功耗曲线较多时的传输效率.总的来说,目前相关924Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023的研究主要集中于理论上并行程度的提高,大部分未考虑到现实攻击的数据量问题.在现实攻击中由于功耗曲线按行分块存储,读取一个采样点的功耗数据需要多次访存,严重影响攻击的效率.所以本文针对现实的攻击提出了一种基于并行计算加速 CPA 的方法.该方法基于现实功耗曲线分块存储、载入内存时会产生大量时间成本的特点,提出将功耗曲线先转置再并行加速,由此读取曲线一次即可获得该采样
17、点对应的所有功耗数据,再根据 CUDA 适用于并行计算的特性,将 CPA 部署至 GPU,以此获得较高的攻击时间效益.实验数据表明,采用这种方法,可以将一次密钥攻击的范围由一个字节扩增至最大四个字节,能够高效地攻击更大范围的密钥空间.此方法通过数据预处理避免了重复访存所带来的时间成本,同传统的并行计算加速方法相比,密钥空间越大,该方法能够节省的时间越多.本文第2节主要介绍 CPA 的基本原理,以及利用 GPU 的 CUDA 编程平台加速 CPA 的可行性.同时也介绍计算相关系数时所采用的在线更新算法(Welfords online algorithm).第34节介绍基于并行计算的侧信道攻击算法
18、的设计与具体实现.第5节介绍该加速方法的具体实验及优化效果.第6节总结全文.2背景技术2.1相关性能量分析(CPA)相关性能量分析(CPA)是目前最流行的能量分析手段之一,本文将其作为侧信道攻击的具体实例.攻击时主要有以下步骤:(1)采集足够多的功耗曲线并以矩阵形式存储,矩阵每行为每条功耗曲线,每列为采样点;(2)选择合适的中间值函数,例如在 AES-128 算法中选取位置中间值函数为 f(d,k),d 为已知数据,k 为猜测子密钥;(3)根据中间值函数计算出中间值,假如子密钥有 8 位,则对应 256 种可能值,即密钥猜测值;(4)将计算得出的中间值映射为假设能量功耗值,常见映射模型有汉明重
19、量模型和汉明距离模型等;(5)比较假设能量功耗值与实际功耗值,与实际功耗值相关性最高的假设值即为该子密钥的正确密钥猜测值.在该攻击过程中,攻击者无需了解被攻击设备的详细知识,即使功耗曲线包含噪声难以区分,只要具备足够多的功耗曲线便可成功恢复密钥3.2.2GPU 与 CUDACUDA19是英伟达(NVIDIA)公司推出的一个通用的并行编程平台.NVIDIA 显卡是支持大量线程并发执行的设备.与现代通用处理器 CPU 相比,两者结构类似,都具有用于计算的核,但 CPU 内核较少,内核集中用于快速处理单个任务,因此 CPU 适合处理复杂的串行计算.GPU 核数较多,适合较简单的并行工作.CPA 数据
20、独立性较高,GPU 的并行特点可以极大地提高其攻击性能.Block 和 Grid 是CUDA 编程上的概念,Grid、Block 和 Thread 都是线程的组织形式,Thread 是最小的逻辑单位,一定数量的 Thread 组成一个 Block,一定数量的 Block 组成一个 Grid,核函数在执行时应配置合适的 Grid 和Block 大小.Numba20开源软件包的提出使我们可以使用 Python 编程语言21对 CUDA 进行编程,并且Numba 提供了一系列函数实现了分配设备内存、在主机与设备间拷贝数据等功能.另外 CUDA 支持高达三维的线程索引,多维线程层次结构使我们能够方便地
21、将并行化算法的组件映射到 GPU 线程上.例如,一维线程索引映射为向量操作,而二维线程索引映射为矩阵操作.在使用时,核函数会根据需要被分配给 N 个不同的线程(Thread),N 个线程并行执行,以达到并行计算加速的作用.对于一个特定的 CUDA内核,线程块的大小是相等的.用户必须在调用 CUDA 内核时指定线程块大小,一个线程块最多设置1024 个线程.线程块的大小是影响 CUDA 并行性能的一个重要因素,需要谨慎选择合适的参数.2.3在线更新算法在 CPA 中,皮尔逊相关系数计算需要计算方差,但是经典方差公式涉及平方和,这极容易出现数值不稳定或算术溢出等问题.在线更新算法22使用逐次更新的
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 核
23、函数对应的维度,以此来实现合适的并行计算16,18.此处以 AES-12823第一轮 S-box 之后的泄漏为例,一个完整的二维 GPU 加速 CPA 攻击设计流程如下:(1)获取中间值矩阵 D.将密码设备每次执行的数据值 di通过穷举密钥猜测得到假设中间值矩阵D,再通过能量映射模型对中间值进行能量映射,本文采用汉明重量能量映射模型,最终得到假设能量消耗矩阵 D 和对齐的功耗曲线 T.(2)设计核函数.其中图1展示了 CPA 攻击二维核函数结果矩阵的组织,图1中网格代表了一次密钥猜测的相关性结果矩阵 R,灰色格子代表了一个二维线程执行核函数的结果,即针对相关性结果矩阵 R 每个点对应的核函数分
24、配二维的线程,所以灰色格子是密钥猜测以及功耗曲线泄漏位置的组合.攻击时,在 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 每列数据(即每个采
25、样点)的相关性系数.根据功耗曲线按行存储、按行读取的原则,相关性系数计算公式一般使用此公式:(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 密码学报
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 并行 计算 信道 攻击 加速 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。