2

我正在实现一些使用可变长度的 id 的程序。这些 id 标识一条消息并发送到将执行某些操作(与问题无关)的代理。但是,代理中此 ID 的最大长度为 24 个字节。我正在考虑使用 SHA 对 id 进行散列(在发送到代理之前)并删除一些字节,直到它仅获得 24 个字节。

但是,我想知道这会增加多少碰撞。所以这是我到目前为止得到的:

我发现对于“完美”的哈希,我们有一个公式p^2 / 2^n+1来描述冲突的概率,p消息的数量在哪里,消息n的大小在哪里。这是我的问题开始的地方。我假设从最终哈希中删除一些字节,函数仍然保持“完美”,我仍然可以使用相同的公式。所以假设我得到:

 5160^2 / 2^192 + 1 = 2.12x10^-51

其中 5160 是消息的选择数,192 基本上是 24 字节中的位数。

我的问题:

  • 我的假设正确吗?通过删除一些字节,哈希是否保持“完美”。

  • 如果是这样并且由于概率非常小,我应该删除哪些字节?最重要还是最不重要?这真的很重要吗?

PS:欢迎任何其他达到相同结果的建议。谢谢。

4

1 回答 1

4

但是,代理中此 ID 的最大长度为 24 个字节。我正在考虑使用 SHA 对 id 进行散列(在发送到代理之前)并删除一些字节,直到它仅获得 24 个字节。

SHA-1 仅输出 20 个字节(160 位),因此您需要填充它。至少如果所有字节都有效,并且您不限于十六进制或 Base64。我建议改用截断的 SHA-2。

我的假设正确吗?通过删除一些字节,哈希是否保持“完美”。

差不多。截断散列应该保留其所有重要属性,显然是在与较小输出大小相对应的降低的安全级别上。

如果是这样并且由于概率非常小,我应该删除哪些字节?最重要还是最不重要?这真的很重要吗?

这根本不重要。NIST 定义了一种截断的 SHA-2 变体,称为 SHA-224,它使用不同的初始状态获取 SHA-256 的前 28 个字节进行哈希计算。


我的建议是使用 SHA-256,保留前 24 个字节。这需要大约 2^96 次散列函数调用才能找到一个冲突。这目前是不可行的,即使对于极其强大的攻击者也是如此,而且对于意外碰撞来说基本上是不可能的。

于 2012-09-17T08:54:39.663 回答