开发者工具 · SHA 哈希计算器
Merkle–Damgård 解释：SHA-1 和 SHA-2 背后的构造
· 背景
sha-256 密码学 浏览器 API
固定大小的压缩函数无法自行散列任意输入。 Merkle-Damgård 将其逐块链接起来；这篇文章解释了它的结构、证明思想以及它的弱点。
任意输入，固定输出——每个哈希函数首先要解决的问题
哈希函数必须将任意输入映射到固定输出。三个字节的消息和三个兆字节的消息都必须为 SHA-256 准确生成 256 位的输出。哈希必须是确定性的，因此相同的输入总是产生相同的输出。输出看起来必须是随机的；改变输入的单个位应该改变大约一半的输出位。
乍一看，这些是矛盾的要求，因为单个快速算法无法处理任意长度的消息并产生统一的固定宽度输出。 Merkle-Damgård 结构通过重复使用固定大小的压缩函数，将每个应用程序的输出输入到下一个应用程序的输入中，解决了这个问题。此结构由 SHA-1 和所有 SHA-2 （SHA-256、SHA-384 和 SHA-512）使用。
压缩函数 — 一个固定大小的混合器，它接受一个状态和一个块并返回一个新状态
压缩函数是为 Merkle–Damgård 哈希提供支持的核心加密原语。它采用固定大小的状态，通常为 SHA-256 的 256 位，或为 SHA-512 的 512 位，以及固定大小的输入块，通常为 SHA-256 的 512 位，或为 SHA-512 的 1024 位。压缩函数使用按位运算、旋转和表查找将它们混合在一起，产生相同大小的新状态。这个函数必须是抗冲突的：找到产生相同输出的两个不同的（状态，块）对一定很困难。
压缩函数本身并不是一个完整的哈希函数——它不处理任意输入长度，甚至不处理没有先前状态的第一个输入。相反，它是建造更大建筑的基石。压缩函数是唯一重复运行的密码操作；其他一切都是簿记，将该函数连接到完整的哈希值。
链接和初始化向量 - 块如何从固定的起始状态相互馈送
初始化向量是固定的起始状态，仔细选择以避免对称或弱点。对于 SHA-256，IV 是从前八个质数的平方根的小数部分派生的八个 32 位字。这些值是任意的但具有确定性，因此每个实现都会产生相同的结果。第一个消息块使用压缩函数与 IV 混合，产生一个新的状态。第二个消息块与该状态混合，产生另一个新状态，依此类推，直到消息的每个块。
这种链接是关键部分：一个块的输出取决于所有先前的块，因此更改任何先前块的任何位都会更改所有后续块。当处理最后一个块时，状态包含有关输入每一位的信息。填充是让这个结构听起来更合理的技巧。消息并不总是均匀地分成块。 Merkle-Damgård 结构使用 MD 强化：在消息中附加一位，然后附加零，直到剩下几乎一个完整的块，然后附加原始消息长度。
用消息长度填充——为什么 MD 强化使得结构听起来更合理
Merkle–Damgård 的安全论点说，如果压缩函数是抗碰撞的，那么整个哈希就是抗碰撞的。证明是一个简化：如果你能在哈希中找到冲突，你就可以在压缩函数中提取冲突，这与压缩函数难以冲突的假设相矛盾。直觉是，哈希中的任何冲突最终都必须在压缩函数调用之一中产生冲突，因为状态被完全向前推进。
尽管基本结构很健全，但随着时间的推移，Merkle–Damgård 的弱点也被发现了。长度扩展就是其中之一：看到消息摘要的攻击者可以扩展消息并计算较长消息的有效摘要，而无需了解有关输入的任何信息。第二个原像攻击是另一种：给定一条消息，找到具有相同哈希值的不同消息比某些类型的消息更容易。这些弱点激发了 SHA-3 的设计，它使用了一种称为海绵结构的不同方法。
长度编码填充分隔填充消息；完整的安全证明是外部存储库证据
SHA-256 的压缩函数采用 256 位状态（八个 32 位字）和 512 位块。该操作使用 64 轮，每轮将状态与块中的常量和字混合。混合使用按位运算：XOR、AND、NOT。它使用旋转和移位来移动位而不改变设置的位。它使用表查找来提供单独 XOR 无法实现的非线性混合。
SHA-512 使用与 SHA-256 相同的结构，但使用 64 位操作而不是 32 位操作。状态为 512 位（八个 64 位字），块大小为 1024 位。压缩函数有80轮而不是64，并且常量和表查找也不同。对于 SHA-384，状态和压缩函数与 SHA-512 相同，但仅输出最终状态的前 384 位。最后 128 位将被丢弃。这种截断就是 SHA-384 抵抗长度扩展的原因。
长度延伸是经过验证的构造边界；多重碰撞和 SHA-3 动机声明被省略
Merkle–Damgård 哈希的安全性取决于所持有的多个属性。压缩函数必须是抗碰撞的，因此直接攻击它是不可行的。填充方案必须确保不同的消息产生不同的填充形式，因此哈希中的每次冲突都必须涉及压缩函数冲突。块大小和状态大小必须足够大，否则暴力破解是不可行的。更广泛的状态扩大了通用搜索空间，但本文没有在没有内联推导和审查来源的情况下附加操作计数或可行性日期。
如果攻击者发现压缩功能中的弱点，或者量子计算机变得实用并且可以在 sqrt(2^n) 时间内而不是 2^n 时间内搜索非结构化空间，那么安全裕度就会受到侵蚀。引发 SHA-3 的弱点不是压缩功能的破坏，而是长度扩展问题和其他结构漏洞。海绵结构通过从不发布其完整的内部状态来避免这些问题。
这不包括什么 - SHA-256 的特定轮函数，在单独的帖子中介绍
Merkle–Damgård 结构如何处理每个输入大小是其设计的实际结果。将消息分割成 512 位块，填充最后一个块，通过压缩函数依次处理每个块，并输出最终状态。对于一字节输入，填充会生成 512 位块（一字节消息、一位填充、447 位零和 64 位长度）。压缩次数为 512 位块的数量，与消息长度成正比。
ToolAcre SHA 哈希计算器生成的每个摘要都来自此构造。 64 字符 SHA-256 摘要是以十六进制打印的最终 256 位状态。 128 字符 SHA-512 摘要是以十六进制打印的最终 512 位状态。 96 字符 SHA-384 摘要是最终 512 位状态的前 384 位。幕后的填充可确保每个可能的消息准确地生成正确数量的块和正确的摘要宽度。这是在浏览器中运行的标准 Merkle–Damgård 结构。
要点：四种算法背后的骨架相同 — ToolAcre SHA 哈希计算器生成的每个摘要都来自此构造
理解其结构有助于了解为什么摘要始终具有相同的宽度以及为什么更改输入的一位会更改整个摘要。链接属性意味着输入的每一位通过一系列混合操作影响输出的每一位。消息早期的一位更改将传播到所有后续压缩，因此最终的摘要完全不同。该属性称为雪崩效应，是健全哈希函数的签名。
Merkle–Damgård 结构已经使用了数十年，并构成了最广泛部署的哈希函数的基础。 SHA-1 和 SHA-2 建立在这种结构之上，许多已部署的系统依赖于它们的输出。该建筑是已建成的而不是实验性的，但历史并不能保证每次使用都是安全的；长度扩展是一种有记录的边界。了解这种结构有助于开发人员理解为什么某些安全属性保持不变以及为什么存在某些攻击向量。