rsacache计攻击原理及实现

rsacache计攻击原理及实现

1基于cache战时攻击的分析在密码分析领域，文献提出了一种新的边路分析，即所谓的微结构分析。该技术理论上利用现代高性能超线程CPU体系结构中的某些部件内部的功能,可以潜在地发现密码系统执行过程中几乎所有的数据或指令访问顺序,进而根据访问的数据或指令推断出密钥。数据Cache、指令Cache和分支预测分析是微架构分析的3种类型。Cache计时攻击是利用访问数据Cache命中和失效特征所表现出来的执行时间差异,进而分析密钥的一种计时攻击方式。这种攻击利用CPU内部组件,即使采用了沙盒和虚拟化保护措施,由于内部组件在这些安全机制之下,也无法避免Cache计时攻击。文献提出通过构建隐通道监控密码进程,测量和记录执行的时间差异,推断密码进程执行过程中访问的数据序列,进一步分析从而推出密钥。文献所做的攻击平均可以正确分析出512bit密钥中的310bit。在Cache计时攻击方面,针对AES、Camellia等密码算法都已经取得成功,由于RSA为公钥密码,不同于对称密码算法的实现,实施起来更为困难。本文在文献的攻击理论基础上,基于Cache命中和失效原理,设计一种新的针对滑动窗口算法的Cache计时攻击方法,提高攻击的可行性。以OpenSSL0.9.8a实现的RSA密码算法签名过程为攻击对象,根据Cache在执行过程中遗留的痕迹,测量和记录执行时间,推断密码进程在执行过程中访问过的初始化表数据,通过对这些数据的分析推断出密钥,这种攻击方式具有抗干扰能力强、执行效率高等特点。2ria公钥密码算法2.1rsa的密钥计算RSA是一个基于模幂运算的公钥密码算法。加密过程为C=MemodN,解密过程为M=CdmodN,其中,M表示明文;C表示密文;N为模数;e为加密指数;d为解密指数。RSA产生密钥的过程如下:首先产生2个大素数(一般512bit以上)p和q,选择公钥e(通常是3、17或65537)并且满足gcd(e,(p-1)(q-1))=1;令N=p×q,通过d=e-1mod(p-1)(q-1)计算解密指数d。RSA加解密的核心运算是模幂运算,常用的模幂算法是平方-乘法算法。2.2窗口滑动的持续过程OpenSSL是目前使用较为广泛的开源SSL库。为提高RSA执行效率,OpenSSL采用了中国剩余定理、蒙哥马利乘法及滑动窗口算法来完成求幂操作。滑动窗口算法采用一个固定大小为k的窗口,在二进制模幂指数d上从左到右(也可以从右到左)滑动。滑动过程直到窗口最右边第一次碰到“1”结束,然后再创建一个窗口从上次结束的地方开始另一次滑动,这样的过程一直持续到d的二进制表达中没有“1”为止。滑动窗口算法需要反复计算一张乘数表,对于窗口大小为k的需要计算2k-1次。因此,为平衡重复计算时消耗时间和实际求幂消耗时间,存在一个最优的窗口大小。对于1024bit的模数OpenSSL采用的窗口大小为6,因此,每次滑动d的位数不超过6个。滑动窗口算法如算法1所描述,其中k表示窗口的大小。算法滑动窗口算法输入m,d=(dtdt-1…d1d0)2,其中,dt=1,整数k≥1输出md当窗口大小k=1时,滑动窗口算法等同于平方-乘法算法。因此,滑动窗口算法可看成是“平方-乘法”算法的一种改进,其主要思想是通过预计算来提高运算速度。本文以滑动窗口算法中的初始化乘法表为突破点,阐述针对RSA算法的Cache计时攻击。3基于cache滑动窗口算法的rsa检测Cache是位于主存和中央处理器之间的一个小的缓存器,为处理器提供一种快速方便地访问最频繁访问的数据和指令的方式。当处理器需要从主存读取数据时,它首先检测这些数据是否存在Cache中,如果存在(Cache命中),处理器立即读取这些数据,而不需要访问主存;否则,处理器必须从主存中读取数据(Cache失效),同时将数据的副本存储在Cache中。每次Cache失效都会产生对更高一级存储器的访问,这将导致额外的存取延迟时间,本文只考虑L1Cache。Cache计时攻击就是基于上述原理,即Cache失效增加了访问数据的时间。现代CPU多使用高速共享存储器技术和同步多线程技术,由于进程切换时并没有清空Cache中的数据,其他进程就可以对Cache中共享数据进行访问。在密码进程的执行过程中,由于对Cache的共享,会留下一些痕迹或中间数据。攻击者只要通过对Cache中私有数据进行访问,找到密码进程执行中与密钥相关特定Cache集合,进而根据Cache失效或命中的组集合与密钥的索引关系,可推断出密钥值。本文针对采用滑动窗口算法实现的RSA建立了Cache计时攻击模型,如图1所示。该模型首先构造一个与Cache(L1Cache)空间大小相等的数组,用来进行清空Cache操作(见图1(b));接着执行一次RSA签名操作,采用滑动窗口算法的RSA签名操作在每次窗口滑动过程中会访问初始化表的元素,访问过的元素将会被加载到Cache中(见图1(c));然后在每次窗口滑动结束后,利用计时手段采集二次访问初始化表导致Cache命中和失效的时间信息,由于对那些已经被加载到Cache中的数据进行访问会发生Cache命中(见图1(d)),而未被加载到Cache中的数据将会发生Cache失效,通过Cache命中与失效表现出来的时间差异推断访问过的初始化表中元素的索引值,而索引值与密钥信息密切相关,通过分析可以推断出密钥。4滑动窗口算法的隐私时间攻击4.1基于cache中性的滑动窗口算法OpenSSL在采用滑动窗口算法的RSA实现过程中,密钥被分离为序列片段,幂运算也是由一序列的平方乘法运算组成。同时,对于每次乘法运算,其中一个乘数是从先前已经计算的存储在表中的数据获得,在查找表中数据时,密钥的一个二进制片段对应的十进制值被用来作为索引检索表中的元素。由于表中的数据是存储在内存中的,当访问表中的元素时需要将其加载到Cache中,通过精确计时二次访问表中所有元素,已经加载到Cache中的表元素将会产生Cache命中,而其他元素导致Cache失效,利用Cache命中和失效的时间差异,攻击者能够推断表中的哪一个元素被访问过,这就使得攻击者知道了查找表时用到的索引值,该索引值对应着密钥的一个片段。通过多次访问进而获取整个密钥的所有片断,推出密钥。在滑动窗口算法中,当滑动窗口的大小为6时,预计算乘法表TABLE[0,1,…,31]={g2,g3,…,g63}={m2,m3,…,m63},如果TABLE[i]=gk,那么k=2i+1,其中i>0(i=0时,k=2)。就像平方乘法算法一样,从左到右滑动窗口算法执行过程中首先执行平方操作。然而,实际上每次执行多位,那么在窗口大小内的这些值将会被检测。如果连续6位是(100001)2,那么中间结果通过查初始化表乘以TABLE,即m33;如果是(10001)2,那么中间结果通过查初始化表TABLE,即m17;后面以此类推。初始化表每个元素大小与模数N的大小(例如对1024bit的模数N,那么每个元素大小为128Byte)。x86的CPU上每个Cache行大小为64Byte,攻击者在计时攻击的过程中,通过重复执行一些清空Cache指令使这些预计算值从Cache中清除,在查表操作结束后,再次访问预计算值,如果预计算表中的第2个元素访问时间很短,可以认为访问该元素时“Cache命中”,那么签名进程访问了预计算值m3,因此,此次窗口滑动对应的密钥片段为(11)2。4.2纳第三，存储了解构机制的时间戳值从上面的分析中可知,为获得私钥d的信息,必须精确获得在签名过程中,Cache命中与失效导致的时间差异信息。因此,在仿真实验中还需要解决以下关键问题:(1)高精度精确计时。本文采用CPU中一个称为时间戳的部件,它以64bit无符号整型数的格式记录了自CPU上电以来经过的时钟周期。在Pentium以上的CPU中,提供了一条机器指令RDTSC(ReadTimeStampCounter)来读取这个时间戳值,通过这一方法,可以达到纳秒级的计时精度。(2)清空Cache。实验中需要在每次新的窗口滑动过程中清空L1数据Cache。实验使用的CPU中L1数据Cache大小为64KB,Cache行大小为64Byte,因此,定义一个大小为64KB的数组intdata[16*1024],当进行清空Cache操作时,对该数组每隔64Byte进行一次访问,这样即可保证每一个Cache行都被替换为data数组的内容。(3)进程的干扰。通常除了理想的解密算法本身产生的计时差别外,在系统中还会存在其他运行的进程和密码进程抢占CPU资源,会对解密计时精度产生影响。尽管通过大量取样平均化处理可能减少这些误差影响,但这使攻击所需要的样本量大幅增加。在本文实验中,尽可能减少其他进程,以便提高攻击准确度。5基于cache不同密钥片的保护机制Cache计时攻击的实验环境如下:操作系统为WindowsXPProfessional;OpenSSL为OpenSSLv.0.9.8a;CPU为Athlon643000+1.81GHz;L1Cache容量为64KB,相联度为2way,Cache行大小为64Byte。笔者在上述实验环境下编写Cache计时攻击仿真程序,利用间谍进程采集每次窗口滑动过程中二次访问初始化表的时钟周期,攻击流程如图2所示。在仿真实验中,通过调用OpenSSL密码库函数随机产生1024bit密钥,滑动窗口大小为6,初始化表长度为32,表中每个元素大小为128Byte。图3给出了第1次窗口滑动后,2次访问初始化表中每个元素时需要的访问时间。可以看出,访问表中索引值为17的元素需要时钟周期只有76,所需时间最少,因此,可以判定第一次滑动窗口过程中访问了表中的元素TABLE,即m35,对应的密钥片段为(100011)2。通过仿真实验可以得到每次滑动窗口对应的密钥片段,由滑动窗口算法的3.1步可知,当di=0时,不需要进行查找表操作,因此,在获得的密钥片段间可能填充有二进制的0。在实际的一次攻击实验中,对于1024bit的密钥,窗口大小为6,理想情况下滑动1024/6=171次,实际中滑动140次~150次,通过Cache计时攻击可以得到700bit以上的密钥,这已大幅减少了密钥搜索空间,根据文献的理论,通过数学计算,则可以获得完整的密钥。Cache计时攻击利用了Cache命中和失效特征导致的时间信息差异,而基于统计方法的计时攻击需要大量的样本。研究人员能够在大约2h内从一个RSA加密服务程序中解析出1024bit的RSA私钥。攻击需要大约350000个时间样本。而在本文的攻击实验中,窗口滑动146次,获得了802位密钥片段,只需要150×32=4672个时间样本。因此,需要的时间样本量大幅减少。6基于cache防高模型的攻击本文研究了基于Cache命中和失效的RSA计时攻击,由于Cache资源的共享,Cache在读取数据时具有命中和失效2种特性,产生不同的时间信息。这种攻击利用了CPU内