HASH GAME - Online Skill Game GET 300

　　• (3) 攻击者在上述两个消息集合中找出可以产生相同 散列值的一对消息。根据“生日悖论”理论，能找 到这样一对消息的概率是非常大的。如果找不到这 样的消息，攻击者再产生一条有效的消息和伪造的 消息，并增加每组中的明文数目，直至成功为止。 (4) 攻击者用第一组中找到的明文提供给签名方要求 签名，这样，这个签名就可以被用来伪造第二组中 找到的明文的数字签名。这样，即使攻击者不知道 签名私钥也能伪造签名。

　　• 如果攻击者希望伪造消息M的签名来欺骗接收者， 则他需要找到满足H(M’)=H(M)的M’来替代M。 对于生成64位散列值的散列函数，平均需要尝 试263 次以找到M’。但是建立在生日悖论上的生 日攻击法，则会更有效。 对于上述问题换种说法：假设一个函数有n个函 数值，且已知一个函数值H(x)。任选k个任意数 作为函数的输入值，则k必须为多大才能保证至 少找到一个输入值y且H(x)=H(y)的概率大于0.5?

　　• 1）填充消息：任意长度的消息首先需要进行填充处理， 使得填充后的消息总长度与448模512同余（即填充后的 消息长度448 mod 512）。填充的方法是在消息后面添 加一位“1”，后续都是“0”。 • 2）添加原始消息长度：在填充后的消息后面再添加一个 64位的二进制整数表示填充前原始消息的长度。这时经过 处理后的消息长度正好是512位的倍数。 • 3）初始值（IV）的初始化：MD5中有四个32位缓冲区， 用（A, B, C, D）表示，用来存储散列计算的中间结果和 最终结果，缓冲区中的值被称为链接变量。首先将其分别 初始化为为：A=0x01234567，B=0x89abcdef， C=0xfedcba98，D=0x76543210。

　　• • 攻击者针对下面的MAC算法，则不需要使用穷举攻击即可获 得密钥信息。 设消息M＝(X1X2…Xm)，即由64位分组Xi联结而成。定义 Δ(M)＝X1X2… Xm Ck(M)=EK[Δ(M)] 攻击者可以用任何期望的Y1至Ym-1替代X1至Xm-1，用Ym替代 Xm来进行攻击，其中Ym如下计算的： Ym＝Y1Y2…Ym-1Δ(M) 攻击者可以将Y1至Ym-1与原来的MAC连结成一个新的消息M’， 接收方收到(M’, Ck(M))时，由于Δ(M’)= Y1 Y2… Ym =Δ(M)，因此Ck(M)=EK[Δ(M’)]，接受者会认为该消息是真实。 用这种办法，攻击者可以随意插入任意的长为64(m-1)位的 消息。

　　• MD5（Message-Digest Algorithm 5）是由 Ronald L. Rivest（RSA算法中的“R”）这90年代初开发 出来的，经MD2、MD3和MD4发展而来。它比MD4复杂， 但设计思想类似，同样生成一个128位的信息散列值。其 中，MD2是为8位机器做过设计优化的，而MD4和MD5却 是面向32位的计算机。 • 2004年8月，在美国召开的国际密码学会议（Crypto’2004） 上，王小云教授给出破解MD5、HAVAL-128、 MD4和 RIPEMD算法的报告。给出了一个非常高效的寻找碰撞的 方法，可以在数个小时内找到MD5的碰撞。