Microsoft Word - 25.doc

Size: px

Start display at page:

Download "Microsoft Word - 25.doc"

渍亨姜
5 years ago
Views:

1 定时攻击技术研究郑媛媛, 杨妆 2, 王韬 (. 军械工程学院计算机工程系, 石家庄 ; 2. 总后勤部指挥自动化工作站, 北京 00842) 摘要 : 定时攻击是指攻击者试图通过分析执行加密算法所需要的时间, 从而对加密系统进行的破解攻击本文从定时攻击的概念及原理出发, 继而以模幂运算作为加密算法为例, 模拟了对该计算进行破解的过程, 最后分析了定时攻击的优点存在的问题以及发展趋势关键词 : 定时攻击, 模幂运算, 平方 - 乘法算法中图法分类号 TP309 文献标识码 A Research on Timing Attack ZHENGYuan-yuan,YANG Zhuang,WANG Tao (.Dept.of Control Engineering,Ordnance Engineering College, Shijiazhuang ; 2.Command Automation Workstation of the General Logistics Dept., Beijing 00842) Abstract Timing attack is a form of attack where the attacker tries to break a cryptosystem by analyzing the time taken to execute cryptographic algorithms. This thesis firstly introduces the basic theory of timing attack and the discription of the related algorithms, and then taking the modular exponentiations for example, emulates the attack process, finally analysises the advantages, several problems waiting for further study and the trend of timing attack.. keywords timing attack,modular exponentiations, square-and-multiply algorithm 引言在现实世界中, 安全是一个相当简单的概念无论是人们的财产安全, 还是各项权利都在安全防护措施的保护伞之下然而, 在数字世界中, 能做到数据安全却绝非易事由于计算机网络具有系统复杂性资源共享边界不可知传输信息的路由不确定性电磁辐射等原因, 使其本身的安全性降低, 因此网络的安全系数一般都比较小 [] 这也就是说即使对信息进行加密, 也并不一定就能保证其安全正是基于这一突破口, 近年来密码攻击技术逐步成为密码学领域研究学者所关心的焦点问题作为密码分析学领域内的一个新兴技术定时攻击, 以其原理简单操作便捷的优点赢得了领域内学者的普遍关注 2 定时攻击定时攻击 (timing attack), 是指利用加密或解密算法对不同的输入进行操作时所消耗时间的不同, 并通过对多种密文解密所需时间的观察, 并从中找出规律性, 从而获得密钥与明

2 文信息的一种攻击方法 Kocher 首先提出定时攻击这个概念他指出攻击者可能仅仅通过定时信息就能够破解 Hiffie-Hellman RSA 和 DES 等加密系统然而,Kocher 所指出的只是定时攻击的基本思想, 并且这些观点仅仅停留在理论上 Kocher 思想的主要问题在于攻击者必须知道欲攻击的加密系统的执行细节 Kocher 的计时攻击思想如图 [2]. 开始密码系统的实现消耗时间保密信息结束图 Kocher 定时攻击思想框图为了更加清楚地阐述定时攻击的原理, 下面以采取简单的模幂运算为加密算法的加密系统为例, 解释这种攻击方式 2. 定时攻击的理论基础在介绍定时攻击原理时, 之所以采用这种运算算法是因为这种运算在大多数加密算法中是非常普遍的例如,RSA 加密算法的加密和解密操作就需要计算模幂除此而外,ElGamal 公钥加密算法的密钥产生算法也需要这种计算即 g x mod p 对于 g,x,p 较小时, 进行模幂的运算很方便然而, 如果这三个数很大时, 尤其是 x 很大时, 进行这种计算就不是很方便因此, 利用数学的方法就可以简化这种计算, 最基本的方法就是平方 - 乘法算法 ( 或称 BR 算法 ) 该算法共分为两个部分, 第一部分就是将十进制的幂指数 x 转换为其二进制的形式, 即 l x= i= 0 i x 2 (0 i l-,x i =0,) 具体的实现步骤( 主要部分 ) 即为 : i 算法 : while(x>=) { s=x/2; array[i]=x%2; i++; x=s; } 平方 - 乘法算法的第二部分, 也就是核心部分在于它能将繁琐的模幂运算 g x mod p 转化为仅仅用一个简单的 for 循环即可实现其算法的主要部分如下 [3] : 算法 2: for(i=i-;i 0;i--) { y=y 2 (mod p);. if(array[i]=); then y=y*g (mod p); 2 } 2

