我了解在MD5中填充的必要性。但是为什么我们将消息长度附加到填充上？

我听说它增强了哈希，但是又如何呢？ ：


长度块的包含有效地编码了所有消息，例如，没有编码输入是任何其他编码输入的尾端。


为什么一条消息作为另一条消息的结尾是不好的（如果是）？

#1 楼

像其他哈希函数一样，MD5使用Merkle-Damgard构造。您将消息分解成固定大小的块。您从初始化向量（IV）开始，将其与第一个块一起输入到压缩函数中。取得输出（与IV的长度相同），并将其与第二个消息块一起馈入压缩函数，依此类推。

调用压缩函数$ c $和“原始”（未填充）哈希函数$ h $，我们有$$ \ begin {align *} h（ZABCD）＆= c（h（ZABC），D）\\＆= c（c（h（ZAB）， C），D）\\＆= c（c（c（h（ZA），B），C），D）\\＆= c（c（c（c（c（h（Z（Z），A），B） ，C），D）\\＆= c（c（c（c（c（c（I，Z , A），B），C），D）\ end {align *} $$具有固定的初始化向量$ I $（每个字母代表一个块）。

不同的哈希函数使用不同的压缩函数。目的是证明只有在压缩函数中找到冲突时，才能在哈希函数中找到冲突（下一步将是证明在压缩函数中找到冲突非常困难）。 >
这种论点如何起作用？我们可以重述一下我们的目标，如下所示：

如果给我两条导致哈希函数发生冲突的消息，我可以为压缩函数找到两对导致冲突的输入。 >
这是我实现这一目标的方法：我接受您给我的两条消息，并将它们分成几块。然后，我找到了两个消息没有共同点的最右边的块。例如，如果第一个消息（填充后）具有$ ZABCD $块，而第二个消息具有$ XKCD $块，则右边的第三个块是不同的（$ B $与$ K $）。

由于$ h（ZABCD）= h（XKCD）$，因此我检查$ h（ZABC）= h（XKC）$。如果不是，我有冲突：

$$ h（ZABCD）= c（h（ZABC），D）= c（h（XKC），D）= h（XKCD）。 $$

另一方面，如果$ h（ZABC）= h（XKC）$，对于$ c $而言这并不是真正的冲突，因为输入值相同。因此，我返回一个块，看看$ h（ZAB）= h（XK）$，然后做同样的事情。如果它们不相等，则发生冲突：$ c（h（ZAB），C）= c（h（XK），C）$。如果它们相等，我再返回另一个程序段。

但是现在$ B \ neq K $，我不必担心$ h（ZA）= h（X） $。我知道$ c（h（ZA），B）= c（h（X），K）$（因为$ h（ZAB）= h（XK））$，并且由于$ B $和$ K $是不同的，这是一个冲突–不同的输入，相同的输出。

我可以针对生成散列函数冲突的任何一对输入进行此过程，以便找到导致压缩函数的一对输入碰撞。 QED，对吗？

但是等等！
如果我从右到左走，在我发现两个不同的块之前，我用光了块呢？然后论据中断了。因此，为了使该参数起作用，我需要使用填充方案来确保一个（填充的）消息永远不会成为另一个消息的末尾。

评论

$ \ begingroup $
我假设我理解您的意思，但是您假设我们能够获得2个具有相同哈希值的消息，并且如果我们能够实现这一点，那为什么还要进一步证明压缩功能如果不好？这会给我们带来什么或证明，您的意思是什么？
$ \ endgroup $
– AB Najjar
2011年12月9日在23:08
$ \ begingroup $
不，如果一个消息位于另一消息的末尾，则它们不一定会发生冲突。我不知道IV是如何选择的（我的第一个猜测是有人会随机选择它），但是MD5的压缩功能是Davies-Meyer构造。参见（en.wikipedia.org/wiki/One-way_compression_function）；内部的H，G，F，I函数实际上是在实现分组密码。因此，我怀疑，如果您想学习这些功能的动机，就必须研究分组密码的构造。现代加密通常遵循这种模式：从简单的事物构建复杂的事物。
$ \ endgroup $
–赛斯
2011-12-10 4:19
$ \ begingroup $
@fgrieu我想指出的是，当哈希XYZ之后的内部状态再次成为初始化向量时，我们希望避免ABCD哈希到与XYZABCD相同的事物（每个字母为一个块）。这就是那里提到的“块用尽”。简单的10000 ...填充在这里将无济于事，它仅有助于抵御最简单的附加攻击。
$ \ endgroup $
–PaŭloEbermann
2011年12月10日下午16:37
$ \ begingroup $
@fgrieu（@Paŭlo和@Paulo都可以ping通我...只使用自动完成建议的内容，或者更容易键入的内容。）我认为这取决于碰撞的定义压缩函数-如果每个$ c（x_1，y_1）= c（x_2，y_2）$加上$（x_1，y_1）\ neq（x_2，y_2）$，那么$ c $中确实会有一些冲突或带有$ I $的原像的“消息尾”，如前所述）。而这似乎就是答案中证明的想法。 （当然必须存在一些冲突，问题在于如何找到它们。）
$ \ endgroup $
–PaŭloEbermann
2011-12-10 18:40


