一种改进的aes和clexia序列驱动攻击方法

一种改进的aes和clexia序列驱动攻击方法

1旁路攻击安全性分析传统的密码分析认为密码算法是一个黑盒。密码算法的安全性完全取决于执行的数学函数和密钥的安全性。线性和微分分析结合了明清文本、消息和算法结构的密钥。随着密码设计复杂度和密钥长度的增加,其在设计之初就经受了大量数学分析考验,安全性得到了极大的提高,传统的线性和差分分析已经很难实现密码破解。然而密码算法实现需依附一个物理设备平台,由于平台自身的一些物理特性,在加解密过程中会泄露出各种中间状态相关的物理效应信息(如时间、功耗、电磁辐射、声音、错误、Cache访问信息等),又称之为旁路信息或边信道信息,利用旁路信息对密码算法实现进行分析的过程称为旁路攻击,主要的攻击类型有计时攻击、功耗攻击、电磁分析、声音攻击、故障攻击、Cache攻击等。目前大部分密码算法实现的安全性均面临旁路攻击的严重威胁,随着先进的测试仪器和计量手段的出现和发展,旁路攻击已经具备实际攻击可行性。本文主要研究利用密码算法在Cache访问时泄露的踪迹信息进行密钥分析的方法。Cache攻击大体分为Cache信息采集和信息分析2个阶段,根据采集信息不同,可将其分为时序驱动、访问驱动和踪迹驱动3种,本文给出了一种改进的Cache踪迹驱动信息分析方法,并对AES和CLEFIA抗Cache攻击安全性进行了分析。在Cache踪迹驱动攻击方面,文献[7~10]利用该方法对AES进行了安全性分析,最近,文献也利用其对CLEFIA进行了安全性分析,但现有文献均不能在第1轮分析中直接恢复AES和CLEFIA完整扩展密钥。本文分析方法同文献类似,利用“Cache失效”踪迹驱动信息进行密钥分析,但本文研究发现,由于分组密码S盒在Cache中的不对齐分布特性,通过对AES和CLEFIA加密的“Cache失效”踪迹驱动信息进行分析,其第1轮完整扩展密钥可在有效样本下快速恢复。表1给出了本文攻击同前人工作的比较,其中,H表示Cache命中,M表示Cache失效,第4列H/M表示攻击中利用的信息是Cache命中还是失效。本文结构如下:第2节对Cache访问信息泄露和Cache攻击分析模型进行了研究,给出了Cache踪迹驱动分析模型,分析了分组密码S盒在Cache中的分布特性,提出了改进的Cache踪迹驱动分析思想;第3、4节分别给出了针对AES和CLEFIA的改进Cache踪迹驱动分析方法,并给出了攻击实验结果与比较;第5节是结束语。2分析内存攻击的模型92.1基于cache的恶意攻击技术高速缓存Cache主要用于解决CPU与主存之间速度不匹配的问题。为提高算法非线性度和软件执行效率,现代分组密码大都使用S盒查表访问Cache。Cache访问命中和失效会带来时间和能量消耗差异,而分组密码加密使用了S盒进行查表操作需要访问Cache,其Cache访问特征信息可通过时间或能量消耗特征信息泄露出来,恶意攻击者通过Cache攻击可采集到分组密码运行过程中泄露的Cache访问信息,这些访问信息同查找S盒索引、明文、密文和密钥有紧密关系,可以用来进行相关密钥恢复。随着高精度和复杂精密测试计量仪器及技术的发展,精确采集Cache泄露的时间和能量消耗差异已经具备实际可行性。根据攻击者的Cache信息采集能力,可将Cache攻击分为时序驱动、访问驱动[15~19]和踪迹驱动[7~11]3种。1)时序驱动Cache攻击需采集一次加解密过程的整个时间,结合高级统计分析方法推测密钥,常需百万计的攻击样本,分析方法复杂;2)访问驱动Cache攻击需通过间谍进程采集密码进程加解密中访问的Cache组集合,使用直接或排除分析方法推测密钥,同时序驱动攻击相比,其对攻击者的信息采集能力要求比较高,但分析方法简单;3)踪迹驱动Cache攻击需采集密码加解密过程中每次Cache访问命中和失效信息的一个序列,结合明文或密文进行密钥推测,分析效率非常高,通常Cache访问踪迹信息的采集主要通过采集Cache访问能量消耗信息来实现。2.2mhsh的cache中性及失效序列在踪迹驱动Cache攻击中,攻击者需获取加密样本每次Cache访问的命中和失效序列,并利用其进行密钥分析。以AES加密第1轮为例,MHHM,MMHH,MHHH,MHMH为16次查表访问的Cache命中和失效序列,其中,H和M分别表示“Cache命中”和“Cache失效”。图1表示同一次加密中对S盒的2次查表访问,2次查表索引分别为x0⊕k0、x1⊕k1,一般来说,如果x0⊕k0是第1次访问Cache,常会发生Cache失效,根据第2次查表访问Cache是命中还是失效,可将分析分为2种情况。1ache访问此时,x0⊕k0=x1⊕k1,二次Cache访问需较短时钟周期或较低能量消耗,并且可直接泄漏部分密钥字节的异或结果可能值k0⊕k1=x0⊕x1。2基于cache的同化检测此时,x0⊕k0≠x1⊕k1,二次Cache访问需较长时钟周期或较高能量消耗,可直接泄漏部分密钥字节的异或结果的不可能值k0⊕k1≠x0⊕x1。通过以上分析,看起来可直接得到k0⊕k1的唯一候选值,假定一个Cache行包含δ个Cache元素,每次Cache失效都会从主存中将整个内存块的δ个元素加载到Cache中,对于Athlon3000+CPU处理器来说,每个Cache元素为4byte,每个Cache行大小为64byte,δ=16,常用的分组密码如AES、Camellia、CLEFIA每个S盒元素为4byte,16个元素常位于同一个Cache行中。每次Cache访问命中时,2次访问对应的元素地址a和b抛开低lbδbit相等,可表示为<a>=<b>。对于8bit的查表索引和δ=16来说,如果第2次查表Cache访问发生Cache命中,常满足<x0⊕k0>=<x1⊕k1>(高4bit相同,低4bit不一定相同),一次分析可直接得到k0⊕k1的高4bit值,但低4bit值未知;反之,如果二次查表发生Cache失效,可得到<x0⊕k0>≠<x1⊕k1>,此时可得到<x0⊕k0>的高4bit的不可能值,多次分析得到k0⊕k1的高4bit值,但低4bit值仍未知。2.3aes的s盒式性能大多数现有攻击均假定分组密码S盒在Cache中是对齐分布的,以AES的S盒为例,S盒大小为1kbyte,共256个元素,每个S盒行对应16个元素,对于Athlon3000+CPU处理器来说,定义u为S盒的第1个元素对应某个Cache行的第u个元素(0≤u<16),如果AES的S盒在Cache中是对齐分布的,即u=0,一个S盒会恰好对应16个Cache行,如图2(a)所示。但是,在Windows系统中,分组密码的S盒在Cache中通常是不对齐分布的,S盒的第1个元素常常不对应某个Cache行中第1个元素(u≠0),一个S盒会恰好对应17个Cache行,如图2(b)所示(u=12),利用该不对齐特性,对AES、Camellia、ARIA、SMS4等分组密码成功进行了访问驱动攻击。2.4不可能值k0k1以图1为例,如果S盒在Cache行中是对齐分布的,第2次Cache访问如果Cache命中,可直接得到k0⊕k1的高4bit值,否则得到一个k0⊕k1高4bit的不可能值,多次分析得到高4bit的正确候选值,这种情况下不可能得到k0⊕k1的低4bit值。但如果S盒在Cache行中是不对齐分布的,x1⊕k1可能等于x0⊕k0所在的Cache行中的16个连续元素,但这16个元素可能位于不同的Cache行中,即16个索引值的高4bit不一定全相同,假设k0=0x01,则k1=x1⊕x0⊕k0,可得到16个高4bit不同,低4bit也不同的k1候选值集合,如果k0预测正确,多次分析后的交集即可得到唯一的k1值;否则会得到k1的一个空集。3改善的协议跟踪驱动程序分析3.1aes加密算法实现AES作为DES的替代者,2001年被美国国家技术标准局(NIST)选用,算法支持128bit、192bit、256bit密钥的不同版本,本文主要关注128bit密钥的AES,分析方法可适用于192bit和256bit密钥的AES。AES是一个基于有限域运算的迭代密码,首先输入16byte明文P,输入的16byte密钥被扩展成44个32bit字所组成的数组w[r],P同初始密钥K进行异或作为初始输入状态变量,然后第r轮迭代根据16byte的输入状态xr-1和一个16byte的子密钥Kr,产生一个16byte输出状态xr。除最后1轮,每一轮迭代都包括对xr-1的4个代数运算:字节代换、行移位、列混淆和轮子密钥Kr异或。为提高加密速度,AES加密快速实现算法在每一轮中,将除与轮密钥异或以外的操作合并为16次查表操作,预先进行计算,计算结果存储在多个查找表中。整个AES加密由160次查表和176次异或操作组成,执行效率非常高,但是频繁的查表操作访问数据Cache也为其带来了严重的Cache计时攻击威胁。攻击者如果采集到足够多的AES加密Cache计时信息,将其转换为查表索引,结合明文或密文就可推断出某一轮扩展密钥信息,由于AES密钥扩展结构具有可逆性,攻击者只要恢复了中间任意轮扩展密钥就相当于恢复了初始密钥。3.2aes加密分析Bertoni等首先提出密码实现功耗轨迹可能会泄漏Cache访问命中和失效信息,利用功耗仿真工具对AES加密功耗进行了仿真,成功获取了AES加密第1轮每次Cache访问和命中序列,然后对Cache命中信息进行分析获取48bitAES-128密钥。O.Acıiçmez将Bertoni攻击延伸到了AES加密第2轮,也是通过对Cache命中信息进行分析,成功获取94.5bitAES-128密钥;JosephBonneau将O.Acıiçmez攻击转移到加密最后1轮,通过分析Cache失效信息进行分析,使用50个样本成功获取128bitAES密钥。3.3把k4作为聚合条件时的文本引进数据攻击中使用的算法为OpenSSLv.0.9.8.(a)密码库中AES优化实现,在加密前9轮使用了4个1kbit的查找表T0、T1、T2、T3,在第10轮仅使用了一个1kbit的T4查找表。AES前9轮加密公式如式(1)所示。可以看出,每轮对T0、T1、T2、T34个查找表分别进行4次查表,共16次查表操作。第1轮查表索引可表示为Pi和Ki分别表示明文和初始密钥的第i个字节,i∈。第1轮中查T0表的4个索引值为第2次查T0表的Cache访问命中和失效信息结合查表索引P4⊕K4,可推断出K0和K4的相关信息。如果第2次访问发生Cache失效,则满足{<P0⊕K0>}表示同P0⊕K0在同一个Cache行的16个索引值,如果S盒在Cache中是对齐分布的(如图2(a)所示),每个查表行对应一个Cache行16个元素,如果P0=0x61,P4=0x73,假设K0=0x00,{<P0⊕K0>}对应16个高4bit相同的字节,第2次访问的失效信息可得出K4的16个不可能值。使用更多样本,如果K0预测值为正确的,多次分析后的交集即可得到16个高4bit相同的K4值;否则会得到K4的一个空集。但是,如果S盒在Cache中是不对齐分布的(如图2(b)所示),如每个S盒查表行对应一个Cache行的后4个元素和下一个Cache行的前12个元素(u=12),如果P0=0x61,P4=0x73,假设K0=0x00,{<P0⊕K0>}对应高4bit和低4bit不同的16byte,第2次访问的失效信息可得出K4的16个不可能值一次Cache失效信息可排除掉K4的高4bit和低4bit值不完全相同的16个候选值,如果K0预测正确,K4多次分析后的交集即可得到唯一值;否则会得到K4的一个空集。将该方法应用到其他2次查T0表可恢复K8,K12,其他12次查T1,T2,T3表可恢复其他12个K字节值。需要注意的是,第j次(j>1)查Ti表Cache失效一次理论上最多排除掉16(j-1)个错误候选值,故后续密钥分析效率会越来越高,但前提是前面密钥字节分析正确。3.4k0103-k0103OpenSSLv.0.9.8.(a)中AES最后1轮仅使用T4表进行了16次查表操作,最后1轮加密公式如下如果第2次查T4表发生Cache失效,可得到无论{<T4-1[C0⊕K010]>}是否为高4bit相同的16个连续值,还是高4bit不完全相同的16个连续值,由于S盒的非线性特性,经查找T4表后都可转换为16个不连续值。因为最后1轮只对T4表进行了16次访问,其排除分析效率要远高于第1轮分析,理想情况下,第16次查表访问Cache失效可一次排除掉240个不可能的密钥字节候选值,但其前提条件是前面15个密钥字节预测正确。3.5aes的s盒攻击在Athlon3000+处理器下(Cache行大小为64byte)进行了攻击仿真试验。Cache访问踪迹信息采集并不是本文的研究重点,实验中通过修改算法由其自动输出Cache访问命中和失效序列。AES第1轮攻击中样本大小同密钥搜索空间如图3所示。可以看出,如果S盒在Cache中是对齐分布的,第1轮攻击只能将其密钥搜索空间降低到80bit,而在不对齐情况下,大约200个样本即可将其搜索空间降低到216左右,经简单暴力破解恢复128bitAES密钥,在仿真环境下,整个攻击过程(包括信息采集与分析)可在1s内完成。AES最后1轮攻击Cache行大小同攻击成功所需样本量关系如图4所示。可以看出,不论AES的S盒在Cache中是否对齐,128bit完整密钥都可在有限样本中恢复,由于S盒的雪崩特性,最后1轮的排除分析效率要高于第1轮攻击。同前人AESCache踪迹驱动攻击[7~10]比较,前人攻击都假定S盒在Cache中是对齐的,通过第1轮分析只能获取48bit密钥,而在实际情况下,大多数情况时S盒元素在Cache中为不对齐分布的,前人攻击将会失效,本文攻击则涵盖了所有情况,在S盒不对齐时分析效率要高于前人攻击。4对于clefna的改善，基于荷叶跟踪的效率分析4.1clefia-合成密钥首先给出CLEFIA算法分析使用的符号说明。P,Xr,C:128bit明文、第r轮中间状态、密文;Pi,Xri,Ci:明文、第r轮中间状态、密文的第i个32bit字;Pi,P(i-j):明文第i个字节和明文第i到第j个字节;WKi,j,RKi,j:第i个白化密钥字和扩展密钥字的第j个字节;CONi128:128bit常量;F0()i,F1()i:加密左右轮函数输出的第i个字节;Li,Ti:密钥扩展中第i次更新的128bit中间变量;第r轮对Sj表的第m次查表索引(第i次查所有表的索引)。CLEFIA算法是索尼公司在2007年FSE大会上提出的一种分组长度为128bit的密码,分组长度为128bit,支持长度为128/192/256bit密钥,采用了广义Feistel结构,并在算法的开头和结尾加入了白化处理,整个加密分为3个步骤。第1步:前期白化。将128bit明文P=(P0,P1,P2,P3)同2个白化密钥异或,即第2步:前期r-1轮变换。F0和F1函数由代换函数S和混淆函数M组成,如图5所示,代换函数均用到了2个不同的8×8的S盒S0和S1,只是使用顺序不同,混淆函数分别使用了4×4的Hadamard型矩阵M0和M1。第r轮变换和前面变换略有不同:第3步:后期白化。将128bit(Xr0,Xr1,Xr2,Xr3)与2个白化子密钥异或,得到密文:CLEFIA-128密钥扩展算法分成两部分:由128bit初始密钥K和24个32bit常数CONi128(0≤i<24)生成128bitL和白化密钥WKi(0≤i<4);由L和36个32bit常数CONi128(24≤i<60)经扩展得到子密钥RKj(0≤j<36)。下面是CLEFIA-128的具体密钥扩展算法:4.2基于cache的clefia-126密钥检测2009年,Chester等对CLEFIA进行了时序驱动Cache计时分析,使用了226.64个样本成功恢复121bitCLEFIA-128密钥;2010年,Chester等对CLEFIA进行了踪迹驱动Cache分析,将Bertoni攻击中利用Cache命中踪迹信息的分析思想应用到CLEFIA分析中,假定可获取到CLEFIA加密中每次Cache访问的命中和失效踪迹信息,使用243个样本1.5h左右恢复CLEFIA-128密钥。本节给出了一种改进的Cache踪迹驱动分析方法,利用S盒的不对齐特性,通过对CLEFIA加密前3轮的Cache失效踪迹信息进行分析,220次加密经分析1s内可恢复CLEFIA-128密钥。4.3多态性检验CLEFIA第1轮对S0和S1分别进行了4次查表访问,8次查表索引为如果第2次查找S0发生Cache失效,可得到对于每个RK0,0预测值和已知的P0和P2字节值,如果RK0,0预测正确,则多个样本排除后可得到唯一的RK0,2值,否则得到一个空集。这样当第m次(1≤m<4)查Sj表发生Cache失效时,最多可排除相关密钥字节的16m个候选值。根据2.4节方法和式(13),通过分析第1轮4次查S0的Cache失效信息,RK0,0,RK0,2,RK1,1,RK1,3值可被依次恢复,通过分析4次查S1的Cache失效信息,RK0,1,RK0,3,RK1,0,RK1,2可被依次恢复。4.4基于cache的sj表失效利用4.3节恢复的RK0和RK1,CLEFIA第2轮8次查表索引值为如果第2轮第1次(整个CLEFIA加密第5次)查找S0发生Cache失效,可得到根据式(13)、式(15)和式(16),由于P,RK0和RK1为已知,多个样本排除后可得到唯一的WK0,0⊕RK2,0值。当第m次(4≤m<8)查Sj表发生Cache失效时,最多可排除相关密钥字节的16m个候选值。这样,根据2.4节方法和式(15),通过分析第2轮4次查S0的Cache失效信息,WK0,0⊕RK2,0,WK0,2⊕RK2,2,WK1,1⊕RK3,1和WK1,3⊕RK3,3可被依次恢复;通过分析4次查S1Cache失效信息,WK0,1⊕RK2,1,WK0,3⊕RK2,3,WK1,0⊕RK3,0和WK1,2⊕RK3,2可被依次恢复。4.5密第9次搜索s0利用前2轮分析恢复的RK0,RK1,RK2⊕WK0,RK3⊕WK1值,CLEFIA第3轮8次查表索引值为如果第3轮第1次(整个CLEFIA加密第9次)查找S0发生Cache失效,可得到根据式(13)、式(15)、式(17)和式(18),由于P、RK0、RK1、RK2⊕WK0和RK3⊕WK1为已知,多个样本排除后可得到唯一的RK4,0值。根据2.4节方法和式(17),通过分析4次查S0Cache失效信息,RK4,0,RK4,2,RK5,1和RK5,3可被依次恢复;通过分析4次查S1Cache失效信息,RK4,1,RK4,3,RK5,0和RK5,2可被依次恢复。4.6前3轮攻击结果根据CLEFIA密钥扩展算法,利用前3轮攻击恢复RK0、RK1、RK2⊕WK0、RK3⊕WK1、RK4、RK5,每个组合值可将CLEFIA-128主密钥空间降低到27。图6(a)给出了生成CLEFIA密钥扩展生成子密钥RKi(0≤i≤7)的过程,图6(b)给出了前3轮攻击的结果,图6(c)给出了利用前3轮攻击结果恢复主密钥K(即WKi,0≤i<4)的过程。具体算法如下:1)根据常量CON0和第1轮攻击结果计算CON0⊕(RK0,RK1)恢复L0(0,7);2)分析CLEFIA密钥扩展中ReveseDoubleSwap函数Σ-1(L0(0,7))恢复L1的64bit;3)计算CON0⊕L1(0,7)恢复T1的64bit;4)根据T1的64bit和RK4,RK5计算T1(0,7)⊕(RK4,RK5)恢复32bitWK0,25bitWK1(0,2);5)计算(WK0,WK1(0,24))⊕(WK0⊕RK2,WK1⊕RK3)恢复32bitRK2,25bitRK3(0,2);6)计算GFN4INV(RK0,RK1,RK2,RK3(0,2),CON)恢复K的121bit值,其余7bit可通过暴力破解获取。4.7clefia-126主密钥攻击仿真结果对于64byteCache行大小,CLEFIA-128第1轮攻击样本大小同RK0,RK1密钥搜索空间关系如图7所示。可以看出,如果S盒在Cache中对齐分布,RK0,RK1密钥搜索空间可降低到240,但是在不对齐情况下80个样本可将RK0、RK1密钥搜索空间分别