公钥密码算法识别技术研究

1、张经纬,舒辉,蒋烈辉,等:公钥密码算法识别技术研究 2011, V ol.32, No.1032430引 言随着互联网技术的飞速发展以及普适计算概念 1-2的提 出, 嵌入式系统越来越多地应用于路由器、 交换机等网络关键 设备中, 其安全性是当前网络安全研究的重点之一。密码算 法在保护嵌入式系统安全方面起着关键作用, 逆向解析系统 中密码算法的实现安全性, 对于保护系统的安全性具有重要 意义, 其中识别嵌入式系统中蕴含的密码算法是对其逆向解 析的前提。鉴于公钥算法的安全机制, 其广泛地应用于数据加密、 数 字签名、 身份认证、 信息的完整性认证等方面, 所以识别嵌入 式系统中的公钥密码算法对于

2、解析其系统安全性尤为重要。 文献 3针对 X86平台下的密码算法统计特征,提出了基于 Bayes 决策的算法识别模型, 该模型主要针对统计特征比较明 显的 Hash 类、 分组类密码算法, 以核心函数为识别粒度, 不能 鉴别具体算法名称。因此, 针对公钥密码算法识别的研究成果并不多见, 本文 在对其实现特征研究的基础上, 结合模型检测等技术, 提出了 一种基于语义的公钥密码算法检测方法 4-6, 该方法具有以下 特点:首次采用有效的基于公钥密码算法实现特征的库函 数调用序列的加密行为描述规则, 能够描述加密行为的复杂 上下文关系和控制流信息; 对算法中的上下文敏感, 流敏感 及路径敏感的函数间

3、分析, 分析精度较高; 根据对几种典型 公钥密码算法特征的分析, 给出了基于库函数调用的加密行 为模型。1公钥密码算法特征识别嵌入式系统的公钥密码算法, 需要深入研究算法的 加密原理特征, 以及其在嵌入式系统中的代码实现特征, 通过 识别具体典型特征进行鉴别。1.1公钥密码加解密特征自公钥密码被提出后,国内外提出了许多公钥密码方收稿日期:2010-10-08;修订日期:2010-12-10。32442011, V ol.32, No.10计算机工程与设计 Computer Engineering and Design案 7-8, 但安全实用的公钥密码系统是:基于大整数因子分解 问题的 RSA

