如何衡量哈希算法的强度

Question

有没有一种方法可以衡量哈希算法的强度？比如，通过在PHP中编写的标准化测试，来衡量像crypt与sha1这样的算法的强度？

强度可能指的是不同的事情；单个家用计算机可以通过彩虹表或字符循环发现密码的能力、密码中比特位的长度或符号和数字的使用。与简单的正则表达式不同，后者发现符号或字符数的数量，对于能够确定强度的PHP函数的要求是从密码、密钥或盐的破解速度中得出的。

我想知道，在没有意见的情况下，PHP哈希算法列表中哪个哈希算法最好。

foreach (hash_algos() as $algorithm) {
    // test strength
}

- nderjung

---

“哈希的强度”对您来说确切意味着什么？它有几个含义？为什么它对您来说非常重要？您是用它做什么的？ - Basile Starynkevitch

在现代哈希算法中发现弱点是研究级别的密码学。如果有这样的算法存在，许多聪明的人就会失业（或至少会用不同的方式度过他们的时间）。 - user395760

你最好去谷歌搜索比较 - 很多人已经写了关于每种类型和其优点等方面的文章。 - BenOfTheNorth

@safarov：我认为很少有长度为2^128的哈希算法存在... - Oliver Charlesworth

@safarov 不要混淆位数和数字范围。一个128位整数需要16个字节来存储，并允许2^128个值，这相当大并且对于哈希算法来说是合理的。一个2^128位的整数需要10^25太字节来存储，并允许2^(2^128)个值（这个数字有10^38个十进制数字）- 换句话说，非常不实用。但无论如何，我的观点是：输出数字范围与算法的强度（按任何合理的定义）几乎没有关系。[所有数字由Wolfram|Alpha提供] - user395760

Answer 1

哈希的强度是一个数学/理论概念，即是否发现了任何理论或实际差异。如果没有发现任何已公开的漏洞，则强度取决于验证码的长度。例如，SHA-1输出160位，但SHA-256输出256位。

“编程”测试强度的唯一方法是暴力破解哈希值，这基本上是无意义的。更好的方法是自己研究每个哈希函数，而不是试图编程确定“最佳”哈希函数。

- GavinCattell

Answer 2

哈希算法将任意输入映射到一个n位的输出序列。一个“好”的哈希算法将长度为n位的每个输入映射到一个不同的n位的输出序列。当两个不同的输入映射到相同的输出时，就会发生冲突。

因此，测试两个哈希算法的相对强度的简单方法是生成大量的输入，将它们提供给两个算法，并计算冲突的数量。

请注意，“简单”意味着“概念上简单”。执行实际测试将需要大量的计算资源。

- Adam Liss

---

由于存在有限数量的位和无限数量的可散列序列，因此必须发生碰撞。并不是你不知道这点，但我认为你的回答是指出这一点的好地方。 - Anthony

最好的哈希函数将会将 n 位输入映射到 n 位输出，且不会有碰撞。只有在输入长度大于输出长度时才会发生碰撞。 - Adam Liss

@AdamLiss：我认为这不是真正重要的标准。更重要的度量标准是构建导致给定输出的输入有多容易。 - Oliver Charlesworth

@AdamLiss：完全不是这样的。我相信MD5遵守你描述的那个属性，但MD5现在被认为是不安全的原因是，恶意地创建一个产生冲突的输入相对容易。 - Oliver Charlesworth

Answer 3

我认为从数学角度来看，考虑算法的运行时间以计算出给定其他适当输入的密钥是一个好方法，如果存在这样的算法。

基于我最近使用一些基本加密算法工具的经验，我可以说，即使是对于基本指数密码而言，寻找k的最快算法的运行时间也是e^(sqrt(log p log log p)), 这使得对于大的p来说不可行。看起来这将是“强度”的一个很好的理论衡量标准。

我绝不是这方面的专家，Gavin和Adam似乎更有知识。

- afkbowflexin