3 用这种方法计算 y= g x mod p 的可靠性是基于离散对数问题 (Discrete Logarithm Problem,DLP), 即已知 g,x 和 p 很容易得到 y, 但是从 y,g 和 p 很难求出 x 因此可证明采用这种加密方法对于用正常的攻击方法是很难破解的许多加密算法都是利用了求离散对数的困难而建立的 2.2 定时攻击原理了解了这种采用模幂运算加密的具体算法, 下面以此为例介绍定时攻击的原理在定时攻击中, 攻击者所能支配的信息是一组密码设备已经被操作的信息, 以及每一个信息相对应的运行时间它的目标是复原秘密参量将用户输入的欲加密的数据作为指数 x( 已转化为其二进制形式 ), 对于作为秘密指数 x 中的每一非零位, 整个处理过程即完成一个 ( 取决于一些可计算的中间值的 ) 额外的模幂运算 ( 算法 2 的语句 2), 那么通过从对取样空间进行定时测量结果的变化以及指数的某一位是否为就可以找出它们之间的关系通过这种方式, 当这种取样空间的分布更精确时, 就能推导出更多的指数位, 最终可以找到密钥 [4] 3 一个攻击实例为了更加清楚明了的理解定时攻击的原理, 下面的例子就是综合了定时攻击方法与一般遍历的强行攻击方法而构造的一个攻击实例为了方便进行计算, 特做以下假定 : 假定 : 采用上述模幂算法的加密算法系统 ; 假定 2: 用户输入的明文已转化为二进制形式 ; 假定 3: 明文 ( 二进制 ) 统一为 L 位, 对于转换后不满 L 位的, 用 0 补齐攻击过程如下 : 首先, 攻击者构造两个极端的情况, 即将 x 设为全 0 或全, 目的是测量执行算法 2 中语句 2 分别消耗的时间长度由于当 x 为全 0 时, 在进行模幂计算时并不执行语句 2, 因此可以的推测出执行语句所用时间同理, 也可以得到执行语句 2 的用时在这里分别用 a,b 表示其次, 攻击者用计时工具测量加密系统对用户输入的 L 位明文进行加密所消耗的时间 t 则即可的如下方程组 : m+n=l n*a+m*(a+b)= t 2 其中 n 表示明文中 0 的个数,m 表示明文中的个数由此可得 : m= (t L*a)/b n = [L*(a+b) - t]/b 最后, 采取遍历的攻击方法攻击者可以选取 min{m,n} 2/L 这样, 尝试的次数为 m 个,n 个 0 所构成的 L 位二进制序列的组合数, 即 C= min{m,n} 在最坏的情况下, L 也就是二进制序列中 0 和的个数相等时, 遍历的次数较单独使用遍历攻击方法执行的次数减少一半, 大大节省了攻击的开销按照上述步骤进行定时攻击的实验, 就能较容易的得到明文然而, 在实验过程中, 由于测得的时间数与解密真正消耗的时间数有微小的差别, 在实验的过程中只能取得逼近的值, 而后从语义的角度出发, 从待选明文选出合适的 4 定时攻击与同类攻击方式的比较 4. 定时攻击的优点在这里我们将有代表性的三种攻击形式加以比较 : 3