$ \ begingroup $
知道了。如果我们考虑在完整散列中发生冲突，则长度允许在$ c $上发生冲突[如$ c（x_i，y_i）= c（x_j，y_j）$且$（x_i，y_i）\ neq（x_j ，y_j）$]，包括在演示的分支中，我们在其中考虑不同长度的消息（冲突必须存在于最后一个块中）。如果没有填充的长度，则可能是在较长的消息中，$ x_0 $在某个时刻被击中，我们只能显示$ c（x_i，y_i）= x_0 $;这对$ c $将是毁灭性的打击，但不是碰撞。
$ \ endgroup $
–fgrieu♦
2011-12-11 7:13


#2 楼

Merkle–Damgård散列结构通常将要散列的消息$ M $填充为1，将单个位设置为1，将最小位数设置为0，并以固定形式将消息的长度表示为二进制位数。然后，填充的消息由多个块$ B_i $组成。通过重复应用压缩函数$ C $：$（X，B）\ rightarrow C（X，B）$，得出$$ H（M）= C（C（.. C（C（IV， B_0），B_1）.. B_ {k-2}），B_ {k-1}）$$

问题是：为什么要填充长度？

在填充中保留长度可以简单地证明安全性：两个已知不同消息之间的完全哈希冲突允许在基础压缩函数中表现出冲突$ C $，即展示$ X，B，X'，B'$，其中$ C（X，B）= C（X'，B'）$和$（X，B）\ ne（X'，B '）$。

证明草图如下：


如果不同的冲突消息长度不同，则最后一次在$ C $中发生冲突块：我们知道$ B_ {k-1}，B'_ {k-1} $是不同的，因为它们包含长度；
如果不同的冲突消息具有相同的长度，则存在定义明确的最右边的块，其中填充的消息有所不同，并且当我们从填充的消息的右边一直到该块扫描$ C $中的冲突时，就会表现出冲突。

没有填充的长度，我们仍然可以有一个安全性证明，但是在$ C $上有更强的假设：两个已知的不同消息之间的全散列冲突允许在上述$ C $中显示冲突，或者显示原图像对于散列定义中给出的$ IV $常量，则显示$ X，B $，且$ C（X，B）= IV $。证明更加复杂：我们必须根据消息是否具有相同的填充长度来对情况1进行细分；在否定的进一步细分中，取决于最短填充消息是否与最长消息的结尾匹配；肯定的是，我们不会发生冲突，而只是$ IV $的原像。没有填充的长度，并且用未知来源的常量替换IV，可以进行如下明确的攻击。考虑类似于MD5或SHA-256的哈希变体，具有以下两个区别： （s）设置为0以填充最后的512位块）；
$ IV $是一些看起来很随机的值（而不是通过增加MD5中的十六进制数字或平方的小数部分得出） SHA-256中前8个质数的根）。

MD5和SHA-256中使用的压缩函数$ C $的格式为
$$（X，K）\ rightarrow C（X，K）= X \ tilde + E（X，K）$$
其中$ \ tilde + $是加法的变体（一些进位被抑制），而$ X \ rightarrow E（X， K）$是具有密钥$ K $的可逆分组密码。

谁定义了$ IV $可以选择一个秘密的512位$ K $，计算得出的$ IV = E ^ {-1} （0，K）$，可确保$ IV = C（IV，K）$，从而允许在任何消息的开头插入$ K $，而无需更改哈希。

摘要：长度允许更简单，更严格的安全证明。据我所知，它不是必不可少的，前提是压缩功能$ C $可以抵抗原像，并且选择$ IV $时不必参考$ C $。

[此新功能答案与我之前的尝试无关，并且受到塞思之前的答案的强烈启发]

评论

$ \ begingroup $
对其他答案的评论总结不错，谢谢。
$ \ endgroup $
–PaŭloEbermann
2011-12-11 14:02
$ \ begingroup $
写得好，并指出我应该提到的要点。
$ \ endgroup $
–赛斯
2011-12-11 20:56


#3 楼

任何Merkle–Damgård构造的保留碰撞填充规则都有一个漂亮的特征：填充规则应无后缀。有关更多详细信息，请参阅Mridul Nandi在2009年发表的论文《表征MD哈希函数保持碰撞安全性的填充规则》。

消息的长度实际上是最简单的填充形式，没有后缀。本文中的证明是自包含的，非常容易理解，因此我没有提出证明的草图。