MD5差分和差分路径的自动化构造算法
周林王政韩文报
（解放军信息工程大学信息工程学院郑州 450002）
摘要：为了得到较好的差分，差分路径和充分条件，本文考察了MD5算法和差分攻击算法的
原理，给出并证明了循环移位差分四种情况的概率，提出了MD5差分路径和充分条件的自动
化构造算法，将构造差分和构造差分路径相结合，调整了搜索步长，提高了构造的成功概率。
试验结果表明：我们得出的新差分路径重量比王教授的少17，所需充分条件要少22。
关键词：MD5; Hash函数; 差分攻击; 隧道技术; 多消息修正方法
中图分类号：TN918.1 文献标识码：A
The Automatic Algorithm to Construct
Difference and Differential Path in MD5
Zhou Lin Wang Zheng Han Wen-bao
(Information Engineering Institute, PLA Information Engineering University, Zhengzhou 450002, China) Abstract:For Finding good difference,differential path and sufficient conditions, this paper
analysed the theory of MD5 and differential attack algorithm, proved four probabilities of circle
shifting difference and proposed the automatic algorithm to construct difference and differential
path in MD5. We combined the construction of difference and differential path, modified the length
of searching step and promoted the successful probability of construction.Experiments proved that
our new differential path’s HW is lower by 17 than Dr Wang’s, and needed less sufficient conditions
by 22.
Key words:MD5; Hash functions; differential attack; tunnel technique; multi-message
modification method
1引言
Hash函数是密码学的重要分支,以SHA-1,MD5为代表的MDx系列Hash算法是最为典型的Hash函数,应用也最为广泛.例如Hash算法在密码协议中具有重要作用.在密码协议设计中一般都使用随机预言模型,即假设所使用的Hash算法是安全的.Hash算法的安全性直接关系到密码协议的安全性.因此对Hash函数的安全性分析一直是密码界的热点.
2004年，王小云证明MD5算法可以产生碰撞[1]。2007年，Marc Stevens，Arjen K. Lenstra和Benne de Weger进一步指出通过伪造软件签名，可重复性攻击MD5算法[2,3]。研究者使用前缀碰撞法（chosen-prefix collision），使程序前端包含恶意程序，利用后面的空间添上垃圾代码凑出同样的MD5 Hash值。同时Marc Stevens等利用X509协议中2048位的RSA大数字段和前缀碰撞法成功伪造的X509证书[9,15].2008年,Y. Sasaki利用差分碰撞算法成功恢复了APOP密钥[13].
上面的攻击的关键技术都是王教授的差分攻击算法,然而王教授没有给出如何寻找差分和差分路径的方法,如何寻找差分和差分路径的方法成为了国内外密码学家关注的焦点.。
2006年Yu Sasaki[]给出了已知差分路径构造充分条件的算法[16]，该算法能构造比王教授更好的充分条件，但是必须已知可行的差分路径，将构造差分路径和构造充分条件分离开，构造充分条件时不能根据需要调整差分路径，降低了算法成功构造充分条件的概率。2007年Marc Stevens提出了已知差分条件构造差分路径和充分条件的算法[14]，该算法同时构造差分路径和构造充分条件，当充分条件发生交叉，
国家863高技术研究发展计划(2009AA01Z417)和国家自然科学基金(2007B74)资助课题
通信作者：周林，男，1984年生，博士生，河南省郑州市1001信箱7410号(450002)，zhoulinpx@https://www.doczj.com/doc/c010117421.html,
不能同时满足时，可以调整差分路径，提高了算法的成功率。但该算法调整步长小，限制了搜索空间，因此算法的适应较小，例如无法构造出王教授提出的差分路径和充分条件。之后文献[6,8]提出过类似Marc Stevens 的算法，但本质上跟Marc Stevens 提出的算法相同。
本文第2节介绍了相关符号，MD5算法及王教授的差分攻击思想。第3节给出了我们的算法和实验结果，第4节总结了全文.
2 MD5及差分攻击算法
2.1. MD5
MD5将任意长的消息压缩成128bits 的消息摘要。给定一个数字串x ，首先将x 扩充为长为512倍数的消息串011{||||,......,||}n M M M -。利用压缩函数h 迭代计算，11(,)i i i H h H M --=，1,2,i n = ，n H 为最后的消息摘要值。
0{067452301, 0EFCDAB89, 098BADCFE, 010325476}H x x x x =
压缩函数11(,)i i h H M --使用1i H -初始化3210{,,,}Q Q Q Q ---，13210{,,,}i H Q Q Q Q ----=，使用1i M -初始化i m ，10115{||||,......,||}i M m m m -=，使用下面过程迭代计算t Q 1,2,,64t = 。
1231(,,),,(,),t t t t t t t t t t t t t t t t
F f Q Q Q T F Q K W R RL T S Q Q R ---+==+++==+
最后的摘要值为
361262163064(){,,,}h M Q Q Q Q Q Q Q Q ---=++++
其中
(,,)()()
015;
1631;
(,,)()()
(,,)3247;(,,)4863;
(,,)()t F X Y Z X Y X Z t t G X Y Z Z X Z Y f X Y Z t H X Y Z X Y Z t I X Y Z Y X Z ?=∧∨∧≤≤?
≤≤=∧∨∧?=?
≤≤=⊕⊕??≤≤=⊕∨?
32
2sin(1),
064t K t t ??=+≤≤??
1237,12,17,220,4,8,12;5,9,14,2016,20,24,28;
(,,,)4,11,16,2332,36,40,44;6,
10,
15,
21
48,52,56,60.
t t t t t t S S S S t t +++=??=?
=?
=??=?
51mod1635mod16
7mod16015;
1631;3247;4863;t t t t t m t m
t W m t m t ++?≤≤?≤≤?=?≤≤??≤≤?
MD5以Merkle-Damgard 理论为基础。Merkle-Damgard 理论表明：MD5的安全性取决于压缩函数h
的安全性。
2.2. 差分攻击算法
Hash 函数攻击算法大体可分为两类:通用算法（例如:生日攻击,中途相遇攻击和穷举攻击）和特定算法（例如:王小云的差分攻击,Dobbertin 的代数攻击）.通用算法一般适用于对所有hash 算法攻击,特定算法只能针对某一个或某一类hash 算法进行攻击.通用算法攻击的复杂度一般都很大,例如假设hash 函数的输出的消息摘要长为n ,则利用生日攻击所需的运算量是2(2)n
O .MD5的消息摘要长是128,所以利用生日攻击所需的运算量是64(2)O ,而使用差分攻击算法,目前最好的结果是只需10(2)O .
特定攻击算法是利用hash 函数的内在结构缺陷,找到hash 函数的弱点有针对性的进行攻击.例如H.Dobbertin 利用MD5中活动状态的高位bit 不能尽快的充分混淆,通过构造两个不同的512消息分组和选择初始IV 值得到半自由初始碰撞.王小云的差分攻击算法也是利用了MSB （最高比特位）不能尽快充分混淆,找到有效的差分和差分路径成功攻击了MD5,MD4,等算法[1]
.
差分攻击算法一般分为三个步骤: 1) 构造可以产生高概率碰撞的差分M ?
2) 推导出M ?的差分路径DP 和实现差分路径需要满足的充分条件SC
3) 利用单消息修正方法,多消息修正方法,隧道技术,“分而治之”技术设计和优化搜索满足充分条
件的碰撞消息对.
步骤1)中,将0M ?≠加上一个消息M 可得到'M ,为了使得'()()h M h M =,差分M ?在压缩函数f 中的扩散和混淆必须按照预先设定的路径进行并最后消失.步骤2)就是要构造这样的差分路径DP,并推出在什么充分条件下能得到这样的DP,充分条件数决定整个攻击算法的运算复杂度.步骤3)利用消息中的自由比特位,使用单消息修正方法,多消息修正方法,隧道技术,“分而治之”技术提高所构造的消息满足所有充分条件的概率.
3 差分路径和充分条件自动化构造算法
在给出算法之前我们先给出几个符合定义和需要用到的结论: t Q :表示当消息输入为t W 时第t 步链变量,1,2,64t = t Q ':表示当消息输入为t W '时第t 步链变量,1,2,64t =
并令:
1212(,,)(,,);t t t t t t t t t F f Q Q Q f Q Q Q δ----'''=- 3;t t t t T F Q W δδδδ-=++ (,)(,);t t t t t R RL T S RL T S δ'=-
1t t t Q Q R δδδ+=+
在构造差分路径时,需要知道循环移位对模差分的影响,[16]证明了根据模差分有四种情况,定理1给出了这四种情况的概率.
定理1：设32122,m m Z ∈，031s ≤≤，12()()y m s m s =<<<-<<<，3212mod2x m m =-，则：
3232323232223232323232223232323232
2232322
2mod 2)mod 2)2;mod 2()1
2mod 2)mod 2)2;
mod 2()2
2mod 2)mod 2)2;mod 22mod 2()21s s s s s s s
s s s
s x s x m m x x s x m m x y x s x m m x x m m x s ---------<<
=?<<<-+≥+
且（（且（（且（（且（3232322mod 2)mod 2)2;
s s s x ---+≥（且 323232322(mod 2)()(2)22s s s s x x P y x s ----??
=<<<=-???? ，
323232(mod 2)(()1)(21)22s s s x x P y x s --??
=<<<+=--???? ，
323232322(mod 2)(()2)22s s s
s x x P y x s ----??
=<<<-=????
，
323232(mod 2)(()21)(1)22s s
s x x P y x s --??
=<<<-+=+????
。
证明：设A 表示3222x m +<，B 表示3232322mod2)mod2)2s s s m x ---+<（（， ?3232323232323232323232()()
()()222(mod 2)22222(mod 2)(2)
22s s s s s s s s
s s s P y x s P AB P B P A B x x x x ---------=<<<==??-??-??=-??
=
-????
， ?323232323232323232(1)()
()()
22(1)(mod 2)2222(mod 2)(21)
22s s
s s s s s s s P y x s P AB P B P A B x x x x -------=<<<+==??
-+????=??=--????
，
?323232323232323232(()2)()
()()22(mod 2)22222(mod 2)22s s s s s s s
s
s s P y x s P AB P B P A B x x x x --------=<<<-==????-??=-??
=
??
??
，
?32323232323232
32(()21)()
()()
2(1)(mod 2)2222(mod 2)(1)22s s s
s s s s s s P y x s P AB P B P A B x x x x -------=<<<-+==??
+????=??=+????
。
构造差分路径的主要思路：从前往后构造第1步到第i 步的差分路径，同时从后往前构造第64步到第1i +步的差分路径。然后调整第i ，1i +，2i +，3i +步的差分路径使得从前往后构造和从后往前构造的差分路径在第i ，1i +，2i +，3i +步同时成立，从而得到整个差分路径。
由[17]可知：对MD4，SHA-1，特别是MD5，从后往前计算的雪崩因子比从前往后计算的雪崩因子要小。因此我们选择从后向前计算差分路径和推导充分条件，设r W δ为第一个不为0的消息差分，则令i r =。因为第1步到第1r -步没有消息差分，因此：
11j Q j r δ==-
在构造差分时可以得到61Q δ，62Q δ，63Q δ，64Q δ，62q δ，63q δ，64q δ，再利用下面的构造方法就可以一步一步推导出160j
Q j δ= ，161j
q j δ= 。
1．控制差分进位扩散。例如17321922Q δ=+，如果19[18]0Q =，则19
[18]1Q '=，不会产生进位。如果19[18]1Q =，则19
1919Q Q Q δ'=+必然产生进位。进位不会影响19Q δ的值，但是会影响布尔函数的值，为了消除多余进位的影响，必然要求更多的充分条件，所以一般我们令()j j q NAF Q δδ=。如果需要进位去影响布尔函数的值，我们可以利用上面的方法产生所需的进位。
2．调整布尔函数的值。例如32182Q δ=+，17321922Q δ=+，32202Q δ=+，32212Q δ=+，
172120202020191820(()5(,,)Q Q Q W f Q Q Q K =->>>---，我们想得到32172Q δ=+，则
3220201918(,,)2f Q Q Q δ=+。因此需要给定2020
[18][18]Q Q '=，18[18]0Q =，18[18]1Q '=，这种情况下需对j q δ进行调整。
3．1t t t R Q Q δδδ+=-由定理1可知：给定t T δ，t R δ可能有四种值，当2031k
t T k δ=≤≤，
t t t R T S δδ=<<<的概率最大。一般情况下，我们令t t t R T S δδ=<<<，所以t t t T R S δδ=>>>，又
由于3t t t
t T F Q W δδδδ-=++，我们推出3t t t t Q T F W δδδδ-=--，
设3t j =+得到
：
3
3
3j j j j Q T F W
δδδδ+++=--。
在连接处的第r ，1r +，2r +，3r +步会产生很多的充分条件，如果充分条件之间有冲突，则构造就会失败，为了减少第r ，1r +，2r +，3r +步的充分条件，当
4,5,6,7j r r r r =++++
时我们需要利用3j F δ+减少j Q δ的重量。如果3j F δ+在33j j T W δδ++-中的差分重量的位置没有差分或有差分但不能抵消，不能消除33j j T W δδ++-中的差分重量，则可以通过尝试差分进位。差分进位会产生较多的充分条件，因此差分进位长度不能太大，我们设差分进位长度小于5。如果还是不能消除，则停止。
连接处是否成功取决于下面的方程组是否成立。
766r r r Q Q R δδδ+++=+
655r r r Q Q R δδδ+++=+ 544r r r Q Q R δδδ+++=+ 433r r r Q Q R δδδ+++=+ 322r r r Q Q R δδδ+++=+
211r r r Q Q R δδδ+++=+ 1r r r Q Q R δδδ+=+
11r r r Q Q R δδδ--=+
其中7r Q δ+，6r Q δ+，5r Q δ+，4r Q δ+，3r Q δ+，2r Q δ+，1r Q δ+，r Q δ在倒推的过程中已经求得，其中3r Q δ+，2r Q δ+，1r Q δ+，r Q δ只是部分形式，还需要调整使得上面方程组成立。定理1中()1y x s =<<<+，()2s y x s =<<<-，()21s y x s =<<<-+三种情况比较难控制，我们令y x s =<<<，
即(,)t t t R RL T S δδ=。由公式*可知：
655552()r r r r r r Q Q S W F Q δδδδδ++++++->>>-=+ 544441()r r r r r r Q Q S W F Q δδδδδ++++++->>>-=+ 43333()r r r r r r Q Q S W F Q δδδδδ+++++->>>-=+
由于10r Q δ-=，因此可求得r Q δ。然后进行如下步骤：
1. 令集合}343{2|2k k r r r A Q Q W δδδ+++=±±在，出现且不在中出现,331r r Q W A δ++=-+,1A A ?。
2. 判断766663()r r r r r r Q Q S W F Q δδδδδ++++++->>>-=+是否成立,如果失败,对6r F δ+进位扩散,扩散长度不超过5,使得766663()r r r r r r Q Q S W F Q δδδδδ++++++->>>-=+,如果失败,令1A A A =-,返回步骤1
3. 由式可得3r F δ+，设
{}1321332|22,2,2,2k k k k k k r r B F F δδ+---++=±±±±±±在出现且不在中出现,
{}22|2k k r C B Q δ+=?±±在中出现,{}12|2k k r D B Q δ+=?±±在中出现,
21r Q C δ+=,*1C C C ∈的幂集.11r Q D δ+=,*1D D D ∈的幂集.
4. 利用SC 算法构造r q δ,1r q δ+,2r q δ+,3r q δ+使得方程成立,如果成功,则已经找到一组有效的差分和
一条有效的差分路径.如果失败,若*D ≠?,则令**1D D D =-,返回步骤3,如果*D =?,令**1C C C =-返回步骤3.
表1是使用王教授的差分搜索的差分路径,未列出的差分路径跟[18]一样,我们得出的新差分路径重
量比王教授的少17,所需充分条件要少22.
表1 差分路径
Table 1 T he differential path
t t W t S t W δ t Q
t Q 3m 5 4m 7 312 62- 5[6]Q - 6 5m 12 62- 6[6]Q -
7 6m 17
62322-- 7[6,7,8,9,10,11,12,13,14,15,16,23,24,25,26,27,28,29,30,31]Q --
8
7m 22
151723222---
8[15,17,18,19,20,23,24,25,26,27]Q ---
表2给出了利用我们的差分路径和充分条件得到的一组MD5碰撞消息.
表2 一组MD5碰撞消息
Table 2 A pair of MD5 collision messages
第一组消息 第二组消息 相同的消息摘要
0x4547ABAE,0xCAE497B0, 0xAB577EE7,0x1045E704, 0x55911BF1,0x3D884311, 0x55AD3306,0x0504B402, 0x73E97A7F,0x1139115C, 0xD8749A17,0xCBA2DBA0, 0xE4E57919,0x8EFD1708, 0xBC9B3E08,0x1811F2EA, 0x0B3D68B5,0x8F6A29B3, 0x48F411C5,0xCCA5F90C, 0x20A967D8,0x507AF5AE, 0x4D7F3BCA,0x9B976B45, 0x8EB8D109,0x96ECFDBB, 0xF8989E75,0x9FC13364, 0x965551B3,0x77F07E53, 0x4547ABAE,0xCAE497B0, 0xAB577E67,0x1045E704, 0x55911BF1,0x3D884311, 0x55AD3306,0x0504B402, 0x73E97A7F,0x11B9115C, 0xD8749A17,0xCBA2DBA0, 0xE4E57999,0x8EFD1708, 0xBC9B3E08,0x1811F2EA, 0x0B3D68B5,0x8F6A29B3, 0x48F41145,0xCCA5F90C, 0x20A967D8,0x507AF5AE, 0x4D7F3BCA,0x9B976B45, 0x8EB8D109,0x966CFDBB, 0xF8989E75,0x9FC13364, 0x96555133,0x77F07E53,
0x9B84EFFF,0xC9A6CE7D
4 结束语
MD5算法的软硬实现效率高,同时安全性也比较高,被广泛应用于数字签名,协议认证等安全领域.对MD5攻击也是研究的热点,特别是自王小云提出差分攻击算法攻破SHA-1, MD5,RIPEMD,MD4后.然而如何得到较好的差分,差分路径和充分条件是现在研究的重点 本文考察了MD5算法和差分攻击算法的原理,给出并证明的循环移位差分四种情况的概率,提出了MD5差分路径和充分条件的自动化构造算法,最后给出了我们的试验结果。
参 考 文 献
[1] Xiaoyun Wang, Dengguo Feng , Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HA V AL-128 and
RIPEMD, rump session, CRYPTO 2004, Cryptology ePrint Archive, Report 2004/199, first version (August 16, 2004), second version (August 17, 2004), https://www.doczj.com/doc/c010117421.html,/2004/199.pdf
[2]Marc Stevens Arjen Lenstra Benne de Weger Vulnerability of software integrity and code signing applications to
chosen-prefix collisions for MD5,https://www.doczj.com/doc/c010117421.html,,2007
[3]Sotirov, Alexander，Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger,MD5
considered harmful today,2008
[4]Y. Sasaki, K. Aoki.Finding Preimages in Full MD5 Faster than Exhaustive Search. EUROCRYPT 2009, LNCS ,
[5]Y. Sasaki, L. Wang, N. Kunihiro, and K. Ohta. New Message Differences for Collision Attacks on MD4 and MD5. IEICE
Transactions,91-A(1):55-63, 2008.
[6]Tao Xie, Dengguo Feng, Fanbao Liu. A New Collision Differential For MD5 With Its Full Differential Path. Cryptology
ePrint Archive (2008/230), https://www.doczj.com/doc/c010117421.html,/.
[7]Jiri Vabek, Daniel Joscak, Milan Bohacek, Jiri Tuma. A New Type of 2-Block Collisions in MD5.INDOCRYPT 2008,
LNCS 5365, pp. 78-90.
[8]Tao Xie, Fanbao Liu, Dengguo Feng. Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5?
LNCS 5479, the poster session of EUROCRYPT 2009. Cryptology ePrint Archive, https://www.doczj.com/doc/c010117421.html,/
[9]Marc Stevens, Alex Sotirov, Jake Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger. Short
chosen-prefix collisions for MD5 and the creation of a rogue CA certificate. Cryptology ePrint Archive, Report 2009/111
[10] C. D. Cannire and C. Rechberger. Preimages for Reduced SHA-0 and SHA-1. CRYPTO 2008, LNCS5157, pp179-202.
[11] E. Andreeva, C. Bouillaguet, P.-A. Fouque, J. J. Hoch, J. Kelsey, A. Shamir, and S. Zimmer. Second PreimageAttacks on
Dithered Hash Functions. EUROCRYPT 2008, LNCS 4965, pp 270-288.
[12]G. Leurent.Message Freedom in MD4 and MD5 Collisions:Application to APOP.Fast Software Encryption 2007,
LNCS4593, pp 309-328.
[13]Y. Sasaki, L. Wang, K. Ohta, and N. Kunihiro. Security of MD5 Challenge and Response: Extension of APOP Password
Recovery Attack. CT-RSA 2008, LNCS 4964, pp1-18
[14]Marc Stevens. On Collisions for MD5, Master's Thesis, 2007. TU Eindhoven, Faculty of Mathematics and Com-puter
Science, available at http://www.win.tue.nl/hashclash/
[15]Marc Stevens, Arjen Lenstra, and Benne de Weger. Chosen-prefix collisions for MD5 and colliding X.509certificates for
different identities. EUROCRYPT 2007, LNCS4515, pp1-22
[16]Yu Sasaki, Yusuke Naito, Jun Yajima, Takeshi Shimoyama, Noboru Kunihiro and Kazuo Ohta How to Construct Sufficient
Condition in Searching Collisions of MD5 2006
[17]M. Daum. Cryptanalysis of Hash Functions of the MD4-Family. PhD thesis, Ruhr-University of Bochum, 2005
[18]Xiaoyun Wang and Hongbo Yu How to Break MD5 and Other Hash Functions Eurocrypt2005