4 功率分析攻击 (power analysis attacks): 它是通过分析密码设备进行操作的功率消耗, 来推导出加密系统所进行的操作和在操作中涉及到的秘密参量电磁泄漏攻击 (electromagnetic emanation attacks): 这种方法是通过在芯片周围放置线圈并且研究可测量的电磁场来实现的定时攻击 (timing attacks): 它通过分析密码设备已经执行的一组操作和进行操作所花费的时间, 来推导出加密系统在计算中涉及到的秘密参量在上述这三种攻击形式中, 定时攻击在解密能力方面无疑是最弱的但是在另一方面, 正是定时攻击所需的设备与测量的简单性使得这种攻击形式应用起来比较简便此外, 在许多情况下, 进行功率和电磁辐射的测量是非常困难的, 几乎不能完成然而定时攻击由于时间的易测性, 却可以冲破客观条件的制约, 圆满完成任务例如, 可以通过测量请求和应答之间的时间延迟就能完成密码分析 4. 2 定时攻击存在的问题实际上, 模幂运算的实现没有明显的时间消耗差异, 仅在极端的情况下一次迭代的执行时间才会大于整个算法的平均执行时间尽管如此, 时间消耗上的差异还是足够大, 以致于这种攻击可以奏效虽然定时攻击是一种严重的威胁, 但却有简单的防范措施 [5] : 常数取幂时间 : 保证所有取幂操作在返回一个结果之前花费同样多的时间随机延时 : 通过取幂算法增加一个随机延时来迷惑定时攻击者盲化 : 在进行取幂运算之前先用一个随机数与密文相乘, 以防止攻击者了解计算中正在处理的密文 5 结束语现阶段, 我国在定时攻击领域内的研究绝大部分还停留在理论研究之上, 其地位仅仅是作为加密技术研究的补充, 这在很大程度上阻碍了定时攻击技术的进一步发展本文的创新点在于以定时攻击为研究对象, 并在实验水平上对其进行深刻剖析, 对其优缺点进行了总结在定时攻击本身的固有特性上, 基于其所受限制, 它的攻击能力还有待提高, 应用领域还有待拓宽对定时攻击技术的研究还是一个较新的研究领域, 如何将其功能逐步完善, 如何提高其实用性, 已经成为一个亟待解决的问题参考文献 [] 陈运. 信息加密原理 [M]. 成都 : 电子科技大学出版社,990.P20~P2. [2] P. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. Advances in Cryptology - CRYPTO'96, Lecture Notes in Computer Science, Vol. 09, pages 04-3, 996. [3] D. R. Stinson. Cryptography: Theory and Practice. CRC Press, Boca Raton, 2 nd edition, [4] Helena Handschuh and Howard M. Heys. A Timing Attack on RC5 [5] 宋维平蔡大鹏. 密码学基本算法的探讨长春大学学报, 第 4 卷, 第 2 期文章编号 : (2004) ,P43-45 [6] 王玉英王昭顺. 信息安全中的公钥密码软件 - 大整数模拟实现微计算机信息 2004 Vol.20 No.9 P.2-22,70 4

5 本课题受国家自然科学基金资助项目 ( ) 作者简介 : 郑媛媛 (98-), 女, 硕士研究生, 军械工程学院计算机工程系, 主要研究方向为网络安全 ; 杨妆 (957-), 女, 大学本科, 工程师, 主要研究领域为计算机应用系统开发 ; 王韬 ( 导师 )(964-), 男, 博士后, 教授, 军械工程学院计算机工程系, 主要研究方向为网络安全联系方式 : 石家庄军械工程学院计算机工程系网络与通信教研室郑媛媛 zheng_yuanyuan75@yahoo.com.cn 5

第 05 期董房等 : 一种卫星遥测在线状态监测及分析系统的设计 WEB 1 2 总体功能及组成 2.1 总体功能 1 2 3Web 2.2 结构组成 Web WEB WEB 2.3 系统各模块接口关系

第 05 期董房等 : 一种卫星遥测在线状态监测及分析系统的设计 WEB 1 2 总体功能及组成 2.1 总体功能 1 2 3Web 2.2 结构组成 Web WEB WEB 2.3 系统各模块接口关系电子科学技术 Electronic Science & Technology 电子科学技术第 02 卷第 05 期 2015 年 9 月 Electronic Science & Technology Vol.02 No.05 Sep.2015 年一种卫星遥测在线状态监测及分析系统的设计董房 1,2, 刘洋 2, 王储 2 2, 刘赞 (1. 上海交通大学, 上海,200240; 2. 上海卫星工程研究所,