对杂凑函数和分组密码算法的分析.pdf

山东大学博士学位论文对杂凑函数和分组密码算法的分析姓名:王高丽申请学位级别:博士专业:信息安全指导教师:王小云 20080420 山东大学博士学位论文对杂凑函数和分组密码算法的分析王高丽山东大学数学学院,山东,济南250100 摘要杂凑函数和分组密码在很多密码安全协议中起着非常重要的作用。杂凑函数最初是为了实现消息的完整性检测和起源认证检测等目的而提出的。当设计出有效且安全的杂凑函数算法之后,人们逐渐认识到若假设杂凑函数是“随机的"(输入和输出独立,各输出之间独立等),杂凑函数可用于其它很多地方,例如:,保护口令,构造有效的数字签名方案,构造诸如认证协议,密钥分配协议,比特承诺等协议,构造加密算法等。分组算法主要用来保密消息,包括在广播消息和储存消息时的保密,其安全性主要依赖于算法能抵抗各种攻击。分组算法的分析主要考虑算法的安全性,密码学家用各种分析技巧分析算法,用以评估其安全性。每个分析技巧都使用不同的模型,试图发现算法某方面的设计漏洞。设计杂凑函数的方法有很多,1991年Rivest第一次用直接构造法设计出了杂凑函数MD4【8】,随后的十多年,按照MD4的设计思想,人们陆续设计了MD4系列杂凑函数, 包括:MD5『131,HA、後L f141,SHA一0『161,RIPEMD f151,SHA一1『231,RIPEMD一128 【261,RIPEMD一160『261,SHA-2【36]等。其中MD5和SHA一1是应用最广泛的国际通用杂凑算法。RIPEMD算法是欧洲新计划RIPE f151的一部分,1996年,,A. 。RIPEMD一128包含两个并行且独立的操作,记为操作1和操作2,每个操作包含四轮(64步),每轮使用不同的轮函数,并且每个操作中消息字的顺序也不一样。随着MD4系列杂凑函数的广泛应用,对其安全性的分析受到了越来越多的关注, 其中最受关注的是对杂凑函数进行碰撞攻击,也就是,找到两个不同的消息,使得它们有相同的杂凑值。,该攻击的计算复杂度概率是222,1996年公布了任意初始值下MD5的碰撞f25],1997年公布两轮RIPEMD算法的碰撞『281,1998年证明了前两轮的MD4算法非单向函数『311。 Boer f201,A. 山东大学博士学位论文 Bosselaers『20]$『32】, f32,441分别给出了对MD5矛HSHA一0的攻击结果。1997年,王小云提出了比特追踪法f291,后来被称为模差分方法[51,52卜2004年美密会上,王小云公布了杂凑函数MD4,MD5,RIPEMD和HAVAL一128的碰撞实例 f431。模差分方法是王小云等破解MD4系列杂凑函数的理论基础,她们用模差分方法破解了大多数MD4系列杂凑函数:MD4[51】,MD5[52】,RIPEMD[51】,HA、厂AL 128f53,541,SHA-0f48]和SHA一1 f491,找到MD4和RIPEMD算法的计算复杂度分别低于285H2TM。模差分方法还可以用来寻找杂凑算法的第二原根f501'攻击HMAC和NMAC (伪造攻击和恢复密钥攻击)f551。随着MD4系列杂凑函数的破解,对基于杂凑函数的分组密码的分析逐渐成为热点。SHACAL一1 ,其分组长度为160比特, 它是NESSIE工程第二阶段评估后胜出的算法之一。以前对SHACAL一1的分析结果参见f38,59,41,45,46,57】。f571给出了对完整SHACAL一1算法的相关密钥矩形攻击, 该攻击的数据复杂度是2159·8(或21s3-8)个选择明文,计算复杂度是2420m(或250L2)。适用于该攻击的弱密钥数占总密钥数的击。SHACAL-2[391是基于杂凑函数SHA-2的分组密码算法,其分组长度为256Et特,它是NESSIE工程最终胜出的算法之一。以前对SHACAL一2的分析结果参见【40,42,58】。就轮数而言,目前对SHACAL一2最好的分析结果见f581,它利用相关密钥矩形攻击分析了42-轮SHACAL一2,其数据复杂度是2243。38个选择明文,。在分析SHACAL广1和SHACAL-2时,找到高概率的差分特征是至关重要的,而找到这些差分特征最关键的部分是分析并利用杂凑函数SHA一1和SHA-2的性质。本文的主要工作分为三部分: ,利用模差分方法,给出了杂凑函数算法RIPEMD一128前两轮的碰撞攻击,找到前两