第40卷 计算机学报 Vol.402017论文在线出版号No.73 CHINESEJOURNALOFCOMPUTERS OnlinePublishingNo.73———————————————本课题得到国家自然科学基金(No.61303224，No.61672433)、博士后科学基金面上项目(No.2013M532081)、中央高校基本科研业务费专项资金（No.3102016JKBJJGZ07）资助. 毛保磊，男，1987年生，博士研究生，主要研究领域为隐通道分析，硬件设计信息流安全分析.E-mail:maobaolei@mail.nwpu.edu.cn. 胡伟(通讯作者)，男，1982年生，博士，副教授，主要研究领域为硬件安全，可重构系统和嵌入式系统设计.E-mail:vinnie@mail.nwpu.edu.cn. 张慧翔，男，1981年生，博士，副教授，中国计算机学会（CCF）会员，主要研究领域为信息安全、模式识别与应用.E-mail:zhanghuixiang@nwpu.edu.cn. 慕德俊，男，1963年生，博士，教授，主要研究领域为信息安全、控制系统设计.E-mail:mudejun@nwpu.edu.cn. 邰瑜，男，1982年生，博士研究生，主要研究领域为硬件安全，逻辑综合及优化.E-mail:taiyu@mail.nwpu.edu.cn. 洪亮，男，1979年生，博士，副教授，主要研究领域为信息安全、嵌入式系统应用.E-mail:hongliang@nwpu.edu.cn.基于信息熵的RSA硬件时间隐通道信息泄露量化研究毛保磊 胡伟 张慧翔 慕德俊 邰瑜 洪亮(西北工业大学自动化学院西安710072)摘要 RSA密码算法作为主流的公钥加密和签名算法，其安全性被工业界和学术界广泛关注。RSA算法的安全性主要包括算法自身的不易破解性和密钥的安全性两个方面。而通过能量和时间隐通道来攻击算法密钥往往比破解RSA算法更为有效。现有的研究大多关注RSA算法软件实现的安全性，并未深入探讨硬件IP(IntellectualProperty) 核中的时间隐通道对安全性的影响；虽然有基于形式化验证的方法对时间隐通道进行检测和隔离，或者采用基于类型系统的方法从硬件设计语言的角度消除时间隐通道，但这些硬件方法都只能实现时间隐通道的定性分析，缺乏有效的模型对时间隐通道进行量化分析。本文针对上述两个基本问题（硬件IP核与时间隐通道）开展研究。首先介绍了RSA时间隐通道的研究背景和硬件实现的威胁模型。然后引入基于信息熵的研究方法，分别建立了基于信息熵的时间隐通道攻击模型和基于信息熵的时间隐通道量化分析模型。本文实验对RSA密码核进行基于信息熵的攻击和基于方差的攻击以评估信息熵攻击的效果。同时，针对同一密码核不同密钥信息泄露进行量化分析；针对多种不同的RSA硬件架构量化分析模幂优化算法对时间隐通道信息泄露的影响；针对时间隐通道抵抗措施评估其减少时间隐通道信息泄露的作用；并通过攻击相应RSA核密钥以验证信息熵量化分析的有效性。最后实验综合评估不同RSA架构对设计复杂度的影响。实验结果显示基于信息熵的攻击方法在猜测正确率确信度方面优于基于方差的攻击方法；信息熵量化分析方法能够有效的评估RSA密码核时间隐通道信息泄露，为RSA密码核时间隐通道的研究提供量化分析的理论依据和测试手段。实验结果同时表明信息熵指标能够辅助设计人员权衡时间隐通道安全性与性能、资源率之间的关系，为硬件设计自动化提供潜在的时间隐通道硬件安全评价指标，实现对硬件设计特征更加精细和完善的描述。关键词 硬件安全；隐通道分析；时间隐通道；信息泄露；RSA算法；信息熵；量化分析中图法分类号TP309毛保磊,胡伟,张慧翔,慕德俊,邰瑜,洪亮, 基于信息熵的RSA硬件时间隐通道信息泄露量化研究,2017,Vol.40,在线出版号No.73MAOBao-Lei,HUWei,ZHANGHui-Xiang,MUDe-Jun,TAI Yu,HONGLiang,Quantitative Analysis of InformationLeakageThroughHardwareRSATimingChannelBasedonEntropyTheory,2017,Vol.40,OnlinePublishingNo.73QuantitativeAnalysisofInformationLeakageThroughHardwareRSATimingChannelBasedonEntropyTheoryMAOBao-Lei HUWei ZHANGHui-Xiang MUDe-Jun TAIYu HONGLiang(SchoolofAutomation,NorthwesternPolytechnicalUniversity,Xi’an710072)网络出版时间：2017-05-26 19:38:12网络出版地址：http://kns.cnki.net/kcms/detail/11.1826.TP.20170526.1938.012.html2 计算机学报 2017年Abstract TheRSAalgorithmisawidelydeployedpublickeycipherfordataencryptionanddigital signature,whosesecurityhas drawnattentionfrombothacademic andindustryfields. Its securityrelies onboththecomputationcomplexityofbreakingthealgorithmitselfandthesecurityoftheencryptionkey.Generally, it ismucheasiertorecovertheencryptionkeythanbreaktheRSAalgorithmthroughpowerandtimingsidechannelanalysis. PreviousworkprimarilyfocusesontimingsidechannelsinsoftwareRSAimplementations, withoutin-depthstudyingtheeffect of hardwarearchitectureontimingchannel security. Althoughthereisworkfordetectingandisolatingtimingchannelbasedonformalverificationoftiminginformationfloworbuildingtimingchannelfreehardwaredesignbyincorporatingnewtypesystemintothehardwaredesignlanguage,theycanonlyprovide qualitative analysis of timingchannel, lackingeffectivemodel toperformquantitative analysis ofhardwaretimingchannel security. Inthiswork, wewill concentrateonhardwareRSAcores andprovideaquantitativeanalysismodeltoevaluatesuchtimingchannelleakage. Firstly,weintroducehardwareRSAtimingchannel anditsthreatmodel.Wethenemploytheentropytheorytosetuptimingattackmodel andquantitativeanalysismodel forRSAarchitecturetimingchannel. Besides, weattackRSAimplementationbasedonentropyandvarianceanalysis, respectively. InordertodemonstratetheeffectivenessofentropyinquantifyinghardwareRSAimplementationleakage,weperformquantitativeanalysisofdifferentkey-pairsinformationleakagewithinthesameRSAarchitecture, quantifyinformationleakagefor different RSAarchitectureimplementationswithtimingchannel algorithmoptimizationtechniques, evaluate the effect of timingchannel countermeasureonreducinginformationleakage; andalsoattackeachRSAimplementationtovalidatetheeffectivenessof ourquantitativeanalysismodel. Finally, weevaluatetheeffect ofdifferent algorithmoptimizations, timingchannelmitigationtechniquesandcountermeasuresondesigncomplexityintermsoftimingchannel, performanceandresourceutilization.ExperimentalresultsshowthatentropymetriccanbeusedtoattackRSAtimingchannelanditcanincreasethesuccessratebycombiningvarianceanalysiswithentropyanalysis.EntropymetriccanbeusedtoquantitativelyanalyzeinformationleakagefromtimingchannelinRSAhardwarearchitectureseffectivelyandefficiently, whichprovidesaneffectivetheoretical basisandtest methodologytoassesstheseverityof timingchannelinformationleakage. Inaddition,entropymetriccanhelpdesignerstotradeoffsecurityrequirementsanddesignoverheadssuchasperformanceandresourceutilization, whichprovidesapotential securitymetrictointegratetimingchannel securitywithtraditional designmetrics(e.g. areaandperformance)tocharacterizethehardwareinmoredetail.Keywords hardware security; side channel analysis; timingchannel; informationleakage; RSAalgorithm;entropy;quantitativeanalysis1引言现代密码算法设计通常基于困难问题求解，如RSA算法基于大数因式分解的极端困难性。密码算法的安全实现不仅要求算法本身难以破解，还要求保障密钥安全性。攻击算法密钥往往比攻击密码算法本身更为有效。在密码算法的具体实现中，可能会存在时间或者能量隐通道。例如，加解密程序指令根据不同的密钥值选择不同执行路径，产生不同时间延迟，攻击者根据时间延迟的特征使用统计分析等方法破解密钥[1-3]。攻击者亦可通过测量、分析加解密实现的功耗获取密钥。这些隐通道导致密钥泄露，严重影响密码算法安全。Kocher博士首次实现了对基本RSA模幂算法的时间隐通道的攻击[1]。Schindler成功攻击了基于中国剩余定理的RSA实现并将其时序攻击方法扩展到其他高级模幂算法[2]。斯坦福大学进行的实验进一步验证了广泛应用的OpenSSL库中的RSA模幂实现存在时间隐通道，导致其在嘈杂的网络环境下依然能被攻击，充分暴露RSA时间隐通道问题的严重性[3]。同时基于共享机制的处理器硬件结构也容易遭受时间隐通道影响，被木马进程获取到机密信息[4]。高速缓冲存储结构Cache是共享硬件泄论文在线出版号No.73 毛保磊等：基于信息熵的RSA硬件时间隐通道信息泄露量化研究 3露信息的重要来源，攻击者可以通过对Cache命中率分析提取AES密钥信息[5]。这些研究集中于软件密码系统，或在CPU架构条件下衡量密钥信息泄露。密码算法属于计算密集型应用，通常通过密码协处理器、IP核等硬件加速。硬件密码核被广泛应用于国防、金融、通讯等社会重要领域的高速加解密计算，其硬件体系结构（IP核）的安全实现对保障国防、通讯系统的安全性和可靠性具有重要的意义。密码算法核的安全性问题日益突出。硬件密码核实现区别于软件层次的实现主要在于：(1) 攻击者可通过调用硬件密码核加解密来精确测量加解密所需的时间，测量结果是周期精确的，可以消除测量误差对时序分析的影响。(2) 硬件架构实现的灵活性更高，设计描述方式和逻辑综合都对实现结果有更显著的影响，导致RSA架构的差异性较大，因此，RSA密码核中时间隐通道的不确定性因素更高。硬件时间隐通道问题受到了研究者的广泛关注，但是，尚无一种有效的方法来检测和消除隐通道。Ciet等利用并行的带有余数系统的RSA抵抗硬件时间隐通道的攻击[6]，Zhang等设计硬件语言强化硬件时间隐通道的非干扰特性[7]，Li等设计基于状态机和时间复用(TimeDivisionMultipleAccess，TDMA)的硬件语言迁移时间隐通道[8]，但未提供有效的检测方法。Oberg等提出利用门级信息流追踪(GateLevel InformationFlowTracking, GLIFT)方法检测时间隐通道[9]，能够实现不同模块间非干扰特性[10]隔离，却不能测量时间隐通道容量，无法量化分析硬件密码核时间隐通道脆弱性。通信中使用的信息论方法能有效衡量一个通信信道的带宽容量，量化分析信道传输能力。我们引入信息熵研究RSA硬件结构对时间隐通道的影响，即量化分析RSA硬件结构的时间隐通道的密钥信息泄露。量化分析能够更加准确地对硬件实现的安全性进行评估。例如，当硬件密码核只泄露密钥的某一位，其他密钥位不存在泄露时，虽然违反了非干扰特性，但是攻击者并不能破解完整的密钥，此时，硬件结构安全，无需降低性能，耗费资源进行改进和重新设计。另外，量化分析能够有效的区分不同硬件密码结构的信息泄露程度，显露密钥是否容易被破解，即使攻击者目前尚未找到高效的破解手段。量化分析亦可有效揭露硬件结构潜在的脆弱性，有利于设计者降低和消除硬件结构潜在的时间隐通道风险。最终目的是为硬件设计者提供一种可量化分析和推理RSA硬件时间隐通道信息泄露的手段，并在资源、性能允许情况下，提高RSA密码核设计的安全性。本文研究硬件RSA时间隐通道的意义不仅在于从理论和实验中验证具体的密码核时间隐通道的信息泄露，还着重于建立一个基于信息论熵的计算模型评估不同RSA密码核时间隐通道的容量。通过这种方法衡量硬件密码核时间隐通道的脆弱性，为RSA密码核的设计提供参考标准。论文主要贡献：（1）提出基于信息熵的攻击方法攻击RSA密码核，并实验验证信息熵的攻击方法优于统计方差方法；（2）引入信息熵理论量化分析RSA密码核时间隐通道，评估RSA硬件设计的密钥信息泄露，量化分析和推理RSA密码核改进架构对时间隐通道安全性的提升，并辅助攻击实验验证其有效性；（3）综合分析RSA信息熵指标与性能、硬件资源利用情况，指出设计者可依据信息熵指标完善RSA硬件设计，权衡时间隐通道安全性与性能、资源利用；（4）利用信息熵理论量化分析粗粒度离散化抵抗措施对时间隐通道的迁移作用。论文结构安排：第1、2节介绍硬件RSA时间隐通道的研究背景和相关工作。第3节描述RSA密码核时间隐通道威胁模型。第4节详细阐述了基于信息熵的时间隐通道量化分析模型和攻击模型。第5节展开实验并进行讨论。第6节简明分析本文研究工作与相关工作的区别和改进，指出本文工作贡献和意义。第7节总结论文并讨论，指出未来研究工作的重点。2相关工作2.1 面向信息论与系统设计的研究工作Clark等使用信息论量化分析带有循环语句的“While”程序的信息泄露，测量私有变量对公共变量的影响[11]；Malacaria和Heusser引入信息论量化分析方法评估C代码，表明了在信息泄露方面与Linux内核相关的系统软件存在脆弱性[12]；Newsome 等利用信息通道容量测量x86二进制程序中输入对输出的影响[13]；Doychev等测量主流密码算法（AES，eSTREAM组合）和排序算法（冒泡排序，插入排序，选择排序）二进制可执行程序在底层Cache中的信息泄露[14]；Standaert等使用信息论方法衡量AES密码实现的能量隐通道的信4 计算机学报 20??年息泄露[15]；Batina等利用互信息作为分类器实现对能量隐通道的攻击[16]。上述研究大多关注软件层次编程语言、操作系统内核、密码算法设计的量化安全分析，或强调密码算法软硬件实现的能量隐通道信息泄露，并未对软硬件实现的时间隐通道问题进行分析，也缺乏对不同软硬件设计时间隐通道安全性强弱的研究。2.2 面向软件时间隐通道分析的研究工作Bernstein对AES软件加密算法在Cache中的时间隐通道问题进行了研究，成功破解相关密钥①；Aciiçmez等利用条件分支预测实现对密码的破解[17,18]；Liu等对多核、多虚拟机环境下RSA密码算法（Square-and-Multiply算法和滑动窗口算法）在共享Cache中的时间隐通道信息泄露问题进行了探讨[19]。软件时间隐通道的问题多存在于系统的不确定性行为，如密码算法在CPU共享Cache中基于缓存命中/错失的时间差异，条件分支结构产生的指令跳转执行时间差异。Kopf 等利用信息论方法评估RSA算法信息泄露的上限，提出利用“bucket”策略减少信息泄露[20，21]和平衡系统性能，对AES算法在ARM架构Cache中信息泄露进行量化分析[22]；Askarov等对OpenSSL中的RSA密码算法进行时间隐通道的迁移和量化分析[23]；Wang等利用分区机制抵抗时间隐通道信息泄露[24]。这些研究中的量化分析方法和时间隐通道抵抗措施集中于CPU架构软件层次，并未深入探讨硬件结构设计变化对时间隐通道的影响，也未深入量化分析硬件时间隐通道抵抗措施的有效性。2.3 面向硬件时间隐通道分析的研究工作Ruby等对不同Cache硬件结构时间隐通道特性进行量化研究，但其侧重Cache设计对AES密码算法的影响[5]；Chen等在微核层次架构下探测共享处理器硬件中的隐通道信息泄露，共享硬件包括总线、高速缓存和整数除法器等[4]；Zhang等则关注硬件设计语言的时间隐通道问题[7]；Oberg和Kastner等提出的门级信息流追踪安全框架虽然能够检测硬件时间隐通道并隔离Cache、密码核、片上系统网络，但无法评估硬件设计时间隐通道容量的大小[9，25-26]，无法对不同的硬件设计脆弱性完成量化区分；Li等提出的基于TDMA的执行租① Bernstein D. Cache-timing attacks on AES.http://cr.yp.to/antiforgery/cachetiming-20050414.pdf,2005赁(Execution-Lease)策略能够有效排除时间隐通道，但使用的非干扰特性过于严苛，会对系统性能造成严重干扰[8]。因此，在保证系统时间隐通道安全性前提下，降低非干扰特性的严苛要求，不对系统性能造成过多约束和干扰，寻求一种有效检测和分析硬件密码核时间隐通道的方法是亟需解决的问题。3 RSA时间隐通道威胁模型在片上系统(System-On-Chip,SoC)中，专用硬件模块通常被集成到系统中作加速使用，通过原语被嵌入式系统核访问和调用，例如RSA、AES核作为ARM核的加解密协处理器。虽然独立的函数模块可有效加速嵌入式系统运算，但也带来了潜在的隐通道信息泄露问题，例如时间隐通道，攻击者通过测量硬件函数模块执行时间获取硬件函数的重要信息。例如图1所示，以机密性规则为例，高安全级别IP核和低安全级别IP核都可调用RSA密码核进行加解密，并观测到执行时间，当高安全级IP核调用密码核加解密时，低安全级IP核可通过请求调用密码核的延迟时钟周期数观测到高安全级IP核加解密原语的运行时间，进而推断高安全级别IP核的密钥信息。图1 SoC威胁模型示意图本文主要以RSA密码核为例研究时间隐通道密钥信息泄露问题，但研究方法可推广应用到其它受系统时钟驱动、与运行时间相关的硬件函数模块。RSA算法是公钥算法，其加密过程中的密钥是公开的，需要加密的信息是机密信息；而解密过程中的私钥是机密信息，需要解密的密文可以是公开的，可被攻击者获取。本文研究建立在RSA解密过程基础上，密钥是机密信息，使用非选择性密文攻击，密文数据随机输入。论文在线出版号No.73 毛保磊等：基于信息熵的RSA硬件时间隐通道信息泄露量化研究 5图2 硬件函数模块时序测量模型本文假设攻击者能够确定硬件函数模块的执行时间。硬件函数模块一般基于系统时钟驱动，其硬件接口中包含时序信号端口，攻击者依据时序信号可确定硬件函数操作的起止时钟，如依据图2中的开始和结束等时序信号。同时，假设攻击者可以访问硬件函数模块的输入和输出，例如，可以为图2中RSA密码核提供不同的密文、密钥等输入并获得结果输出。因此攻击者能够对给定输入数据的硬件函数模块的执行时间进行测量。本文实验建立在FPGA(FieldProgrammingGateArray) 平台基础上，对不同的RSA密码核实现进行评估，通过相应的辅助逻辑电路对RSA密码核时序信息处理并收集执行时间，例如图2所示，根据RSA密码核的开始、结束信号，截取开始结束信号之间的时钟周期的个数表示解密时间长短，对不同密文输入的执行时间进行周期精确的记录和分析。4 RSA时间隐通道分析与攻击方法4.1 RSA模幂算法和时间隐通道算法1. RSA模幂算法.输入：m,e,n(m为密文，e为私钥，n为模)输出：c=memodn1 LETs0=m,c0=12 FORi=0TOw-1:3 IF(bitiOFe)IS1THEN4 LETci+1=ci *si modn5 ELSE6 LETci+1=ci7 LETsi+1=si2modn8 ENDFOR9 RETURNcwRSA算法中的模乘可采用不同算法实现，如移位加算法（Blakley算法）等。模幂可采用Square-and-Multiply算法实现。模幂运算中的IF-ELSE条件分支语句存在延时差异是造成时间隐通道的根本原因，如算法1所示，由于语句3-4的模乘运算和语句5-6的赋值运算存在明显的时间差异导致不同的密钥会产生不同的解密运算时间。另外密文、密钥和模都参与模乘运算，对语句4和语句7中的模乘时间亦造成影响。上述两种因素是造成RSA密码算法时间隐通道信息泄露的重要因素。4.2 信息熵本文引入香农信息熵(ShannonEntropy)[27]理论进行时间隐通道的研究。香农将信息定义为离散随机事件出现的概率。假设x是采样空间X中的一个随机变量，p代表X空间中变量的概率分布密度函数，香农信息熵的定义为：(1)信息熵衡量系统不稳定性。方差是衡量数据集合中变量值偏离期望的程度的参数。当方差较小时，表示数据分布集中于均值附近，当方差较大时，则数据分布分散。Kocher在论文[1]中使用方差攻击时间隐通道。为了与本文中使用的信息熵作对比，在此给出方差的定义：x1,x2,…,xn是变量X的采样值，可得方差计算公式：(2)表示变量X的期望值。下面本文将描述信息熵衡量信息泄露的模型和相应的攻击模型，并在5.2节中通过实验比较分析基于信息熵和基于方差的攻击方法。4.3 时间隐通道量化分析模型针对某个具体RSA核，不同密文、密钥对解密消耗的系统时钟数不同，产生时间隐通道，泄露相关密钥信息；针对不同架构RSA核实现时，可能因为应用不同运算方法使得一个密码核的模乘运算比另一个核的模乘运算消耗时钟少，造成不同的密码核对同一个解密测试(相同的密文、密钥对)产生不同运算时间，导致不同密码核时间隐通道存在差异。基于观测到的事实我们引入定义1的描述。定义1 RSA硬件体系结构在密文、密钥对（密钥和模）等输入数据的作用下产生时间信息流。依据第3节中威胁模型和定义1建立信息泄露模型。以机密性为安全规则定义相关信息：高安全级别的信息包括密钥K；低安全级别的信息包括( ) ( )log ( )x XHX px pxÎ=-å12( ) ( )niiVARX x x== - åx6 计算机学报 20??年RSA核的解密时间T，因为解密时间T是攻击者可以观测的。RSA硬件密码核时间隐通道信息泄露的特征函数用F表示，密码核时间隐通道会导致密钥K的信息流入到低安全域中。其特征反映相应RSA密码核的时间隐通道的特性。依据定义1以数学形式抽象完整描述RSA信息泄露如公式（3）所示，表示密钥K，密文C和模M的信息通过函数F流入到时间域T中：T↩F(K;C;M) (3)RSA是公钥算法，模M的值是公开的，并与私钥K成对出现，可将模型简化为：T↩F(K;C) (4)由于密文和密钥分布是离散的，本文使用离散概率密度函数来刻画RSA密码核关于密钥K的时间隐通道。假设当密文和密钥确定时(K=k，C=c)，T=t是RSA核关于密钥信息泄露的一次采样，即一条密文模幂时间是攻击者对密钥的一次时间隐通道的采样。那么，刻画时间隐通道特征函数F的泄露函数L（K,C）可定义为：(5)若能够采集所有的实验数据（密文、密钥、时间T能够遍历其空间中所有值），理论上可以构造完整精确的泄露函数L。但实际应用中只能选择适当数目的测试向量（一定数目的密文和密钥）来近似估计函数L。本文将此估计函数表示为。基于估计函数的假设，若密文数目固定（例如指定5000条密文），随着采样样本数目的增加，解密时间的概率密度函数将会随着采样样本的变化而变化，并显现密钥的特征。本文中将其抽象为时间隐通道，并利用信息熵的概念量化通道容量。将公式(5)代入公式(1)，获得相应信息熵计算公式：(6)4.4 时间隐通道攻击模型Kocher在建立RSA时间隐通道攻击方案时假设每个密钥位的处理时间相互独立[1]。基于我们对论文[1]中描述的方差攻击过程的观测，当密钥位数较大时，每个密钥位攻击成功率之间的影响微弱。例如，一个RSA密码核密钥是W位，前s位（s<<W）密钥位攻击成功率对后面密钥位攻击成功率影响很小。本文攻击模型也遵从同样的前提假设。假设1当密钥位数较大时处理每个密钥位的时间是相互独立的。本文以Kocher的攻击方案为基础，描述基于信息熵的攻击方法。当攻击者从最低位LSB(LeastSignificantBit) 开始攻击RSA核时，会逐渐猜测出各个密钥位的值，直到密钥最高位MSB(MostSignificantBit) 被破解。假设正确的密钥的概率分布密度获得的信息熵为H，由公式(6)计算获得；由已猜测密钥位及其处理时间产生的概率分布密度获得的信息熵表示为Hs，表示前s位已猜测密钥位的处理时间，则：(7)考虑到单个密钥位处理时间可近似相互独立，将未猜测密钥位的值及其处理时间也描述为一个概率分布密度函数并以熵∆H的形式来表述其特征，表示余下未猜测密钥位的运算时间，则：(8)随着密钥位被逐渐破解，熵∆H逐渐减小，如果所有密钥比特位都猜测正确，∆H最终减少至0。但如果存在密钥比特位猜测错误，∆H不能减少至0。基于此事实分析，我们提出定理1。定理1 猜测正确的密钥位将使∆H减小，并逐渐减少至0。依据定理1，当Hs趋近于H时，∆H趋近于0，可得：(9)本文采用的攻击步骤算法流程如下：过程1.信息熵攻击过程步骤1：假设T表示使用正确密钥处理n条密文消耗时间的向量，Tj表示使用正确密钥处理第j条密文的时间，则：(10)步骤2：假设前s-1位密钥位已被猜出，需要猜测第s位密钥位时：处理第j条密文，当密钥第s位为0时，密钥前s位处理时间是 ，当密钥第s位是1时，其前s位处理时间是 。可计算：(11)(12)考虑到共有n条密文，则：0ˆ ˆ( 0) j j sj s T T T k - D = =1ˆ ˆ( 1) j j sj s T T T k - D = =,( , ) { | , }c Ck KLKC T t CK pÎ Î= =1 2 { , ,..., } n TT T = T, 0 Hs H HH H Hs® D ®D µ -当 时( ) ( )log ( )k K c CHT pT t pT tÎ Î=- = = å，L%ˆ0 ( ) j s s T k=ˆ1 ( ) s sj T k =ˆ ˆ( ) ( )log ( ) s s HsT pT T pT T =- = = åˆ ˆ( ) ( )log ( ) HT pT T pT T D =- =D =D åˆs TL%论文在线出版号No.73 毛保磊等：基于信息熵的RSA硬件时间隐通道信息泄露量化研究 7(13)(14)步骤3：依据定理1和公式(9)，∆H越小，则该密钥位越可能被猜测正确。若 的熵 比 的熵小，则密钥s位的值为0；反之，密钥s位值为1。步骤4：重复步骤2、3，直至攻击至密钥最高位。另外本文直接测量系统时钟周期数，已经内在排除了时间测量误差引起的噪声。影响密钥破解的因素集中于未知密钥位引起的时间变化，这也是如果所有密钥位都猜测正确，熵∆H会减少至0的原因。本文将在实验部分详细描述信息熵在RSA时间隐通道攻击方面较方差具备更好的特性。5实验结果分析和讨论5.1节简要介绍实验设计框架。为检验硬件RSA密码核时间隐通道安全性和攻击模型的有效性，5.2节利用信息熵攻击RSA密码核，并实验验证基于信息熵的方法优于基于方差的攻击方法。为验证量化分析模型的有效性，5.3节首先利用信息熵量化分析同一密码核不同密钥的信息泄露；然后量化不同RSA架构的信息泄露，并辅助以攻击实验进行佐证；最后综合评估RSA密码核设计复杂度。5.4节利用信息熵量化分析时间隐通道抵抗措施对RSA密码核时间隐通道信息泄露的迁移作用。实验结果表明了信息熵量化分析对RSA密码核安全设计工作的改进和意义。设计者可依据信息熵指标完善RSA硬件安全设计。5.1 实验设计为了对RSA密码核中时间隐通道进行评估，本文使用XilinxML605评估板构建硬件测试平台。整个实验环境由两部分组成：FPGA端和主机端测试程序。具体框架如图3所示。FPGA端程序包括可综合的RSA设计和相应的控制逻辑，主要完成RSA计算时间的测量、存储和传输。RSA核选用两种不同方案产生。第一种方案依据4.1节中RSA密码算法的时间隐通道特征，设计产生五种不同的RSA架构，分别检验模乘器时间差异和条件分支语句时间差异对时间隐通道特征的影响；第二种方案采取时间离散化抵抗措施产生五种不同粒度的RSA时间隐通道的迁移设计。图3 RSA时间隐通道测试框架主机测试程序主要完成两项功能：第一、向FPGA发送测试向量（密文、密钥、模），从FPGA读取所测量的RSA运算时间；第二、对相应RSA核进行攻击和量化分析。主机端程序模拟片上系统中可以访问密码核的处理器运算。5.1.1 基于XilinxML605的板级实现依据第3节中时序测量模型的描述，我们在FPGA端设计并实现对RSA解密时间的记录、保存和传输。RSA密码核的控制逻辑包括控制命令状态机模块，RSA时序测量包模块和通信接口模块。控制命令状态机完成通信接口模块提供的命令和数据的编解码，为RSA密码核提供密文、密钥和模值信息。当控制命令状态机完成对密文、密钥和模的解析转化后，若遇到主机端来的开始解密命令，则会通知RSA时序测量包启动RSA核开始进行第一条密文的解密。由于量化信息泄露的过程和密钥攻击过程都需要大量的密文，实验中利用块存储器来存储数据，控制命令状态机同时维护块存储器的数据存取。RSA时序测量包模块主要完成每个RSA解密操作的时间记录和控制，例如控制RSA解密操作启动和停止的时间，需要的解密操作个数（即解密多少条密文）以及每个解密操作的时钟周期数的记录存储等。通信接口模块完成FPGA端RSA时间数据的发送和主机端发来的命令和数据的接收。这些命令和数据经过控制命令状态机进行编解码，其具体的命令和数据格式定义如表1所示。由于解密速度可能快于通信传输速度，为防止时间数据被覆盖而导致数据丢失，使用Xilinx的FIFO(First-In-First-Out)IP核以缓存数据。表1 控制命令和数据命令格式定义命令类型 命令编码 数据类型 数据名称开始命令 0xAA0 01 02 0 , ,...,ˆ ˆ ˆ ˆ{ } n T T T D =D D D T1 11 12 1 , ,...,ˆ ˆ ˆ ˆ{ } n T T T D =D D D T0ˆ( ) H D DT 1ˆ( ) H D DT 1ˆDT 0ˆDT8 计算机学报 20??年结束命令 0x00数据命令 0x05 0xA5 密文数据命令 0x05 0x55 密钥数据命令 0x05 0x5A 模5.1.2 主机端实现本文使用Python脚本实现主机端主程序设计，包括利用OpenSSL0.9.8h程序产生测试向量（RSA密钥和模），利用Python的内置随机函数库产生随机密文数据，使用Python的科学计算包Numpy进行统计方差和信息熵的计算，利用Python的PySerial构建通信接口模块。主机端程序主要完成两项计算任务：第一，给定密钥情况下，采集多条密文的完整解密时间，进而利用4.3节信息熵量化方法测量RSA密码核的信息泄露；第二，持续向FPGA发送测试向量，收集相应的时间信息进行计算，采用4.4节中的攻击步骤（过程1）完成攻击（Kocher采用基于统计方差的方法[1]，本文使用信息熵的攻击方法）。5.2 利用信息熵攻击RSA密码核在此实验中，本节对Blakley算法实现的密码核进行攻击，使用5000个密文测试50个不同密钥对。如图4所示为使用方差、信息熵攻击RSA密码核的成功率。基于对攻击过程的观察，随着猜测密钥位的逐渐增加，∆H呈现逐渐减小的趋势，假设猜测第一位之后，∆H值为∆H1，猜测第二位之后∆H值为∆H2，…，可得：(15)当∇Hi值较大时，第i位密钥位猜测正确的可能性就很高，而当∇Hi很小时，通常意味着第i位密钥位猜测错误。为衡量对每个密钥位猜测正确性的确信度，本文首先引入方差和熵的猜测信心域参数%V和%H：图4 使用方差，信息熵攻击RSA结果(16)(17)将信心域参数值平均分成10个区间，即[50%-55%]，[55%-60%]，…，[95%-100%]。统计对应区间下，一共存在的密钥位个数N，以及猜测正确密钥位的个数Nr。获取确信度的计算公式：(18)绘制相关曲线如图5所示，例如，[55%-60%]区间中的Entropy-Local的节点表示由∇Hi的值获得的%H值在区间[55%-60%]中，则攻击者有81%的确信度认为此密钥位的猜测是正确的。而Variance-Local在[55%-60%]区间中的确信度几乎为0。当Entropy-Global信息熵的信心域参数达到[65%-70%]时，其猜测正确率确信度达到100%，而方差Variance-Global 的信心域参数需达到[75%-80%]，其猜测正确率确信度达到100%。局部(Local)的max(∇Hi)中的∇Hi本文使用测量的单个指定密钥的所有密钥位∇Hi；全局(Global)的max(∇Hi)中的∇Hi文中使用测量的100个密钥所有密钥位的∇Hi。方差分析亦然。由图4实验结果，基于熵的攻击方法与基于方差的攻击方法具备相当的密钥破解能力，图5实验结果表明基于熵的攻击方法在全局、局部猜测信心域参数和猜测正确率确信度方面较方差具备更好的性能。图4结果的方差-信息熵曲线表明同时利用信息熵和方差攻击相应密钥，能显著提高密钥的破解成功率。1% * *100%50%2 ( )iiHHmax HÑ= +Ñ1% * *100%50%2 ( )iiVarVmax VarÑ= +Ñ1 i i i H H H+ Ñ =D -D*100%NrDN=论文在线出版号No.73 毛保磊等：基于信息熵的RSA硬件时间隐通道信息泄露量化研究 9图5 方差，信息熵攻击成功率信心参数5.3 信息熵量化RSA密码核信息泄露应用分析5.3.1 信息熵量化RSA密码核不同密钥信息泄露图6 信息熵量化RSA信息泄露和攻击结果本节实验使用Blakley算法RSA核，随机测试30个不同的密钥。为更好佐证密钥信息泄露，实验对相应的密钥进行实际攻击。使用4.3节中的信息熵量化分析方法衡量密钥信息的泄露，并利用4.4节中的攻击方法（过程1）攻击对应的30个密钥，结果如图6所示。实验结果表明，由信息熵量化的信息泄露能够较好的反映不同密钥导致的时间隐通道泄露。当信息熵较大时，攻击成功率明显增加；而信息熵较小时攻击成功率则呈现减小趋势。5.3.2 信息熵量化不同RSA密码核信息泄露本节实验使用五个不同的RSA密码核，其中三个采用不同模乘算法，分别是Blakley算法[28]、Barrett算法[29]、Montgomery算法[30]。另外一种设计采用Power-Ladder模幂算法[31]，是基本模幂算法的一种改进设计用以平衡条件分支语句执行时间。第五种设计是一个并行的RSA密码核①（两个模乘运算器并行执行，后文以Parallel设计表示）。①http://opencores.org/project,basicrsa由于前四个密码核结构中的模乘和模平方操作使用同一个模乘器，模乘和模平方操作在时序上交替进行。而Parallel设计利用两个模乘器，模乘和模平方可以并行执行。图7 五种RSA设计信息熵和攻击结果同样利用4.3节中的信息熵量化密钥信息的泄露，利用4.4节中的攻击方法（过程1）攻击相应RSA密码核，结果如图7所示。Blakley算法密码核是五种设计中攻击成功率最高的，其信息熵也是五种设计中最大的。Barrett算法设计的攻击成功率和信息熵比Blakley设计都要减小。Power-Ladder设计与Barrett设计攻击成功率和信息熵相近，Power-Ladder设计信息熵和攻击成功率较Blakley设计显著减小。而Montgomery设计和Parallel设计则是五种设计中时间隐通道安全性最高的，二者的攻击成功率相同，但是Parallel设计的信息熵较Montgomery设计的信息熵减小。具体分析五种RSA密码核结构，Blakley设计解密时间受到密钥和模乘运算的影响变化很大，实现Blakley算法的模乘器对每个密钥位的处理时间随密文变化显著。而Barrett设计在实现模乘器时首先进行乘法运算，然后进行模运算，但所用的乘法器运算时间固定，只有做模运算时才会有时间变化，其模乘时间随密文变化较小。因此Barrett设计信息熵和攻击成功率较Blakley设计减小。Power-Ladder设计将模平方操作移入条件分支语句内，并改进算法流程，使每次密钥位的处理都要实施模乘和模平方的计算，有效减小了因为密钥位值的不同引起的IF-ELSE条件分支语句的延时差异。如图7所示，其时间隐通道安全性获得提高。Montgomery设计的模乘的时间只随着模变化，对不同密文的解密时间是不变的，只有当密钥发生变化时，解密时间才会改变。而Parallel设计利用算10 计算机学报 20??年法1模幂算法的特殊性（在同一个密钥位的处理时间范围内，模乘和模平方运算之间不存在数据依赖关系；但在相邻密钥位处理时，模乘和模平方运算存在数据依赖关系）和FPGA资源丰富的特点（可在空间上增加模乘器数量）实现模乘器的并行性运算，而做模平方运算的模乘器时间总是多于或者等于做模乘运算的模乘器时间，解密时间几乎完全由密钥的最高位位置决定，解密时间受密文影响变化微弱。Montgomery设计和Parallel设计时间隐通道特征的共同之处在于二者的解密时间都（几乎）不受密文的影响。不同之处在于，Montgomery设计的解密时间会随着密钥的变化而变化，不仅受到密钥最高位位置的影响，还受到其他密钥位的影响；而Parallel设计的解密时间受到密钥最高位位置影响显著。在攻击RSA核时，主要利用不同密文解密的时间差异获得的信息熵破解密钥，因此，若攻击Montgomery设计，当猜测密钥的密钥位值给定时，所有密文解密时间都相同。此时攻击过程1中步骤3密钥位0值获得的熵和密钥位1值的熵都等于0，攻击者无法判断密钥位取0值或取1值；当攻击Parallel设计时，所有密钥位猜测的值都为1。基于熵和方差的攻击方法对这两种设计是失效的。在量化分析RSA核时，信息熵量化分析的计算包含了不同密钥引起的解密时间的变化，导致Parallel设计的信息熵较Montgomery设计减小，而两种设计的信息熵都不会减小为0。但Montgomery设计的密钥依旧面临被破解的威胁。例如，使用暴力破解方法找到猜测密钥，使其解密时间与正确密钥解密时间相同即可。而Parallel设计即使使用暴力破解方法依然无法利用时间隐通道破解完整的密钥，因其解密时间几乎完全由密钥的最高位MSB位置确定，确实只有密钥最高位才能被准确破解。图7实验结果表明，信息熵量化分析结果完全符合相关RSA设计的时间隐通道密钥信息泄露的特征：Barrett设计和Montgomery设计通过减小或消除模乘器运行时间的差异以减少时间隐通道信息泄露；Power-Ladder设计通过减小条件分支语句执行时间差异以减少密钥信息泄露；Parallel设计通过增加并行性操作减少信息泄露。实验结果亦显示即使在已知攻击方法不能破解相关密钥情况下，信息熵量化分析亦可揭露RSA密码核潜在的密钥信息泄露的风险(如Montgomery设计)。信息熵可有效量化分析RSA改进设计对时间隐通道的影响。5.3.3 权衡信息熵与性能、资源利用率之间的关系上述实验结果显示信息熵可以量化不同密钥信息泄露的程度和不同RSA密码核密钥信息泄露程度，信息熵可以作为量化RSA密码核时间隐通道的指标。为了更加完整评估密码核设计，本文利用XilinxISE综合相关设计，获得相应的资源利用状况，如表2所示。并收集各个密码核的平均解密时间，如表3所示。实验结果显示，Parallel设计性能最高，平均每个解密操作需要21896个时钟周期，但是由于使用两个模乘器，消耗板上资源接近Blakley设计的两倍。Blakley设计消耗资源最少，但是解密速度减小。Barrett设计消耗最多的资源却只达到Blakley设计的速度。Power-Ladder设计消耗资源比Blakley设计较多，性能却远低于Blakley设计，仅达到Blakley设计的2/3。Montgomery设计资源利用过多而性能只达到Blakley设计的一半。我们将时间隐通道安全性纳入评估内容，并以Blakley密码算法核为参照。Power-Ladder设计仅在损失性能情况下降低RSA密码核信息泄露。Barrett设计同时损失资源与性能降低RSA时间隐通道信息泄露。Montgomery设计在损失性能和资源的条件下获得了隐通道的安全性。而Parallel设计则在只损失硬件资源的条件下，达到了性能和时间隐通道安全性的提高。信息熵量化分析模型的指标可为设计者提供时间隐通道安全性的度量标准，如同资源利用率量化逻辑资源使用情况、时钟周期数量化加解密速度的性能。设计者可根据信息熵指标评价或改善RSA密码核设计，实现资源利用、性能和时间隐通道安全性最佳权衡和取舍。表2 FPGA资源利用情况LUTSliceregisterDSP48EOccupiedSlicesLUT-FFpairsBlakley 1683 1710 0 707 2099Barrett 11944 5548 340 3511 13327Power-Ladder 2400 1949 0 685 2524Montgomery 5969 4882 0 1915 6325Parallel 3484 1803 0 1156 3731表3 RSA密码核平均运行时间不同设计 平均时钟周期数Blakley设计 46292Barrett 设计 46814Power-Ladder设计 62438论文在线出版号No.73 毛保磊等：基于信息熵的RSA硬件时间隐通道信息泄露量化研究 11Montgomery设计 95383Parallel设计 218965.4 RSA密码核时间隐通道抵抗措施下信息熵量化应用分析5.3节实验利用信息熵量化分析不同RSA硬件密码核结构的时间隐通道。实验结果表明，在没有任何RSA时间隐通道抵抗措施的情况下，信息熵能够有效量化分析硬件架构对时间隐通道的影响。本节将引入时间隐通道抵抗措施，使用信息熵量化分析方法研究时间隐通道迁移设计的信息泄露。RSA时间隐通道表现为密码核模幂运算的时间差异。一种通用而简易的抵抗措施是在RSA模幂运算末尾引入空操作，增加单个模幂运算的时间延迟，减少甚至消除不同模幂操作的执行时间差异。文献[20]中提出一种粗粒度离散化的添加空操作的时间延迟方案：例如，将原来以一个时钟周期进行计数的时间离散化为使用10个或者100个时钟周期进行阶梯式计数的时间。例如，当使用100个时钟周期进行阶梯计数时，原始模幂时间是46187个时钟周期，而加入空操作离散化后的模幂时间为46200。推广到极端情况，所有的模幂时间都采用最大值，即所有模幂运算时间都为恒定值，则完全消除时间隐通道，但是因为时间都采用最大值，模幂运算效率低。本节采用Blakley设计为基准RSA密码核完成相关时间隐通道抵抗措施的实验。抵抗措施采用粗粒度离散化模幂时间延迟方法，在基准设计的基础上再增加五种不同粒度的离散化设计：Discrete50设计、Discrete75设计、Discrete100设计和Discrete150设计分别采用的时间延迟阶梯间隔为50、75、100和150个时钟周期，Constant设计则将所有模幂运算时间延迟到最大值。然后利用4.3节中的信息熵量化分析方法测量密钥信息泄露，利用4.4节中的攻击过程1攻击相应RSA密码核，结果如图8所示。图8 隐通道抵抗措施下RSA信息熵和攻击结果图8实验结果显示，采用粗粒度离散化方案，随着离散化的时间间隔增大，信息熵和攻击成功率呈现下降的趋势。Constant设计中信息熵结果显示为0，表征其不存在时间隐通道。实验结果表明信息熵可有效量化分析时间隐通道抵抗措施减少时间侧信道信息泄露的作用。同时在表4中列出相应密码核平均运行时间进行简要分析：Discrete50设计性能略微减小，但时间隐通道安全性获得改善；Discrete100 设计和Discrete150 设计性能较Discrete50和Discrete75设计略有减小，而时间隐通道安全性获得大幅提高。Constant设计是粗粒度离散化设计中性能最低但安全度最高的，实现了非干扰特性。表4 RSA密码核平均运行时间不同设计 平均时钟周期数Blakley设计 46292Discrete50设计 46350Discrete75设计 46375Discrete100设计 46400Discrete150设计 46450Constant设计 517296与硬件时间隐通道工作的对比为了更加清晰和直观的对比相关工作，本文从实验场景，分析方法和体系结构层次等方面进行了概括和分析，如表5所示。Myers等应用信息流分析方法从硬件设计语言迁移时间隐通道[7]。Ruby等利用信息论方法量化分析和验证改进的Cache设计减少AES密钥信息泄露[5]。Chen等对共享硬件结构(除法器、高速缓存、总线)进行事件相关行分析以检测隐通道[4]。12 计算机学报 20??年与本文工作最密切的是能够检测所有硬件设计时间隐通道的门级信息流追踪的分析方法。因为本文除Constant设计外其余所有RSA设计都存在时间隐通道问题，能够被GLIFT全部检出。但是本文提出的分析方法能够有效量化鉴别相关设计的时间隐通道的危害大小，可以更加准确有效的辅助设计者在利用门级信息流分析技术基础上实现加解密硬件关于时间隐通道的安全设计。表5 本文与相关工作对比目标/实验场景 分析精度/方法 体系结构层次Myers[7]Language 设计 信息流分析 硬件语言Chen[4]Bus，Divider，Cache隐通道检测事件相关性分析 微体系架构Ruby[5]Cache设计 量化分析 微体系架构GLIFT[9,25]时序逻辑电路 信息流定性分析 门级电路本文 协处理器RSA核 量化分析 SoC结构7结束语和讨论本文研究了硬件RSA解密实现中的时间隐通道安全性问题，阐述了基于信息熵的方法在量化分析RSA硬件密码核时间隐通道中的应用，通过对不同RSA硬件结构进行量化分析和攻击测试，实验验证了信息熵量化分析方法的有效性。本文所提方法为RSA密码核时间隐通道的评估提供了一种有效的量化分析的理论依据和测试手段。本文引入信息熵的攻击方法攻击硬件RSA时间隐通道，实验结果表明信息熵的攻击方法要优于基于方差的攻击方法。同时利用信息熵和方差的攻击方法能显著提高攻击的成功率。虽然攻击结果的成功率和量化分析结果都能够对硬件RSA的时间隐通道特征进行一定程度的定量化描述，但是攻击过程比量化分析过程消耗的时间有两个数量级的差异，量化分析方法更具效率。同时，信息熵量化分析方法能够有效的揭露RSA密码核潜在的时间隐通道风险（已有攻击方法无效时），并为非干扰特性（信息熵为0）提供辅助的理论性证明，量化分析方法更具效果。通过RSA密码核性能、资源利用和时间隐通道安全性关系的分析，设计者可依据信息熵指标改善RSA密码核设计，权衡和取舍密码核设计性能、资源利用和时间隐通道安全性。本文RSA密码核只涉及基本RSA设计，近些年提出的高级模幂算法实现，如基于滑动窗口的RSA算法，基于中国剩余定理的RSA算法，基于掩码的RSA设计等需要采取不同于本文的攻击方案，虽然可以应用信息熵进行量化分析，但是由于现有攻击方案有限而且标准不统一[2,3,32]，其攻击成功率无法与本文中的攻击成功率（攻击难易程度）进行统一的对比。即不同的攻击方案只针对特定一种或者几种RSA算法设计有效，并有效利用相应RSA设计的时间隐通道特征破解其密钥。如何将基于信息熵的量化分析方法推广应用到高级模幂算法，并建立衡量攻击难易程度的统一的攻击框架以验证量化分析的有效性是后续研究的一个重要探索方向。同时，本文的量化分析模型虽然只应用到RSA密码核设计，但是对其他涉及时间隐通道问题的算法如椭圆曲线密码算法、数字签名标准（DigitalSignatureStandard,DSS）等同样具有借鉴的意义，也是未来研究工作的重要方向。致 谢 衷心感谢审稿专家和编辑部老师提出的宝贵意见和建议。同时衷心感谢加州大学圣迭戈分校计算机科学与工程系RyanKastner教授关于实验设计、分析的讨论和建议。参考文献[1] Kocher PC. Timingattacks onimplementations of Diffie-Hellman,RSA, DSS, andothersystems//KoblitzNeds.AdvancesinCryptology-CRYPTO’96.Heidelberg，Germany:Springer,1996:104-113[2] SchindlerW.Atimingattackagainst RSAwiththechineseremaindertheorem//Koç Ç K, Paar C eds. Cryptographic Hardware andEmbedded Systems-CHES 2000. Heidelberg，Germany: Springer,2000:109-124[3] BrumleyD, BonehD. Remotetimingattacksarepractical. ComputerNetworks,2005,48(5):701–716[4] Chen J, Venkataramani G. Cc-hunter: Uncovering covert timingchannels on shared processor hardware//Proceedings of the 47thAnnual IEEE/ACMInternational Symposiumon Microarchitecture.Cambridge,UK,2014:216-228[5] ZhangT, LeeRB. Newmodelsofcachearchitecturescharacterizinginformationleakagefromcachesidechannels//Proceedingsofthe30thAnnual Computer SecurityApplications Conference. NewOrleans,USA,2014:96-105[6] Ciet M, NeveM, PeetersE, et al. Parallel FPGAimplementationofRSA with residue number systems-can side-channel threats beavoided?//Proceedingsofthe2003IEEE46thMidwest SymposiumonCircuitsandSystems.Cairo,Egypt,2003:806-810[7] ZhangD, WangY, SuhGE, et al. Ahardwaredesignlanguagefortiming-sensitive information-flowsecurity//Proceedings of the 20thACM International Conference on Architectural Support forProgramming Languages and Operating Systems(ASPLOS2015).论文在线出版号No.73 毛保磊等：基于信息熵的RSA硬件时间隐通道信息泄露量化研究 13Istanbul,Turkey,2015:503-516[8] Li X, Kashyap V, Oberg J K, et al. Sapper: Alanguage forhardware-level security policy enforcement. ACM SIGARCHComputerArchitectureNews,2014,42(1):97-112[9] ObergJ, Meiklejohn S, SherwoodT, et al. Leveraginggate-levelpropertiestoidentifyhardwaretimingchannels. IEEETransactionsonComputer-Aided Design of Integrated Circuits and Systems, 2014,33(9):1288-1301[10] GoguenJA, Meseguer J. Securitypolicies andsecuritymodels//Proceedings of the1982IEEESymposiumonSecurityandPrivacy.Oakland,USA,1982:11-11[11] ClarkD, Hunt S, MalacariaP. Quantifiedinterferencefor awhilelanguage. Electronic Notes inTheoretical Computer Science, 2005,112:149-166[12] Heusser J, and Malacaria P. Quantifying information leaks insoftware//Proceedings of the 26th Annual Computer SecurityApplicationsConference.Austin,USA,2010:261–269[13] NewsomeJ, McCamant S, SongD. Measuringchannel capacitytodistinguish undue influence//Proceedings of the ACMSIGPLANFourth Workshop on Programming Languages and Analysis forSecurity(PLAS’2009).Dublin,Ireland,2009:73–85[14] DoychevG, KöpfB, MauborgneL, et al. CacheAudit: atool forthestatic analysis of cache side channels. ACMTransactions onInformationandSystemSecurity(TISSEC),2015,18(1):4[15] Standaert FX, MalkinTG, YungM. Aunifiedframeworkfor theanalysisofside-channel keyrecoveryattacks//JouxAeds.AdvancesinCryptology-EUROCRYPT2009. Heidelberg，Germany: Springer,2009:443-461[16] BatinaL, GierlichsB, ProuffE, et al.Mutual informationanalysis: acomprehensivestudy.JournalofCryptology,2011,24(2):269–291[17] AciiçmezO, KoçÇK, Seifert JP. Onthepower of simplebranchprediction analysis//Proceedings of the 2nd ACMSymposiumonInformation, Computer and Communications Security (ASIACCS).Singapore,2007:312-320[18] AciiçmezO, KoçÇK, Seifert JP. Predictingsecret keysviabranchprediction//Abe M eds. Topics in Cryptology-CT-RSA 2007.Heidelberg，Germany:Springer,2007:225-242[19] LiuF,YaromY,GeQ, etal. Last-level cacheside-channel attacksarepractical//Proceedings of the2015IEEESymposiumonSecurityandPrivacy.SanJose,USA,2015:605-622[20] KöpfB,DürmuthM.Aprovablysecureandefficient countermeasureagainst timing attacks//Proceedings of the 22nd IEEE ComputerSecurityFoundationsSymposium.PortJefferson,USA,2009:324-335[21] Köpf B, Basin D. An information-theoretic model for adaptiveside-channel attacks//Proceedings of the 14th ACMconference onComputer and communications security(CCS’07). Alexandria, USA,2007:286-296[22] KöpfB, MauborgneL, OchoaM.Automaticquantificationofcacheside-channels//Proceedings of the 24th international conference onComputerAidedVerification.Berkeley,USA,2012:564-580[23] AskarovA, ZhangD, MyersAC. Predictiveblack-boxmitigationoftiming channels//Proceedings of the 17th ACMconference onComputer and Communications Security. Chicago, USA, 2010:297-307[24] WangY, FerraiuoloA, ZhangD, et al. SecDCP: secure dynamiccachepartitioningfor efficient timingchannel protection//Proceedingsof the 53rdAnnual DesignAutomation Conference(DAC). Austin,USA,2016:74[25] HuW,MuD,ObergJ, et al.Gate-level informationflowtrackingforsecurity lattices. ACMTransactions on Design Automation ofElectronicSystems(TODAES),2014,20(1):2[26] Kastner R, HuW, Althoff A. Quantifyinghardwaresecurityusingjoint information flowanalysis//Proceedings of the 2016 Design,Automation &Test in Europe Conference &Exhibition (DATE).Dresden,Germany,2016:1523-1528[27] Shannon CE. Amathematical theory of communication. ACMSIGMOBILEMobileComputingandCommunicationsReview, 2001,5(1):3-55[28] BlakelyGR. Acomputer algorithmfor calculatingtheproductABmoduloM.IEEETransactionsonComputers,1983,32(5):497-500[29] Barrett P. ImplementingtheRivest Shamir andAdlemanpublickeyencryptionalgorithmonastandarddigital signal processor//OdlyzkoAMeds.AdvancesinCryptology-CRYPTO’86. Heidelberg，Germany:Springer,1986:311-323[30] Montgomery PL. Modular multiplication without trial division,Mathematicsofcomputation,1985,44(170):519-521[31] JoyeM, YenSM. TheMontgomerypoweringladder//Kaliski BS,Koç ÇK, Paar Ceds. Cryptographic Hardware and EmbeddedSystems.Heidelberg:Springer,2002:291-302[32] SchindlerW. Exclusiveexponent blindingisnot enoughtopreventany timing attack on RSA. Journal of Cryptographic Engineering,2016,6(2):101-119MaoBao-lei, bornin1987, Ph.D.candidate. His current researchinterests includehardwaresecurityand information flowanalysis ofhardwaredesign.HuWei, born in1982, Ph.D.，Associate Professor. His currentresearchinterestsincludehardwaresecurity, logic synthesis and optimization, reconfigurablecomputingandembeddedsystemsdesign.ZhangHui-xiang, bornin1981, Ph.D.，AssociateProfessor.His current research interests include information security,patternrecognitionandapplications.MuDe-jun, born in 1963, Ph.D.，Professor. His currentresearch interests include information security and controlsystemdesign.Tai Yu, bornin1982, Ph.D. candidate. His current researchinterests include hardware security, logic synthesis andoptimization.HongLiang, bornin1979, Ph.D.，AssociateProfessor. His14 计算机学报 20??年current research interests include information security and embeddedsystemapplications.BackgroundRuntime for computing cryptographic functions canreveal asignificant amount of informationabout secret data.Attackers can retrieve the secret key by observingthroughruntime measurements. Researchers look into the timingchannelsintwodifferent directions. Onewayistodetect thetiming channel by attacking the design. Another moreimportantbranchaimstoreducesuchleakageorprotectitfromattacks.Most researchworkfocusesonprogramminglanguageand mitigation algorithmdesign. Designers usually ignoretimingchannelduringhardwarearchitectureimplementation.Ourresearchgrouphasbeenfocusingonbuildingsecurehardware architectures recent years using information flowtrackingmethod.Althoughgatelevelinformationflowtracking(GLIFT) is efficient for detecting timing channel leakagequalitatively, it is not able to quantify howmuch thetiming-based information flows is if any. We propose tomeasure this timing channel leakage using informationtheoreticmethodstoprovidecluesof securityabout differenthardwareimplementations.This paper focuses ontimingchannel leakage of RSAcryptographiccores.Wemeasurethistiming-basedinformationflowsleakageusingentropytheoryandverifytheeffectivenessof our proposedmeasurement byattackingthecorrespondingRSAarchitectures. Thisinitial workindicatesthat informationtheoreticmethodcanprovideakindoftimingchannel securityguarantee, whichwillmotivatetheemployment ofinformationtheoreticmeasuresforsecurehardwaredesign.Our previous workoninformationflowsecurityhavebeenpublishedinElectronicDesignAutomation(EDA) andinformationsecurityjournals andconferences suchas IEEETransactionsonComputer-AidedDesignof IntegratedCircuitsandSystems, IEEETransactionsonInformationForensicsandSecurity, ACM Transactions on Design Automation ofElectronic Systems, Design Automation Conference, DesignAutomation &Test in Europe Conference &Exhibition,International ConferenceonComputer-AidedDesignandIETInformationSecurity,etc.ThisworkwassupportedbytheNationalNaturalScienceFoundation of China under grant 61303224, the NationalNatural ScienceFoundationof Chinaunder grant 61672433,the China Postdoctoral Science Foundation under grant2013M532081, andtheFundamental ResearchFunds for theCentralUniversitiesundergrant3102016JKBJJGZ07.