防范密码分析突破：结合多个哈希函数

#1 楼

SSL / TLS在其内部“ PRF”（实际上是密钥派生功能）的定义中对MD5和SHA-1进行了组合。对于给定的哈希函数，TLS定义了一个KDF，该KDF依赖于HMAC，而HMAC则依赖于哈希函数。然后，两次调用KDF，一次使用MD5，一次使用SHA-1，然后将结果异或在一起。这个想法是为了抵抗MD5或SHA-1中的密码分析中断。请注意，对两个哈希函数的输出进行异或运算取决于微妙的假设。例如，如果我为固定常数$ C $定义$ \ mathrm {SHB-} 256（m）= \ mathrm {SHA-} 256（m）\ oplus C $，那么SHB-256就是一个很好的哈希用作SHA-256;但两者的XOR总会产生$ C $，对于哈希目的而言，这根本不好。因此，TLS的构造并没有真正受到科学权威的认可（恰好没有被破坏）。 TLS-1.2不再使用该组合。它依赖于具有单个可配置哈希函数的KDF，通常为SHA-256（在2011年是明智的选择）。哈希函数的构建。该书由Joux于2004年出版，然后由Hoch和Shamir于2006年推广，涉及涉及迭代和级联的大量构造。但是请留意细则：这并不是要真正解决哈希函数中的弱点，而是要使自己的钱物有所值。也就是说，如果您将一个具有128位输出的哈希函数和另一个具有160位输出的哈希函数进行连接，然后将结果连接起来，那么抗冲突性将不会比这两者中最强的一个差； Joux展示的是，它也不会更好。使用$ 128 + 160 = 288 $位的输出，您可以瞄准$ 2 ^ {144} $的阻力，但是Joux的结果表明您不会超出$ 2 ^ {87} $的范围。

因此，问题就变成了：是否有一种方法，如果可能的话，可以组合两个哈希函数，使得结果与两个哈希函数中的最强函数一样具有抗冲突性，而又不会导致串联的输出扩大？在2006年，Boneh和Boyen发表了一个结果，该结果简单地指出答案是“否”，但前提是每个哈希函数只能评估一次。

编辑：Pietrzak在2007年解除了后一种情况（即多次调用每个哈希函数无济于事）。

#2 楼

您对原始问题的想法是正确的。如果要防止的是原图像，则链接哈希函数会产生至少与其两个分量中最强的函数一样强的函数：

$$ H _ {\ circ}（x）= H_0 （H_1（x））$$

如果要防止碰撞，则串联的强度至少要强于其两个分量中的最强强度：

$ $ H_ {|}（x）= H_0（x）| H_1（x）$$

组合函数可能还需要其他一些属性，例如伪随机性。对于伪随机性，您可以将两个哈希函数结合在一起，例如： >最棘手的部分（如您所观察到的）是您是否要拥有这些属性中的多个。到目前为止，我所知道的最好的研究是Anja Lehmann的论文。 （您可以在Tahoe-LAFS项目的“一百年密码学”维基上找到有关此主题和相关主题的讨论。）

如果我需要安全哈希函数中的多个属性，并且不必理会额外的CPU周期，也不介意将输出大小增加一倍，那么我可能会使用雷曼（Lehmann）的$ Comb_ {4P} $结构，而不必太担心结果组合功能可能无法保留预图像抵抗力。

如果您确定只需要一个属性（请注意此处-请仔细考虑，并明确写下您依赖的一个或多个属性，以及攻击者可以做什么）每个可能的属性均不成立），则可以安全地使用上述组合器之一。

顺便说一句，该论文还包含了在该线程中讨论的其他两个主题的非常有趣的结果：是否可以具有组合函数$ C（H_1，H_2）$，其抗碰撞性比$的强度强。 H_1 $加上$ H_2 $的强度（她肯定地回答），以及SSL和TLS结合SHA1和MD5的方式是否安全（答案：有点...）。

#3 楼

我相信@Thomas会给出详尽的答案。在此期间，我只想指出您的第一个构造$ H_1（m）|| H_2（M）$的耐碰撞性并不比$ H_1（M）$好多少。请参阅本文的第4节：

迭代哈希函数中的多重冲突。在级联结构中的应用。

#4 楼

好吧，我看到了两种切实可行的方法来抵抗这些漏洞。

如果要使用两个哈希函数，请确保将HMAC中的原始数据反馈给第二个函数：

hash = algo1(data)
hash = hmac(algo2, data, hash)

这里的好处是，由于MAC的缘故，algo1的任何冲突都不会自动成为algo2的冲突。因此，为了使碰撞攻击起作用，攻击者必须使用相同的源数据为两个功能找到碰撞。实际上，这比独立地攻击两个功能要困难得多（这至少与攻击两个功能中的最强功能一样困难）。

另一种方法是简单地迭代单个哈希功能（带反馈）。这看起来与以前的算法相似。

hash = hmac(algo1, pack('N', 1), data)
for (i = 0 ... n) 
    hash ^= hmac(algo1, hash, data)

其中n大于或等于0。它越大，计算速度就越慢。请注意，这基本上只是带有空盐的PBKDF2，并且将length参数设置为哈希的输出大小。

“拉伸”的好处在于，它既可以防止原图攻击也可以防止碰撞攻击，因为即使攻击者能够在第一轮找到原图，仍然需要多轮攻击。考虑到反馈，攻击特定回合所需的数据将在下一轮被销毁。因此，即使攻击者确实设法完成了一轮原像攻击，也很难（如果不是不可能）攻击另一轮。

#5 楼

怎么样，比如对基本哈希函数输出的位进行交织以生成密钥（依次从每个哈希中获取一位，跳过没有剩余未合并位的哈希），然后使用每个具有很多位的基本哈希函数生成HMAC可以使用的密钥数量： H（x）= HMAC_ {H_0}（K（x），x）\ | HMAC_ {H_1}（K（x），x）\ | HMAC_ {H_2}（K（x），x）$$

这样，每个HMAC理论上都依赖于所有哈希算法。您可能不希望将$ K（x）$的前几位用于$ HMAC_ {H_0} $的密钥，而是将$ HMAC_ {的后几位使用$ K（x）$ H_1} $，依此类推，将$ K（x）$与自身连接在一起，以获得足够的位来键控所有HMAC。 ）$（等）作为您的哈希，对于$ H $的每次调用（以及对$ K（x）$的相应调用），可能以不同的顺序使用基本哈希函数。

#6 楼

有一篇研究论文解释了为什么链哈希不能从随机预言的不可区分性上提供更好的安全性

#7 楼

使用修改后的双工结构。首先通过$ h_1 $运行消息，然后获取结果的最后32位，然后将其与512位IV的前32位进行XOR运算。然后将IV放入512位哈希函数$ h_2 $。然后使用哈希函数的前32位并将其放入哈希缓冲区。重复此过程，直到将足够的哈希放入缓冲区中为止。我知道，速度是$ n（h + i）$，其中$ h $是$ h_1 $的速度，$ i $是$ h_2 $的速度，$ n $是回合数。但是，如果$ h_1 $和$ h_2 $确实非常快，那将是个好消息！

#8 楼

组合的哈希函数只是一个哈希函数，将具有它自己的理论和实践漏洞。

我的断言是，可以设计两个哈希函数$ H_1 $和$ H_2 $使得$ H_1 $好，$ H_2 $好，但是$ H_1 + H_2 $很弱。

因此，通过组合两个哈希函数，可以实现相反的效果。是否必须独立建立。