简介

Merkle–Damgård 构造简称为 MD 构造，次要用在 hash 算法中抵挡碰撞攻打。这个构造是一些优良的 hash 算法，比方 MD5,SHA- 1 和 SHA- 2 的根底。明天给大家解说一下这个 MD 构造和对他进行的长度延展攻打。

MD 构造

MD 构造是 Ralph Merkle 在 1979 年的博士论文中形容的。因为 Ralph Merkle 和 Ivan Damgård 别离证实了这个构造的合理性，所以这个构造被称为 Merkle–Damgård 构造。

接下来，咱们看下 MD 构造是怎么工作的。

MD 构造首先对输出音讯进行填充，让音讯变成固定长度的整数倍（比方 512 或者 1024）。这是因为压缩算法是不能对任意长度的音讯进行解决的，所以在解决之前必须进行填充。

通常来说，咱们会应用恒定的数据，比如说 0 来填充整个音讯块。

举个例子，如果咱们的音讯是“HashInput”，压缩块的大小是 8 字节（64 位），那么咱们的音讯将会被分成两个块，前面一个块应用 0 来填充，将会失去：“HashInpu t0000000”。

然而这样做往往是不够的，因为通常对于压缩函数来说，会删除掉最初面的额定的 0，所以导致填充和不填充最初计算出来的 hash 值是一样的。

为防止这种状况，必须更改填充常量数据的第一位。因为常量填充通常由零组成，因而第一个填充位将强制更改为“1”。

也就是“HashInpu t1000000”。

咱们还能够对填充进行进一步的加强，比方应用一个额定的 block 来填充音讯的长度。

然而额定的应用一个 block 往往有点节约，一个更加节约空间的做法就是，如果填充到最初一个 block 的 0 中有住够的空间的话，那么能够音讯的长度放在那里。

填充好 block 之后，接下来就能够对音讯进行压缩了，咱们看下一下 MD 的流程图：

音讯被分成了很多个 block，最开始的初始化向量和第一个 block 进行 f 操作，失去了的后果再和第二个 block 进行操作，如此循环进行，最终失去了最初的后果。

长度延展攻打

在密码学中长度延展攻打就是指攻击者通过已知的 hash(message1) 和 message1 的长度，从而可能晓得 hash（message1‖message2）的值。其中‖ 示意的是连接符。并且攻击性并须要晓得 message1 到底是什么。

上一节咱们讲到的 MD 构造，是将音讯分成一个一个的 block，前一个 block 运算进去的值会跟下一个 block 再次进行运算，这种构造能够很不便的进行长度延展攻打。前提是咱们须要晓得原音讯的长度。

咱们举个例子，假如咱们有上面的申请：

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

下面的例子是给编号为 1 的用户发送鸡蛋馅的华夫饼，并附带了音讯签名，以保障音讯的正确性。这里音讯签名应用的 MAC 算法。

如果歹意攻击者想把 waffle 的值从 eggo 批改成为 liege。

那么新的数据将会是这样的：

count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

为了对该新音讯进行签名，通常，攻击者须要晓得该音讯签名应用的密钥，并通过生成新的 MAC 来生成新的签名。然而，通过长度扩大攻打，能够将哈希（下面给出的签名）作为输出，并在原始申请已中断的中央持续进行 hash 输入，只有晓得原始申请的长度即可。

如果思考到 padding（音讯填充）的影响的话，咱们还须要复原原始音讯的填充内容，而后在复原过后的内容之后再增加咱们的攻打代码：

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x02\x28&waffle=liege

这样咱们就能够失去新的 MAC 值：

New Signature: 0e41270260895979317fff3898ab85668953aaa2

Wide pipe

为了防止长度延展攻打，咱们能够对 MD 构造进行一些变形。

先看一下 Wide Pipe 构造：

wide pipe 和 MD 的流程基本上是统一的，不同的是生成的两头长期的加密后的音讯长度是最终生成音讯长度的两倍。

这也就是为什么上图中会有两个初始向量 IV1 和 IV2。如果最终的后果长度是 n 的话，那么在两头生成的后果的长度就是 2n。咱们须要在最初的 final 这一步中，将 2n 长度的数据缩减为 n 长度的数据。

SHA-512/224 和 SHA-512/256 只是简略的抛弃掉一半数据。

Fast wide pipe

还有一种比 wide pipe 更快的算法叫做 fast wide pipe：

和 wide pipe 不同的是，它的次要思维是将前一个链接值的一半转发给 XOR，而后将其与压缩函数的输入进行 XOR。

本文已收录于 http://www.flydean.com/md-length-extension/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！