4、体制; 基于离散对数问题的 ElGamal 公钥密码 体制、 椭圆曲线公钥密码体制。公钥密码算法即非对称式密钥算法, 也称双钥密码算法, 该算法中加密密钥与解密密钥不同。加密密钥为公开密钥,简称公钥 (PK ; 解密密钥必须保密, 称为私钥 (SK 。公钥密码体制的基本思想为:每个用户产生一对密钥 PK 和 SK ; 加密密钥 (即公钥 PK 公开, 解密密钥 (即私钥 SK 保密; 加密算法 E 和解密算法 D 均公开;私钥 SK 由公钥 PK 决定, 但不能根据 PK 计算出 SK 。用 PK 加密消息=¿É±íʾÎ&

5、#170;£º。其原理图如图 1所示。 1.2公钥密码算法逆向分析特征基于二进制逆向的公钥密码算法特征分析与研究是进行公钥密码算法识别的前提和基础, 研究角度不同, 算法特征的 体现形式也有所差异。 同时, 对公钥密码算法加密原理、 软件 实现以及逆向分析的熟悉程度是进行公钥密码算法识别的必 备要素。通过对几种典型的公钥密码算法加密原理的分析及研究 得出, 公钥密码算法加密具有以下几个特点:(1 加、 解密速度较慢, 由于进行的都是大数计算, 使得非 对称式密钥算法最快的情况也比对称式密钥算法慢很多; (2 除了基本运算操作加、 减、 移位和异或, 对应于算法的 乘法结构,

6、 还存在着大量的乘法操作, 如模乘等;(3 公钥密码算法需要进行大数运算, 在软件实现过程中 体现为大量复杂的函数调用, 尤其常调用一些国外著名的密 码学函数库。 公钥密码算法的实现过程中需进行复杂的库函数调用, 本文将其称之为公钥密码算法的“库函数实现特征” 。公钥密码算法在加密时通常会调用大数库来完成算法功 能。 国外常用的著名密码学函数库 9有:freeLIP 、 Miracl 、 Crypto+、 GMP 、 OpenSSL 、 FGInt 、 LibTomCrypt 等。其中 Miracl 库10是当 前应用广泛的基于公钥加密算法保护实现的大数库之一, 其 支持 RSA 公钥系统、

7、Diffie-Hellan 密钥交换、 DSA 数字签名系统及基于 GF (的椭圆曲线加密系统。 Miracl 库一 个十分重要的特性是可以定位程序运行过程中出错的函数, 其在初始化函数的同时也会初始化集成在 Miracl 库中的错误 跟踪系统。 它为每个函数定义了一个特定的常量作为标识符,因此无论何时只要函数调用序列中的任何一个函数发生错误 都会被检测到, 包括错误本身。实现该错误处理机制的语句 是 MR_IN( , 用来表示 Miracl 中的函数退出及退出代码, 因 此通过退出代码便知是哪个函数出错。每个函数的 “ ” 均不 同, 如函数 mirvar 为 MR_IN(23 , 函数 s

8、et_user_function为 MR_IN (111 。对调用 Miracl 库的公钥密码算法的反汇编结果进行 分析后发现其中含有代码 MR_IN(23 , 无论如何编译 Miracl , MR_IN(23 都会在最终生成库文件里面, 其在反汇编结果中为 以下形式:mov dword ptr esi +eax*4+24h, 17h其中, 17h 即十进制 23, 可判断出程序调用的是 Miracl 中 的 mirvar 函数。继续向下分析, 可分别找到如图 2所示代码, 可判断出又分别调用了 mirsys , cinstr , powmod 这 3个函数。以上指令都具有相同的形式:mov

9、dword ptr esi +eax*4+24h, xxh通过该指令中的退出代码即可得知所调用的库函数, 因此将该指令特征作为公钥密码算法调用 Miracl 库的一个“库 函数实现特征” 。2基于语义的公钥密码算法识别方法分析2.1公钥密码算法识别的抽象模型该模型使用有限状态自动机 (finite states automata , FSA 描述公钥密码算法加密行为;下推自动机 (pushdown automata , PDA 描述目标文件的全局状态空间, 即目标文件的执行路径 空间; 然后使用模型检测方法检查目标文件中是否存在公钥 密码算法的加密行为。该抽象模型如图 3所示。图 3中,公钥密

10、码算法加密行为的 FSA采用五元组 , , ÊÇÓÐÏÞ״̬¼¯ºÏ£¬±íʾָÁîÖ´Ðйý³ÌÖУ¬Ã¿¸ö¼Ä´æÆ÷&#

11、188;°Ëù²Ù×÷ÄÚ´æµ¥ÔªµÄÈ¡Öµ£»¡ÆÊÇÓÐÇîµÄÊäÈëÖ¸ÁºÏ£¬±í&#

12、202;¾¿âº¯Êýµ÷ÓÃÐòÁÐÖеÄÿ¸ö¿âº¯ÊýÄÚµÄÖ¸ÁîÐòÁУ»×映射到是结束状态集合。为了表示目标文件的全局状态空间, 即包含函

13、数调用的 执行路径集合, 需要使用栈来记录其返回地址, 由栈产生的语 言为上下文无关语言,因此存在一个接受语言。该下推自动机采用三元组 , 表示:其中是有穷的栈符号表,发 送 者密 文=张经纬,舒辉,蒋烈辉,等:公钥密码算法识别技术研究 2011, V ol.32, No.103245 合, 则表明目标文件中包含有公钥密码算法。2.2公钥密码算法加密行为模型公钥密码算法加密行为模型是对算法加密过程的抽象表示。由于公钥密码算法完成加密的函数主要由大数库提供, 本文通过对此类库函数的识别, 以及深入分析其在汇编级别 体现出的控制结构特征, 挖掘其中所蕴含的语义信息, 最终构 建出公钥密码算法加密行

14、为模型。在建模阶段, 首先采用 FLIRT 技术 12完成对加密过程中 调用的库函数的标识。 FLIRT 是 IDA 用于识别库代码的一组 技术,其核心是各种模式匹配算法。应用 FLIRT 技术创建特 征文件包括两个阶段:函数的预处理和特征文件的创建。在 预处理阶段提取函数的 PAT 特征, 形成特征文件。该模式文 件是一个文本文件, 其包含提取出的、 标识被解析库中的函数 的模式、 名字、 CRC16以及创建特征文件所需的其它信息; 在 创建阶段对该模式文件进行签名, 生成对应的签名文件, 唯一 标识该库函数; 在对完成加密功能的库函数分别建模之后, 将 这些函数按时序关系形成一个实现加密功

15、能的库函数序列, 其次采用有限状态自动机建模, 直观地描述这种状态之间的 转移关系, 完成对库函数调用序列的标识。实验通过对几种典型公钥密码算法的分析提出了相应的 算法加密行为模型,以 RSA 为例说明行为模型的构建过程:RSA 公钥密码算法是第一个既能用于数据加密又能用于数字 签名的算法, 易于理解和操作。该算法首先随机选两个大素数×选取与互素的加密密钥模 的逆元 , 调用函数 mirvar (和 cinstr (完成相关初始化及转换工作,到达状态和公钥<3; 调用 函数 powmod (, nres_powmod(, nres_modmult(完成加密的核 心部分,即计算密

16、文,到达状态 32462011, V ol.32, No.10计算机工程与设计 Computer Engineering and Design 本文中的实验采用 IDA Pro 5.213完成对目标文件的反汇 编处理。 在数据流分析阶段主要完成了对库函数调用的识别; 控制流分析阶段使用了改进的识别关键控制流结构 (即分支 控制结构和循环控制结构 算法, 该算法经实验验证比现有算 法更加快速和准确 14-15。在数据流和控制流分析的基础上, 将 汇编代码转换成与其相对应的中间语言, 最后通过为每个中 间语言建立抽象语法树和抽象语法树流图, 构建出目标文件 的下推自动机, 以此描述目标文件的全局状

17、态空间。2.4模型检测在模型检测阶段, 采用了基于自动机理论的模型检测方法 16, 即通过判断公钥密码算法的 FSA 和目标文件的 PDA 的 乘积自动机所接受的语言是否为空。 乘积自动机的非空问题 采用 Tarjan 的深度优先搜索算法遍历图的强连通分支,通过 检查是否至少存在一个从初始状态可达的环路包含一个接收 状态。由于可遍历程序的每条路径, 因此是流敏感且路径敏 感;还可匹配函数的返回地址和调用地址,因此是上下文敏 感。若目标文件中存在这样一个环路, 则说明其内部包含公 钥密码算法, 并返回该反例路径。3测 试为验证基于语义的公钥密码算法识别模型的正确性和可 靠性, 实验选取了几款常用

18、的加密软件进行测试。测试平台 为:Windows XP 操作系统, Pentium4处理器, 1GB 内存。测试 结果如表 1所示。表 1中, 用于对测试程序反汇编的时间不包括在识别时间 内。分析结果表明该行为模型能够准确识别出目标应用程序 中的公钥密码算法。 在测试过程中, 虽然对公钥密码算法的识别时间会随着目标应用程序的增加而线性递增, 但是基于公钥密码算法行为特征模型准确有效的特点, 识别时间相对较短。4结束语基于软件逆向的公钥密码算法特征研究是其识别的基础, 本文结合公钥密码算法的加密原理, 提出了对基于语义的 公钥密码算法加密行为的描述, 并给出了以 RSA 为例的算法 加密行为模型

19、。利用该方法并结合模型检测技术, 通过对几 种典型的公钥密码算法和目标文件的分析及测试, 被证明能 够有效地识别嵌入式系统中包含的公钥密码算法。 下一步工 作的重点是建立和完善加密行为模式库, 更完整和地分析公 钥密码算法的加密行为, 并在此基础上实现对公钥密码算法 的自动化识别。参考文献 :1杨帆 , 李彩霞 , 曹奇英 . 基于单向函数的普适计算密钥管理方案 J . 计算机工程 ,2009,35(8 :175-181.2庞礼军 , 樊林波 , 赵明 . 基于嵌入式系统的身份认证和密钥协商 算法 J . 贵州大学学报 (自然科学版 ,2010,27(2 :74-77.3李继中 , 蒋烈辉 .

20、 基于 Bayes 决策的密码算法识别技术 J . 计算 机工程 ,2008,34(20 :1-3.4李佳静 , 梁知音 . 一种基于语义的恶意代码检测方法 J . 北京大 学学报 (自然科学版 ,2008,44(4 :537-542.5Kinder J,Katzenbeisser S,Schllhart C.Detecting malicious code by model checking C .Vienna:Proceedingof the GISIG SIDAR Conference on Detection of Instrusions and Malware &Vulner

21、-ability Assessment.Springer,2005:174-187.6Christodorescu M,Jha S,Seshia S A.Semantics-aware Malware detection C .IEEE Symposium on Security and Privacy,2005:32-46. 7张雁 , 林英 , 郝林 . 椭圆曲线公钥密码体制的研究热点综述 J . 计 算机工程 ,2004,30(3 :127-129.8叶生勤 . 公钥密码理论与技术的研究现状及发展趋势 J . 计算 机工程 ,2006,32(17 :4-6.9Alfred J Menez

22、es,Paul C Oorschot,Scott A. Vanstone. 应用密码 学手册 M . 胡磊 , 译 . 北京 :电子工业出版社 ,2005:1-232.10段刚 . 加密与解密 M . 3版 . 北京 :电子工业出版社 , 2008:167-191.图 5描述 RSA 加密过程的有限状态自动机开始othermirvar (iv /cinstr (x, s compare (x, y otherotherotherother othern r e s _p o w m o d(x , y , z powmod (x, y, z, w mirkill (mem, n /mirexi

23、tnres_modmult(x, y, z表 1对公钥密码算法分析结果扫描软件名称 文件大小 /B识别时间 /s公钥密码算法识别结果796211.221ELGAMAL正确(下转第 3273页 王信敏,尹刚,张涛:AES 算法的差分差错攻击2011, V ol.32, No.103273 可能的集合的方法最终获得子密钥的正确值, 同时给出了算 法的具体操作步骤, 最后进行了实验模拟测试, 结果表明, 只 要获得了所需的差错位置及密文对, 该方法在普通配置计算 机上, 瞬间内即可完成, 该方法是合理有效的。 同时本文还存 在一些有待提高之处, 未来研究包括分析更多位置的差错出 现所产生的差分特征,

24、 并利用这些特征提高子密钥计算的效 率, 研究该方法在分组长度和密钥长度为 192比特和 256比特 的 AES 算法上的可行性及操作方法, 研究该方法在其它分组 加密算法中的适用性等。参考文献 :1Daemen J, Rijmen V . The design of rijndael M . Heidelberg:Springer,2002.2Dusart P,Letourneux G,Vivolo O.Differential fault analysis on AES J . Applied Cryptography and Network Security, 2003, 2846:29

25、3-306.3Bl ömer J,Seifert J P.Fault based cryptanalysis of the advanced encryption standard (AES C . FC, LNCS 2742. Heidelberg:Springer,2003:162-181.4Piret G,Quisquater J J.A differential fault attack technique against SPN structures C . CHES, LNCS 2779. Heidelberg:Springer, 2003:77-88.5Giraud C

26、.DFA on AES C .AES,LNCS 3373.Heidelberg:Springer,2005:27-41.6Moradi A, Shalmani M T M, Salmasizadeh M. A generalized method of differential fault attack against AES cryptosystem C . CHES,LNCS 4249.Heidelberg:Springer,2006:91-100.7Debdeep M.An improved fault based attack of the advanced en-cryption standard C .AFRICACRYPT,LNCS 5580.Heidelberg:Springer,2009:421-434.810Chong H K,Jean-Jacques Q.New differential fault analysis onAES key schedule:Two faults are enough