algorithm - 需要存储什么状态以允许可恢复的哈希计算？

Question

这个问题只是和现实世界的问题有间接的联系，更多的是出于兴趣。我并不真正了解当前现实世界的哈希算法在内部是如何工作的。

我确实知道典型的散列计算(和 CRC 计算等)是递增的，更新一些状态 依次为每个字节/字 [事实证明算法一次工作一个 block ，尽管接口(interface)通常会自动处理]。因此，稍后可以恢复部分完成的哈希计算 - 存储该状态，然后重新加载它并从您中断的地方继续。 SO 上已经有关于此的问题，但它们似乎都与特定的库有关。

根据 CRC-16 的古老知识(是的，真的 - 由于过时的文件格式)，我的印象是 CRC 值本身就是您需要存储以恢复计算的所有状态。显然，实现可以用奇怪的方式编写，但原则上，到目前为止看到的文件部分内容的 CRC-16 是从该点恢复计算所需的完整状态。

现在使用的所有常见哈希计算都是这样吗？特别是 MD5、SHA-1 和 SHA-256。或者必须存储一些其他(附加或替代)状态才能恢复计算？

显然需要在文件中恢复的位置，但除此之外，您还需要存储什么精确状态才能使用普通哈希函数恢复哈希计算。

对于额外的奖励积分 - 我如何在 C++ 中使用 Crypto++ 访问该状态？ (文档正确部分的链接或引用可能非常有帮助)。

我将其标记为“算法”，因为这是这里的重点 - 来自现实世界算法的需求，而不是任何特定语言或库的实现。

Answer 1

当今大多数加密哈希，包括 MD5 , SHA-1和 SHA-2家庭，基于Merkle–Damgård construction .

在这个结构中，输入是通过将它分成固定长度的 block 来处理的，这些 block 一次一个地被送入一个“混合函数”，该函数不可逆地将它们与算法的内部状态(这也是一个固定长度的位串)。在输入结束时，生成的内部状态进一步不可逆地转换以防止某些类型的攻击:

(即将推出的 SHA-3 哈希标准基于较新的 cryptographic sponge construction ，它在一些细节上有所不同，但在此处讨论的一般级别上并不显着。)

如果没有长度填充和最终确定步骤，您可以只获取任何消息的哈希值并使用它来计算该消息的哈希值并附加一些额外的数据，就像您可以对 CRC 所做的那样。 las，从密码学的角度来看，这被认为是一件坏事，并且最终确定步骤专门包含在该过程中以使其不可能。

因此，如果您想在消息中间中断散列过程并在稍后恢复它，您需要在它经过填充和完成阶段之前获取内部状态字符串。

(您可能还需要存储少量附加数据，例如到目前为止为正确长度填充处理的 block 数，并且，如果散列在 block 中间中断，则任何部分输入 block 都不会尚未输入混合功能。)

---

大多数加密库使用存储内部状态并允许以任意片段提供输入的哈希对象来实现哈希算法，如下所示(伪代码):

HashFunction hash = new SomeHashFunction();
hash.addInput( data );
// ...
hash.addInput( moreData );
BitString output = hash.finalize();

通常，即使哈希对象可能不提供对其内部状态的直接访问，它们通常也会提供克隆和/或序列化自身的方法。我不是特别熟悉 Crypto++具体但一眼看去，它seems提供一个 Clone() 方法。

---

附言。如果您对使用加密哈希进行文件完整性验证感兴趣，您可能需要查看 universal hashing ，特别是基于多项式评估的通用哈希函数，如 GHASH或 Poly1305 .这些是非常快速且可并行化的哈希函数，通常用作 authenticated encryption 的一部分。方案，但也可以单独用作 message authentication codes .它们的好处在于，它们不仅可以增量计算，而且通过一些巧妙的数学运算，如果对数据的中间 进行了更改，它们甚至可以增量更新。它们的主要缺点是，为了防止伪造(例如创建两个具有相同散列的文件)的加密安全，它们需要与 key 一起使用。