密码学/破解哈希算法

从密码学的角度来看，密码学哈希函数是最难破解的东西之一。

密码学哈希函数专门设计为“单向”：如果你有一些消息，很容易向前推导出相应的哈希值；但如果你只有哈希值，密码学哈希函数专门设计为难以计算出产生该哈希值的原始消息——或任何其他产生相同哈希值的的消息。

正如我们在之前的哈希中提到的，密码学安全的哈希旨在具有以下属性

• 抗原像：给定 H，应该很难找到 M 使得 H = hash(M)。
• 抗第二原像：给定输入 m1，应该很难找到另一个输入 m2（不等于 m1）使得 hash(m1) = hash(m2)。
• 抗碰撞：应该很难找到两个不同的消息 m1 和 m2 使得 hash(m1) = hash(m2)。

密码学家区分对哈希函数的三种不同类型的攻击

• 碰撞攻击：尝试找到任何两个不同的消息 m1 和 m2 使得 hash(m1) = hash(m2)。
• 原像攻击：仅给定哈希值 H，尝试恢复 *任何* M 使得 H = hash(M)。
• 第二原像攻击：给定输入 m1，尝试找到另一个输入 m2（不等于 m1）使得 hash(m1) = hash(m2)。
• 一些哈希函数（MD5、SHA-1、SHA-256 等）容易受到“长度扩展攻击”。

（唉，不同的密码学家对这三种攻击使用不同的，有时是矛盾的术语。在这本书之外，一些密码学家使用“碰撞”来指代对这三种攻击类型的任何一种的成功攻击，并使用术语“自由碰撞”来指代本书所说的“成功碰撞攻击”，或“绑定碰撞”来指代“成功原像攻击”或“成功第二原像攻击”中的任何一种。）

在设计需要哈希函数的新系统时，大多数密码学家建议使用据我们所知能够抵抗所有这些攻击的哈希函数（例如 SHA-3、BLAKE、Grøstl、Skein 等）。

碰撞攻击是最容易的攻击类型，也是最难防御的攻击类型。 由于有无限数量的可能的邮件，鸽笼原理告诉我们，理论上存在无限数量的哈希碰撞，即使对于“理想的”随机预言机哈希也是如此。 密码学哈希旨在使其难以——仅使用我们太阳系中可用的资源，在实际上是不可能的——找到 *任何* 这些哈希到给定哈希值的邮件。

一些应用程序需要抗碰撞性。 当可能的攻击者生成一条消息，并且我们想要确认该人向爱丽丝展示的消息与该人向鲍勃展示的消息相同，以确保消息完整性时，我们需要一个具有抗哈希碰撞性的哈希。

许多应用程序实际上不需要抗碰撞性。 例如，密码哈希需要抗原像和抗第二原像（以及其他一些特殊特性），但不需要抗碰撞性。 例如，重复数据删除文件系统、主机证明文件系统（如 IPFS）、数字签名等，仅需要抗第二原像性，不需要抗原像或抗碰撞性，因为在这些应用程序中，假设攻击者已经知道哈希到给定值的原始消息。 例如，使用 HMAC 的消息认证不需要抗碰撞性，并且不受长度扩展的影响；因此，截至 2011 年，密码学家认为在现有应用程序中使用 HMAC-MD5 消息认证是可以接受的，尽管他们建议新应用程序使用其他一些替代方法，例如 HMAC-SHA256 或 AES-CMAC。

在实际上不需要抗碰撞性的应用程序中，MD5 和 SHA-1 哈希函数仍然被认为是足够的。

许多人出于错误的原因批评 MD5 和 SHA1。 目前没有已知的针对 MD5 或 SHA-1 的实际或近似实际的抗原像攻击，更不用说抗第二原像攻击了，只有碰撞攻击。

这些碰撞攻击包括

• Dobbertin 在 1996 年宣布了 MD5 压缩函数的碰撞...
• 截至 2009 年，在笔记本电脑上找到 MD5 中的选定前缀碰撞大约需要 30 秒。
• Manuel 和 Peyrin 的 SHA-0 攻击
• Nat McHugh 的 MD5 碰撞攻击

• 等等
• 等等

在接下来的章节中，我们将讨论

• 碰撞
• 生日攻击
• 彩虹表