密码学系列之:Merkle–Damgård 结构和长度延展攻击
简介
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 再次进行运算，这种结构可以很方便的进行长度延展攻击。前提是我们需要知道原消息的长度。
我们举个例子，假设我们有下面的请求：
上面的例子是给编号为 1 的用户发送鸡蛋馅的华夫饼，并附带了消息签名，以保证消息的正确性。这里消息签名使用的 MAC 算法。
假如恶意攻击者想把 waffle 的值从 eggo 修改成为 liege。
那么新的数据将会是这样的：
为了对该新消息进行签名，通常，攻击者需要知道该消息签名使用的密钥，并通过生成新的 MAC 来生成新的签名。但是，通过长度扩展攻击，可以将哈希（上面给出的签名）作为输入，并在原始请求已中断的地方继续进行 hash 输出，只要知道原始请求的长度即可。
如果考虑到 padding（消息填充）的影响的话，我们还需要恢复原始消息的填充内容，然后在恢复过后的内容之后再添加我们的攻击代码：
这样我们就可以得到新的 MAC 值：
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/
最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！
欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！
版权声明: 本文为 InfoQ 作者【程序那些事】的原创文章。
原文链接:【http://xie.infoq.cn/article/f652e16b815b60e67bc62814b】。文章转载请联系作者。
关注公众号：程序那些事，更多精彩等着你！ 2020.06.07 加入
最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧，尽在公众号：程序那些事！
评论