2

我一直在消息摘要领域进行一些初步研究。特别是加密散列函数（例如 MD5 和 SHA-1）的冲突攻击，例如Postscript 示例和X.509 证书副本。

据我所知，在 postscript 攻击的情况下，生成了特定数据并将其嵌入到 postscript 文件的标题中（在渲染过程中被忽略），这导致 md5 的内部状态处于修改后的措辞文档的最终 MD 值与原始 postscript 文件相同。X.509 采用了类似的方法，将数据注入证书的注释/空白部分。

好的，这是我的问题，我似乎找不到任何人问这个问题：

  1. 为什么不将仅消耗的数据的长度作为最终块添加到 MD 计算中？

  2. 在 X.509 的情况下 - 为什么将空格和注释作为 MD 的一部分考虑在内？

诸如以下之一的简单过程是否不足以解决建议的碰撞攻击：

  1. MD(M + |M|) = xyz
  2. MD(M + |M| + |M| * magicseed_0 +...+ |M| * magicseed_n) = xyz

在哪里 ：

  1. M : 是消息
  2. |M| : 消息的大小
  3. MD ：是消息摘要函数（例如：md5、sha、whirlpool 等）
  4. xyz : 是消息 M 和 |M| 的实际消息摘要值的配对。<M,|M|>
  5. magicseed_{i}：是一组随机值，​​由种子根据添加大小之前的内部状态生成。

该技术应该有效，因为迄今为止所有此类碰撞攻击都依赖于向原始消息添加更多数据。

简而言之，生成碰撞消息所涉及的难度级别如下：

  1. 它不仅生成相同的MD
  2. 但也是可理解的/可解析的/兼容的
  3. 并且与原始消息的大小相同，

如果不是几乎不可能的话，也是非常困难的。有没有讨论过这种方法？任何指向论文等的链接都会很好。

进一步的问题：对于从 U 中随机选择的散列函数 H，公共长度的消息冲突的下限是多少，其中 U 是通用散列函数的集合？

是 1/N（其中 N 是 2^(|M|)）还是更大？如果它更大，则意味着有超过 1 条长度为 N 的消息将映射到给定 H 的相同 MD 值。

如果是这样的话，找到这些其他消息有多实用？蛮力将是O（2 ^ N），有没有一种时间复杂度低于蛮力的方法？

4

2 回答 2

0

不能说剩下的问题，但第一个问题相当简单——在散列过程的任何阶段（第一个块、第 N 个块、最后一个块）将长度数据添加到 md5 的输入中只会改变输出哈希。之后您无法从输出哈希字符串中检索该长度。不可能从另一个长度完全相同的字符串产生冲突也不是不可想象的，所以说“原始字符串是 17 个字节”是没有意义的，因为冲突的字符串也可能是 17 个字节。

例如

md5("abce(17bytes)fghi") = md5("abdefghi<long sequence of text to produce collision>")

还是有可能的。

于 2011-01-14T05:51:55.423 回答
0

特别是在 X.509 证书的情况下，“注释”不是编程语言意义上的注释：它们只是带有 OID 的附加属性，表明它们将被解释为注释。证书上的签名被定义为包含所有附加属性的整个tbsCertificate（“待签名”证书）结构的 DER 表示。

不过，散列函数设计是相当深奥的理论，可能在Theoretical CS Stack Exchange上得到更好的服务。

但是，正如@Marc 指出的那样，只要可以修改的位多于散列函数的输出所包含的位，那么根据鸽巢原理，某些输入对就必须存在冲突。由于密码散列函数通常被设计为在其输入上表现出伪随机性，因此冲突将倾向于均匀分布在可能的输入上。

编辑：将消息长度合并到散列函数的最后一个块中相当于将之前所有内容的长度附加到输入消息中，因此实际上不需要修改散列函数来执行此操作；相反，将其指定为给定上下文中用法的一部分。我可以看到这会使某些类型的碰撞攻击更难实施，因为如果您更改消息长度，则攻击修改的区域的“下游”字段会发生变化。但是，这不一定会阻止X.509 中间 CA 伪造攻击，因为 的长度tbsCertificate没有被修改。

于 2011-01-14T05:54:30.973 回答